# How to cope with a long method resolution order?

4 views

### Simon King

Mar 29, 2011, 3:07:15 PM3/29/11
to sage-devel
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).

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?

Cheers,
Simon

### Florent Hivert

Mar 29, 2011, 3:54:58 PM3/29/11
Hi Simon,

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

Mar 30, 2011, 1:48:58 AM3/30/11
to sage-devel
Hi Florent,

On 29 Mrz., 21:54, Florent Hivert <florent.hiv...@univ-rouen.fr>
wrote:
> 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

I think, the question is (at least on the short run), how one can work
around.

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

Mar 30, 2011, 2:00:22 AM3/30/11
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.
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

Mar 30, 2011, 2:20:02 AM3/30/11
to sage-devel
Hi David,

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.

"base" is a Python method (I looked it up), and if one makes the class
End in Florent's example derive from Parent, then defining
c_long.base = Parent.base
"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

Mar 30, 2011, 2:21:14 AM3/30/11
to sage-devel
On 30 Mrz., 08:20, Simon King <simon.k...@uni-jena.de> wrote:
> "base" is a Python method (I looked it up),

I meant to say: "a def method, not cpdef", but of course it is in
a .pyx file.

### Nicolas M. Thiery

Mar 30, 2011, 2:22:49 AM3/30/11
On Tue, Mar 29, 2011 at 12:07:15PM -0700, Simon King wrote:
> 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).

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

Mar 30, 2011, 2:32:31 AM3/30/11
On Wed, Mar 30, 2011 at 02:00:22AM -0400, David Roe 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.

> 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

Mar 30, 2011, 3:04:56 AM3/30/11
to sage-devel
Hi Nicolas,

On 30 Mrz., 08:32, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
> On Wed, Mar 30, 2011 at 02:00:22AM -0400, David Roe 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.

I was just starting to try that, and found in category_object.pxd:
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).

You mean, the category framework would be used to speed things up?
That would be nice!

Cheers,
Simon

### Simon King

Mar 30, 2011, 3:06:32 AM3/30/11
to sage-devel
On 30 Mrz., 08:32, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
> Another trick to try would be add in Modules.ParentMethods:
>
>         def __init_extra__(self):
>             self.basis_ring = self.base_ring

Would that work for objects that don't allow attribute assignment?

### Simon King

Mar 30, 2011, 3:11:13 AM3/30/11
to sage-devel
On 30 Mrz., 09:06, Simon King <simon.k...@uni-jena.de> wrote:
> Would that work for objects that don't allow attribute assignment?

Well, there's always try-except, I suppose...

### Simon King

Mar 30, 2011, 3:17:06 AM3/30/11
to sage-devel
Hi,

On 30 Mrz., 09:04, Simon King <simon.k...@uni-jena.de> wrote:
> So, apparently it *was* thought of making these things cpdef!!
>
> Was there a reason to not make base and base_ring 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

Mar 30, 2011, 3:44:00 AM3/30/11
to sage-devel
Hi Nicolas,

On 30 Mrz., 08:32, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
> Another trick to try would be add in Modules.ParentMethods:
>
>         def __init_extra__(self):
>             self.basis_ring = self.base_ring
>

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.

Best regards,
Simon

### Simon King

Mar 30, 2011, 4:19:43 AM3/30/11
to sage-devel
Hi Nicolas,

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.

It turns out that one needs to change Parent._init_category_: The idea
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

Mar 30, 2011, 4:34:03 AM3/30/11
Hi there,

> I think, the question is (at least on the short run), how one can work
> around.
>
> 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

Mar 31, 2011, 7:12:45 PM3/31/11
On Wed, Mar 30, 2011 at 12:17:06AM -0700, Simon King wrote:
> 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.