Opened 8 years ago

Last modified 7 years ago

#11943 closed enhancement

The category graph should comply with Python's method resolution order — at Version 38

Reported by: SimonKing Owned by: nthiery
Priority: major Milestone: sage-5.1
Component: categories Keywords: category graph, method resolution order
Cc: hivert, mderickx Merged in:
Authors: Simon King Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11900 Stopgaps:

Description (last modified by SimonKing)

Let C be a category. C.all_super_categories() starts with C.super_categories() and finds all super categories inductively.

Unfortunately, the algorithm of C.all_super_categories() does not comply with the C3 algorithm, that is used by Python to determine the method resolution order for C.parent_class and C.element_class.

The aim of this ticket is to be more consistent. Eventually, for any category C (perhaps with modifications for hom categories), one should have

sage: C.parent_class.mro() == [X.parent_class for X in C.all_super_categories()] + [object]
True
sage: C.element_class.mro() == [X.element_class for X in C.all_super_categories()] + [object]
True

and that test should become part of the test suite.

At #11900, the implementation of all_super_categories() has been changed, so, work should rely on #11900.

Unfortunately, it seems that the C3 algorithm can not simply be imported from Python, even though Python uses it internally, namely in Objects/typeobject.c. Looking at the implementation, it requires that one gets a list of types, while we want to use it on a list of objects.

Therefore, we need to implement C3 from scratch. Implementing C3 is easy, but if it shall be fast, one needs to be careful.

In particular, one needs to be able to L.pop(0) quickly, where L is a list. Unfortunately, L.pop(0) is slow, even in Cython. I found that, if the lists are not too long, it is best to revert L and do L.pop() instead, which is optimized in Cython. See the discussion at sage-devel.

My plan is:

  • Provide the C3 algorithm in a new extension module sage.misc.c3
  • Use it to compute all_super_categories()
  • Add a test _test_category_graph, asserting that self.parent_class.mro() and self.all_super_categories() are compatible.

First tests indicate that the change of order on C.all_super_categories() is fine (sage does not crash, and most tests in sage.categories pass. However, one really needs to look at the performance.

Apply:

trac11943_mro_for_all_super_categories_lazy_hook.patch

Change History (38)

comment:1 follow-up: Changed 8 years ago by SimonKing

With the new test, I found a bug in algebra_ideals:

sage: C = AlgebraIdeals(FreeAlgebra(QQ,2,'a,b'))
sage: C.parent_class
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (396, 0))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/king/Seminar/<ipython console> in <module>()

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/lazy_attribute.pyc in __get__(self, a, cls)
    507         if a is None: # when doing cls.x for cls a class and x a lazy attribute
    508             return self
--> 509         result = self.f(a)
    510         if result is NotImplemented:
    511             # Workaround: we make sure that cls is the class

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/categories/category.pyc in parent_class(self)
    626         """
    627         return dynamic_class("%s.parent_class"%self.__class__.__name__,
--> 628                              tuple(cat.parent_class for cat in self.super_categories()),
    629                              self.ParentMethods,
    630                              reduction = (getattr, (self, "parent_class")))

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/cachefunc.pyc in __call__(self, *args, **kwds)
    553             return self.cache[k]
    554         except KeyError:
--> 555             w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
    556             self.cache[k] = w
    557             return w

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/cachefunc.pyc in _instance_call(self, inst, *args, **kwds)
    776 
    777         """
--> 778         return self._cachedfunc.f(inst, *args, **kwds)
    779 
    780     def _get_instance_cache(self, inst):

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/categories/algebra_ideals.pyc in super_categories(self)
     67             [Category of algebra modules over Univariate Polynomial Ring in x over Rational Field]
     68         """
     69         from algebra_modules import AlgebraModules
     70         R = self.algebra()
---> 71         return [AlgebraModules(R)]

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/classcall_metaclass.pyc in __call__(cls, *args, **options)
    256             return cls.__classcall_private__(cls, *args, **options)
    257         elif hasattr(cls, "__classcall__"):
--> 258             return cls.__classcall__(cls, *args, **options)
    259         else:
    260             return type.__call__(cls, *args, **options)

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/cachefunc.pyc in __call__(self, *args, **kwds)
    176             return self.cache[k]
    177         except KeyError:
--> 178             w = self.f(*args, **kwds)
    179             self.cache[k] = w
    180             return w

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/structure/unique_representation.pyc in __classcall__(cls, *args, **options)
    447             True
    448         """
