How to cope with a long method resolution order?
Simon King
Tickets #9944 and #9138 provide some nice features, but slow things
down. It seems to me that the reason of the performance loss is that
the patches from these tickets make the method resolution order of
polynomial rings much longer - in some cases the length doubles (15
versus 39 steps until <type 'object'> is reached).
As much as I understand: If the mro is longer than Python needs more
time to look up a method that is defined for a very basic class (such
as sage.structure.category_object.CategoryObject or
sage.structure.parent.Parent).
In the example, R is some polynomial ring, and the patches from the
tickets are applied, and the timings for R.base_ring() and
R.category() are better without the patches:
sage: R
Multivariate Polynomial Ring in x, y over Univariate Polynomial Ring
in t over Rational Field
sage: from sage.structure.category_object import CategoryObject
sage: timeit('R.base_ring()',number=10^6)
1000000 loops, best of 3: 453 ns per loop
sage: timeit('R.category()',number=10^6)
1000000 loops, best of 3: 1.13 µs per loop
There is a way to work around the method resolution order, and it
considerably speeds up the access of attributes:
sage: timeit('Parent.base_ring(R)',number=10^6)
1000000 loops, best of 3: 353 ns per loop
sage: timeit('CategoryObject.category(R)',number=10^6)
1000000 loops, best of 3: 331 ns per loop
My questions:
Shall we use the above idiom in basic arithmetic/coercion? These basic
methods are frequently used in arithmetic: R.__call__, for example,
contains 15 calls to .base_ring()!
Or is "Parent.base_ring(R)" not pythonic enough? Aparently, that idiom
is a nightmare for duck typing. On the other hand, in arithmetic, we
*now* that we have sub-classes of Parent and Element.
One way of improvement would be (at least in this concrete example) to
edit R.__call__, define base_ring=self.base_ring() once, and avoid the
other 14 method calls.
But I wonder: Does Python provide the possibility to declare
shortpaths for certain methods?
That's to say, when defining MPolynomialRing_polydict (say), can one
declare that the method "base_ring()" can be found in
sage.structure.category_object.CategoryObject, so that it is not
needed to walk down the mro?
Perhaps like this:
class Foo(Algebra):
base_ring = CategoryObject.base_ring
Would that speed things up, and if "yes", is it considered good or bad
practice?
Python experts, please speak up!
Cheers,
Simon
Florent Hivert
On Tue, Mar 29, 2011 at 12:07:15PM -0700, Simon King wrote:
> Hi!
>
> Tickets #9944 and #9138 provide some nice features, but slow things
> down. It seems to me that the reason of the performance loss is that
> the patches from these tickets make the method resolution order of
> polynomial rings much longer - in some cases the length doubles (15
> versus 39 steps until <type 'object'> is reached).
>
> As much as I understand: If the mro is longer than Python needs more
> time to look up a method that is defined for a very basic class (such
> as sage.structure.category_object.CategoryObject or
> sage.structure.parent.Parent).
I may be wrong but I have the impression that there is a cache here:
Let's create a long mro
class End(object):
def toto(self):
return 1
def long_mro(n):
if n == 0:
return End
else:
class New(long_mro(n-1)):
pass
return New
obj_long = long_mro(500)()
obj_end = End()
Then after that:
sage: len(type(obj_long).mro())
502
sage: len(type(obj_end).mro())
2
sage: timeit('obj_long.toto()',number=10^6)
1000000 loops, best of 3: 187 ns per loop
sage: timeit('obj_end.toto()',number=10^6)
1000000 loops, best of 3: 188 ns per loop
So it seems that there is no difference... Well actually I just figured out
that this has something to do with Cython: if I change
class End(object):
to
class End(SageObject):
Then:
sage: timeit('obj_long.toto()',number=10^6)
1000000 loops, best of 3: 9.22 �s per loop
sage: timeit('obj_end.toto()',number=10^6)
1000000 loops, best of 3: 203 ns per loop
Now we see the difference. Maybe it's a bug... I'll as on Cython-dev.
Cheers,
Florent
Simon King
On 29 Mrz., 21:54, Florent Hivert <florent.hiv...@univ-rouen.fr>
wrote:
> that this has something to do with Cython: if I change
>
> class End(object):
>
> to
>
> class End(SageObject):
>
> Then:
>
> sage: timeit('obj_long.toto()',number=10^6)
> 1000000 loops, best of 3: 9.22 s per loop
> sage: timeit('obj_end.toto()',number=10^6)
> 1000000 loops, best of 3: 203 ns per loop
around.
Taking your example:
class End(SageObject):
def toto(self):
return 1
sage: c_long = long_mro(500)
sage: obj_long = c_long()
sage: obj_end = End()
sage: timeit("obj_end.toto()")
625 loops, best of 3: 963 ns per loop
sage: timeit("obj_long.toto()")
625 loops, best of 3: 22.8 µs per loop
So, as you confirmed, a long mro matters, at least if Cython is
involved.
But it seems possible to speed things up by offering a short path:
sage: c_long.toto = End.toto
sage: timeit("obj_long.toto()")
625 loops, best of 3: 2.55 µs per loop
My question is:
Is it good or at least acceptable practice to do things like
class MPolynomialRing_polydict( MPolynomialRing_macaulay2_repr,
PolynomialRing_singular_repr, MPolynomialRing_generic):
...
base_ring = CategoryObject.base_ring
base = CategoryObject.base
...
cdef class MPolynomial(CommutativeRingElement):
...
parent = Element.parent
...
The example above indicates that it would very well speed things up.
Or is there a good reason to avoid that short path?
Cheers,
Simon
David Roe
David
--
To post to this group, send an email to sage-...@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
Simon King
On 30 Mrz., 08:00, David Roe <r...@math.harvard.edu> wrote:
> I think that base_ring and parent are cpdef'd methods (I don't want to look
> it up at the moment). You want to be a little careful overriding such
> methods with Python functions living in the dictionary, because then the
> functions called by Cython code that knows the type of your object, and the
> code called by Python code will be different.
End in Florent's example derive from Parent, then defining
c_long.base = Parent.base
would still allow to do obj_long.base(), but makes the access to
"base()" almost 15 times faster.
I did some test with has_coerce_map_from. That method *is* cpdef. With
the patches from #9944, I get:
sage: R.<x,y> = ZZ['t'][]
sage: timeit("R.has_coerce_map_from")
625 loops, best of 3: 903 ns per loop
sage: R.__class__.has_coerce_map_from = Parent.has_coerce_map_from
sage: timeit("R.has_coerce_map_from")
625 loops, best of 3: 326 ns per loop
sage: R.has_coerce_map_from(ZZ)
True
So, providing the short path makes the attribute lookup almost 3 times
faster, but the method still works. Of course, that's not a proof that
it'll always work...
On the other hand, I remember that I have seen compiler warnings of
the type "overriding a Cython method by a Python method" or so. If
there are compiler warning then one should better not use short paths.
But what else?
Cheers,
Simon
Simon King
> "base" is a Python method (I looked it up),
a .pyx file.
Nicolas M. Thiery
> down. It seems to me that the reason of the performance loss is that
> the patches from these tickets make the method resolution order of
> polynomial rings much longer - in some cases the length doubles (15
> versus 39 steps until <type 'object'> is reached).
>
> As much as I understand: If the mro is longer than Python needs more
> time to look up a method that is defined for a very basic class (such
> as sage.structure.category_object.CategoryObject or
> sage.structure.parent.Parent).
Note: for good or bad, the Cython classes come before categories in
the mro:
sage: sage: C = CombinatorialFreeModule(ZZ, ZZ)
sage: C.__class__.mro()
[<class 'sage.combinat.free_module.CombinatorialFreeModule_with_category'>,
<class 'sage.combinat.free_module.CombinatorialFreeModule'>,
<class 'sage.structure.unique_representation.UniqueRepresentation'>,
<type 'sage.modules.module.Module'>,
<type 'sage.structure.parent.Parent'>,
<type 'sage.structure.category_object.CategoryObject'>,
<type 'sage.structure.sage_object.SageObject'>,
<class 'sage.categories.modules_with_basis.ModulesWithBasis.parent_class'>, ... <type 'object'>]
So the number of classes to walk through to find base_ring only
increases by 1 (due to the _with_category).
Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Nicolas M. Thiery
> I think that base_ring and parent are cpdef'd methods (I don't want to
> look it up at the moment).
Not at this point apparently: category_object.pyx, line 479:
def base_ring(self): # This should be in a category or elsewhere, but not here
return self._base
def base(self):
return self._base
Maybe making them such would solve Simon's problem? And actually
accelerate things, since Cython could optimize (inline?) their call in
the coercion/arithmetic code.
> You want to be a little careful overriding such methods with
> Python functions living in the dictionary, because then the
> functions called by Cython code that knows the type of your
> object, and the code called by Python code will be different.
Another trick to try would be add in Modules.ParentMethods:
def __init_extra__(self):
self.basis_ring = self.base_ring
therefore adding a short path for base_ring in all parents in Modules.
This should be rather safe (I don't expect the base_ring method to
change over time).
Simon King
On 30 Mrz., 08:32, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
> > I think that base_ring and parent are cpdef'd methods (I don't want to
> > look it up at the moment).
>
> Not at this point apparently: category_object.pyx, line 479:
>
> def base_ring(self): # This should be in a category or elsewhere, but not here
> return self._base
>
> def base(self):
> return self._base
>
> Maybe making them such would solve Simon's problem? And actually
> accelerate things, since Cython could optimize (inline?) their call in
> the coercion/arithmetic code.
cdef class CategoryObject(sage_object.SageObject):
cdef _generators
cdef _category
cdef public _base
cdef public _cdata
cdef public _names # will be _printer
cdef public _factory_data
cdef object __weakref__
# cpdef Generators gens(self, category = *)
# cpdef gen(self, index = *, category = *)
# cpdef ngens(self, category = *)
# cpdef base(self, category = *)
# cpdef base_extend(self, other, category = *)
So, apparently it *was* thought of making these things cpdef!!
Was there a reasong to not make base and base_ring cpdef?
> Another trick to try would be add in Modules.ParentMethods:
>
> def __init_extra__(self):
> self.basis_ring = self.base_ring
>
> therefore adding a short path for base_ring in all parents in Modules.
> This should be rather safe (I don't expect the base_ring method to
> change over time).
That would be nice!
Cheers,
Simon
Simon King
>
> def __init_extra__(self):
> self.basis_ring = self.base_ring
Simon King
> Would that work for objects that don't allow attribute assignment?
Simon King
On 30 Mrz., 09:04, Simon King <simon.k...@uni-jena.de> wrote:
> So, apparently it *was* thought of making these things cpdef!!
>
I tested, and found that cpdef'ing does not help (much):
With def:
sage: R.<x,y> = QQ['t'][]
sage: timeit('R.base_ring')
625 loops, best of 3: 967 ns per loop
With cpdef:
sage: R.<x,y> = QQ['t'][]
sage: timeit('R.base_ring')
625 loops, best of 3: 958 ns per loop
Manually defining R.base_ring = R.base_ring:
sage: timeit('R.base_ring')
625 loops, best of 3: 896 ns per loop
Simon King
>
> def __init_extra__(self):
> self.basis_ring = self.base_ring
>
Rings.ParentMethods, but it is not called when I create R.<x,y> =
QQ['t'][], even though (with the patches from #9944 and #9138 at
least) it belongs to a subcategory of the category of rings, and
R._is_category_initialized() yields True.
Best regards,
Simon
Simon King
On 30 Mrz., 09:44, Simon King <simon.k...@uni-jena.de> wrote:
> When is that called? I provided a __init_extra__ for
> Rings.ParentMethods, but it is not called when I create R.<x,y> =
> QQ['t'][], even though (with the patches from #9944 and #9138 at
> least) it belongs to a subcategory of the category of rings, and
> R._is_category_initialized() yields True.
is to consider all super-categories. If the ParentMethods of a super-
category provide a __init_extra__, then it shall be called.
I provided a short path for several methods of rings that are
frequently used in arithmetic (base, base_ring, has_coerce_map_from
and coerce_map_from).
I obtain:
sage: R.<x,y> = QQ['t'][]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 152 µs per loop
That is a lot (157%) faster than in an unpatched Sage!
So, I guess I will submit it on a new ticket, and make #9944 depend on
it (because, as it is, #9944 slows arithmetic down). If everything
works, then the new patch + #9944 + #9138 will yield a considerable
speedup.
Cheers
Simon
Florent Hivert
> I think, the question is (at least on the short run), how one can work
> around.
>
> Taking your example:
> class End(SageObject):
> def toto(self):
> return 1
> sage: c_long = long_mro(500)
> sage: obj_long = c_long()
> sage: obj_end = End()
> sage: timeit("obj_end.toto()")
> 625 loops, best of 3: 963 ns per loop
> sage: timeit("obj_long.toto()")
> 625 loops, best of 3: 22.8 �s per loop
>
> So, as you confirmed, a long mro matters, at least if Cython is
> involved.
I don't have to investigate further but, according to Stefan Behnel on
cython-users it seems to be solved in cython 0.14 !
Cheers,
Florent
Nicolas M. Thiery
> I tested, and found that cpdef'ing does not help (much):
>
> With def:
> sage: R.<x,y> = QQ['t'][]
> sage: timeit('R.base_ring')
> 625 loops, best of 3: 967 ns per loop
>
> With cpdef:
> sage: R.<x,y> = QQ['t'][]
> sage: timeit('R.base_ring')
> 625 loops, best of 3: 958 ns per loop
>
> Manually defining R.base_ring = R.base_ring:
> sage: timeit('R.base_ring')
> 625 loops, best of 3: 896 ns per loop
I expected a potential improvement not when calling base_ring from the
interpreter, but from compiled Cython code, typically in
coercion/arithmetic.