Opened 8 years ago

Closed 2 years ago

#16220 closed enhancement (duplicate)

Waste of time in iterator_edges 3

Reported by: Vincent Delecroix Owned by: Vincent Delecroix
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords: graphs, datastructure
Cc: Nathann Cohen Merged in:
Authors: Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Vincent Delecroix)

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!

Change History (11)

comment:1 Changed 8 years ago by Vincent Delecroix

Branch: public/16220
Commit: 98286f45fc077f9778708ca3f064a2f5a13853ad
Description: modified (diff)
Keywords: graphs datastructure added
Type: PLEASE CHANGEenhancement

New commits:

56ec117trac 16005: Waste of time in iterator_edges 2
567600btrac #16005: merge into 6.2.beta8
9623fd7Merge branch 'u/ncohen/16005' of trac.sagemath.org:sage into 16005-waste_of_times_graph2
98286f4optimization of edge_iteration in SparseGraphBackend + documentation

comment:2 Changed 8 years ago by Nathann Cohen

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

comment:3 in reply to:  2 ; Changed 8 years ago by Vincent Delecroix

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?

comment:4 in reply to:  3 Changed 8 years ago by Nathann Cohen

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

comment:5 Changed 8 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:6 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:7 Changed 2 years ago by 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.

comment:8 Changed 2 years ago by David Coudert

We can certainly close it.

comment:9 Changed 2 years ago by gh-kliem

Milestone: sage-6.4sage-duplicate/invalid/wontfix
Status: newneeds_review

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

comment:10 Changed 2 years ago by David Coudert

Reviewers: David Coudert
Status: needs_reviewpositive_review

Agreed.

comment:11 Changed 2 years ago by Samuel Lelièvre

Authors: Vincent Delecroix
Branch: public/16220
Commit: 98286f45fc077f9778708ca3f064a2f5a13853ad
Resolution: duplicate
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.