--> 449         instance = type.__call__(cls, *args, **options)
    450         assert isinstance( instance, cls )
    451         if instance.__class__.__reduce__ == UniqueRepresentation.__reduce__:

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/categories/algebra_modules.pyc in __init__(self, A)
     53         from sage.categories.commutative_algebras import CommutativeAlgebras
     54         if not hasattr(A, "base_ring") or not A in CommutativeAlgebras(A.base_ring()):
---> 55             raise TypeError, "A (=%s) must be a commutative algebra"%A
     56         Category_module.__init__(self, A)
     57 

TypeError: A (=Free Algebra on 2 generators (a, b) over Rational Field) must be a commutative algebra

Thus, apparently, that category has never been used.

The problem is that the super categories of the category of algebra ideals should be the category of algebra modules. However, while the former accepts non-commutative algebras, the latter wants to see commutative algebras.

The clean way to proceed would be: Make algebra modules work over non-commutative rings. If that is too much of work, C.super_categories() should be [] if C is the category of algebra ideals over a non-commutative rings.

comment:2 follow-up: Changed 8 years ago by SimonKing

  • Authors set to Simon King
  • Dependencies set to #11900
  • Status changed from new to needs_review

Patch's up!

To my surprise, the change in the order of super categories was relatively harmless. In few cases, a test involving all_super_categories had to change.

I added a test _test_category_graph to the Test Suite of categories. By that test, I found one bug in algebra_ideals, which I fixed. Hom categories can not use the new test yet, since it tests the mro of the parent class against the list of parent classes of all super categories - which is fairly inconsistent for hom categories. That is already a "to do", and should be part of the next category overhaule.

Apart from these small changes, all doc tests passed! In particular, I did not need to change super_categories (except for algebra ideals): The current category graph seems to be consistent!!

That was the good news.

The bad news is that we have a regression in the computation of all_super_categories. With #11900, we have

sage: L = [Algebras(GF(p)) for p in prime_range(10000)]
sage: %time X = [C.all_super_categories() for C in L]
CPU times: user 0.74 s, sys: 0.01 s, total: 0.75 s
Wall time: 0.75 s

With the patches from here added, we only have

sage: L = [Algebras(GF(p)) for p in prime_range(10000)]
sage: %time X = [C.all_super_categories() for C in L]
CPU times: user 1.06 s, sys: 0.02 s, total: 1.07 s
Wall time: 1.08 s

I tried hard to make my C3 implementation as fast as possible in the range we need: few lists (say, 4) of moderate length (not more than 60).

I think the performance should be improved. But a review can already be started.

comment:3 in reply to: ↑ 1 Changed 8 years ago by nthiery

Replying to SimonKing:

With the new test, I found a bug in algebra_ideals: The problem is that the super categories of the category of algebra ideals should be the category of algebra modules. However, while the former accepts non-commutative algebras, the latter wants to see commutative algebras. The clean way to proceed would be: Make algebra modules work over non-commutative rings. If that is too much of work, C.super_categories() should be [] if C is the category of algebra ideals over a non-commutative rings.

+1. Actually my patch on #10963 is adding a TODO about it :-)

comment:4 in reply to: ↑ 2 Changed 8 years ago by nthiery

Replying to SimonKing:

To my surprise, the change in the order of super categories was relatively harmless. In few cases, a test involving all_super_categories had to change.

I am not so surprised, since most categories are actually used by some parent (which detects any incompatibility). But it's very nice to detect such incompatibilities earlier on and to catch them systematically in the TestSuite?!

Cheers,

Nicolas

comment:5 Changed 8 years ago by SimonKing

I tried to track down the regression of all_super_categories. Recall that my patch from #11900 did improve the implementation of all_super_categories, but did not change the algorithm.

With #11900, the main work is done in _all_super_categories_raw. With the patch from here, the work is done in c3_algorithm - and according to %prun, less time is spent in c3_algorithm than it was in _all_super_categories_raw. However, more time is spent in the expression

C.all_super_categories() for C in self.super_categories()

I guess I have to improve the implementation of the recursion.

comment:6 follow-up: Changed 8 years ago by SimonKing

PS: It also seems that much time is spent in super_categories(), which is a cached method. Probably it would be better to turn it into a lazy attribute (or have two lazy attributes, namely for the case proper=True and proper=False).

Namely, even though #11115 will almost totally reduce the overhead of calling a cached function, a lazy attribute will always be faster.

comment:7 in reply to: ↑ 6 Changed 8 years ago by SimonKing

