This is a follow up of the thread [1] in which we noticed that there is a substantial performance issue in the Graph.neighbors method. The point of this thread is mainly to draw your attention and perhaps spot what is causing the described issue.
As it turns out our default graph backend is actually quite efficient and the slowdown appears to be caused by wrapping it up within higher level objects. Examples. sage: G = graphs.RandomBarabasiAlbert(1000,2) sage: %timeit E = [(u,v) for u in xrange(1000) for v in G.neighbor_iterator(u)] 100 loops, best of 3:* 4.64 ms* per loop What G.neighbors_iterator() *essentially* does is calls the out_neighbors() method in the SparseGraph backend. Calling this method directly is quite efficient : sage: %timeit E = [(u,v) for u in xrange(1000) for v in G._backend._cg.out_neighbors(u)] 1000 loops, best of 3:* 719 us* per loop As well as directly creating a SparseGraph object. sage: from sage.graphs.base.sparse_graph import SparseGraph sage: S = SparseGraph(1000) sage: for i,j in G.edges(labels=False): S.add_arc(i,j) sage: %timeit E = [(u,v) for u in xrange(1000) for v in S.out_neighbors(u)] 1000 loops, best of 3: *386 us* per loop In particular, the same slowdown happens if we use use the NetworkX backend for our Graph object. sage: H = G.networkx_graph() # this creates a NetworkX graph sage: %timeit EE = [(u,v) for u in xrange(1000) for v in H[u]] 1000 loops, best of 3: *636 us *per loop BUT sage: I = Graph(implementation='networkx') # this uses networkX as the graph backend for Graph sage: for i,j in G.edges(labels=False): I.add_edge(i,j) sage: %timeit EE = [(u,v) for u in xrange(1000) for v in I.neighbor_iterator(u)] 100 loops, best of 3: *2.03 ms* per loop The calling trace from Graph.neighbor_iterator to the point in the backend where neighbors are actually retrieved is quite simple and does not appear to cause the slowdown directly (though if it does you're wellcome to point to the specific section of the code in which the slowdon occurs) Instead it smells like there is some implicit overhead in wrapping objects like that. At this point we are quite desperate to spot the slowdown hence if you have *any* kind of suggestions at what to try or check, let us know in this thread! [1] Graph neighbours - room for huge performance boost, https://groups.google.com/forum/#!topic/sage-devel/eWu_01zQNwM -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/groups/opt_out.
