Changes between Initial Version and Version 8 of Ticket #11943


Ignore:
Timestamp:
10/23/11 21:48:56 (7 years ago)
Author:
SimonKing
Comment:

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

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #11943

    • Property Status changed from new to needs_review
    • Property Dependencies changed from to #11900
    • Property Authors changed from to Simon King
  • Ticket #11943 – Description

    initial v8  
    2727
    2828First 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.
     29
     30Apply:
     31
     32 [attachment:trac11943_mro_for_all_super_categories_lazy.patch]