Replying to SimonKing:

PS: It also seems that much time is spent in super_categories(), which is a cached method. Probably it would be better to turn it into a lazy attribute (or have two lazy attributes, namely for the case proper=True and proper=False).

Sorry, I meant: One lazy attribute C.super_categories, and two lazy attributes C.all_super_categories and C.all_super_categories_proper (super_categories() has no arguments).

comment:8 Changed 8 years ago by SimonKing

  • Description modified (diff)

I have created a more invasive patch: It turns C.super_categories() and C.all_super_categories(proper) into lazy attributes, and it uses the C3 algorithm in a more efficient way.

The two patches are alternative. Personally, I prefer the second patch. If the reviewer disagrees and suggests to use the first patch, I'd like to add one improvement to the first patch. If the reviewer agrees with me, then eventually either this patch or the patch from #11935 needs to be rebased.

I just tested that all doctests pass, with sage-4.7.2.alpha3+#11900+the second patch from here.

And here are some timings: With just #11900:

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage

real    0m18.089s
user    0m17.633s
sys     0m0.344s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage

real    0m5.578s
user    0m5.084s
sys     0m0.400s

and

sage: L = [Algebras(GF(p)) for p in prime_range(10000)]
sage: %time X = [C.all_super_categories() for C in L]
CPU times: user 0.72 s, sys: 0.01 s, total: 0.72 s
Wall time: 0.73 s

With #11900+the second patch from here:

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage

real    0m17.799s
user    0m17.333s
sys     0m0.384s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage

real    0m5.408s
user    0m4.956s
sys     0m0.376s

and

sage: L = [Algebras(GF(p)) for p in prime_range(10000)]
# all_super_categories is lazy now, we are not calling it
sage: %time X = [C.all_super_categories for C in L]
CPU times: user 0.54 s, sys: 0.00 s, total: 0.54 s
Wall time: 0.54 s

Note an additional doc test, demonstrating that the new version of all_super_categories can detect inconsistencies:

sage: class X(Category):
...    @lazy_attribute
...    def super_categories(self):
...        return [Objects()]
sage: class X(Category):
...    @lazy_attribute
...    def super_categories(self):
...        return [Objects()]
sage: class Y(Category):
...    @lazy_attribute
...    def super_categories(self):
...        return [Objects()]
sage: class A(Category):
...    @lazy_attribute
...    def super_categories(self):
...        return [X(),Y()]
sage: class B(Category):
...    @lazy_attribute
...    def super_categories(self):
...        return [Y(),X()]
sage: class Foo(Category):
...    @lazy_attribute
...    def super_categories(self):
...       return [A(),B()]
sage: F = Foo()

Python is not able to create a consistent mro for the parent class - and all_super_categories detects that inconsistency as well:

sage: F.parent_class
Traceback (most recent call last):
...
TypeError: Cannot create a consistent method resolution
order (MRO) for bases X.parent_class, Y.parent_class
sage: F.all_super_categories
Traceback (most recent call last):
...
ValueError: Can not merge the items Category of x, Category of y.

Of course, there still is the new consistency test for the category graph in the test suite.

So, it can really be reviewed now, and my suggestion is:

Apply trac11943_mro_for_all_super_categories_lazy.patch

comment:9 Changed 8 years ago by SimonKing

There was no reply on sage-combinat-devel and only little reply on sage-devel: The only reply was Jason Grout stating that the use of attributes is often more pythonic than the use of a method.

So, the idea to turn super_categories and all_super_categories into lazy attributes is supported.

comment:10 Changed 8 years ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues set to Preserve super_categories etc. as methods, but introduce a lazy attribute _super_categories

Maarten suggested the following:

What I think would be the best solution in this case would be is:

make lazy attributes

_super_categories and
_all_super_categories

Make the functions super_categories and all_super_categories say in the
documentation that developers shouldn't use these but that they should use
the lazy attributes.

I think that this would be a very good solution indeed.

comment:11 Changed 8 years ago by SimonKing

I think the following model is best for preserving backwards compatibility:

  • If one wants to provide the super categories of a category, one should implement a method super_categories() - this is what one would currently do.
  • There is a new lazy attribute _super_categories defined for the base class of categories. That lazy attribute calls the method super_categories(). Of course, calling the method happens only once, so that the speed is acceptable.
  • In all applications, the method call super_categories() shall be replaced by getting the attribute _super_categories. That is explained in a note to the developers in the documentation of super_categories.
  • There is a lazy attribute _all_super_categories and _all_super_categories_proper, and there is still a method all_super_categories(proper=False). The method returns the appropriate lazy attribute, and the documentation of the method states that one should better use the lazy attributes.

