#13589: Controlling C3 to solve once for all the Method Resolution Order issues
for
category classes
----------------------------------------------------------+-----------------
Reporter: nthiery | Owner:
nthiery
Type: defect | Status:
needs_review
Priority: major | Milestone:
sage-5.10
Component: categories | Resolution:
Keywords: method resolution order, C3 | Work issues:
Report Upstream: N/A | Reviewers:
Simon King, Florent Hivert
Authors: Nicolas M. Thiéry | Merged in:
Dependencies: #13501, #12894, #12876, #11935, #12895 | Stopgaps:
----------------------------------------------------------+-----------------
Comment (by nthiery):
Replying to [comment:22 SimonKing]:
> Some random remarks:
>
> - Why is `Category._cmp_key` a cached method and not a lazy attribute?
> - Why is `CategoryWithParameters._cmp_key` a method and not a lazy
attribute or at least a cached method?
To be discussed. If I remember correctly, it's slightly easier to use
super in cached methods than attributes, but I guess both would work.
> - Why has this example
> {{{
> sage: Groups().example().algebra(ZZ).categories()
> ...
> }}}
> been completely removed from sage/categories/groups.py? Similarly
`sage: Modules(Integers(9)).all_super_categories()` from
sage/categories/modules.py etc.
Because they neither bring useful test or information, and
need to be updated whenever the category order changes which is a good
source of conflicts.
> - In the documentation of primer.py:
> {{{
> #!rst
> However this must be considered as an *implementation detail*: `C_1`
> and `C_2` are incomparable categories, then the order in which they
> appear must be mathematically irrelevant:
> }}}
> I guess there is "If" missing after the first colon.
> - In sage/misc/c3_controlled.pyx, line 123: Should be "classes that an
object inherits from.", not "classes that an object inherit from."
> - ... line 139, "However, this has several inconvenients:" I guess this
should be "However, this has several drawbacks" or "However, this is
inconvenient in several regards" or so.
Thanks, I'll fix that! Probably on Monday, together with the fix for
the failing long test.
> Do I understand correctly: As you outline in lines 148-166, the creation
of classes will become slower (`O(n^3)` instead of `O(n^2)` for getting
the MRO, etc) if one explicitly puts the desired MRO into a long list of
bases. This would certainly be a reason for an increased startup time and
other regressions. Therefore, in a first step, you compute ''short'' lists
of bases that ensure that the C3 algorithm still reconstruct the intended
MRO. However, is this additional step (namely: Computing lists of bases)
takes some time, not affecting the startup time?
Please read further :-) That would be O(n^3) if one was brute forcing
the complete mro in the list of bases. Luckily it's more clever than
that! New bases are only added when absolutely necessary; in fact, in
the current situation it turns out that no base is actually added even
for non trivial categories like Fields or GradedHopfAlgebrasWithBasis.
> I still have to read the actual code (and not just the documentation).
One question, though, which is in the spirit of #11935. In
sage.categories.category, you have
> {{{
> #!python
> (result, bases) = C3_sorted_merge([cat._all_super_categories
> for cat in
self._super_categories] +
> [self._super_categories],
> key = attrcall('_cmp_key'))
> self._super_categories_for_classes = bases
> return [self] + result
> }}}
> I guess in many cases the result will be the same up to the base rings.
Shouldn't we think of a way to avoid duplication of work? I could imagine
that here is the reason for the startup time regression.
This code is only called if all_super_categories is called. And by
#11935 this should happen only once for all base ring in the same
category. (unless one calls explicitly all_super_categories). I have
not kept the timings under hand, but I did not see a difference in our
usual elliptic curves benchmark.
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13589#comment:23>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
