#20681: Cythonize the special methods in the categories that handle coercion in
arithmetic
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-7.3
Component: categories | Resolution:
Keywords: performance | Merged in:
Authors: Nicolas M. Thiéry | Reviewers: Travis Scrimshaw
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/nthiery/cythonize_arithmetic_special_methods_in_the_categories|
2f83f598d7d08ee2002b749e6ba2f81d48983a25
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Description changed by nthiery:
Old description:
> Recall that the Sage categories provide implementations for Python's
> special methods for the basic arithmetic operations (e.g. `__mul__`,
> `__add__`), that dispatch to the coercion model or call Sage's special
> methods (e.g. `_mul_`, `_add_`) for the internal operations.
>
> Before this ticket, this indirection induces an overhead of roughly
> 500ns:
> {{{
> sage: S = Semigroups().example()
> sage: x = S.an_element()
>
> sage: sage: %timeit [x*x for i in range(1000)]
> 1000 loops, best of 3: 1.21 ms per loop
> sage: sage: %timeit [x.__mul__(x) for i in range(1000)]
> 1000 loops, best of 3: 1.12 ms per loop
> sage: sage: %timeit [x._mul_(x) for i in range(1000)]
> 1000 loops, best of 3: 643 µs per loop
> }}}
> (the average timing don't vary much if we try again)
>
> After this ticket, which Cythonize those methods, the overhead is
> reduced to roughly 260ns, which is a speedup by a factor of 2:
> {{{
> sage: %timeit [x*x for i in range(1000)]
> 1000 loops, best of 3: 929 µs per loop
> sage: %timeit [x.__mul__(x) for i in range(1000)]
> 1000 loops, best of 3: 884 µs per loop
> sage: %timeit [x._mul_(x) for i in range(1000)]
> 1000 loops, best of 3: 624 µs per loop
> }}}
New description:
Recall that the Sage categories provide implementations for Python's
special methods for the basic arithmetic operations (e.g. `__mul__`,
`__add__`), that dispatch to the coercion model or call Sage's special
methods (e.g. `_mul_`, `_add_`) for the internal
operations. Furthermore, the default implementation for `_mul_` is to
delegate the work to the `product` method of the parent.
Before this ticket, those indirections induced an overhead of roughly
100ns for `*`, 480ns for `__mul__` and 340ns for `_mul_`:
{{{
sage: S = Semigroups().example()
sage: x = S.an_element()
sage: x*x
42
sage: sage: %timeit [x*x for i in range(1000)]
1000 loops, best of 3: 1.21 ms per loop
sage: sage: %timeit [x.__mul__(x) for i in range(1000)]
1000 loops, best of 3: 1.12 ms per loop
sage: sage: %timeit [x._mul_(x) for i in range(1000)]
1000 loops, best of 3: 643 µs per loop
sage: %timeit [S.product(x,x) for i in range(1000)]
1000 loops, best of 3: 300 µs per loop
}}}
After this ticket, which Cythonize those methods, the overhead is
reduced to roughly 20ns for `*`, 100ns for `__mul__` and 160ms for
`_mul_`, which is a speedup by a factor of 3 on the accumulated
overhead, and an overall speedup by a factor of 2 for this particular
parent:
{{{
sage: %timeit [x*x for i in range(1000)]
1000 loops, best of 3: 596 µs per loop
sage: %timeit [x.__mul__(x) for i in range(1000)]
1000 loops, best of 3: 572 µs per loop
sage: %timeit [x._mul_(x) for i in range(1000)]
1000 loops, best of 3: 467 µs per loop
sage: %timeit [S.product(x,x) for i in range(1000)]
1000 loops, best of 3: 300 µs per loop
}}}
Notes
=====
The average timings vary by about 5-10% from one run to the other.
In this parent, the product is trivial, and implemented as a plain
Python `product` method in the parent. For a parent with a non trivial
Python product, the overhead of the indirections is now of 20%, which
is getting closer to acceptable::
{{{
sage: S = Semigroups().Finite().example()
sage: x = S.an_element()
sage: %timeit [S.product(x,x) for i in range(1000)]
100 loops, best of 3: 4.39 ms per loop
sage: %timeit [x*x for i in range(1000)]
100 loops, best of 3: 5.28 ms per loop
}}}
For comparison, here is the cost of the product of two (Sage)
integers::
{{{
sage: x = 3
sage: %timeit [x*x for i in range(1000)]
1000 loops, best of 3: 162 µs per loop
sage: x = int(3)
sage: %timeit [x*x for i in range(1000)]
10000 loops, best of 3: 63.9 µs per loop
}}}
So the 120ns overhead when using coercion methods `__mul__` provided
by categories (rather than from a Cython super class) is of the same
order of magnitude as the cost of a trivial multiplication.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/20681#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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
