#15978: Waste of time in g.edges() (acually in iterator_edges)
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.2
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | 768a63ea1d24e569a254f99b01b1f4c568198bc9
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/15978 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by mmezzarobba):
Probably a stupid question, but: Why is `CompleteGraph(3000)` a
`SparseGraph`?
I don't know anything about the graph code, but I did a bit of profiling
out of curiosity. And it looks like nested loops such as
{{{
# SparseGraph.iterator_edges
for u_int in self._cg.out_neighbors(v_int):
if u_int >= v_int:
for l_int in self._cg.all_arcs(v_int, u_int):
...
}}}
are a pretty redundant and not too cache-friendly way of enumerating the
edges. In particular:
* `all_arcs_unsafe(u, v, ...)` seems to spend LOTS of time looking for
`temp` such that `temp.vertex == v`, while (if I understand correctly)
`out_neighbors_unsafe` already had to visit the corresponding
`SparseGraphBTNode`. But perhaps the graph is just too dense for the hash
table to do its job, and it would work just fine with a sparse graph?
* The test `u_int <= v_int` can also be a bit expensive, perhaps due to
branch mispredictions or something like that.
--
Ticket URL: <http://trac.sagemath.org/ticket/15978#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