comment:12 Changed 8 years ago by SimonKing

  • Cc hivert mderickx added
  • Status changed from needs_work to needs_review
  • Work issues Preserve super_categories etc. as methods, but introduce a lazy attribute _super_categories deleted

I have changed my patch according to what I learnt from the discussion on sage-devel. Namely:

  • I preserved the old methods super_categories and all_super_categories, so that the users can still work with them and can read their documentation.
  • In particular, if one wants to define a new category, one would still define a method (no need for a cached method) called super_categories that returns the immediate super categories. However, the documentation now also states that internally (i.e., for development), the new lazy attributes explained below should be used.
  • The patch introduces three lazy attributes _super_categories, _all_super_categories and _all_super_categories_proper that carry the lists of (immediate or all) super categories. If one asks for the super categories in code, the fastest way is to request these lazy attributes, not calling the old methods.

Anyway, why do I see a need to make things faster? Recall that the purpose of this ticket is to order the list of all super categories according to Python's method resolution order, i.e., the C3 algorithm. I did my very best to implement the C3 algorithm as fast as possible. However:

  • When I keep super_categories() what they are, then even my best attempt to implement all_super_categories based on C3 resulted in a mild regression.
  • When I keep super_categories() what they are (namely cached methods) and use #11115, then there is neither a regression nor a speed-up.
  • When I replace super_categories() by _super_categories (a lazy attribute), then I am getting a speed-up, even without #11115.

Here are the data. I've run sage -t devel/sage/sage/schemes/ and found these total running times:

  • 620.7 seconds with sage-4.7.3.alpha3
  • 600.1 seconds with sage-4.7.3.alpha3 and #11943 (plus dependencies)

That's not much (3.3% speedup), but certainly better than a regression.

comment:13 Changed 8 years ago by SimonKing

I forgot the patch bot:

Apply trac11943_mro_for_all_super_categories_lazy.patch

comment:14 follow-up: Changed 8 years ago by SimonKing

  • Status changed from needs_review to needs_work

There is a new suggestion, also based on the sage-devel thread:

If we want to test whether a category C is a super category of a category D, then we currently try to find C in the list of all super categories. But it is much faster to search it in a frozen set of super categories.

So, I suggest to use a lazy attribute _set_of_super_categories, providing the frozen set. It will be used in is_subcategory. Of course, the list of super categories should still be available, and its order should comply with Python's mro, according to the subject of this ticket.

Since #11115 is merged into sage-4.7.3.alpha1, I wonder whether it is still necessary to have the list of all super categories as a lazy attribute, or whether a cached method is fast enough. I'll need some tests.

However, I think it is a good idea to have a lazy attribute _super_categories. In that way, we have the speed even if the user does not use @cached_method when (s)he implements the method super_categories(). "Needs work", until I have sorted it out.

comment:15 follow-up: Changed 8 years ago by SimonKing

I found another detail that may fit here: Category.is_subcategory contains the lines

        assert(isinstance(c, Category))
        if isinstance(self, JoinCategory):
            for cat in self._super_categories:
                if cat.is_subcategory(c):
                    return True
            return False

First, I don't see why it should be needed to assert that c is a Category. It seems like a waste of time to me.

Secondly, the loop does nothing more than to test the cat is in the set of super categories of self. So, it can be safely erased. And it is a lot faster. For example:

With my current patch, we have

sage: P.<x,y> = QQ[]
sage: C = CommutativeRings()
sage: P.category()
Join of Category of unique factorization domains and Category of commutative algebras over Rational Field
sage: P in C
True
sage: %timeit P in C
625 loops, best of 3: 12.1 µs per loop

With my patch after deletion of the lines criticised above, we have

sage: P.<x,y> = QQ[]
sage: C = CommutativeRings()
sage: P.category()
Join of Category of unique factorization domains and Category of commutative algebras over Rational Field
sage: P in C
True
sage: %timeit P in C
625 loops, best of 3: 6.39 µs per loop

So, my next patch version will remove these lines, provided that doc tests pass.

comment:16 Changed 8 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:17 in reply to: ↑ 14 Changed 8 years ago by nthiery

  • Milestone set to sage-4.8

Replying to SimonKing:

