@cached_method does not work for special methods

[saraedum]

Caching does not work for the ~ operator.

sage: class A(object):
...    @cached_method
...    def __invert__(self):
...        return 1
sage: a = A() 
sage: ~a is ~a
False

Also the value of a.__invert__ changes when calling ~a.

This happens because special methods are called through the type and not the actual instance for new-style classes: http://docs.python.org/release/2.7.2/reference/datamodel.html?highlight=data%20model#special-method-lookup-for-new-style-classes

As of 5.0.beta4 no operators in sage use @cached_method.

Depends on #15038

Upstream: Completely fixed; Fix reported upstream

CC: @simon-king-jena

Component: misc

Keywords: cached_method, cache, operator, special method

Author: Simon King

Branch/Commit: u/SimonKing/ticket/12601 @ 6cf1fad

Reviewer: Nils Bruin

Issue created by migration from https://trac.sagemath.org/ticket/12601

[saraedum]

comment:1

As discussed with Simon, I'm working on a patch for this.

[simon-king-jena]

Changed upstream from Reported upstream. Little or no feedback. to none

[simon-king-jena]

comment:2

Since no operators in Sage use @cached_method (yet), one shouldn't mark this ticket as "defect" but as "enhancement", I believe.

Since I don't think I am "upstream", I think the "report upstream" field should be "Doesn't apply".

[saraedum]

Upstream: Reported upstream. Little or no feedback.

[saraedum]

comment:3

I didn't consider you "upstream" - I reported it to sage-release.

I filed it as a bug because code I used in 4.8 broke with 5.0. This is also fixed by solving this underlying problem. But you're right, this is an enhancement.

[simon-king-jena]

comment:4

Replying to @saraedum:

I didn't consider you "upstream" - I reported it to sage-release.

I see - or better, I didn't see: I am not regularly reading that list...

Anyway. I think it would be nice to have a mechanism to make use of the cached_method decorator for magical Python methods such as __invert__ or __hash__.

[roed314]

Changed upstream from Reported upstream. Little or no feedback. to Reported upstream. No feedback yet.

[simon-king-jena]

comment:7

Note to myself: Don't forget this ticket...

[simon-king-jena]

comment:8

I think I found the problem. Since the special method of the class is called, the __get__ method of CachedMethod is relevant. Its purpose is to return a "cached method caller" that is bound to the instance.

This __get__ method currently supposes that it is only called if the attribute is not overridden on the instance's __dict__. Namely, if the CachedMethodCaller is in the instance's __dict__, then Python's attribute lookup will not care about the CachedMethod if the instance's class.

Hence, __get__ currently does

        # This is for Parents or Elements that do not allow attribute assignment:
        try:
            name = self._cachedfunc.__name__
        except AttributeError:
            name = self.__name__
        try:
            return (<dict>inst.__cached_methods).__getitem__(name)
        except (AttributeError,TypeError,KeyError),msg:
            pass

and would then create a new CachedMethodCaller. However, in the example from the ticket description, there already is a CachedMethodCaller in the instance's __dict__, but it is ignored by the __get__ method of the CachedMethod.

So, a potential solution is to additionally check inst.__dict__.__getitem__(name).

What I don't like about this solution is that it would involve an additional dictionary lookup, which would slow-down every call to a cached method, fortunately only in the case that the instance does not support attribute assignment. And in addition, the call to the special method will always involve running this __get__ method and doing a dictionary lookup.

Alternatively, one could create a special kind of cached method, specifically for special methods of new style classes whose instances allow for attribute assignment.

[simon-king-jena]

Attachment: trac12601-cached_special_methods.patch.gz

[simon-king-jena]

comment:9

In principle, it would be possible to change CachedMethod.__get__ to deal both with usual and special methods. However, the price to pay would be either a slow-down when using cached methods on instances that don't allow attribute assignment, or cached special methods would be slow.

Therefore, I created a new class CachedSpecialMethod that overloads the __get__ method. Now, cached_method is a function (not an alias of CachedMethod) that chooses amongst CachedMethod and CachedSpecialMethod based on the name of the wrapped method.

I also tried to tweak the case of (usual) cached methods in the case of forbidden attribute assignment.

Timings and examples

With the patch:

