Opened 5 years ago
Closed 5 years ago
#15715 closed enhancement (fixed)
Teach the graph backend that 'yield' exists in Cython
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.2 
Component:  graph theory  Keywords:  
Cc:  azi  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  u/tscrim/ticket/15715 (Commits)  Commit:  a78ed71c0497c46f26e5de28453bcbf27fb452de 
Dependencies:  Stopgaps: 
Description
The graph backends are currently building lists, only to return an iterator on that list. But Cython supports 'yield' now, so that can be simplified.
Nathann
Change History (9)
comment:1 Changed 5 years ago by
 Branch set to u/ncohen/15715
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
 Commit set to 1c5283a412d5deaa6ed575d7ddf977a7dc4847fa
comment:3 Changed 5 years ago by
 Status changed from needs_review to needs_work
You're missing a yield on line 1777 of c_graph.pyx. (Line comments would be really nice...)
comment:4 Changed 5 years ago by
 Commit changed from 1c5283a412d5deaa6ed575d7ddf977a7dc4847fa to be87ba4f553356855239b02bcc3cca0db68978f4
comment:5 Changed 5 years ago by
 Status changed from needs_work to needs_review
Sorryyyyyyyy ! It is now fixed.
Nathann
comment:6 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:7 Changed 5 years ago by
 Branch changed from u/ncohen/15715 to u/tscrim/ticket/15715
 Commit changed from be87ba4f553356855239b02bcc3cca0db68978f4 to a78ed71c0497c46f26e5de28453bcbf27fb452de
I've made some tweaks to squeeze some extra speed out. Here are my timings:
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.multiple_edges(True) sage: G.add_edge(1,2,3,False) sage: G.add_edge(1,2,3,False) sage: G.add_edge(1,2,3,False) sage: G.add_edge(1,2,3,False) sage: G.add_edge(1,2,3,False) sage: %timeit list(G.iterator_edges(range(9), False)) 100000 loops, best of 3: 15.5 us per loop sage: %timeit list(G.iterator_edges(range(9), True)) 100000 loops, best of 3: 16 us per loop sage: %timeit list(G.iterator_in_edges([1], False)) 100000 loops, best of 3: 4.8 us per loop sage: %timeit list(G.iterator_in_edges([1], True)) 100000 loops, best of 3: 5 us per loop sage: %timeit list(G.iterator_out_edges([1], False)) 100000 loops, best of 3: 5.67 us per loop sage: %timeit list(G.iterator_out_edges([1], True)) 100000 loops, best of 3: 6.17 us per loop
Before my changes:
sage: %timeit list(G.iterator_edges(range(9), False)) 10000 loops, best of 3: 20.3 us per loop sage: %timeit list(G.iterator_edges(range(9), True)) 10000 loops, best of 3: 21.6 us per loop sage: %timeit list(G.iterator_in_edges([1], False)) 100000 loops, best of 3: 4.86 us per loop sage: %timeit list(G.iterator_in_edges([1], True)) 100000 loops, best of 3: 4.85 us per loop sage: %timeit list(G.iterator_out_edges([1], False)) 100000 loops, best of 3: 7.08 us per loop sage: %timeit list(G.iterator_out_edges([1], True)) 100000 loops, best of 3: 7.51 us per loop
This will likely be more pronounced as there are more and more multiple edges. If you're happy with my changes, then it's positive review.
New commits:
4c76814  Merge branch 'u/ncohen/15715' of trac.sagemath.org:sage into u/tscrim/ticket/15715

a78ed71  Tweaks for speed in sparse graph backend for #15715.

comment:8 Changed 5 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Well, seems free for healthy graphs and better for the others, so yes good idea :D
THaaaaaaaaaaanks !
Nathann
comment:9 Changed 5 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #15715: Teach the graph backend that 'yield' exists in Cython