#18395: (moderate) Speedup in layout_spring
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.7
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | 49ddee04c89bbe5a5536305e47bfe777dde7f79a
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18395 |
Dependencies: |
-------------------------+-------------------------------------------------
Description changed by ncohen:
Old description:
> This branch improves (a bit) the performances of the 'layout_spring'
> algorithm, i.e. the attraction/repulsion layout for graphs.
>
> I tested it on the `CameronGraph` (big and dense), with the following
> results:
>
> Before:
>
> {{{
> sage: g = graphs.CameronGraph()
> sage: %time _=g.layout_spring(iterations=100000)
> CPU times: user 30.8 s, sys: 8 ms, total: 30.8 s
> Wall time: 30.8 s
> }}}
>
> After
>
> {{{
> sage: g = graphs.CameronGraph()
> sage: %time _=g.layout_spring(iterations=100000)
> CPU times: user 14.3 s, sys: 4 ms, total: 14.3 s
> Wall time: 14.3 s
> }}}
>
> Honestly, that is mostly a failure. Most of the speedup comes from
> templating the code so that `dim=2` and `dim=3` are decided at compile-
> time. Most of the time it spend mulsitplying floats, and that's what I
> have been trying to reduce. Not with obvious success `:-/`
>
> Nathann
New description:
This branch improves (a bit) the performances of the 'layout_spring'
algorithm, i.e. the attraction/repulsion layout for graphs.
I tested it on the `CameronGraph` (big and dense), with the following
results:
Before:
{{{
sage: g = graphs.CameronGraph()
sage: %time _=g.layout_spring(iterations=100000)
CPU times: user 30.8 s, sys: 8 ms, total: 30.8 s
Wall time: 30.8 s
}}}
After
{{{
sage: g = graphs.CameronGraph()
sage: %time _=g.layout_spring(iterations=100000)
CPU times: user 14.3 s, sys: 4 ms, total: 14.3 s
Wall time: 14.3 s
}}}
Honestly, that is mostly a failure. Most of the speedup comes from
templating the code so that `dim=2` and `dim=3` are decided at compile-
time. Most of the time it spend multiplying floats, and that's what I have
been trying to reduce. Not with obvious success `:-/`
Nathann
--
--
Ticket URL: <http://trac.sagemath.org/ticket/18395#comment:5>
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.
For more options, visit https://groups.google.com/d/optout.
