#14659: Useless memory allocation in subgraph_search
---------------------------------+------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Nathann Cohen | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Changes (by ncohen):
* status: new => needs_review
Old description:
> This patch exist because I am an idiot.
>
> 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
New description:
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
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14659#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