So, I suggest to use a lazy attribute _set_of_super_categories, providing the frozen set. It will be used in is_subcategory. Of course, the list of super categories should still be available, and its order should comply with Python's mro, according to the subject of this ticket.

+1 (obviously :-)), though I kind of like better _all_super_categories_as_set to insist on the fact that it is very close to all_super_categories.

Since #11115 is merged into sage-4.7.3.alpha1, I wonder whether it is still necessary to have the list of all super categories as a lazy attribute, or whether a cached method is fast enough. I'll need some tests.

+1 on getting rid of this lazy attribute, unless there is a very clearly defined use case where speed is essential.

However, I think it is a good idea to have a lazy attribute _super_categories. In that way, we have the speed even if the user does not use @cached_method when (s)he implements the method super_categories().

+1

Cheers,

Nicolas

comment:18 in reply to: ↑ 15 ; follow-up: Changed 8 years ago by nthiery

Replying to SimonKing:

I found another detail that may fit here: Category.is_subcategory contains the lines

        assert(isinstance(c, Category))
        if isinstance(self, JoinCategory):
            for cat in self._super_categories:
                if cat.is_subcategory(c):
                    return True
            return False

First, I don't see why it should be needed to assert that c is a Category. It seems like a waste of time to me.

As for any reasonable programming language, Python allows to completely disable assertion tests, to encourage the programmer to put more safety guards and write programmatically his preconditions/assertions/..., knowing that in production there won't be any penalty. Alas, this can't be done on the fly like in MuPAD for switching between debugging and full speed computation modes inside a given session (a feature I loved). Still this can be achieved in principle on a new session by passing -O to the Python interpreter. Maybe we should add this option to the Sage script itself.

In that particular case, I guess I once met a bug where something was passed to is_subcategory which was not a category, so I felt safer with the assertion test.

Secondly, the loop does nothing more than to test the cat is in the set of super categories of self. So, it can be safely erased. And it is a lot faster. ... So, my next patch version will remove these lines, provided that doc tests pass.

I don't remember anymore why I did a special case for join categories, so +1.

Cheers,

Nicolas

comment:19 in reply to: ↑ 18 ; follow-up: Changed 8 years ago by SimonKing

  • Status changed from needs_work to needs_review

Dear Nicolas,

Replying to nthiery:

In that particular case, I guess I once met a bug where something was passed to is_subcategory which was not a category, so I felt safer with the assertion test.

But I think, in this particular case, nothing nasty can happen.

Ultimately, it is tested whether the argument c belongs to the list of all super categories of self. Hence, unexpected things can only happen if c is not a category but is equal to a category, or if self.super_categories() contains something that is not a category.

So, my next patch version will remove these lines, provided that doc tests pass.

I don't remember anymore why I did a special case for join categories, so +1.

I have just attached a new version of my patch. I used several techniques to speed up is_subcategory.

In particular, I rely on the hypothesis that if a category C1 has a base (ring) and is super-category of C2, then C2 must have the same base (ring). Hence, if the base rings differ or C2 has no base ring then we can very quickly conclude that C1 is not a super-categoriy of C2.

This turns out to be very helpful in elliptic curve computations. Namely, it often suffices to study the base rings, so that it is not needed to construct the list of all super categories.

By consequence, I needed to introduce a base() method for various settings. For example, tensor products preserve the base. And for join categories, I argue: If C = JoinCategory((C1,C2,...)) then C.base() should be the first answer that one obtains by walking through the list C1.base(), C2.base(),....

I think this makes sense in the intended application: By #9138, polynomial rings over F belong to a join category of a base-free category (unique factorization domains) and a category with base F (F-algebras).

The code of is_subcategory is now (with some comments added):

# No cached method, currently
    def is_subcategory(self, c):
        if c is self:  # short path for a common case
            return True
        if isinstance(c, JoinCategory):
            return all(self.is_subcategory(x) for x in c._super_categories)
        try:
            # If the lazy attribute has already been computed, then we do not
            # need to bother about the categories having bases.
            # Here, the trick is that we look in self.__dict__, so that we do
            # not trigger computation of self._set_of_super_categories, if it has
            # not been done before.
            return c in self.__dict__['_set_of_super_categories']
        except KeyError:
            pass
        # In elliptic curves, one often has categories over different base rings.
        # Thus, as a short-path, we compare the base rings first, before we try
        # to compute the set of all super-categories.
        try:
            cbase = c.base()
        except (AttributeError, TypeError, NotImplementedError):
            cbase = None
        if cbase is not None:
            try:
                selfbase = self.base()
            except (AttributeError, TypeError, NotImplementedError):
                selfbase = None
            if selfbase is not cbase:
                return False
        # Now, the only remaining thing to do is to look at the super categories.
        # Looking it up in a (frozen) set is quickest:
        return c in self._set_of_super_categories

