#15303: Coercion discovery fails to be transitive
-------------------------------------+-------------------------------------
Reporter: nbruin | Owner:
Type: defect | Status: needs_work
Priority: major | Milestone: sage-5.13
Component: coercion | Resolution:
Keywords: | Merged in:
Authors: Simon King | Reviewers:
Report Upstream: N/A | Work issues: Crash in permgroup.py
Branch: | Commit:
u/SimonKing/ticket/15303 | 807550bbc45e9872ac365fc98b817ccd5bcfbb95
Dependencies: #14711, #15329, | Stopgaps:
#15331 |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
I have suggested to get both a speed-up and a cleaner behaviour of the
backtracking algorithm with respect to "comparison of parents by
identity".
Namely, paths in the coerce digraph are currently marked as "already used
in backtracking" by the cdef function "_register_pair(x,y,tag)", and the
mark is removed by another cdef function "_unregister_pair(x,y,tag)".
In both cases, the functions create an instance of the cdef class
`EltPair`, and stores resp. removes it in some dictionary. The instances
of `EltPair` are compared by comparing `(x,y,tag)`, and the hash also is
obtained in that way.
But that means parents are compared by `==`, whereas in the innards of the
coercion system parents (even non-unique parents!) are generally compared
by `is`. Moreover, comparison by identity and hash by id would be a lot
faster, and creating an instance of `EltPair` each time also is a waste of
time.
Couldn't we use a `TripleDict` instead? It would compare by identity, it
is about triples `x,y,tag`, and I think we have made tests showing that
containment tests and so on are faster than when using a Python dict keyed
by triples.
I only worry about the weak references. Could it happen that registered
pairs will be automatically removed from the triple dict while
backtracking, resulting in an infinite recursion? I guess this can not
happen, because the backtracking algorithm will only visit parents that
are strongly referenced.
Anyway, I'd say it is worth trying. If it works, then fine. If it doesn't,
we can move this to a separate ticket, that will be using a ''strong''
version of `TripleDict`.
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:86>
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.
For more options, visit https://groups.google.com/groups/opt_out.
