#11900: Serious regression caused by #9138
----------------------------+-----------------------------------------------
Reporter: SimonKing | Owner: tbd
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.7.3
Component: performance | Keywords: categories regression
Work_issues: fix doctests | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies: #9138 #11911
----------------------------+-----------------------------------------------
Comment(by SimonKing):
Hi Nicolas,
Replying to [comment:52 nthiery]:
> Replying to [comment:50 SimonKing]:
> > and also it is faster to do `base_ring.is_ring()` if `is_ring` is a
parent method.
>
> I thought that you had optimized the `in` containment to make it as
> fast as a method call?
That's #10667 and needs much more work than this. My aim ''here'' is to
try and find a sufficiently good solution, so that #9138 can be rescued.
It could very well be that some of the changes (e.g. the use of `is_ring`)
will be reverted by #10667, and replaced with a better solution. But I
simply wouldn't like to wait another couple of months for #10667 to be
finished - it would be a shame to postpone #9138 (which happens to be a
dependency for #10667) such a long time.
> - X in Fields() would return whether X is already known to be a field.
>
> - X.is_field() would return whether X *is* a field, possibly
> launching a costly computation if needed, and possibly updating the
> category afterward
You are mistaken. Please look at the `__contains__` method of `Fields()`.
It dispatches to `sage.rings.fields.is_Field`, which dispatches to
`P.is_field()`.
Besides, in cases where this is a problem, there is a `proof=False` option
for is_field. I would accept to argue that `P in Fields()` should be
preserved, because of the difficulty of testing field-ness, and because it
is not tested so often.
But `P in Rings()` is tested often and is too slow. X in Rings()` takes an
awful lot of time and is one of the four main causes for the regression.
Bear in mind what `X in Rings()` involves:
* Calling `Rings()`, which will be faster by #11115 (cached methods), but
currently is not cheap. Thus, defining `_Rings = Rings()` once in a module
and then testing `X in _Rings` is already an improvement.
* Calling `C=X.category()` - that's relatively cheap.
* Calling `C.is_subcategory(_Rings)`, which is cached. However, in the
elliptic curves code, `C` takes around 1000 different values, thus,
caching really doesn't help here.
* is_subcategory involves constructing `C.all_super_categories()`. Again,
1000 times in the elliptic curves code. Note that this is because of
#9138: Before, C would constantly be `CommutativeRings()`, but with #9138,
it is `CommutativeAlgebras(F)` for different fields F.
Note that all_super_categories ''__alone__'' already takes 2 seconds in
the `%time L = EllipticCurve('960d1').prove_BSD()` example! That's a third
of the total computation time! The `P in C` idiom is to blame for a part
of it, and `Category.join` is to blame for the rest.
It is much faster to define and use a parent method `is_ring` in the
category of rings. Moreover, the base class `sage.rings.ring.Ring` also
has a method `is_ring`, which is even faster than a method inherited from
the category. Here is an example:
{{{
sage: R = Rings()
sage: MS = MatrixSpace(QQ,3)
sage: %timeit MS in R
625 loops, best of 3: 10.2 µs per loop
sage: %timeit MS.is_ring() # inherited from the category
625 loops, best of 3: 4.3 µs per loop
sage: P.<x,y> = PolynomialRing(GF(127))
sage: %timeit P.is_ring() # inherited from the base class
625 loops, best of 3: 392 ns per loop
}}}
On the long run, I would prefer to have fast containers (see #10667), so
that one can do
{{{
#!python
O = Rings().objects()
for P in {many different parents with different categories]:
if P in O:
...
}}}
But for now, I'd prefer a fast work-around.
'''__Summary__'''
The four main causes for the regression from #9138 are:
* `P in Rings()` is too slow (because it calls `is_subcategory`). #10667
will make it fast, on the long run, but for now it is easier and faster to
add a parent method `is_ring` that returns True for rings.
* `Category.join` also involves calling `is_subcategory` too often.
Fortunately, in many cases, the categories to be joined are known up to
the base ring. Thus, it is possible to write down `JoinCategory` directly.
* `C.is_subcategory(C2)` is too slow, since `C.all_super_categories()` is
too slow. I provide a faster (but equivalent) algorithm here.
* `C.parent_class` is too slow. In my not-yet-posted patch, I make it a
little faster by calling `dynamic_class_internal.f` directly, thus,
completely avoiding the `cached_function` overhead. `C.parent_class`
should only depend on the base ring when absolutely necessary, but that
will be dealt with on a different ticket.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11900#comment:53>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