With the new patch, all long doctests pass - needs review!

I am now attending a lecture and will try to provide some timings afterwards.

Apply trac11943_mro_for_all_super_categories_lazy.patch

comment:20 in reply to: ↑ 19 Changed 8 years ago by SimonKing

  • Status changed from needs_review to needs_work

Replying to SimonKing:

Replying to nthiery: By consequence, I needed to introduce a base() method for various settings. For example, tensor products preserve the base. And for join categories, I argue: If C = JoinCategory((C1,C2,...)) then C.base() should be the first answer that one obtains by walking through the list C1.base(), C2.base(),....

I think that's a bad idea, after all. For example, one would have

sage: C = Category.join([Algebras(GF(5)),Modules(ZZ)])
sage: C.is_subcategory(Modules(ZZ))
False

But I have a suggestion:

base() provides a speed-up in an important application: Polynomial rings over F. In that situation, one has a join category that clearly should have a base, namely F. So, perhaps one should add an optional parameter base=None to the construction of a join category.

So, one could have something like

sage: P.<x,y> = QQ[]
sage: P.category()
Join over Rational Field of Category of unique factorization domains and Category of commutative algebras over Rational Field
sage: P.category().base()
Rational Field

and at the same time

sage: C = Category.join([Algebras(GF(5)),Modules(ZZ)])
sage: print C.base()
None

What do you think?

comment:21 follow-up: Changed 8 years ago by mderickx

Where can I find the specific elliptic curve code you mention?

comment:22 in reply to: ↑ 21 ; follow-up: Changed 8 years ago by SimonKing

Replying to mderickx:

Where can I find the specific elliptic curve code you mention?

I was referring to the things that were discussed on #11900. That ticket is about a serious speed regression in elliptic curves caused by #9138. And analysing it, using prun and so on, it turned out that really a lot of time has been spent on computing the list of all super categories. The problem is that caching the list of super categories does not really help, since one has many different categories (of algebras, for example) over different base fields.

But now that you mention it: It could be that the remark in the code above

        # In elliptic curves, one often has categories over different base rings.
        # Thus, as a short-path, we compare the base rings first, before we try
        # to compute the set of all super-categories.

is misleading.

The code is supposed to recognise very quickly that a category with base is not contained in a category with a different base. I am afraid I can not show you the original example that made me suggest this bit of code. However, here are some examples showing that it helps.

With the base test (each example being in a new session):

sage: L = [GF(p)['x','y'] for p in prime_range(5000)]
sage: C = CommutativeRings()
# here the test is not used - this is to show that there is almost no regression
sage: %time [X in C for X in L] 
CPU times: user 0.29 s, sys: 0.00 s, total: 0.29 s
Wall time: 0.29 s
sage: L = [GF(p)['x','y'] for p in prime_range(5000)]
sage: D = Modules(ZZ)
sage: %time [X in D for X in L]
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.06 s

With the base test commented out:

sage: L = [GF(p)['x','y'] for p in prime_range(5000)]
sage: C = CommutativeRings()
sage: %time [X in C for X in L]
CPU times: user 0.26 s, sys: 0.00 s, total: 0.26 s
Wall time: 0.27 s
sage: L = [GF(p)['x','y'] for p in prime_range(5000)]
sage: D = Modules(ZZ)
sage: %time [X in D for X in L]
CPU times: user 0.28 s, sys: 0.00 s, total: 0.28 s
Wall time: 0.28 s

So, if base rings are involved then the test is much faster, and if no base rings are involved, the test is not much slower.

comment:23 in reply to: ↑ 22 Changed 8 years ago by SimonKing

Replying to SimonKing:

I am afraid I can not show you the original example that made me suggest this bit of code.

Now I remember the story.

By #9138, we have that the category of a polynomial ring is the join of a category of algebras with a base-free algebra, for example:

sage: P.<x,y> = ZZ[]
sage: P.category()
Join of Category of unique factorization domains and Category of commutative algebras over Integer Ring

Originally, that category has been computed via

sage: Category.join([UniqueFactorizationDomains(), CommutativeAlgebras(ZZ)])
Join of Category of unique factorization domains and Category of commutative algebras over Integer Ring

