Opened 10 years ago
Closed 10 years ago
#10496 closed defect (fixed)
The default call method of maps does not do as promised by the documentation
Reported by: | SimonKing | Owned by: | robertwb |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.2 |
Component: | coercion | Keywords: | generic call map |
Cc: | Merged in: | sage-4.6.2.alpha1 | |
Authors: | Simon King | Reviewers: | David Roe |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The documentation of sage.categories.map.Map.__call__
states:
- If ``x`` can be coerced into the domain of ``self``, then the method ``_call_`` (single underscore) is called after coercion. - Otherwise, it is tried to call the method ``pushout`` to ``x`` (which may be provided in subclasses); in that way, ``self`` could be applied to objects like ideals.
However, in the code, we had
if not PY_TYPE_CHECK(x, Element): return self._call_(x) elif (<Element>x)._parent is not self._domain: try: x = self._domain(x) except TypeError: try: return self.pushforward(x) except (TypeError, NotImplementedError): raise ...
Hence, there is a typo in the documentation (it is pushforward, not pushout):
- If the argument is no element, one should expect that
pushforward
rather than_call_
is called. This is a problem if the argument happens to be a sub-module. Sub-modules are no elements (this is incontrast to ideals). Hence, currently, module morphisms have to implement a custom__call__
method.
- In contrast to the statement of the documentation, the code is only about conversion, but not about coercion. I think this is a problem, as in the following example. There is no coercion from the abstract number field to the embedded number field, but no error is raised when calling the coerce embedding of the embedded field with an element of the abstract field:
sage: K.<a>=NumberField(x^2-3,embedding=1) sage: L.<b>=NumberField(x^2-3) sage: K.has_coerce_map_from(L) False sage: K.coerce_embedding()(b) 1.732050807568878?
- I was told that in the
_call_
(single underscore) and_call_with_args
methods one can assume that the argument belongs to the domain of the map. This is, however, not the case, since an argument that is not an element (like a python int, for example!) will not be converted into the domain before passing it to_call_
.
I propose the following:
- If
parent(x)
does not coerce into the map's domain,pushforward
is called onx
together with the additional arguments. If it is not implemented or produces aTypeError
, proceed with the next step. - Try to convert
x
into the domain; this is now either a coercion, or it is a back-up solution for the failing pushfoward. If the conversion fails, raise an error that mentions the pushforward method. - Call
_call_
resp._call_with_args
.
There is a new doc test, demonstrating _call_
, _call_with_args
and pushforward
. Apart from that, only small changes were needed in the doctests: Some error messages have changed.
I have no idea about the proper component. I hope "coercion" is fine.
Attachments (1)
Change History (12)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 10 years ago by
- Reviewers set to David Roe
- Status changed from needs_review to needs_work
comment:3 in reply to: ↑ 2 Changed 10 years ago by
Replying to roed:
I think you need to add some fast pathways for common cases, such as
x
actually lying in the domain.
Right, I'll do so. Note that I use parent_c
(copied from sage.structure.parent
) in order to speed things up.
What common cases, apart from parent_c(x) is self._domain
, do you have in mind?
Similarly, use
PY_TYPE_CHECK
in cython files, rather thanisinstance
.
My patch introduces only one "isinstance", namely in the call method of Set_Python_class
. The updated patch (hopefully being submitted in an hour or so) will use PY_TYPE_CHECK
instead.
A propos: I was not aware of that Cython alternative to is_instance
. Can you point me to a documentation of these and similar PY_...
Cython functions?
I also found another way to speed the generic call method up: The current implementation does
if len(args) == 0 and len(kwds) == 0: return self._call_(x)
Using timeit", I found that
if not(args) and not(kwds)` would be much faster:
sage: args=tuple(ZZ.random_element() for i in range(3)) sage: kwds=dict((i,ZZ.random_element()) for i in range(3)) sage: args0=() sage: kwds0={} sage: timeit("if len(args)==0 and len(kwds)==0: a=2") 625 loops, best of 3: 3.37 µs per loop sage: timeit("if len(args0)==0 and len(kwds)==0: a=2") 625 loops, best of 3: 6.76 µs per loop sage: timeit("if len(args0)==0 and len(kwds0)==0: a=2") 625 loops, best of 3: 7.21 µs per loop sage: timeit("if not args and not kwds: a=2") 625 loops, best of 3: 129 ns per loop sage: timeit("if not args0 and not kwds: a=2") 625 loops, best of 3: 275 ns per loop sage: timeit("if not args0 and not kwds0: a=2") 625 loops, best of 3: 597 ns per loop
So, I'll change the patch accordingly.
comment:4 Changed 10 years ago by
- Status changed from needs_work to needs_review
I updated my patch. Here are some timings for different situations.
With the patch:
sage: R.<x,y> = QQ[]; phi=R.hom([y,x]) # Element in domain sage: timeit("a=phi(y)") 625 loops, best of 3: 32.3 µs per loop # Element coerces into domain sage: timeit("a=phi(5)") 625 loops, best of 3: 51.3 µs per loop # non-Element that converts into domain sage: D={(0, 2): -1, (0, 0): -1, (1, 1): 7, (2, 0): 1/3} sage: phi(D) -x^2 + 7*x*y + 1/3*y^2 - 1 sage: timeit("a=phi(D)") 625 loops, best of 3: 119 µs per loop # use pushforward sage: I = R*[x^2*y^4-2*y^2, 3*x*y-y^3] sage: phi(I) Ideal (x^4*y^2 - 2*x^2, -x^3 + 3*x*y) of Multivariate Polynomial Ring in x, y over Rational Field sage: timeit("a=phi(I)") 625 loops, best of 3: 164 µs per loop
The same examples without my patch:
sage: R.<x,y> = QQ[]; phi=R.hom([y,x]) sage: timeit("a=phi(y)") 625 loops, best of 3: 32.3 µs per loop sage: timeit("a=phi(5)") 625 loops, best of 3: 37.1 µs per loop sage: D={(0, 2): -1, (0, 0): -1, (1, 1): 7, (2, 0): 1/3} sage: phi(D) --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) /home/king/SAGE/work/modules/<ipython console> in <module>() /mnt/local/king/SAGE/sage-4.6/local/lib/python2.6/site-packages/sage/categories/map.so in sage.categories.map.Map.__call__ (sage/categories/map.c:3145)() /mnt/local/king/SAGE/sage-4.6/local/lib/python2.6/site-packages/sage/rings/morphism.so in sage.rings.morphism.RingHomomorphism_im_gens._call_ (sage/rings/morphism.c:5761)() AttributeError: 'dict' object has no attribute '_im_gens_' sage: I = R*[x^2*y^4-2*y^2, 3*x*y-y^3] sage: phi(I) Ideal (x^4*y^2 - 2*x^2, -x^3 + 3*x*y) of Multivariate Polynomial Ring in x, y over Rational Field sage: timeit("a=phi(I)") 625 loops, best of 3: 492 µs per loop
Hence:
- If the argument has the right parent, it is as quick as before.
- If the argument coerces into the domain, it is slower. That is no surprise, because "not doing coercion" is certainly faster than "doing coercion", but "not doing coercion" is a bug IMO.
- If the argument is not an element and is not dealt with by pushforward but converts into the domain, my patch fixes a bug (it is now added as doctest).
- Calling pushforward works a lot quicker with my patch.
So, I do think that overall it is a progress. I am now starting doctests, but I think it is ready for review again.
comment:5 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues set to speed things up
I think there is yet another way to speed things slightly up.
If there is coercion then there is a coerce map. Hence, rather than testing "self._domain.has_coerce_map_from(P)", one could directly request "caller=self._domain.coerce_map_from(P)", and then do "caller(x)" if it is not None. That should be faster than doing "self._domain(x)", because the call method of "self._domain" would request a coerce map as well!
I'll test a bit later. So, it will be "needs work" for two hours or so.
Changed 10 years ago by
comment:6 Changed 10 years ago by
- Status changed from needs_work to needs_review
Here are the same tests again, with the updated patch:
sage: R.<x,y> = QQ[]; phi=R.hom([y,x]) sage: timeit("a=phi(y)") 625 loops, best of 3: 33 µs per loop sage: timeit("a=phi(5)") 625 loops, best of 3: 39.2 µs per loop sage: D={(0, 2): -1, (0, 0): -1, (1, 1): 7, (2, 0): 1/3} sage: phi(D) -x^2 + 7*x*y + 1/3*y^2 - 1 sage: timeit("a=phi(D)") 625 loops, best of 3: 121 µs per loop sage: I = R*[x^2*y^4-2*y^2, 3*x*y-y^3] sage: phi(I) Ideal (x^4*y^2 - 2*x^2, -x^3 + 3*x*y) of Multivariate Polynomial Ring in x, y over Rational Field sage: timeit("a=phi(I)") 625 loops, best of 3: 163 µs per loop
I think that are acceptable timings: No significant slowdown, but a significant speedup in one case, and some bug fixes. Back to "needs review", modulo passing doctests...
comment:7 Changed 10 years ago by
Doctests do pass for me.
comment:8 Changed 10 years ago by
Looks good in general. I'm traveling today, but once I have a bit of time I'll take a look at your changes.
comment:9 Changed 10 years ago by
- Status changed from needs_review to positive_review
Looks good to me. You asked about documentation for PY_TYPE_CHECK earlier; I'm not sure where to find documentation, but the functions are included in sage/ext/stdsage.pxi
and you can find a list of them there. The other files in that directory are also worth looking at, especially if you're dealing with python objects.
Anyway, positive review.
comment:10 Changed 10 years ago by
- Work issues speed things up deleted
comment:11 Changed 10 years ago by
- Merged in set to sage-4.6.2.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
I approve of the design and goals, but I'm worried about the implementation speed. The current implementation does not introduce much overhead over
_call_
, butare both pretty costly calls. I think you need to add some fast pathways for common cases, such as
x
actually lying in the domain.Similarly, use
PY_TYPE_CHECK
in cython files, rather thanisinstance
.