Opened 3 years ago

Closed 3 years ago

#20686 closed enhancement (fixed)

Refactor getattr_from_other_class() for lookup of methods in categories

Reported by: nthiery Owned by:
Priority: major Milestone: sage-7.4
Component: categories Keywords:
Cc: jdemeyer, tscrim Merged in:
Authors: Jeroen Demeyer Reviewers: Vincent Delecroix
Report Upstream: Fixed upstream, in a later stable release. Work issues:
Branch: 74041f3 (Commits) Commit: 74041f30d8de4c15055345f14340a4f443236ffa
Dependencies: #21030, #21409 Stopgaps:

Description (last modified by jdemeyer)

For parents and elements implemented in Cython, category lookup is emulated in __getattr__ using getattr_from_other_class. In this ticket, this is refactored a bit:

  1. We should not pick up special attributes from type, there is no point in returning the type name of the category here (similarly for __dict__, __mro__, ...):
    sage: ZZ(1).__name__
    'JoinCategory.element_class'
    sage: ZZ.__name__
    'JoinCategory.parent_class'
    

This change causes a few failures which need to be fixed.

  1. The implementation of getattr_from_other_class is not very robust. For example, static methods are not supported. We fix this by using low-level Python functions to get the attribute and we manually call the descriptor __get__ if needed.
  1. We shouldn't do anything special with double-underscore private attributes: in plain Python, this is implemented by the parser and not by getattr(). So __getattr__ would already receive the mangled private name.
  1. Some of the changes broke _sage_src_lines_, so we also change that: currently, _sage_src_lines_() is used both to get the source lines of a class (e.g. dynamic classes) and an instance (e.g. cached functions). We change this to always mean the source lines of an instance, which makes things clearer.
  1. The lookup using getattr_from_other_class is about 9 times slower than a normal method lookup::
    sage: def foo(self): return
    sage: Sets().element_class.foo = foo
    sage: def g(x):
    ....:     for i in range(1000):
    ....:          x.foo()
    
    sage: x = Semigroups().example().an_element()
    sage: y = 1
    
    sage: %timeit g(x)
    10000 loops, best of 3: 115 µs per loop
    
    sage: %timeit g(y)
    1000 loops, best of 3: 1.18 ms per loop
    

