Opened 7 years ago
Closed 6 months ago
#16220 closed enhancement (duplicate)
Waste of time in iterator_edges 3
Reported by: | vdelecroix | Owned by: | vdelecroix |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | graphs, datastructure |
Cc: | ncohen | 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 7 years ago by
- Branch set to public/16220
- Commit set to 98286f45fc077f9778708ca3f064a2f5a13853ad
- Description modified (diff)
- Keywords graphs datastructure added
- Type changed from PLEASE CHANGE to enhancement
comment:2 follow-up: ↓ 3 Changed 7 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 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 7 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 in reply to: ↑ 3 Changed 7 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 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:6 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:7 Changed 7 months 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:8 Changed 6 months ago by
We can certainly close it.
comment:9 Changed 6 months ago by
- Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
With #30665, I think this can be closed. The branch certainly doesn't work anymore after redesign.
comment:10 Changed 6 months ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
Agreed.
comment:11 Changed 6 months ago by
- Branch public/16220 deleted
- Commit 98286f45fc077f9778708ca3f064a2f5a13853ad deleted
- Resolution set to duplicate
- Status changed from positive_review to 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