#9143: Speed up graph generation using Cython
----------------------------+-----------------------------------------------
Reporter: jason | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.4.3
Component: graph theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
It's amazing how slow our graph generator is:
{{{
sage: %time gg=list(graphs(7))
CPU times: user 12.31 s, sys: 0.10 s, total: 12.41 s
Wall time: 12.87 s
}}}
Compare this to nauty's C implementation (with approximately the same
algorithm)
{{{
sage: %timeit hh=graphs.nauty_geng('-q 7')
5 loops, best of 3: 171 ms per loop
}}}
Notice that the vast majority of the time is spent in some python calls,
which presumably could be much, much faster if we instead used the
underlying C structure via Cython.
{{{
sage: %prun gg=list(graphs(7))
4355876 function calls (4284237 primitive calls) in 14.011 CPU
seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
46134 2.668 0.000 2.923 0.000 {iterator_edges}
362828 1.897 0.000 1.897 0.000 {add_edge}
33007 1.698 0.000 7.775 0.000 graph.py:760(__init__)
289792 1.209 0.000 1.209 0.000 {has_edge}
125832 0.625 0.000 0.625 0.000 {iterator_verts}
6564 0.604 0.000 5.020 0.001
{sage.groups.perm_gps.partn_ref.refinement_graphs.search_tree}
33006 0.476 0.000 8.523 0.000
generic_graph.py:416(__copy__)
13050/1045 0.441 0.000 14.000 0.013
graph_generators.py:5059(canaug_traverse_edge)
33007 0.395 0.000 0.470 0.000
function_mangling.py:205(fix_to_pos)
20064/13314 0.321 0.000 2.453 0.000
generic_graph.py:10582(relabel)
33006 0.318 0.000 0.318 0.000 {add_vertices}
289792 0.282 0.000 1.491 0.000
generic_graph.py:5256(has_edge)
6750 0.255 0.000 1.923 0.000 generic_graph.py:72(__eq__)
5893 0.235 0.000 0.354 0.000
graph_generators.py:5228(check_aut_edge)
142579/89695 0.195 0.000 7.128 0.000 copy.py:65(copy)
546806 0.191 0.000 3.114 0.000
generic_graph.py:5386(edge_iterator)
46692 0.175 0.000 0.524 0.000
generic_graph.py:4817(vertices)
33007 0.166 0.000 0.824 0.000
generic_graph.py:28(__init__)
13314 0.162 0.000 0.162 0.000 {relabel}
128177 0.135 0.000 0.135 0.000 {sorted}
132025 0.126 0.000 0.171 0.000 generic_graph.py:1531(name)
125832 0.124 0.000 0.749 0.000
generic_graph.py:4731(vertex_iterator)
105955 0.110 0.000 0.110 0.000 {hasattr}
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9143>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
