Waste of time in iterator_edges 3

[vdelecroix]

Further optimizations for graph iterations following #16005.

The sparse graph backend (i.e. sage.graphs.base.sparse_graph.SparseGraph and sage.graphs.base.sparse_graph.SparseGraphBackend) lacks optimization especially for edge iteration. We need to see what is the best we can do and work on it!

[vdelecroix]

New commits:

​56ec117	trac 16005: Waste of time in iterator_edges 2
​567600b	trac #16005: merge into 6.2.beta8
​9623fd7	Merge branch 'u/ncohen/16005' of trac.sagemath.org:sage into 16005-waste_of_times_graph2
​98286f4	optimization of edge_iteration in SparseGraphBackend + documentation

[ncohen]

Isn't there a problem if you want to iterate over the edges but stop midway ? Isn't it the case that the array is never deallocated ?

Nathann

[vdelecroix]

Replying to ncohen:

Isn't there a problem if you want to iterate over the edges but stop midway ? Isn't it the case that the array is never deallocated ?

You are right, with a code like

sage: it = build_me_an_edge_iterator()
sage: it.next()
sage: del it

we keep an array never deallocated. But what happens for alloc/dealloc inside cdef functions?

A solution would be to implement an iterator in Cython with direct access to the SparseGraph (doing all proper deallocation in __dealloc__). Is it worth it?

[ncohen]

we keep an array never deallocated. But what happens for alloc/dealloc inside cdef functions?

I would say that it never happens, and that the only way is to create a class with a constructor/destructor. Which is a lot of code.

A solution would be to implement an iterator in Cython with direct access to the SparseGraph (doing all proper deallocation in __dealloc__). Is it worth it?

Well, the question is whether an iterator is cheaper than a malloc.

Nathann

[gh-kliem]

#30665 does some improvements to the edge iterator. It is surely not optimized out. Not sure, if we want to close this ticket here. Or keep it for further improvements.

[dcoudert]

We can certainly close it.

[gh-kliem]

With #30665, I think this can be closed. The branch certainly doesn't work anymore after redesign.

[dcoudert]

Agreed.