But that turned out to be a problem for elliptic curve computations:

  • In the benchmarks discussed on #11900, polynomial rings over many different finite fields are constructed.
  • For each of them, Category.join(...) was called.
  • Internally, Category.join(...) tests whether the categories to be joined are sub-categories of each other.
  • Hence, for each prime p, one had to compute CommutativeAlgebras(GF(p)).all_super_categories(), in order to test whether it is a sub-category of UniqueFactorizationDomains().

In fact, that was the main reason for the speed regression from #9138.

For fixing it, I had (at least) the following two ideas:

  1. Do not call Category.join(...), but construct JoinCategory(...) directly. Advantage: JoinCategory.__init__ does not test for sub-categories. So, no time is wasted.
  2. When testing UniqueFactorizationDomains().is_subcategory(CommutativeAlgebras(F)), one does not need to waste time by computing CommutativeAlgebras(F).all_super_categories(). The fact that UniqueFactorizationDomains() has no base ring suffices to recognise that it is not a sub-category.

In #11900, I went for the first approach. Here, I'd like to also add the second approach. It is not needed for fixing an existing regression, but I still think it is a good idea.

Here is an example for what I have explained:

We start with a list of categories of algebras over different finite fields. The aim is to compute the join with the category of unique factorization domains.

sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(5000)]
sage: C = UniqueFactorizationDomains()

With sage-4.6.2 (as an old reference):

sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.65 s, sys: 0.00 s, total: 0.65 s
Wall time: 0.65 s

With sage-4.7.2.alpha3 (hence, with #9138, but without #11900):

sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(5000)]
sage: C = UniqueFactorizationDomains()
sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.76 s, sys: 0.00 s, total: 0.77 s
Wall time: 0.77 s

