#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 ncohen):
Yoooooo !
> Probably a stupid question, but: Why is `CompleteGraph(3000)` a
`SparseGraph`?
No good answer to that. There is a Dense Graph backend which is never used
unless you ask for it, and as it is never tested I expect it to be quite
buggy.
> 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?
There is a waste of time there indeed. I just never re-wrote these
parts... The backend code is Robert Miller's, I never touched the data
structures. I wrote some backends I needed for efficient implementations,
and in those implementations you will not find such waste...
I should either rewrite the default backend for graphs, or write lower-
level code for functions like that.
I just hate labels and multiple edges.....
> * The test `u_int <= v_int` can also be a bit expensive, perhaps due to
branch mispredictions or something like that.
Hmmmm... I understand, but how can you do without ?
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/15978#comment:6>
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.
