-
-
Notifications
You must be signed in to change notification settings - Fork 491
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Coercion failures in symmetric functions #12969
Comments
comment:3
I can confirm that the problem occurs with vanilla sage-5.2.rc0, namely resulting in this error:
|
comment:4
Observation: When starting with your example, one gets
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
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
Question: Why is that method not overridden for the different realisations of |
comment:7
If I understand correctly, the coercion maps are supposed to go via Schur basis. But while one has
one has (or does in fact not have)
|
comment:8
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
Adding
to |
comment:10
Helas. It is not the same. Doing the above, one gets an awfully complicated composition of maps, probably rather inefficient.
|
comment:11
I added def test_coercions(self):
return self._coerce_from_hash to self.structure.parent.Parent, and obtain
In other words, trying to find the coercion from P to m changes the coercion cache of Ht. Funny. |
This comment has been minimized.
This comment has been minimized.
comment:14
Hi Simon! Thank you for investigating this. I should mention that Mike Zabrocki and I just finished a patch in #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 #8899. Franco, could you post your precise failure? Anne |
comment:15
Replying to @anneschilling:
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
Replying to @simon-king-jena:
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. |
comment:17
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, |
comment:18
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):
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
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
Replying to @simon-king-jena:
No, to my surprise, it isn't:
Sets seem slower than dictionaries by 5%. |
comment:21
Replying to @nthiery:
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
Replying to @simon-king-jena:
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, |
comment:23
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
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
and
(the latter being the same as in vanilla sage) |
Author: Simon King |
comment:25
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
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
Replying to @simon-king-jena:
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
Replying to @anneschilling:
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). |
Attachment: trac12969_fix_coercion_cache.patch.gz Using the old syntax for symmetric function algebras (pre-#5457) |
comment:29
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 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. |
Attachment: trac12969_rel_5457.patch.gz Rewrite one doctest to use the syntax introduced in #5457 |
comment:30
I have attached a second patch. It is only needed if #5457 is applied. Since there seems to be no regression, I think it can now be reviewed. For the release manager: Use the second patch on top of that, as soon as #5457 is merged. For the patchbot: Apply trac12969_fix_coercion_cache.patch |
This comment has been minimized.
This comment has been minimized.
comment:31
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 x2 + 1" to the rational field is temporarily disregarded. Even weirder: When doing 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
I found that a coercion from None is sought when asking the following:
I suggest to fix that here, unless it is too complicated. |
comment:33
Got it. In sage/structure/parent_old.pyx, which unfortunately is still involved in
However, is S is |
comment:34
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 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, I tend to say that it is the responsibility of the person writing 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
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! |
Shortcut when searching for a coercion from a type that is no parent (e.g., ) |
This comment has been minimized.
This comment has been minimized.
comment:36
Attachment: trac_12969-avoid_coercion_from_none.patch.gz 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., 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.
Here is a discussion of how it is justified.
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 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
Replying to @nthiery:
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
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 |
Reviewer: Anne Schilling |
Merged: sage-5.3.beta0 |
The following code triggers a coercion failure in the symmetric function code
The coercion path does exist, however!
This can also be checked with the new syntax using the patches in #5457 as follows:
The bug is in the coercion system. Sage does
not find a path from P to Ht, whereas there definitely is one:
Apply
CC: @sagetrac-sage-combinat @saliola @zabrocki
Component: coercion
Keywords: symmetric functions
Author: Simon King
Reviewer: Anne Schilling
Merged: sage-5.3.beta0
Issue created by migration from https://trac.sagemath.org/ticket/12969
The text was updated successfully, but these errors were encountered: