Opened 11 years ago

Closed 12 months ago

#9143 closed enhancement (duplicate)

Speed up graph generation using Cython

Reported by: jason Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: ncohen, rlm, robertwb Merged in:
Authors: Reviewers: Dave Morris
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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}

Change History (13)

comment:1 Changed 11 years ago by rlm

Every time I ask about "yield" statements in Cython, I always get the same response: very close, not there yet. It will be very easy for me to fix this, once they are implemented. Until then, it's probably ten times the work...

comment:2 Changed 11 years ago by jason

  • Cc robertwb added

Ah, okay, thanks for the update. I'm CCing robertwb so that he sees (yet again) another vote for yield statements in Cython. I'm sure they'll come in time.

comment:3 follow-up: Changed 11 years ago by robertwb

Well, we're very close, but not there yet ;). Realistically, I'm 90% sure they'll be implemented by the time the summer is out, now that I don't have to spend every waking minute on my thesis.

comment:4 in reply to: ↑ 3 Changed 11 years ago by rlm

Replying to robertwb:

... now that I don't have to spend every waking minute on my thesis.

+1!

I was also going to mention in response to

I'm CCing robertwb so that he sees (yet again) another vote for yield statements in Cython.

that I believe in one-person-one-vote, and I must disclose that I have already voted for this :)

comment:5 Changed 9 years ago by rlm

This is now part of #9559.

comment:6 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:7 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 13 months ago by gh-DaveWitteMorris

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

As mentioned in comment:5, the problem has been fixed, so this ticket can be closed as a duplicate of #9559.

sage: ### try sage
sage: %time gg=list(graphs(7))
CPU times: user 83.6 ms, sys: 15.4 ms, total: 99.1 ms
Wall time: 117 ms
sage: ###
sage: ### now compare with nauty
sage: %timeit hh=graphs.nauty_geng('-q 7')
The slowest run took 11.31 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 5: 409 ns per loop
sage: ###
sage: ### try a larger example with sage
sage: %time gg=list(graphs(8))
CPU times: user 390 ms, sys: 17.6 ms, total: 407 ms
Wall time: 426 ms
sage: ###
sage: ### now compare with nauty again
sage: %timeit hh=graphs.nauty_geng('-q 8')
The slowest run took 9.17 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 5: 456 ns per loop

comment:11 Changed 13 months ago by gh-DaveWitteMorris

  • Status changed from needs_review to positive_review

comment:12 Changed 13 months ago by gh-DaveWitteMorris

  • Reviewers set to Dave Morris

comment:13 Changed 12 months ago by chapoton

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.