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: |
Description (last modified by )
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
Branch: | → public/16220 |
---|---|
Commit: | → 98286f45fc077f9778708ca3f064a2f5a13853ad |
Description: | modified (diff) |
Keywords: | graphs datastructure added |
Type: | PLEASE CHANGE → enhancement |
comment:2 follow-up: 3 Changed 8 years ago by
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 follow-up: 4 Changed 8 years ago by
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 Changed 8 years ago by
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
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:6 Changed 8 years ago by
Milestone: | sage-6.3 → sage-6.4 |
---|
comment:7 Changed 2 years ago by
#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:9 Changed 2 years ago by
Milestone: | sage-6.4 → sage-duplicate/invalid/wontfix |
---|---|
Status: | new → needs_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
Reviewers: | → David Coudert |
---|---|
Status: | needs_review → positive_review |
Agreed.
comment:11 Changed 2 years ago by
Authors: | Vincent Delecroix |
---|---|
Branch: | public/16220 |
Commit: | 98286f45fc077f9778708ca3f064a2f5a13853ad |
Resolution: | → duplicate |
Status: | positive_review → closed |
New commits:
trac 16005: Waste of time in iterator_edges 2
trac #16005: merge into 6.2.beta8
Merge branch 'u/ncohen/16005' of trac.sagemath.org:sage into 16005-waste_of_times_graph2
optimization of edge_iteration in SparseGraphBackend + documentation