For a quick summary, the current implementation of graphs is as follows: - there is a C backend which uses only integers as vertices. This version uses B-tree (which are written from scratch with some non optimizes routines, see in particular #14690) which allows dynamical graphs (ie adding/removing vertices and edges). - the graph we see from Sage stores a dictionnary (label) -> (integer) to communicate with the C backend Actually, this is not quite True as there is an intermediate layer between those two to deal with graph vs digraph.
Note that in order to enuerate the neighbors, there is no use of the dictionnary as we go in the other direction (integer) -> (label) which is just a C array PythonObject **. This method conversion is moreover implemented in C and I guess that it is quite efficient (but I did not check that). Now, that being said there is some overhead in neighbors iteration as each layer actually build the list of neighbors and iterate through it. The main reason was because it was not possible to use iterator with Cython. I guess that neighbor iterations may be simplified in that direction but, if I remember well you tried it in #13730. One other option would be to pass the iteration of neighbor iteration to some level down in the hierarchy of backends. This, together with #14690, might be enough to get some speed up. Best Vincent 2013/8/30 Jernej Azarija <azi.std...@gmail.com>: > 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. -- 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.