sage: class CCache(object):
....:     @cached_method
....:     def __hash__(self):
....:         print "computing hash"
....:         return int(5)
....:     @cached_method
....:     def f(self):
....:         print "computing cached method with no args"
....:         return 4
....:     @cached_method
....:     def g(self, x):
....:         print "computing cached method with args"
....:         return x*2
....:     
sage: class CNoncache(object):
....:     def __hash__(self):
....:         return int(5)
....:     def f(self):
....:         return 4
....:     def g(self, x):
....:         return x*2
....:     
sage: c = CCache()
sage: hash(c)
computing hash
5
sage: hash(c)
5
sage: c.f()
computing cached method with no args
4
sage: c.f()
4
sage: c.g(4)
computing cached method with args
8
sage: c.g(4)
8
sage: c.g(int(4))
8
sage: %timeit hash(c)
1000000 loops, best of 3: 241 ns per loop
sage: %timeit c.f()
10000000 loops, best of 3: 139 ns per loop
sage: %timeit c.g(4)
1000000 loops, best of 3: 694 ns per loop
sage: n = CNoncache()
sage: %timeit hash(n)
1000000 loops, best of 3: 827 ns per loop
sage: %timeit n.f()
1000000 loops, best of 3: 389 ns per loop
sage: %timeit n.g(4)
1000000 loops, best of 3: 669 ns per loop

Note that the cached hash is faster than an uncached hash that returns a constant number!!

Without attribute assignment (special methods can't be wrapped in Cython, so I can't wrap __hash__):

sage: cython("""
....: from sage.structure.parent cimport Parent
....: from sage.misc.cachefunc import cached_method
....: cdef class MyParent(Parent):
....:     @cached_method
....:     def f(self):
....:         return 4
....:     @cached_method
....:     def g(self,x):
....:         return x*2
....: """)
sage: m = MyParent()
sage: m.f() is m.f()
True
sage: m.g(4) is m.g(4)
True
sage: %timeit m.f()
1000000 loops, best of 3: 237 ns per loop
sage: %timeit m.g(4)
1000000 loops, best of 3: 831 ns per loop

Without the patch

The classes and instances are defined as above. As we know, caching the hash did not work, but of course it did work on usual methods:

sage: hash(c)
computing hash
5
sage: hash(c)
computing hash
5
sage: c.f() is c.f()
computing cached method with no args
True
sage: c.g(int(4)) is c.g(4)
computing cached method with args
True

The timing with the possibility to assign attributes did not change (as expected):

sage: %timeit c.f()
10000000 loops, best of 3: 137 ns per loop
sage: %timeit c.g(4)
1000000 loops, best of 3: 702 ns per loop

The timings without attribute assignment did improve with my patch as well:

sage: %timeit m.f()
1000000 loops, best of 3: 334 ns per loop
sage: %timeit m.g(4)
1000000 loops, best of 3: 958 ns per loop

Conclusion

I believe that my patch solves the problem and would be glad about a review :)

I didn't run the full test suite yet.

It could be that there is an interference with #15038, which I thus add as a dependency (it already has positive review).

[simon-king-jena]

Author: Simon King

[simon-king-jena]

Changed upstream from Reported upstream. No feedback yet. to Completely fixed; Fix reported upstream

[simon-king-jena]

Dependencies: #15038

[simon-king-jena]

comment:10

PS: One thing I worry about is the startup time. After all, for each cached method, it is now needed to decide whether the function name starts and ends with two underscores.

[nbruin]

comment:11

Replying to @simon-king-jena:

PS: One thing I worry about is the startup time. After all, for each cached method, it is now needed to decide whether the function name starts and ends with two underscores.

If that's a problem, why not just leave them separate decorators? By the time someone is decorating a special method, they probably are doing the wrong thing or they really know what they're doing. Plus, not all __*__ are special method, are they? Since the list of special methods is short and discrete, I think you should match on the whole name. Perhaps the list is available in the python library somewhere.

Incidentally, I suspect that this will not work for cdef classes at all, due to the special way in which special methods get compiled (and the fact they end up in slots)

By the way, have you done timings on ArgumentFixer overhead? Calling a cached function with arguments has considerable overhead (easily 4 times as expensive). As a result, instantiating a CachedRepresentation no-op class with __init__ arguments is much more expensive than instantiating the corresponding normal no-op class. I think this can really affect things like creating matrices from a list of arguments (the default way!) because the parent, the matrix algebra, must get created.

