#14214: Cythoned homsets
----------------------------------------------+-----------------------------
Reporter: SimonKing | Owner: tbd
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.8
Component: performance | Resolution:
Keywords: Hom, cython, cached method | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Simon King | Merged in:
Dependencies: #14159, #12951 | Stopgaps:
----------------------------------------------+-----------------------------
Changes (by SimonKing):
* status: new => needs_review
Comment:
Timings with the patch:
{{{
sage: E = J0(11)
sage: F = J0(22)
sage: H = Hom(ZZ,QQ)
sage: HE = Hom(E,E)
sage: HF = Hom(E,F)
sage: D = {H:1,HE:2,HE:3}
sage: timeit("Hom(E,E)", number = 10^4)
10000 loops, best of 3: 9.25 µs per loop
sage: timeit("Hom(E,F)", number = 10^4)
10000 loops, best of 3: 122 µs per loop
sage: timeit("Hom(ZZ,QQ)", number = 10^4)
10000 loops, best of 3: 12 µs per loop
sage: timeit("hash(HE)", number = 10^6)
1000000 loops, best of 3: 2.41 µs per loop
sage: timeit("hash(H)", number = 10^6)
1000000 loops, best of 3: 1.46 µs per loop
sage: timeit("hash(HF)", number = 10^6)
1000000 loops, best of 3: 1.49 µs per loop
sage: timeit("H in D", number = 10^6)
1000000 loops, best of 3: 1.48 µs per loop
sage: timeit("HE in D", number = 10^6)
1000000 loops, best of 3: 2.38 µs per loop
sage: timeit("HF in D", number = 10^6)
1000000 loops, best of 3: 1.48 µs per loop
sage: timeit("HF.domain()", number = 10^6)
1000000 loops, best of 3: 392 ns per loop
sage: timeit("HE.domain()", number = 10^6)
1000000 loops, best of 3: 415 ns per loop
sage: timeit("H.domain()", number = 10^6)
1000000 loops, best of 3: 356 ns per loop
sage: timeit("HF._domain", number = 10^6)
1000000 loops, best of 3: 524 ns per loop
sage: timeit("HE._domain", number = 10^6)
1000000 loops, best of 3: 881 ns per loop
sage: timeit("H._domain", number = 10^6)
1000000 loops, best of 3: 502 ns per loop
sage: %timeit TestSuite(H).run()
100 loops, best of 3: 7.01 ms per loop
sage: %timeit TestSuite(HE).run(skip=['_test_elements'])
10 loops, best of 3: 38.8 ms per loop
sage: %timeit TestSuite(HF).run(skip=['_test_elements'])
10 loops, best of 3: 91.3 ms per loop
}}}
Timings without the patch:
{{{
sage: timeit("hash(HE)", number = 10^6)
1000000 loops, best of 3: 3.97 µs per loop
sage: timeit("hash(H)", number = 10^6)
1000000 loops, best of 3: 2.74 µs per loop
sage: timeit("hash(HF)", number = 10^6)
1000000 loops, best of 3: 2.7 µs per loop
sage: timeit("Hom(E,E)", number = 10^4)
10000 loops, best of 3: 12.9 µs per loop
sage: timeit("Hom(E,F)", number = 10^4)
10000 loops, best of 3: 132 µs per loop
sage: timeit("Hom(ZZ,QQ)", number = 10^4)
10000 loops, best of 3: 21.6 µs per loop
sage: timeit("H in D", number = 10^6)
1000000 loops, best of 3: 2.77 µs per loop
sage: timeit("HE in D", number = 10^6)
1000000 loops, best of 3: 4 µs per loop
sage: timeit("HF in D", number = 10^6)
1000000 loops, best of 3: 2.81 µs per loop
sage: timeit("HF.domain()", number = 10^6)
1000000 loops, best of 3: 1.13 µs per loop
sage: timeit("HE.domain()", number = 10^6)
1000000 loops, best of 3: 1.74 µs per loop
sage: timeit("H.domain()", number = 10^6)
1000000 loops, best of 3: 1.18 µs per loop
sage: timeit("HF._domain", number = 10^6)
1000000 loops, best of 3: 520 ns per loop
sage: timeit("HE._domain", number = 10^6)
1000000 loops, best of 3: 933 ns per loop
sage: timeit("H._domain", number = 10^6)
1000000 loops, best of 3: 522 ns per loop
sage: %timeit TestSuite(H).run()
100 loops, best of 3: 7.79 ms per loop
sage: %timeit TestSuite(HE).run(skip=['_test_elements'])
10 loops, best of 3: 42.3 ms per loop
sage: %timeit TestSuite(HF).run(skip=['_test_elements'])
1 loops, best of 3: 95.7 ms per loop
}}}
__Conclusion__
- There is a clear improvement in all timings.
Some details I am not yet totally happy with (todo on a different
ticket?):
- Getting a homset out of the cache could still be faster. The time-
limiting factor is that one needs to find an appropriate category, if it
is not explicitly passed as an argument. But since the cache is weak
anyway, couldn't we simply cache the same homset ''twice'', namely as
`Hom(X,Y)` and as `Hom(X,Y,C)`? This would give a considerable speed-up.
- The hash is ''much'' too slow. Ideally, one would simply inherit from
`WithEqualityById`, but that's non-trivial, as I have pointed out above.
Doctests pass for me. Needs review!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14214#comment:2>
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.
