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: sage-6.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 ncohen

  • Branch set to u/ncohen/15715
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 1c5283a412d5deaa6ed575d7ddf977a7dc4847fa

Branch pushed to git repo; I updated commit sha1. New commits:

1c5283atrac #15715: Teach the graph backend that 'yield' exists in Cython

comment:3 Changed 5 years ago by robertwb

  • 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 git

  • Commit changed from 1c5283a412d5deaa6ed575d7ddf977a7dc4847fa to be87ba4f553356855239b02bcc3cca0db68978f4

Branch pushed to git repo; I updated commit sha1. New commits:

44dd9d3trac #15715: Rebase on 6.1.rc0
be87ba4trac #15715: Forgot an important keyword

comment:5 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

Sorryyyyyyyy ! It is now fixed.

Nathann

Last edited 5 years ago by ncohen (previous) (diff)

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 5 years ago by tscrim

  • 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:

4c76814Merge branch 'u/ncohen/15715' of trac.sagemath.org:sage into u/tscrim/ticket/15715
a78ed71Tweaks for speed in sparse graph backend for #15715.

comment:8 Changed 5 years ago by ncohen

  • 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 vbraun

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