#11900: Serious regression caused by #9138
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: tbd
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.7.3
Component: performance | Keywords: categories regression
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies: #9138 #11911
---------------------------+------------------------------------------------
Old description:
> At [http://groups.google.com/group/sage-
> devel/browse_thread/thread/d885434ba9c22d66 sage-devel], Jeroen reported
> a massive regression in elliptic curve computations. The regression was
> introduced in the transition from sage-4.7.2.alpha2 to sage-4.7.2.alpha3.
>
> It seems that #9138 is responsible, at least for a big part of the
> regression. With unpatched sage-4.7.2.alpha2, we find
> {{{
> sage: E = J0(46).endomorphism_ring()
> sage: %time g = E.gens()
> CPU times: user 5.54 s, sys: 0.15 s, total: 5.69 s
> Wall time: 5.81 s
> }}}
> Adding #9138 and its dependency, we obtain
> {{{
> sage: E = J0(46).endomorphism_ring()
> sage: %time g = E.gens()
> CPU times: user 8.72 s, sys: 0.18 s, total: 8.89 s
> Wall time: 8.92 s
> }}}
>
> It turns out that much time is wasted for calls to
> `sage.categories.Category.join` and to
> `sage.categories.Category.hom_category`.
>
> When caching these two methods, one can reduce the speed difference to
> something like that (sage-4.7.2.alpha3 plus #11115 plus an experimental
> patch for the caching):
> {{{
> sage: E = J0(46).endomorphism_ring()
> sage: %time g = E.gens()
> CPU times: user 6.82 s, sys: 0.16 s, total: 6.98 s
> Wall time: 7.40 s
> }}}
> However, that's still far from good. After caching join and hom_category,
> there is still too much time spent (according to %prun) for the
> initialisation of matrix spaces.
>
> Apply:
>
> * [attachment:trac11900_no_categories_for_matrices.patch]
> * [attachment:trac11900_category_speedup.patch]
New description:
At [http://groups.google.com/group/sage-
devel/browse_thread/thread/d885434ba9c22d66 sage-devel], Jeroen reported a
massive regression in elliptic curve computations. The regression was
introduced in the transition from sage-4.7.2.alpha2 to sage-4.7.2.alpha3.
It seems that #9138 is responsible, at least for a big part of the
regression. With unpatched sage-4.7.2.alpha2, we find
{{{
sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 5.54 s, sys: 0.15 s, total: 5.69 s
Wall time: 5.81 s
}}}
Adding #9138 and its dependency, we obtain
{{{
sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 8.72 s, sys: 0.18 s, total: 8.89 s
Wall time: 8.92 s
}}}
It turns out that much time is wasted for calls to
`sage.categories.Category.join` and to
`sage.categories.Category.hom_category`.
When caching these two methods, one can reduce the speed difference to
something like that (sage-4.7.2.alpha3 plus #11115 plus an experimental
patch for the caching):
{{{
sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 6.82 s, sys: 0.16 s, total: 6.98 s
Wall time: 7.40 s
}}}
However, that's still far from good. After caching join and hom_category,
there is still too much time spent (according to %prun) for the
initialisation of matrix spaces.
Apply:
* [attachment:trac11900_no_categories_for_matrices.patch]
* [attachment:trac11900_category_speedup.patch]
* [attachment:trac11900_further_tweaks.patch]
--
Comment(by SimonKing):
Replying to [comment:70 jdemeyer]:
> Hi Simon, thanks for all this work! I will certainly do tests of these
patches, to see whether they don't break anything and also timing tests.
Before you start: I just added another patch. The patch is not tested yet.
It fixes some more doc string formatting, and it provides some smaller
improvements. For example, it removes import statements from `__init__`
methods. It also introduces a cached function that computes the category
used for a homset - the same computation used to happen ''repeatedly''
during homset creation. Also, the string representation is now only
computed when needed - not during initialisation.
The effect of these improvements is certainly not as evident as what is
done in the first patch. Nevertheless, since elliptic curve computations
involve the creation of thousands of polynomial rings over finite fields,
it is noticeable.
Apply trac11900_no_categories_for_matrices.patch
trac11900_category_speedup.patch trac11900_further_tweaks.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11900#comment:71>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