ArgumentFixer can definitely be improved: several lists there get intensively rewritten and some methods get looked up where straight PyList_... python library calls could get used. I'm not sure to what extent that would improve the situation and how much we lose to this overhead in practice, but it's definitely a possible source: ArgumentFixer is not definitely not without cost and it gets used for any cached method/function call that has arguments.

[simon-king-jena]

comment:12

Replying to @nbruin:

Replying to @simon-king-jena:

PS: One thing I worry about is the startup time. After all, for each cached method, it is now needed to decide whether the function name starts and ends with two underscores.

If that's a problem, why not just leave them separate decorators?

If that's a problem. I simply don't know yet whether it is noticeable in startup-time. If it does not create a slow-down, I think it is more convenient to have a single decorator that works for both kind of methods.

Plus, not all __*__ are special method, are they? Since the list of special methods is short and discrete, I think you should match on the whole name. Perhaps the list is available in the python library somewhere.

Right. However, if we are talking about a cached non-special double underscore method for an instance that allows to assign attributes, then the distinction between CachedMethod and CachedSpecialMethod is irrelevant! Namely, if attribute assignment works, then the __get__ method will be called precisely once. There are only three reasons why the __get__ method could be called repeatedly:

• Attribute assignment does not work, hence, stuff will be stored in (and retrieved from) inst.__cached_methods.
• We have a special method, so that Python won't look into inst.__dict__.
• The user does del inst.method_name.

So, I think it is a non-issue. But of course, we could do a look-up in a finite list of special methods. I just fear that this would create an even bigger slow-down (if there is any slow-down noticeable).

Incidentally, I suspect that this will not work for cdef classes at all, due to the special way in which special methods get compiled (and the fact they end up in slots)

Sure. That's why I wrote "(special methods can't be wrapped in Cython, so I can't wrap __hash__)" in comment:9.

In any case, cdef classes do not play totally nicely with cached methods anyway. They quite often don't allow attribute assignment, and that's why I introduced inst.__cached_methods in the first place, a couple of years ago. Without it, cached methods on cdef classes would not only be even slower, but they wouldn't be cached at all!

By the way, have you done timings on ArgumentFixer overhead?

I didn't change argument fixer here. There was some change in #15038, namely: Postpone creation of the argument fixer. I think it was #8611 and #11115 when I last worked on speeding up the argument fixer.

Calling a cached function with arguments has considerable overhead (easily 4 times as expensive). As a result, instantiating a CachedRepresentation no-op class with __init__ arguments is much more expensive than instantiating the corresponding normal no-op class. I think this can really affect things like creating matrices from a list of arguments (the default way!) because the parent, the matrix algebra, must get created.

That's clearly for a different ticket. Actually I have played with the idea of using an ArgumentFixer in CachedRepresentation.__classcall__ so that different equivalent ways of providing arguments (by position or by name) result in the same instance of the class. And then, further optimisations (e.g., for singleton classes) would easily available.

ArgumentFixer can definitely be improved: several lists there get intensively rewritten and some methods get looked up where straight PyList_... python library calls could get used. I'm not sure to what extent that would improve the situation and how much we lose to this overhead in practice, but it's definitely a possible source: ArgumentFixer is not definitely not without cost and it gets used for any cached method/function call that has arguments.

Again, that's a different ticket.

[simon-king-jena]

comment:13

According to the patchbot, there is no slow-down in startup time. Hence, we might think of following your suggestion to let @cached_method do a slightly more expensive test for choosing between CachedMethod and CachedSpecialMethod.

Recall that I am not totally convinced that a more explicit choice ("only be special for methods that are really special in Python") has any benefit. Choosing a CachedSpecialMethod for a double-underscore non-special method will result in a working cached method, but might have a speed-penalty. However, this speed-penalty would only occur if the instance does not allow attribute assignment; otherwise, there is no difference in speed nor in functionality between the two wrappers. That's why I think it is fine to just test for double underscores.

Anyway, the patchbot also reports a failure. I could not reproduce it at home. So, I hope it is random noise.

[simon-king-jena]

comment:14

The second patchbot finds that all tests pass. So, we may have detected a neutrino...

[simon-king-jena]

comment:15

Review, anyone?

[nbruin]

comment:16

Replying to @simon-king-jena:

Right. However, if we are talking about a cached non-special double underscore
method for an instance that allows to assign attributes, then the distinction
between CachedMethod and CachedSpecialMethod is irrelevant!

Only if the number of calls is significantly larger than 1.

But of course, we could do a look-up in a finite list of special methods. I
just fear that this would create an even bigger slow-down (if there is any
slow-down noticeable).

No that should be fine. Strings like that would be fully interned, so looking
them up in a set or as dictionary keys will actually be significantly faster
than doing string manipulations. (remember that these are attribute names.
Python is very much invested in making attribute lookup lightning fast)

Example:

special_methods=set(['__get__','__set__','__hash__'])

def is_special1(method):
  return method in special_methods
def is_special2(method):
  return method.startswith('__') and method.endswith('__')

Lookup is quite a bit faster than doing string manipulations:

sage: timeit("is_special1('__hash__')",number=100000)
100000 loops, best of 3: 124 ns per loop
sage: timeit("is_special2('__hash__')",number=100000)
100000 loops, best of 3: 380 ns per loop

[nbruin]

comment:17

In an attempt to be a little systematic in extracting a complete list of methods that get stored in slots on a type object (those are the methods that need special attention, right?), I used

grep 'SLOT(".*"' Objects/typeobject.c

to extract the relevant lines from the definition of slotdefs in the python source. When processed, I obtain the list:

['__abs__', '__add__', '__and__', '__call__', '__cmp__', '__coerce__', '__contains__', '__del__', '__delattr__', '__delete__', '__delitem__', '__delslice__', '__div__', '__eq__', '__float__', '__floordiv__', '__ge__', '__get__', '__getattr__', '__getattribute__', '__getitem__', '__getslice__', '__gt__', '__hash__', '__hex__', '__iadd__', '__iand__', '__idiv__', '__ifloordiv__', '__ilshift__', '__imod__', '__imul__', '__index__', '__init__', '__int__', '__invert__', '__ior__', '__ipow__', '__irshift__', '__isub__', '__iter__', '__itruediv__', '__ixor__', '__le__', '__len__', '__long__', '__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__', '__new__', '__nonzero__', '__oct__', '__or__', '__pos__', '__pow__', '__radd__', '__rand__', '__rdiv__', '__repr__', '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__set__', '__setattr__', '__setitem__', '__setslice__', '__str__', '__sub__', '__truediv__', '__xor__', 'next']

Hopefully this list is complete. Is there another source of such methods? I noticed that there is a non-underscored method in there as well: next (this got fixed in Python 3). Admittedly, one should probably never cache that, but it's not the job of the decorator to enforce that.

Unfortunately, this list is not complete. For instance:

class T(object):
  @cached_method
  def __complex__(self):
    print "called"
    return 1
t=T()

does not cache on complex(t). The key seems to by calls to _PyObject_LookupSpecial, which does the lookup on the type rather than on the instance. The only uses of this routine yield:

"__length_hint__", "__format__", "__missing__", "__instancecheck__", "__subclasscheck__", "__complex__", "__reversed__", "__unicode__", "__dir__", "__sizeof__"

so hopefully adding those does give us a complete list.

[simon-king-jena]

comment:18

Replying to @nbruin:

Example:

special_methods=set(['__get__','__set__','__hash__'])

def is_special1(method):
  return method in special_methods
def is_special2(method):
  return method.startswith('__') and method.endswith('__')

With the full list and with Cython, one gets

sage: cython("""
....: cdef list special_methods = ['__abs__', '__add__', '__and__', '__call__', '__cmp__', '__coerce__', '__contains__', '__del__', '__delattr__', '__delete__', '__delitem__', '__delslice__', '__div__', '__eq__', '__float__', '__floordiv__', '__ge__', '__get__', '__getattr__', '__getattribute__', '__getitem__', '__getslice__', '__gt__', '__hash__', '__hex__', '__iadd__', '__iand__', '__idiv__', '__ifloordiv__', '__ilshift__', '__imod__', '__imul__', '__index__', '__init__', '__int__', '__invert__', '__ior__', '__ipow__', '__irshift__', '__isub__', '__iter__', '__itruediv__', '__ixor__', '__le__', '__len__', '__long__', '__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__', '__new__', '__nonzero__', '__oct__', '__or__', '__pos__', '__pow__', '__radd__', '__rand__', '__rdiv__', '__repr__', '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__set__', '__setattr__', '__setitem__', '__setslice__', '__str__', '__sub__', '__truediv__', '__xor__', 'next']
....: def is_special1(str method):
....:     return method in special_methods
....: def is_special2(str method):
....:     return method.startswith('__') and method.endswith('__')
....: """
....: )
....: 
sage: timeit("is_special1('__hash__')",number=100000)
100000 loops, best of 3: 835 ns per loop
sage: timeit("is_special2('__hash__')",number=100000)
100000 loops, best of 3: 161 ns per loop

So, I disagree. If Cython is used then startswith and endswith are faster.

[simon-king-jena]

comment:19

PS: If the list only contains three elements (as in your not very realistic example), then still the string methods are faster.

sage: cython("""                                     
cdef list special_methods = ['__get__', '__set__', '__hash__']def is_special1(str method):    return method in special_methodsdef is_special2(str method):    return method.startswith('__') and method.endswith('__')"""                                                         )                                                         ....: 
sage: timeit("is_special1('__hash__')",number=100000)
100000 loops, best of 3: 174 ns per loop
sage: timeit("is_special2('__hash__')",number=100000)
100000 loops, best of 3: 159 ns per loop

PPS: When we use a frozenset instead, then using the string methods is not faster any more, even with the complete set of special attribute names.

sage: cython("""                                     
cdef frozenset special_methods = frozenset(['__abs__', '__add__', '__and__', '__call__', '__cmp__', '__coerce__', '__contains__', '__del__', '__delattr__', '__delete__', '__delitem__', '__delslice__', '__div__', '__eq__', '__float__', '__floordiv__', '__ge__', '__get__', '__getattr__', '__getattribute__', '__getitem__', '__getslice__', '__gt__', '__hash__', '__hex__', '__iadd__', '__iand__', '__idiv__', '__ifloordiv__', '__ilshift__', '__imod__', '__imul__', '__index__', '__init__', '__int__', '__invert__', '__ior__', '__ipow__', '__irshift__', '__isub__', '__iter__', '__itruediv__', '__ixor__', '__le__', '__len__', '__long__', '__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__', '__new__', '__nonzero__', '__oct__', '__or__', '__pos__', '__pow__', '__radd__', '__rand__', '__rdiv__', '__repr__', '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__set__', '__setattr__', '__setitem__', '__setslice__', '__str__', '__sub__', '__truediv__', '__xor__', 'next'])
def is_special1(str method):
    return method in special_methods
def is_special2(str method):
    return method.startswith('__') and method.endswith('__')
"""
)
....: 
sage: timeit("is_special1('__hash__')",number=100000)
100000 loops, best of 3: 113 ns per loop
sage: timeit("is_special2('__hash__')",number=100000)
100000 loops, best of 3: 169 ns per loop

[nbruin]

comment:20

Replying to @simon-king-jena:

PPS: When we use a frozenset instead, then using the string methods is not faster any more, even with the complete set of special attribute names.

Right, better use sets to check membership. Also, note that next is a special method that does not get detected with the underscore rule.

I've edited #12601:comment:17 above with a list of special methods which should be usable as a lookup. It doesn't seem there's a store of these available somewhere already, so it looks like we'll have to make our own set.

[simon-king-jena]

Branch: u/SimonKing/ticket/12601

[simon-king-jena]

Commit: 6cf1fad

[simon-king-jena]

New commits:

[changeset:6cf1fad]	Faster and more thorough detection of special method names
[changeset:fe1e739]	Remove trailing whitespace
[changeset:13b500b]	#12601: Cached special methods

[simon-king-jena]

comment:23

I have created a git branch for this ticket, containing the original patch, removing some trailing whitespace that the patch has introduced, and then changing the detection of special method names to using a frozenset of all names that Nils has mentioned here (note that Nils presented two lists, and I combined both).

Tests pass for me. Needs review, then.

[nbruin]

comment:24

Looks good to me. The approach seems solid. We'll see how it stands up once people start using it.

[jdemeyer]

comment:25

Please clarify whether the patch or branch should be merged. In the latter case, set the milestone to sage-6.0. Also, the Reviewer field should be filled in.

[simon-king-jena]

comment:26

I hope Nils does not mind that I filled the fields for him (as he gave a positive review).

[simon-king-jena]

Reviewer: Nils Bruin