Opened 6 years ago

Closed 6 years ago

#14659 closed defect (fixed)

Useless memory allocation in subgraph_search

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.11
Component: graph theory Keywords:
Cc: azi, Stefan, dimpase Merged in: sage-5.11.beta0
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

This patch exist because I am an idiot. A C array was allocated and freed at each iteration of a loop, while it makes much more sense to allocate it BEFORE the loop begins, and free it when it ends. And the same memory segment is used all along. That's all.

This should also solve the other problem of this class : it often segfaults when using CTRL+C while it computes.

Not spending its lifetime allocating and freeing memory is definitely a step in the right direction.

And this will have to be rewritten with a real data structure someday, like the one from #14589 >_<

Before :

sage: g = graphs.CompleteMultipartiteGraph([9]*5)     
sage: %time g.subgraph_search(graphs.CompleteGraph(6))
CPU times: user 18.31 s, sys: 0.01 s, total: 18.32 s
Wall time: 18.36 s

After:

sage: g = graphs.CompleteMultipartiteGraph([9]*5)
sage: %time g.subgraph_search(graphs.CompleteGraph(6))
CPU times: user 6.95 s, sys: 0.00 s, total: 6.95 s
Wall time: 6.96 s

Nathann

Attachments (1)

trac_14659.patch (10.4 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 6 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by vdelecroix

Hi,

Why do you write

sequence[i] = 1 if self.has_arc_unsafe(vertices[i], v) else 0

instead of

sequence[i] = self.has_arc_unsafe(vertices[i], v)

?

Changed 6 years ago by ncohen

comment:3 follow-up: Changed 6 years ago by ncohen

rightrightrightrightright :-P

Nathann

comment:4 in reply to: ↑ 3 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Replying to ncohen:

rightrightrightrightright :-P

Well done!

Vincent

comment:5 Changed 6 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix

comment:6 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.10 to sage-5.11

comment:7 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.11.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.