#12969 closed defect (fixed)
Coercion failures in symmetric functions
Reported by: | aschilling | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.3 |
Component: | coercion | Keywords: | symmetric functions, coercion |
Cc: | sage-combinat, saliola, zabrocki | Merged in: | sage-5.3.beta0 |
Authors: | Simon King | Reviewers: | Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The following code triggers a coercion failure in the symmetric function code
sage: H = MacdonaldPolynomialsH(QQ) sage: P = MacdonaldPolynomialsP(QQ) sage: m = SFAMonomial(P.base_ring()) sage: Ht = MacdonaldPolynomialsHt(QQ) sage: m(P.one()) m[] sage: Ht(P.one())
The coercion path does exist, however!
This can also be checked with the new syntax using the patches in #5457 as follows:
sage: R = QQ['q,t'].fraction_field() sage: Sym = sage.combinat.sf.sf.SymmetricFunctions(R) sage: H = Sym.macdonald().H(); sage: P = Sym.macdonald().P(); sage: m = Sym.monomial(); sage: Ht = Sym.macdonald().Ht(); sage: m(P.one()) sage: Ht(P.one())
The bug is in the coercion system. Sage does not find a path from P to Ht, whereas there definitely is one:
def coercion_graph(self, G = None): if G is None: G = DiGraph() if self not in G.vertices(): G.add_vertex(self) for h in self._introspect_coerce()['_coerce_from_list']: coercion_graph(h.domain(), G) G.add_edge(h.domain(), self) return G R = QQ['q,t'].fraction_field() R.rename("R") Sym = sage.combinat.sf.sf.SymmetricFunctions(R); Sym.rename("Sym") p = Sym.p(); p.rename("p") s = Sym.schur(); s.rename("s") e = Sym.elementary(); e.rename("e") m = Sym.monomial(); m.rename("m") h = Sym.complete(); h.rename("h") H = Sym.macdonald().H(); H.rename("H") P = Sym.macdonald().P(); P.rename("P") J = Sym.macdonald().J(); J.rename("J") S = Sym.macdonald().S(); S.rename("S") Ht = Sym.macdonald().Ht(); Ht.rename("Ht") m.coerce_map_from(P); print Ht.coerce_map_from(P) G = coercion_graph(Ht) G.show()
Apply
- trac12969_fix_coercion_cache.patch and trac_12969-avoid_coercion_from_none.patch, if #5457 is not applied
- All three patches, if #5457 is applied
Attachments (3)
Change History (44)
comment:1 Changed 7 years ago by
- Cc saliola added
comment:2 Changed 7 years ago by
comment:3 Changed 7 years ago by
I can confirm that the problem occurs with vanilla sage-5.2.rc0, namely resulting in this error:
TypeError: do not know how to make x (= McdP[]) an element of self (=Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field)
comment:4 Changed 7 years ago by
Observation: When starting with your example, one gets
sage: from sage.structure.element import get_coercion_model sage: cm = get_coercion_model() sage: Ht.has_coerce_map_from(P) False sage: cm.discover_coercion(P,Ht) (None, Composite map: From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field Defn: Composite map: From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field Defn: Generic morphism: From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis then Generic morphism: From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field then Generic morphism: From: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field) sage: Ht.has_coerce_map_from(P) False sage: cm.discover_coercion(Ht,P) (Composite map: From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field Defn: Composite map: From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field Defn: Generic morphism: From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis then Generic morphism: From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field then Generic morphism: From: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, None) sage: Ht.has_coerce_map_from(P) False
Thus, apparently the problem is that "coerce_map_from" does not call discover_coercion when it should. Broken cache, apparently. Non-unique parents?
comment:5 Changed 7 years ago by
In sage.structure.parent.Parent.coerce_map_from, I see the lines
mor = self.discover_coerce_map_from(S) #if mor is not None: # # Need to check that this morphism doesn't connect previously unconnected parts of the coercion diagram # if self._embedding is not None and not self._embedding.codomain().has_coerce_map_from(S): # # The following if statement may call this function with self and S. If so, we want to return None, # # so that it doesn't use this path for the existence of a coercion path. # # We disable this for now because it is too strict # pass # # print "embed problem: the following morphisms connect unconnected portions of the coercion graph\n%s\n%s"%(self._embedding, mor) # # mor = None if mor is not None: # NOTE: this line is what makes the coercion detection stateful # self._coerce_from_list.append(mor) pass self._coerce_from_hash[S] = mor
Looks suspicious to me. A lot of commented-out code, and an empty special case when the coercion is not None.
comment:6 follow-up: ↓ 17 Changed 7 years ago by
sage: Ht._coerce_map_from_?? Type: builtin_function_or_method Base Class: <type 'builtin_function_or_method'> String Form: <built-in method _coerce_map_from_ of MacdonaldPolynomials_ht_with_category object at 0x4686c50> Namespace: Interactive Definition: Ht._coerce_map_from_(self, S) Source: cpdef _coerce_map_from_(self, S): """ Override this method to specify coercions beyond those specified in coerce_list. If no such coercion exists, return None or False. Otherwise, it may return either an actual Map to use for the coercion, a callable (in which case it will be wrapped in a Map), or True (in which case a generic map will be provided). """ return None
Question: Why is that method not overridden for the different realisations of MacdonaldPolynomials
?
comment:7 Changed 7 years ago by
If I understand correctly, the coercion maps are supposed to go via Schur basis. But while one has
sage: H = MacdonaldPolynomialsH(QQ) sage: P = MacdonaldPolynomialsP(QQ) sage: m = SFAMonomial(P.base_ring()) sage: Ht = MacdonaldPolynomialsHt(QQ) sage: Ht._s Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis sage: Ht._s.has_coerce_map_from(P) True
one has (or does in fact not have)
sage: P._s --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) /home/simon/SAGE/prerelease/sage-5.2.rc0/<ipython console> in <module>() /home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__getattr__ (sage/structure/parent.c:5967)() /home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/structure/misc.so in sage.structure.misc.getattr_from_other_class (sage/structure/misc.c:1427)() AttributeError: 'MacdonaldPolynomials_p_with_category' object has no attribute '_s' sage: P._self_to_s(P.one()) --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) /home/simon/SAGE/prerelease/sage-5.2.rc0/<ipython console> in <module>() /home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/combinat/sf/macdonald.pyc in _self_to_s(self, x) 421 (3*q-6)*s[1, 1, 1] + (-4*q+1)*s[2, 1] 422 """ --> 423 return self._s._from_cache(x, self._s_cache, self._self_to_s_cache, q = self.q, t = self.t) # do we want this t = self.t? 424 425 def c1(self, part): /home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__getattr__ (sage/structure/parent.c:5967)() /home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/structure/misc.so in sage.structure.misc.getattr_from_other_class (sage/structure/misc.c:1427)() AttributeError: 'MacdonaldPolynomials_p_with_category' object has no attribute '_s'
comment:8 Changed 7 years ago by
Looking at sage/combinat/sf/macdonald.py, there is a cache from different realisations (bases) to Schur basis. There are two exceptions: The P-basis and the Q-basis. Why? Perhaps that is the culprit?
comment:9 Changed 7 years ago by
Adding
def _coerce_map_from_(self,S): if not hasattr(self,'_s'): return None try: S_to_s = self._s.coerce_map_from(S) except: return None if S_to_s is None: return None return self.coerce_map_from(self._s)*S_to_s
to MacdonaldPolynomials_generic
solves the problem. But I first have to check whether the original coercion from P to Ht (which exists if one does not do m(P.one())
) is the same.
comment:10 follow-up: ↓ 16 Changed 7 years ago by
Helas. It is not the same. Doing the above, one gets an awfully complicated composition of maps, probably rather inefficient.
sage: H = MacdonaldPolynomialsH(QQ) sage: P = MacdonaldPolynomialsP(QQ) sage: m = SFAMonomial(P.base_ring()) sage: Ht = MacdonaldPolynomialsHt(QQ) sage: Ht.coerce_map_from(P) Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field Defn: Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis Defn: Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the H basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field Defn: Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis Defn: Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the J basis with q=q and t=t over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field Defn: Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis Defn: Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the S basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field Defn: Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis Defn: Generic morphism: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field then Generic morphism: From: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis then Generic morphism: From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis To: Macdonald polynomials in the S basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field then Generic morphism: From: Macdonald polynomials in the S basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis then Generic morphism: From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis To: Macdonald polynomials in the J basis with q=q and t=t over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field then Generic morphism: From: Macdonald polynomials in the J basis with q=q and t=t over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis then Generic morphism: From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis To: Macdonald polynomials in the H basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field then Generic morphism: From: Macdonald polynomials in the H basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis then Generic morphism: From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis To: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
comment:11 Changed 7 years ago by
I added
def test_coercions(self): return self._coerce_from_hash
to self.structure.parent.Parent, and obtain
sage: H = MacdonaldPolynomialsH(QQ) sage: P = MacdonaldPolynomialsP(QQ) sage: m = SFAMonomial(P.base_ring()) sage: Ht = MacdonaldPolynomialsHt(QQ) sage: P in Ht.test_coercions() False sage: P.one() McdP[] sage: P in Ht.test_coercions() False sage: phi = m.coerce_map_from(P) sage: P in Ht.test_coercions() True sage: Ht.test_coercions()[P] is None True
In other words, trying to find the coercion from P to m changes the coercion cache of Ht. Funny.
comment:12 Changed 7 years ago by
- Description modified (diff)
comment:13 follow-up: ↓ 14 Changed 7 years ago by
- Cc zabrocki added
comment:14 in reply to: ↑ 13 ; follow-up: ↓ 15 Changed 7 years ago by
Hi Simon!
Thank you for investigating this. I should mention that Mike Zabrocki and I just finished a patch in http://trac.sagemath.org/sage_trac/ticket/5457 which changes the syntax for symmetric functions. As far as I know the coercion also breaks in that set-up.
At the Sage Days in Minneapolis last week, Franco Saliola also told me that he was hit by the coercion bug in their code on quasisymmetric functions http://trac.sagemath.org/sage_trac/ticket/8899. Franco, could you post your precise failure?
Anne
comment:15 in reply to: ↑ 14 Changed 7 years ago by
Replying to aschilling:
At the Sage Days in Minneapolis last week, Franco Saliola also told me that he was hit by the coercion bug in their code on quasisymmetric functions http://trac.sagemath.org/sage_trac/ticket/8899. Franco, could you post your precise failure?
If I recall correctly, we didn't hit upon the problem with the current code, but with new bases that we implemented on top of it. These new bases are not going in to Sage as part of #8899 (we are only implementing the "classical" bases in this first stage).
Franco
comment:16 in reply to: ↑ 10 ; follow-up: ↓ 21 Changed 7 years ago by
comment:17 in reply to: ↑ 6 Changed 7 years ago by
Question: Why is that method not overridden for the different realisations of
MacdonaldPolynomials
?
Because the coercions are registered explicitly during the initialization of Sym / macdonald polynomials. This is better because it leaves maximal freedom to the coercion model (e.g. the coercion model can't do transitivity with _coerce_map_from).
Cheers,
Nicolas
comment:18 Changed 7 years ago by
I think I can explain (and thus, solve) the problem!
The bug is in the backtracking algorithm for finding a coercion path.
Every parent A has a list of other parents B1, B2, ... such that a coercion from B1, B2 to A is registered. When searching for a coercion from parent X to A, and a direct coercion is not registered, then a coercion from X to B1, B2, ... is (in that order!) is searched. But of course one must avoid infinite recursions, and thus any coercion path from X to B1, B2, via X is disregarded. Disregarding one node in the backtracking algorithm is the purpose of _register_pair in sage.structure.parent.
Now consider the following situation, where arrows denote registered coercions (partially the coercions are registered in both directions - that's what happening in the symmetric functions code):
X -> B2 <-> A <-> B1
We first ask for a coercion from X to A.
There is no coercion from X to A found in the cache. Thus, we disregard (X,A) in our backtracking algorithm, and search for a coercion from X to B1. The only coercion path from X to B1 would be via A, but that is disregarded in the backtracking algorithm. The absence of a coercion from X to B1 is cached. In the next step, a coercion from X to A via B2 is found, cached and returned.
But when later asking for a coercion from X to B1, the cache states that there is no coercion!
Here's the bug: The absence of a coercion from X to B1 must only be cached if X is not the starting point of any disregarded search path (such as (X,A) in the example above), with the only exception of (X,B1).
comment:19 follow-up: ↓ 20 Changed 7 years ago by
And while we are at it: _register_pair uses a dictionary in order to implement a set. I think it would be more efficient to use a set right away.
comment:20 in reply to: ↑ 19 Changed 7 years ago by
Replying to SimonKing:
And while we are at it: _register_pair uses a dictionary in order to implement a set. I think it would be more efficient to use a set right away.
No, to my surprise, it isn't:
sage: cython(""" ....: def testD(dict D): ....: cdef int i ....: for i from 0<=i<10000: ....: b = (i in D) ....: def testS(set S): ....: cdef int i ....: for i from 0<=i<10000: ....: b = (i in S) ....: """) sage: D = dict([(i,1) for i in range(5000)]) sage: S = set(range(5000)) sage: %timeit testD(D) 625 loops, best of 3: 495 µs per loop sage: %timeit testS(S) 625 loops, best of 3: 520 µs per loop sage: %timeit testD(D) 625 loops, best of 3: 496 µs per loop sage: %timeit testS(S) 625 loops, best of 3: 520 µs per loop
Sets seem slower than dictionaries by 5%.
comment:21 in reply to: ↑ 16 ; follow-up: ↓ 22 Changed 7 years ago by
Replying to nthiery:
Yes that's the well know issue (#8878) of the current coercion model implementation: it does a depth first search rather than a breath first.
OK. I think #8878 would involve a considerable amount of work. So, for simplicity, I suggest to fix the cache bug in the current implementation of depth first search here. And if in future someone will tackle #8878, he/she should do so on top of that fix.
comment:22 in reply to: ↑ 21 Changed 7 years ago by
Replying to SimonKing:
OK. I think #8878 would involve a considerable amount of work. So, for simplicity, I suggest to fix the cache bug in the current implementation of depth first search here. And if in future someone will tackle #8878, he/she should do so on top of that fix.
I actually have an implementation for #8878 in the queue I had written two years ago; however it's disabled because there remained quite some work cleaning up Sage here and there for things to work smoothly.
So, yes, if you have a quick fix to the depth first search, please go ahead; my patch certainly needs a lot of rebasing anyway.
Cheers,
Nicolas
comment:23 follow-up: ↓ 27 Changed 7 years ago by
Question: Is #5457 very close to being positively reviewed? Namely, we must decide whether we use the old syntax for the to-be-written doctest (in that case, this ticket would be a dependency for #5457), or use the new syntax (in that case, due to deprecation warnings, #5457 would become a dependency for this ticket).
For now, I will use the old syntax.
comment:24 Changed 7 years ago by
- Status changed from new to needs_review
The attached patch seems to fix the problem.
Questions:
Is there a speed regression?
With my patch, the absence of a coercion from X to Y is only cached, if no coercion path from X to Z (with Z different from Y) is temporarily disabled. But if there really is no coercion from X to Y, then the fix might involve a speed regression. Potential solution: If the old buggy depth first algorithm would cache the absence of a coercion from X to Y, while the new fixed version wouldn't, then we might investigate the paths from X to Y again, right after re-enabling the other paths starting from X.
What about #5457
I did not run the tests, yet. But the new test in my patch would fail because of the deprecation warnings introduced by #5457. So, we must decide whether making #5457 depend on this ticket or the other way around?
For the record: Without #5457, I now get
sage: H = MacdonaldPolynomialsH(QQ) sage: P = MacdonaldPolynomialsP(QQ) sage: m = SFAMonomial(P.base_ring()) sage: Ht = MacdonaldPolynomialsHt(QQ) sage: m(P.one()) m[] sage: Ht(P.one()) McdHt[]
and
sage: Ht.coerce_map_from(P) Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field Defn: Composite map: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis Defn: Generic morphism: From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field then Generic morphism: From: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis then Generic morphism: From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis To: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
(the latter being the same as in vanilla sage)
comment:25 Changed 7 years ago by
For the record: With my patch, all tests pass on bsd.math. However, with the patch, it takes 6403.9 seconds, but it is 6106.7 seconds without the patch. Hence, it could be that we have a serious regression, but of course it could also be due to the machine being busy. Should be investigated.
comment:26 Changed 7 years ago by
Another data point: On my laptop, the tests for sage/schemes/elliptic_curves took 431.4 seconds without the patch, but 441.4 seconds with the patch. That means a regression of 2.3%, which probably isn't significant. But I'd feel better if the reviewer did some timings as well.
comment:27 in reply to: ↑ 23 ; follow-up: ↓ 28 Changed 7 years ago by
Replying to SimonKing:
Question: Is #5457 very close to being positively reviewed? Namely, we must decide whether we use the old syntax for the to-be-written doctest (in that case, this ticket would be a dependency for #5457), or use the new syntax (in that case, due to deprecation warnings, #5457 would become a dependency for this ticket).
For now, I will use the old syntax.
Mike and I already cross reviewed 5457. We are just waiting for green light from Dan Bump or Franco Saliola. So hopefully (!?) 5457 will go in soon.
Anne
comment:28 in reply to: ↑ 27 Changed 7 years ago by
Replying to aschilling:
Replying to SimonKing:
Question: Is #5457 very close to being positively reviewed? Namely, we must decide whether we use the old syntax for the to-be-written doctest (in that case, this ticket would be a dependency for #5457), or use the new syntax (in that case, due to deprecation warnings, #5457 would become a dependency for this ticket).
For now, I will use the old syntax.
Mike and I already cross reviewed 5457. We are just waiting for green light from Dan Bump or Franco Saliola. So hopefully (!?) 5457 will go in soon.
OK. The only problem related with #5457 is the syntax in one new doctest. I suggest that I provide a second optional patch (like: if #5457 is in then use both patches, otherwise only use one patch).
comment:29 Changed 7 years ago by
I have slightly updated the patch. Only difference: A dictionary, that previously was declared as "cdef object", is now "cdef dict".
I repeated timings for sage -t devel/sage/sage/schemes/elliptic_curves/
. I did three runs, the time is in seconds:
Vanilla sage-5.2.rc0
442.5, 441.9, 442.3
sage-5.2.rc0 plus the patch
443.3, 440.8, 442.1
So, apparently the 2.3% regression that I found earlier has been random noise.
comment:30 Changed 7 years ago by
- Description modified (diff)
comment:31 Changed 7 years ago by
The patch seems to work. But meanwhile I wonder whether my fix is really correct.
The aim is: Find a coercion from X to Y.
Backtracking means: We know some B1,B2,... that coerce into Y. Hence, we try to find a coercion from X to B1,B2,... but avoiding Y, so that there is no infinite loop. That's why the pair (X,Y) is temporarily disregarded when searching for a coerce path.
In particular, the recursive search will always start at X.
Hence, it was my understanding that all temporarily disregarded paths start at X. That's why I wrote
cdef bint _may_cache_none(x, y, tag) except -1: # Are we allowed to cache the absence of a coercion # from y to x? We are only allowed, if y is *not* # part of any coerce path that is temporarily disregarded, # with the only exception of the path from y to x. # See #12969. cdef EltPair P for P in _coerce_test_dict.iterkeys(): if (P.y is y) and (P.x is not x) and (P.tag is tag): return 0 return 1
However, to be on the safe side, I tested whether I drew the correct conclusion. Apparently I didn't.
Namely, when Sage starts and a coercion from the complex double field into, say, the integer ring is sought, then the path from the complex lazy field to the complex double field is disregarded. Also, while trying to find a coercion from the complex lazy field to the integers, the search path from "Number Field in I with defining polynomial x^{2} + 1" to the rational field is temporarily disregarded.
Even weirder: When doing m(P.one())
in the example from the ticket description, the coercion from "<type 'str'>" to Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field is disregarded, while searching for a coerce path from None (sic!) to the ring of integers.
I wonder how this can possibly happen, given how backtracking works. And what does that mean for the patch? I guess the cleanest solution would be to find out why the wrong paths are temporarily disregarded, and why the heck a coercion from None to anything is requested.
comment:32 Changed 7 years ago by
I found that a coercion from None is sought when asking the following:
sage: P = QQ['x','y','a'] sage: P.has_coerce_map_from(str)
I suggest to fix that here, unless it is too complicated.
comment:33 Changed 7 years ago by
Got it. In sage/structure/parent_old.pyx, which unfortunately is still involved in MPolynomialRing_libsingular
, there is line 152:
sage_type = py_scalar_parent(S)
However, is S is <type 'str'>
then its py_scalar_parent is None (which seems wrong, or if it isn't wrong then one should at least catch the special case None). The function py_scalar_parent is in sage/structure/coerce.pyx.
comment:34 Changed 7 years ago by
It turns out: When making a special case when py_scalar_parent is None, then indeed in our example it is always the case that the starting point of a coerce path we are looking for is the same as the starting point of any path we temporarily disregard. This is how it should be. I will update my patch a bit later.
However, when starting Sage, it is still the case that the path from Number Field in I with defining polynomial x^2 + 1
to Rational Field
is blocked while searching for a path from Complex Lazy Field
to Integer Ring
, or Algebraic Field
to Real Field with 53 bits of precision
is blocked while searching for <type 'float'>
to Algebraic Field
.
But I think I understand that as well: When searching for a coercion from P to, e.g., the complex field CC, the first thing the coercion model does is to temporarily disregard (P,CC) for the backtracking algorithm. Then, CC._coerce_map_from_(P)
is called at some point. But the last line of that method calls CC._coerce_map_via([CLF],P)
. Hence, while (P,CC) is still disregarded, not only a coerce path from P to CLF but also a coerce path from CLF to CC is sought.
I tend to say that it is the responsibility of the person writing _coerce_map_from_
for a parent to avoid ill effects.
Therefore, I still think that the solution of my patch ("do not cache the absence of a coerce path from A to B if there is any temporarily disregarded path that stars at A") is fine. If the reviewer disagrees then we may consider a very strict solution: "do not cache the absence of a coerce path from A to B if there is any temporarily disregarded path besides (A,B) itself."
Thoughts?
comment:35 follow-up: ↓ 37 Changed 7 years ago by
I haven't checked the detail, but the music sounds good. In any cases, we are just looking for a temporary fix that improves the situation until we rewrite completely the search algorithm; if it's not perfect, so be it. So I would say: if all tests pass, go for it.
Thanks!
Changed 7 years ago by
Shortcut when searching for a coercion from a type that is no parent (e.g., <str>)
comment:36 Changed 7 years ago by
- Component changed from combinatorics to coercion
- Description modified (diff)
I added another patch. Its purpose:
Python types are sometimes considered as parents. There is a function sage.structure.coerce.py_scalar_parent returning a parent that corresponds to a type. Some types, e.g., <type 'str'>
, do not correspond to a parent, hence py_scalar_parent(str) returns None.
Still, the code in sage.structure.parent_old would try to construct a coercion from None (the non-existing parent) to self. The result is clear a-priori: There is no such coercion. The new patch establishes a short-cut.
For the reviewer:
Here is a summary of how the main patch trac12969_fix_coercion_cache.patch works.
- When searching for a coerce path from A to B by back-tracking, it is vital that it is not attempted to construct a path from A to B in the inner parts of the recursion. Hence, the path from A to B is temporarily disregarded, by calling
_register_pair(B,A,"coerce")
-- that's existing code. - When a coercion from A to B is found, then it is cached. When a coercion from A to B is not found, then the unpatched code would cache that as well. With the patch, the absence of a coercion from A to B is only cached, if
_register_pair(C,A,"coerce")
has not been called for any C different from B.
Here is a discussion of how it is justified.
- In a pure back-tracking algorithm searching for a path from A to B, any temporarily disregarded path starts in A. Hence, it is correct to focus on such paths in 2. above.
- There are cases in which a
_coerce_map_from_
method breaks the pure back-tracking algorithm. So, theoretically, the following can happen: i) We search a path from A to B, which is temporarily disregarded in back-tracking. ii) While searching, a_coerce_map_from_
method is called that internally searches a path from C to D. iii) There is a path from C to D, but it would involve a path from A to B. iv) Since that path is disregarded and since "A is not C", we would cache the absence of a coercion from C to D in 2. above - which may be wrong. - While the preceding point is a theoretical possibility, it is the responsibility of the author of _coerce_map_from_ that it does not occur in reality.
If the reviewer disagrees and believes that we must exclude the theoretical possibility of a failure, we could modify 2. above, as follows:
2'. When a coercion from A to B is found, then it is cached. When a coercion from A to B is not found, then the unpatched code would cache that as well. With the patch, the absence of a coercion from A to B is only cached, if
_register_pair(D,C,"coerce")
has not been called for any (C,D) different from (A,B).
Anyway. Since tests pass and since (even better) the sporadic errors with #715, #12215, #11521 and #12313 seem to vanish with the patch, I would suggest to keep the patch as it is now.
PS: I am changing the component, since it isn't about combinatorics but about coercion.
Apply trac12969_fix_coercion_cache.patch trac_12969-avoid_coercion_from_none.patch
comment:37 in reply to: ↑ 35 ; follow-up: ↓ 38 Changed 7 years ago by
Replying to nthiery:
In any cases, we are just looking for a temporary fix that improves the situation until we rewrite completely the search algorithm; if it's not perfect, so be it. So I would say: if all tests pass, go for it.
I agree. The main purpose is a fix of the existing algorithm, so that the memleak fixes in #715, #12215, #11521 and #12313 work reliably. I am confident that a fix relying on a new algorithm should work as well.
comment:38 in reply to: ↑ 37 Changed 7 years ago by
Thanks, Simon, for fixing this bug! Your solution looks ok to me, though I strongly recommend that someone reprograms the coercion algorithm in the future.
I ran all tests on top of 5457 and all tests passed! So I am giving this a positive review. Hopefully it can be merged together with 5457 (but if 5457 gets held up, this can go in nonetheless).
Anne
comment:39 Changed 7 years ago by
- Reviewers set to Anne Schilling
- Status changed from needs_review to positive_review
comment:40 Changed 7 years ago by
- Merged in set to sage-5.3.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:41 Changed 4 years ago by
- Description modified (diff)
Just for the record: My impression was that solving this ticket could also help with a couple of coercion-related memory leaks considered in #715, #12215, #12313 and so on.