Opened 7 years ago

Closed 3 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 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!

Change History (11)

comment:1 Changed 7 years ago by vdelecroix

  • Branch set to public/16220
  • Commit set to 98286f45fc077f9778708ca3f064a2f5a13853ad
  • Description modified (diff)
  • Keywords graphs datastructure added
  • Type changed from PLEASE CHANGE to enhancement

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 follow-up: Changed 7 years ago by 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

comment:3 in reply to: ↑ 2 ; follow-up: Changed 7 years ago by 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?

comment:4 in reply to: ↑ 3 Changed 7 years ago by 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

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 4 months 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 4 months ago by dcoudert

We can certainly close it.

comment:9 Changed 4 months ago by gh-kliem

  • 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 4 months ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

Agreed.

comment:11 Changed 3 months ago by slelievre

  • Authors Vincent Delecroix deleted
  • Branch public/16220 deleted
  • Commit 98286f45fc077f9778708ca3f064a2f5a13853ad deleted
  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.