New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
graph add_edges/delete_edges are dramatically slow #28259
Comments
Changed keywords from none to days100 |
This comment has been minimized.
This comment has been minimized.
comment:3
It's true that we should work on optimizing the backend, and also simplifying it. But we have to be careful as it might have a strong impact (slowdown) on other kinds of operations. |
Attachment: cf_prof_K2_Q2000_R5.pdf.gz |
comment:4
For me, it is the other way around. My code is slow because of the slowness of vertex/edge manipulation... have a look at attachment: cf_prof_K2_Q2000_R5.pdf. |
comment:5
The profiling is impressive: 95% of the computation is spent by the vertex/edge management
Of course, my computation use the graphs extensively. But still it does not only use that... The only thing I can do to make it faster is to either make Sage graphs better or get rid of them in my program. At this stage, I am not sure which direction to take. The sparse graph backend is a huge mess of code. Rewriting any part of it will take a considerable amount of time. I will probably write a custom graph class from scratch that fits my need. In a second time, I will see whether it can be plugged in as a backend for Sage. |
This comment has been minimized.
This comment has been minimized.
comment:7
I agree that we must rewrite and simplify the graph backend and that it's not an easy task. As far as I know, it has been designed like that to allow some optimization of some specific use when vertices are only integers in 0..n-1 and are created in this order, but it has a cost for other usage. Another important task is to better distinguish the label and the id of a vertex. Roughly, for most internal use, we should only manipulate integers and not the labels of the vertices. |
comment:8
I created a meta ticket #28895 for all those tickets simplifying or improving graph backends. Currently I'm working on improving the deleting of vertices. The solution should be, to move the reversed graph to the CGraph structure. The backend keeps a reversed copy of the graph, but the CGraph doesn't know it and can't use it. Therefore deleting vertices takes forever (the CGraph doesn't know the incoming edges, but the reversed one would have known it easily). |
comment:9
Ticket retargeted after milestone closed |
comment:10
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date. |
comment:12
#30769 might be a good step towards this goal. With this ticket, I get the following timings:
Note that sparse graphs also carry a copy of the reversed graph, so the actual arc is added twice. Profiling suggests that this business of This also implies that improving the data structure for sparse graphs could give us a large speedup here. (But I'm even less sure how to proceed with this.) |
comment:13
Replying to @kliem:
Nice!
This is a pity. Maybe a flag
I did try in the past to rewrite sparse graph (do not remember which ticket), but it ended up being painful. Ideally we should just be wrapping some pure C implementation but vertex labels and edge labels are delicate to deal with. Also, we could introduce a new (simpler) datastructure similar to static sparse graphs but for which one can reallocate individually the arrays used for neighbor lists. This can be amortized in terms of graph creation and would benefit from all algorithms already implemented for static sparse graph. However, such data structure will be a bit costly for merging vertices. |
comment:14
Apparently, our heuristics are better for strings than for integers. So something must be wrong: This is on top of #30769:
|
comment:15
in your timing, |
comment:16
Replying to @dcoudert:
Fixed. |
comment:17
Setting new milestone based on a cursory review of ticket status, priority, and last modification date. |
When dealing with dynamical graph (where vertices and edges have to change many times) then I suffer a lot from the slowness of
add_edges
anddelete_edges
. Compared to a pair of dictionary of lists (to save adjacencies) one get ax3
factorplain defaultdict: 46.5ms
Sage DiGraph: 129ms
igraph: 18.7ms
CC: @dcoudert
Component: graph theory
Keywords: days100
Issue created by migration from https://trac.sagemath.org/ticket/28259
The text was updated successfully, but these errors were encountered: