Opened 11 years ago
Closed 9 years ago
#12601 closed enhancement (fixed)
@cached_method does not work for special methods
Reported by: | Julian Rüth | Owned by: | Jason Grout |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.1 |
Component: | misc | Keywords: | cached_method, cache, operator, special method |
Cc: | Simon King | Merged in: | |
Authors: | Simon King | Reviewers: | Nils Bruin |
Report Upstream: | Completely fixed; Fix reported upstream | Work issues: | |
Branch: | u/SimonKing/ticket/12601 (Commits, GitHub, GitLab) | Commit: | 6cf1fad162f761dd9a0191a7f8d862cb6300583b |
Dependencies: | #15038 | Stopgaps: |
Description
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
.
Attachments (1)
Change History (29)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
Report Upstream: | Reported upstream. Little or no feedback. → N/A |
---|---|
Type: | defect → enhancement |
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".
comment:3 follow-up: 4 Changed 11 years ago by
Report Upstream: | N/A → Reported upstream. Little or no feedback. |
---|
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.
comment:4 Changed 11 years ago by
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__
.
comment:5 Changed 10 years ago by
Report Upstream: | Reported upstream. Little or no feedback. → Reported upstream. No feedback yet. |
---|
comment:6 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:8 Changed 9 years ago by
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.
Changed 9 years ago by
Attachment: | trac12601-cached_special_methods.patch added |
---|
comment:9 Changed 9 years ago by
Authors: | → Simon King |
---|---|
Dependencies: | → #15038 |
Report Upstream: | Reported upstream. No feedback yet. → Completely fixed; Fix reported upstream |
Status: | new → needs_review |
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).
comment:10 follow-up: 11 Changed 9 years ago by
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.
comment:11 follow-up: 12 Changed 9 years ago by
Replying to SimonKing:
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.
comment:12 follow-up: 16 Changed 9 years ago by
Replying to nbruin:
Replying to SimonKing:
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 straightPyList_...
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.
comment:13 Changed 9 years ago by
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.
comment:14 Changed 9 years ago by
The second patchbot finds that all tests pass. So, we may have detected a neutrino...
comment:16 follow-up: 18 Changed 9 years ago by
Replying to SimonKing:
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
andCachedSpecialMethod
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
comment:17 Changed 9 years ago by
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.
comment:18 Changed 9 years ago by
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.
comment:19 follow-up: 20 Changed 9 years ago by
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
comment:20 Changed 9 years ago by
Replying to SimonKing:
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.
comment:21 Changed 9 years ago by
Branch: | → u/SimonKing/ticket/12601 |
---|---|
Modified: | Oct 14, 2013, 9:35:47 PM → Oct 14, 2013, 9:35:47 PM |
comment:22 Changed 9 years ago by
Commit: | → 6cf1fad162f761dd9a0191a7f8d862cb6300583b |
---|
New commits:
[changeset:6cf1fad] | Faster and more thorough detection of special method names |
[changeset:fe1e739] | Remove trailing whitespace |
[changeset:13b500b] | #12601: Cached special methods |
comment:23 Changed 9 years ago by
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.
comment:24 Changed 9 years ago by
Status: | needs_review → positive_review |
---|
Looks good to me. The approach seems solid. We'll see how it stands up once people start using it.
comment:25 Changed 9 years ago by
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.
comment:26 Changed 9 years ago by
Milestone: | sage-5.13 → sage-6.0 |
---|---|
Reviewers: | → Nils Bruin |
I hope Nils does not mind that I filled the fields for him (as he gave a positive review).
comment:27 Changed 9 years ago by
Milestone: | sage-6.0 → sage-6.1 |
---|
comment:28 Changed 9 years ago by
Resolution: | → fixed |
---|---|
Status: | positive_review → closed |
As discussed with Simon, I'm working on a patch for this.