Waste of time in iterator_edges 3

[videlec]

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!

CC: @nathanncohen

Component: graph theory

Keywords: datastructure

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/16220

[videlec]

Branch: public/16220

[videlec]

Commit: 98286f4

[videlec]

Changed keywords from none to datastructure

[videlec]

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

[nathanncohen]

comment:2

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

[videlec]

comment:3

Replying to @nathanncohen:

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?

[nathanncohen]

comment:4

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

[kliem]

comment:7

#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]

comment:8

We can certainly close it.

[kliem]

comment:9

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

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:10

Agreed.

[slel]

Changed branch from public/16220 to none

[slel]

Changed author from Vincent Delecroix to none

[slel]

Changed commit from 98286f4 to none