With unpatched sage-4.7.3.alpha1 (which contains #11900):

sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.59 s, sys: 0.01 s, total: 0.60 s
Wall time: 0.61 s

With sage-4.7.3.alpha1 plus the patch from here (thus, using base rings):

sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.39 s, sys: 0.00 s, total: 0.39 s
Wall time: 0.39 s

Believe it or not, but that kind of differences had a noticeable effect, as I found out while working on #11900.

Conclusion

I still believe that one should exploit the base of a category for short-cuts in subcategory tests.

comment:24 Changed 8 years ago by SimonKing

  • Status changed from needs_work to needs_review

I have updated my patch. As I have announced, I add the possibility to define a join category with a base. It is used for polynomial rings, who clearly should belong to a category with a base, but also to a join category.

comment:25 follow-up: Changed 8 years ago by mderickx

I think base has nothing to do with join logically so I think it is a bad idea to only add it to joins of categories for this shortcut purpose. Also I don't like your 'base' concept since it is just a speedup thing right now and doesn't relate to something wich has a real mathematical meaning. The second thing is that I don't like the way how the code is organized right now in is_subclass. The reason for this is that this way of making shortcuts scales very bad and that other people thinking of other specific shortcuts to speed stuff up might make this a very cluttered method very soon. I'd say its cluttered already since this generic method already has special code for categories witch are a join of something and special code for the case that self and other have a base method. I think it is better to provide a truly generic implementation in combination with something like a subclasshook as python has for Abstract Base Classes http://docs.python.org/library/abc.html#abc.ABCMeta.__subclasshook . In this way you we can have the JoinCategory? specific code where it belongs and you can have your "base" optimisation in the place where it belongs, and other people can add their own shortcuts as they please.

comment:26 Changed 8 years ago by mderickx

  • Status changed from needs_review to needs_work

something went wrong with the previous link cause of the wiki formatting it should be this link

comment:27 in reply to: ↑ 25 ; follow-up: Changed 8 years ago by SimonKing

Replying to mderickx:

I think base has nothing to do with join logically

I think it does, to some extent. If C is a category with a base B, then all its objects are supposed to have this base B as well. If you form a join J of C with another category, then all objects of J are also objects of C and thus have the base B.

It only starts to lack logic if you join categories with distinct bases.

But if you join a list of categories such that at least one of them has base B and all other categories on the list either have no base at all or have the base B as well, then I think it is alright to say that the join has base B.

The second thing is that I don't like the way how the code is organized right now in is_subclass. ... I think it is better to provide a truly generic implementation in combination with something like a __subclasshook__

One could argue that super_categories() alreay plays the role of __subclasshook__: It determines how different categories are contained in one another, and is used in a generic method Category.is_subcategory.

But I agree that it is conceivable that JoinCategory or Category_over_base could benefit from using a specialised method for detecting subcategories.

comment:28 follow-up: Changed 8 years ago by mderickx

No, super_categories() plays the exact opposite role of __subclashook__ . The subclass hook allows you to define what you consider as subclass of self and not what you consider a super class. What you claim is sort of saying that class inheritance plays the same role as subclasshook!

comment:29 in reply to: ↑ 27 Changed 8 years ago by mderickx

Maybe my real problem is with the way how you implement the base logic. I think that asuming that if two categories have a different base then they cannot be sub categories of each other is way to strict, this is not an interface wich I like to program to. And that by your current implementation you add way to much specific code to the general parts of the category framework that will not nicely generalize to more situations and don't fit nicely with the mathematical concept of base.

comment:30 in reply to: ↑ 28 Changed 8 years ago by SimonKing

Replying to mderickx:

No, super_categories() plays the exact opposite role of __subclashook__ . The subclass hook allows you to define what you consider as subclass of self and not what you consider a super class.

Yes, you are right! Even though a while ago I did some experiments with the ABC module, I forgot that one is registering sub-classes, not super-classes. Sorry.

Let me see. When we do A.is_subcategory(B) then with or without my patch we make a special case when B is a join category. With my patch, we also make a special case when B has a base - and actually what we really want is a special case for Category_over_base (recall the original use case, where A is the category of unique factorization domains and B is a category of algebras).

So, it seems like a good idea that both JoinCategory and Category_over_base and perhaps also TensorProductsCategory get a method subcategory_hook, and that Category.is_subcategory then looks as follows:

def is_subcategory(self, C):
    try:
        return C.subcategory_hook(self)
    except AttributeError:
        return C in self._set_of_super_categories

Of course, one should add a comment about the new "magical" method into the docs.

Is that what you suggested?

comment:31 Changed 8 years ago by mderickx

That is indeed my suggestion. But my specific implementation would be:

def is_subcategory(self, C): 
   hook_result = C.subcategory_hook(self)
   if hook_result is not NotImplemented:
       return hook_result
   return C in self._set_of_super_categories

So that it is more similar to the __subclasshook__ that python provides and your shortcut can just return NotImplemented? to signify that the shortcut didn't work (just like you can do with the subclasshook). And make a default implementation in Category that just returns NotImplemented?. The new magical method should indeed be documented.

comment:32 Changed 8 years ago by mderickx

and maybe it should be _subcategory_hook_ since I consider it more of a developer thing then an enduser.

comment:33 Changed 8 years ago by SimonKing

Now I wonder how we should proceed. Namely, I introduced the special case for categories with base not here, but in #11900.

I would argue as follows: #11900 is explicitly about speed. It provides speed. Hence, let it stay as it is.

The ticket here is more about structure. Hence, part of it should be to fix here my messy code from #11900.

comment:34 Changed 8 years ago by SimonKing

I am now rewriting it, and first tests seem to indicate that a cleaner implementation of is_subcategory is faster than the current mess. So, thank you for your suggestion, Maarten!

comment:35 Changed 8 years ago by mderickx

No problem :). I think you deserve way more credit, considering the huge amount of work you have done to make the category framework better lately.

comment:36 Changed 8 years ago by SimonKing

  • Work issues set to use a "_subcategory_hook_" and document it

I will add documentation to sage.categories.primer. The section in the primer on "how to implement a new category" is rather short anyway. It even does not explain that one should provide a method super_categories (it only tells that the order of super-categories should follow certain rules), and it does not mention ParentMethods and ElementMethods at all. I'll add that, plus some words on the new _subcategory_hook_.

comment:37 Changed 8 years ago by SimonKing

  • Status changed from needs_work to needs_review
  • Work issues use a "_subcategory_hook_" and document it deleted

I have added Maarten's idea of a _subcategory_hook_ and documented it. The subcategory hook is used for Category_over_base (hence, it is not needed to check for the existence of a base() attribute).

Moreover, in order to keep the generic implementation of is_subcategory clean, I provided JoinCategory with a specialised is_subcategory.

The documentation looks fine to me, and all tests pass. Needs review!

comment:38 Changed 8 years ago by SimonKing

  • Description modified (diff)

I forgot to inform the patch bot:

Apply trac11943_mro_for_all_super_categories_lazy_hook.patch

Note: See TracTickets for help on using tickets.