We improve on this by roughly a factor 2 (but even then, it's still a lot slower than usual method lookup).

NOTE: This needs a trivial Cython patch, see #21030 for the Cython upgrade.

Change History (81)

comment:1 Changed 3 years ago by jdemeyer

  • Cc jdemeyer added

comment:2 Changed 3 years ago by jdemeyer

I might have some ideas... discuss in Meudon?

comment:3 Changed 3 years ago by nthiery

+1

comment:4 Changed 3 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Description modified (diff)

comment:5 Changed 3 years ago by jdemeyer

  • Branch set to u/jdemeyer/optimize_method_lookup_from_the_categories_for_instances_of_cython_classes

comment:6 Changed 3 years ago by jdemeyer

  • Commit set to bbd0b05c11b0431f02b34c1b55bed6b775de7fa8
  • Dependencies set to #20825

New commits:

a143a32EvaluationMethods should be a new-style class
bbd0b05Improve getattr_from_other_class

comment:7 Changed 3 years ago by git

  • Commit changed from bbd0b05c11b0431f02b34c1b55bed6b775de7fa8 to 3cd449f14dc1b8c07d326ae1192067f4fdf7e644

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

44e80b3EvaluationMethods should be a new-style class
3cd449fImprove getattr_from_other_class

comment:8 Changed 3 years ago by jdemeyer

  • Description modified (diff)
  • Report Upstream changed from N/A to Reported upstream. No feedback yet.

comment:9 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:10 Changed 3 years ago by jdemeyer

  • Report Upstream changed from Reported upstream. No feedback yet. to Fixed upstream, but not in a stable release.

comment:11 Changed 3 years ago by git

  • Commit changed from 3cd449f14dc1b8c07d326ae1192067f4fdf7e644 to e906b7e6201c92438e41055b08a2ac085f9aa6b7

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e906b7eImprove getattr_from_other_class

comment:12 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:13 Changed 3 years ago by git

  • Commit changed from e906b7e6201c92438e41055b08a2ac085f9aa6b7 to 92f4520d01640379590d6c5974622f3d6f396e9b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

92f4520Improve getattr_from_other_class

comment:14 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:15 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:16 Changed 3 years ago by git

  • Commit changed from 92f4520d01640379590d6c5974622f3d6f396e9b to 9f529b0c4c8fd3523ebb557c9821e39799c41476

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9f529b0Improve getattr_from_other_class

comment:17 Changed 3 years ago by git

  • Commit changed from 9f529b0c4c8fd3523ebb557c9821e39799c41476 to ff3a496289bbb6611d0feaf583d031522d69c90f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ff3a496Improve getattr_from_other_class

comment:18 Changed 3 years ago by jdemeyer

  • Status changed from new to needs_review

comment:19 Changed 3 years ago by jdemeyer

  • Description modified (diff)
  • Summary changed from Optimize method lookup from the categories for instances of Cython classes to Refactor getattr_from_other_class() for lookup of methods in categories

comment:20 Changed 3 years ago by git

  • Commit changed from ff3a496289bbb6611d0feaf583d031522d69c90f to d49b67a34d416f17285c25d576c6444ad977f7b0

Branch pushed to git repo; I updated commit sha1. New commits:

d49b67aTest that static methods work

comment:21 Changed 3 years ago by tscrim

  • Cc tscrim added

comment:22 Changed 3 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:23 Changed 3 years ago by git

  • Commit changed from d49b67a34d416f17285c25d576c6444ad977f7b0 to 30594cce7e9bdb3e8a8ff5bfb601e93a52da175b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a9514e5Improve getattr_from_other_class
f912586Test that static methods work
30594ccImprove _sage_src_lines_()

comment:24 Changed 3 years ago by git

  • Commit changed from 30594cce7e9bdb3e8a8ff5bfb601e93a52da175b to 851fa16587c1d74797b6ce66e101915e5ebbe339

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

851fa16Improve _sage_src_lines_()

comment:25 Changed 3 years ago by git

  • Commit changed from 851fa16587c1d74797b6ce66e101915e5ebbe339 to f5361d972a61dcb60a76425264baa9e6d134e54b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9a1ff6eImprove getattr_from_other_class
744ffa6Test that static methods work
f5361d9Improve _sage_src_lines_()

comment:26 Changed 3 years ago by embray

  • Keywords test added

comment:27 Changed 3 years ago by embray

  • Keywords test removed

comment:28 Changed 3 years ago by embray

  • Description modified (diff)

comment:29 Changed 3 years ago by embray

  • Description modified (diff)

comment:30 Changed 3 years ago by embray

  • Description modified (diff)

comment:31 Changed 3 years ago by git

  • Commit changed from f5361d972a61dcb60a76425264baa9e6d134e54b to 8a4f48d047a06ef9fcb2a0e01b5198f7ef439f9b

Branch pushed to git repo; I updated commit sha1. New commits:

dc84d88Remove comments about "private" attributes with two underscores
8a4f48dAbstract away category lookup in cdef method getattr_from_category

comment:32 Changed 3 years ago by nthiery

  • Branch changed from u/jdemeyer/optimize_method_lookup_from_the_categories_for_instances_of_cython_classes to u/nthiery/optimize_method_lookup_from_the_categories_for_instances_of_cython_classes

comment:33 Changed 3 years ago by jdemeyer

  • Branch changed from u/nthiery/optimize_method_lookup_from_the_categories_for_instances_of_cython_classes to u/jdemeyer/optimize_method_lookup_from_the_categories_for_instances_of_cython_classes

comment:34 Changed 3 years ago by embray

  • Commit changed from 8a4f48d047a06ef9fcb2a0e01b5198f7ef439f9b to 7140ee389ac63921f356d5abc4cdc94a6bf48580
  • Description modified (diff)

New commits:

88d9757Comment that getattr_from_other_class is cached
7140ee3Prefer absolute imports

comment:35 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:36 Changed 3 years ago by jdemeyer

Thanks Erik!

comment:37 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:38 Changed 3 years ago by jdemeyer

  • Dependencies changed from #20825 to #21030
  • Description modified (diff)
  • Report Upstream changed from Fixed upstream, but not in a stable release. to Fixed upstream, in a later stable release.
  • Status changed from needs_review to needs_work

comment:39 Changed 3 years ago by git

  • Commit changed from 7140ee389ac63921f356d5abc4cdc94a6bf48580 to fc6487cb02514a811cb1f7ccfd92bed177bb2dea

Branch pushed to git repo; I updated commit sha1. New commits:

9cb4c3cUpgrade to Cython 0.24.1
fc6487cMerge remote-tracking branch 'trac/u/jdemeyer/upgrade_to_cython_0_24_1' into t/20686/optimize_method_lookup_from_the_categories_for_instances_of_cython_classes

comment:40 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:41 Changed 3 years ago by git

  • Commit changed from fc6487cb02514a811cb1f7ccfd92bed177bb2dea to 16d474363c051b081383dcdbc1944828e735c41e

Branch pushed to git repo; I updated commit sha1. New commits:

16d4743EvaluationMethods should be a new-style class

comment:42 Changed 3 years ago by git

  • Commit changed from 16d474363c051b081383dcdbc1944828e735c41e to 54ccd828cb20b1254aeaf55bf7edab4a73f1032a

Branch pushed to git repo; I updated commit sha1. New commits:

54ccd82Remove __dict__ attribute from ElementWrapper

comment:43 follow-up: Changed 3 years ago by vdelecroix

why is this test removed

-        We test that "private" attributes are not requested from the element class
-        of the category (:trac:`10467`)::
-
-            sage: C = EuclideanDomains()
-            sage: P.<x> = QQ[]
-            sage: C.element_class.__foo = 'bar'
-            sage: x.parent() in C
-            True
-            sage: x.__foo
-            Traceback (most recent call last):
-            ...
-            AttributeError: 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint' object has no attribute '__foo'

comment:44 Changed 3 years ago by vdelecroix

similarly

-        We test that "private" attributes are not requested from the element class
-        of the category (:trac:`10467`)::
-
-            sage: P = Parent(QQ, category=CommutativeRings())
-            sage: P.category().parent_class.__foo = 'bar'
-            sage: P.__foo
-            Traceback (most recent call last):
-            ...
-            AttributeError: 'sage.structure.parent.Parent' object has no attribute '__foo'

comment:45 in reply to: ↑ 43 Changed 3 years ago by jdemeyer

Replying to vdelecroix:

why is this test removed

Because #10467 was a mistake, see point 3 in the ticket description.

comment:47 Changed 3 years ago by jdemeyer

Aargh....... this whole "category lookup" mechanism is causing me so much frustration with #20767. It is a very fragile hack which just happens to work correctly in the current setting but when you change anything in the coercion model it breaks.

I am starting to think we should reconsider the whole category approach.

comment:48 follow-up: Changed 3 years ago by nthiery

In case this could be useful, we could have a live chat about this tomorrow between 11pm and 2pm, or latter in the week.

Cheers,

comment:49 in reply to: ↑ 48 Changed 3 years ago by vdelecroix

Replying to nthiery:

In case this could be useful, we could have a live chat about this tomorrow between 11pm and 2pm, or latter in the week.

You meant 11am-2pm? Given that Santiago is -6h from Paris, it will be hard for me before 2pm (=8am in Santiago).

comment:50 Changed 3 years ago by jdemeyer

I am available most days during Paris daytime...

comment:51 Changed 3 years ago by jdemeyer

Anyway, I am also hitting Cython bugs/oddities, so there are other battles to fight.

comment:52 Changed 3 years ago by jdemeyer

In #20767, I "solved" the category problem (see 47) in the following way:

  • double-underscore methods (e.g. __add__) are never taken from the category.
  • anything deriving directly from Element fully supports single-underscore methods (e.g. _add_) from the category.
  • anything deriving from ModuleElement, RingElement,... has only partial support for single-underscore methods from the category.
  • nothing changes for non-arithmetic methods (e.g. base_ring).

The above rules do not break any existing usage of categories. I hope you can live with this...

comment:53 follow-up: Changed 3 years ago by vdelecroix

The following example of getattr_from_other_class line 249-253 in sage/structure/misc.pyx seems broken

sage: n = 1
sage: ip = get_ipython()
sage: ip.magic_psearch('n.N')
Traceback (most recent call last):
...
AttributeError: 'SageTerminalInteractiveShell' object has no attribute 'magic_psearch'

comment:54 in reply to: ↑ 53 Changed 3 years ago by jdemeyer

Replying to vdelecroix:

The following example of getattr_from_other_class line 249-253 in sage/structure/misc.pyx seems broken

True, but surely not because of this ticket. Most likely, it has to do with the IPython 5 upgrade.

comment:55 follow-up: Changed 3 years ago by vdelecroix

Is that what we want

if self._category is None:
    # Usually, this will just raise AttributeError in
    # getattr_from_other_class().
    cls = type
else:
    cls = self._category.parent_class

In other words, are there use case where the category is not initialized but we still might need to go through __getattr__?

comment:56 follow-up: Changed 3 years ago by vdelecroix

Why in Element there is a two stage __getattr__ -> getattr_from_category -> getattr_from_other_class whereas in Parent there is no intermediate getattr_from_category?

comment:57 in reply to: ↑ 56 ; follow-up: Changed 3 years ago by jdemeyer

Replying to vdelecroix:

Why in Element there is a two stage __getattr__ -> getattr_from_category -> getattr_from_other_class whereas in Parent there is no intermediate getattr_from_category?

Mainly because I care more about Element than Parent (with #20767 in mind). The idea of getattr_from_category was to allow direct access to the category methods without normal methods. In the end, I am not using this in #20767 but I kept it because it looked potentially useful. And, since this a cdef method, there is essentially no performance penalty.

comment:58 in reply to: ↑ 55 Changed 3 years ago by jdemeyer

Replying to vdelecroix:

In other words, are there use case where the category is not initialized but we still might need to go through __getattr__?

Probably not, but the old code also supported that (directly raising an AttributeError). But I just let getattr_from_other_class raise the error.

comment:59 in reply to: ↑ 57 ; follow-up: Changed 3 years ago by vdelecroix

Replying to jdemeyer:

Replying to vdelecroix:

Why in Element there is a two stage __getattr__ -> getattr_from_category -> getattr_from_other_class whereas in Parent there is no intermediate getattr_from_category?

Mainly because I care more about Element than Parent (with #20767 in mind). The idea of getattr_from_category was to allow direct access to the category methods without normal methods. In the end, I am not using this in #20767 but I kept it because it looked potentially useful. And, since this a cdef method, there is essentially no performance penalty.

It just looks weird to have twice the same thing implemented differently. I am just complaining about readability.

comment:60 in reply to: ↑ 59 Changed 3 years ago by jdemeyer

Replying to vdelecroix:

It just looks weird to have twice the same thing implemented differently. I am just complaining about readability.

OK, I will make the requested changes. I will also move the category lookup stuff from Parent to CategoryObject where it belongs.

comment:61 Changed 3 years ago by jdemeyer

  • Milestone changed from sage-7.3 to sage-7.4
  • Status changed from needs_review to needs_work

comment:62 Changed 3 years ago by git

  • Commit changed from 54ccd828cb20b1254aeaf55bf7edab4a73f1032a to a501048a8480fd66300c37ff614969469509d189

Branch pushed to git repo; I updated commit sha1. New commits:

a501048Move category attribute lookup to CategoryObject.getattr_from_category()

comment:63 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:64 follow-up: Changed 3 years ago by vdelecroix

Do you know whether it is worth it to keep this __cached_method dictionary? I would be happy to see timings here. (though this is rather disjoint from the main preoccupation of this ticket)

comment:65 Changed 3 years ago by vdelecroix

In CategoryObject.__getattr__ it would better to do

try:
    return self.__cached_methods[name]
except KeyError:
    if self._category is None:
        cls = type
    else:
        cls = self._category.parent_class
    attr = getattr_from_other_class(self, cls, name)
    self.__cached_methods[name] = attr
    return attr

comment:66 Changed 3 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix

comment:67 in reply to: ↑ 64 Changed 3 years ago by jdemeyer

  • Reviewers Vincent Delecroix deleted

Replying to vdelecroix:

Do you know whether it is worth it to keep this __cached_method dictionary?

I would guess so since a lookup in a dictionary should be faster than whatever getattr_from_other_class is doing.

comment:68 Changed 3 years ago by jdemeyer

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

comment:69 Changed 3 years ago by git

  • Commit changed from a501048a8480fd66300c37ff614969469509d189 to 0fabb7a5dc50518946d1913488bf4a0444730c0f

Branch pushed to git repo; I updated commit sha1. New commits:

0fabb7aOptimize CategoryObject.getattr_from_category()

comment:70 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:71 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Got two failures with ptestlong

File "src/sage/combinat/root_system/integrable_representations.py", line 189, in sage.combinat.root_system.integrable_representations.IntegrableRepresentation.__init__
Failed example:
    TestSuite(V).run()
Expected nothing
Got:
   Failure in _test_additive_associativity:
   Traceback (most recent call last):
   ...
   AttributeError: 'IntegrableRepresentation' object has no attribute '_an_element_'
   ...

and similarly

**********************************************************************
File "src/sage/homology/hochschild_complex.py", line 98, in sage.homology.hochschild_complex.HochschildComplex.__init__
Failed example:
    TestSuite(H).run(skip="_test_category")
Expected nothing
Got:
    Failure in _test_additive_associativity:
    Traceback (most recent call last):
    ...
    AttributeError: 'HochschildComplex' object has no attribute '_an_element_'
    ...

comment:72 Changed 3 years ago by vdelecroix

And also not related to _an_element_

**********************************************************************
File "src/sage/combinat/root_system/integrable_representations.py", line 189, in sage.combinat.root_system.integrable_representations.IntegrableRepresentation.
__init__
Failed example:
    TestSuite(V).run()
Expected nothing
Got:
    ...
    Failure in _test_not_implemented_methods:
    Traceback (most recent call last):
    ...
    AssertionError: Not implemented method: __contains__
    ...

comment:73 Changed 3 years ago by jdemeyer

The last patchbot report was green, so this must be a recently-introduced problem.

comment:74 Changed 3 years ago by jdemeyer

Interestingly, these failures are for classes inheriting from CategoryObject but not Parent.

comment:75 Changed 3 years ago by jdemeyer

Those failures are true bugs in HochschildComplex and IntegrableRepresentation: they pretend to be in some category but do not actually implement everything needed to be in that category. This ticket causes the category tests to be run (which is good) but then the tests fail.

sage: SGA = SymmetricGroupAlgebra(QQ, 3)
sage: T = SGA.trivial_representation()
sage: H = SGA.hochschild_complex(T)
sage: H in CommutativeAdditiveGroups()
True
sage: H.zero()
...
TypeError: 'HochschildComplex' object is not callable

and

sage: Lambda = RootSystem(['A',3,1]).weight_lattice(extended=true).fundamental_weights()
sage: V = IntegrableRepresentation(Lambda[1]+Lambda[2]+Lambda[3])
sage: V in CommutativeAdditiveGroups()
True
sage: V.zero()
...
TypeError: 'IntegrableRepresentation' object is not callable

I think the right thing to do here is to mark those tests as # known bug.

Last edited 3 years ago by jdemeyer (previous) (diff)

comment:76 Changed 3 years ago by git

  • Commit changed from 0fabb7a5dc50518946d1913488bf4a0444730c0f to 74041f30d8de4c15055345f14340a4f443236ffa

Branch pushed to git repo; I updated commit sha1. New commits:

74041f3Mark broken testsuites as # known bug

comment:77 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

I created #21386 and #21387 for the broken testsuites.

comment:78 Changed 3 years ago by tscrim

I hope to fix both today.

comment:79 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to positive_review

good to go!

comment:80 Changed 3 years ago by vbraun

  • Dependencies changed from #21030 to #21030, #21409

This ticket seems to cause #21409

comment:81 Changed 3 years ago by vbraun

  • Branch changed from u/jdemeyer/optimize_method_lookup_from_the_categories_for_instances_of_cython_classes to 74041f30d8de4c15055345f14340a4f443236ffa
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.