#11900: Serious regression caused by #9138
-----------------------------------------------------------------------------------+
Reporter: SimonKing
| Owner: tbd
Type: defect
| Status: needs_work
Priority: critical
| Milestone: sage-4.8
Component: performance
| Keywords: categories regression
Work_issues: finalize the patch with the different ideas that have been
explored | Upstream: N/A
Reviewer: Jeroen Demeyer, Nicolas M. Thiéry
| 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]
> * [attachment:trac11900_further_tweaks.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]
* [attachment:trac_11900-category_singleton-sk.patch]
--
Comment(by SimonKing):
Replying to [comment:111 nthiery]:
> Replying to [comment:110 SimonKing]:
> > I have attached a new patch, which is your patch but with the
modifications I explained above.
>
> That all sounds good! Do you mind folding the different ideas we agreed
upon in a single overview patch
Do you mean "combine the four patches into one"? Or are there ideas
concerning singleton that we discussed (for ''this'' ticket; I know that
we had further ideas for other tickets) and are not included in the
singleton patch yet?
I succeeded to save yet another bit of time: Use the fact that the
argument of `__contains__` should be a `CategoryObject`, or it is no
object in a category.
Moreover, I found that it is both easier and slightly faster to use
`ConstantFunction` for the `__hash__`.
And finally, I tried to get rid of the custom `__contains__` method of
Fields(). It should all use categories by now.
Current timings are:
{{{
sage: MS = MatrixSpace(QQ,2)
sage: P.<x,y,z> = QQ[]
sage: RC = Rings()
sage: FC = Fields()
sage: F3 = GF(3)
sage: %timeit Rings()
625 loops, best of 3: 2.04 µs per loop
sage: %timeit Fields()
625 loops, best of 3: 2.08 µs per loop
sage: %timeit MS in RC
625 loops, best of 3: 726 ns per loop
sage: %timeit MS in FC
625 loops, best of 3: 793 ns per loop
sage: %timeit F3 in RC
625 loops, best of 3: 667 ns per loop
sage: %timeit F3 in FC
625 loops, best of 3: 671 ns per loop
sage: %timeit {FC:1,RC:2}
625 loops, best of 3: 1.37 µs per loop
sage: %timeit hash(FC)
625 loops, best of 3: 352 ns per loop
}}}
The patch still needs work: Documentation needs to be written, and tests
need to pass (I didn't try yet). But of course you can already see whether
you might like the result.
Apply trac11900_no_categories_for_matrices.patch
trac11900_category_speedup.patch trac11900_further_tweaks.patch trac_11900
-category_singleton-sk.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11900#comment:112>
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.
