Containers for storing coercion data#
This module provides TripleDict
and MonoDict
. These are
structures similar to WeakKeyDictionary
in Python’s weakref
module, and are optimized for lookup speed. The keys for TripleDict
consist of triples (k1,k2,k3) and are looked up by identity rather than
equality. The keys are stored by weakrefs if possible. If any one of the
components k1, k2, k3 gets garbage collected, then the entry is removed from
the TripleDict
.
Key components that do not allow for weakrefs are stored via a normal
refcounted reference. That means that any entry stored using a triple
(k1,k2,k3) so that none of the k1,k2,k3 allows a weak reference behaves
as an entry in a normal dictionary: Its existence in TripleDict
prevents it from being garbage collected.
That container currently is used to store coercion and conversion maps between
two parents (github issue #715) and to store homsets of pairs of objects of a
category (github issue #11521). In both cases, it is essential that the parent
structures remain garbage collectable, it is essential that the data access is
faster than with a usual WeakKeyDictionary
, and we enforce
the “unique parent condition” in Sage (parent structures should be identical
if they are equal).
MonoDict
behaves similarly, but it takes a single item as a key. It
is used for caching the parents which allow a coercion map into a fixed other
parent (github issue #12313).
By github issue #14159, MonoDict
and TripleDict
can be optionally
used with weak references on the values.
Note that this kind of dictionary is also used for caching actions and coerce maps. In previous versions of Sage, the cache was by strong references and resulted in a memory leak in the following example. However, this leak was fixed by github issue #715, using weak references:
sage: # needs sage.combinat sage.modules sage.rings.finite_rings
sage: K.<t> = GF(2^55)
sage: for i in range(20):
....: a = K.random_element()
....: E = EllipticCurve(j=a)
....: P = E.random_point()
....: Q = 2*P
sage: L = [Partitions(n) for n in range(200)] # purge strong cache in CachedRepresentation
sage: import gc
sage: n = gc.collect()
sage: from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_finite_field
sage: LE = [x for x in gc.get_objects() if isinstance(x, EllipticCurve_finite_field)]
sage: len(LE)
1
- class sage.structure.coerce_dict.MonoDict#
Bases:
object
This is a hashtable specifically designed for (read) speed in the coercion model.
It differs from a python WeakKeyDictionary in the following important ways:
Comparison is done using the ‘is’ rather than ‘==’ operator.
Only weak references to the keys are stored if at all possible. Keys that do not allow for weak references are stored with a normal refcounted reference.
The callback of the weak references is safe against recursion, see below.
There are special cdef set/get methods for faster access. It is bare-bones in the sense that not all dictionary methods are implemented.
IMPLEMENTATION:
It is implemented as a hash table with open addressing, similar to python’s dict.
INPUT:
data
– optional iterable defining initial data, as dict or iterable of (key, value) pairs.weak_values
– optional bool (default False). If it is true, weak references to the values in this dictionary will be used, when possible.
EXAMPLES:
sage: from sage.structure.coerce_dict import MonoDict sage: L = MonoDict() sage: a = 'a'; b = 'ab'; c = '-15' sage: L[a] = 1 sage: L[b] = 2 sage: L[c] = 3
The key is expected to be a unique object. Hence, the item stored for
c
cannot be obtained by providing another equal string:sage: L[a] 1 sage: L[b] 2 sage: L[c] 3 sage: L['-15'] Traceback (most recent call last): ... KeyError: '-15'
Not all features of Python dictionaries are available, but iteration over the dictionary items is possible:
sage: sorted(L.items()) [('-15', 3), ('a', 1), ('ab', 2)] sage: del L[c] sage: sorted(L.items()) [('a', 1), ('ab', 2)] sage: len(L) 2 sage: for i in range(1000): ....: L[i] = i sage: len(L) 1002 sage: L['a'] 1 sage: L['c'] Traceback (most recent call last): ... KeyError: 'c'
Note that
MW
also accepts values that do not allow for weak references:sage: MW[k] = int(5) sage: MW[k] 5 The following demonstrates that :class:`MonoDict` is safer than :class:`~weakref.WeakKeyDictionary` against recursions created by nested callbacks; compare :issue:`15069` (the mechanism used now is different, though):: sage: M = MonoDict() sage: class A: pass sage: a = A() sage: prev = a sage: for i in range(1000): ....: newA = A() ....: M[prev] = newA ....: prev = newA sage: len(M) 1000 sage: del a sage: len(M) 0 The corresponding example with a Python :class:`weakref.WeakKeyDictionary` would result in a too deep recursion during deletion of the dictionary items:: sage: import weakref sage: M = weakref.WeakKeyDictionary() sage: a = A() sage: prev = a sage: for i in range(1000): ....: newA = A() ....: M[prev] = newA ....: prev = newA sage: len(M) 1000 Check that also in the presence of circular references, :class:`MonoDict` gets properly collected:: sage: import gc sage: def count_type(T): ....: return len([c for c in gc.get_objects() if isinstance(c,T)]) sage: gc.freeze() # so that gc.collect() only deals with our trash sage: N = count_type(MonoDict) sage: for i in range(100): ....: V = [MonoDict({"id":j+100*i}) for j in range(100)] ....: n = len(V) ....: for i in range(n): V[i][V[(i+1)%n]] = (i+1)%n ....: del V ....: _ = gc.collect() ....: assert count_type(MonoDict) == N sage: count_type(MonoDict) == N True sage: gc.unfreeze() AUTHORS: - Simon King (2012-01) - Nils Bruin (2012-08) - Simon King (2013-02) - Nils Bruin (2013-11)
- class sage.structure.coerce_dict.MonoDictEraser#
Bases:
object
Erase items from a
MonoDict
when a weak reference becomes invalid.This is of internal use only. Instances of this class will be passed as a callback function when creating a weak reference.
EXAMPLES:
sage: from sage.structure.coerce_dict import MonoDict sage: class A: pass sage: a = A() sage: M = MonoDict() sage: M[a] = 1 sage: len(M) 1 sage: del a sage: import gc sage: n = gc.collect() sage: len(M) # indirect doctest 0
AUTHOR:
Simon King (2012-01)
Nils Bruin (2013-11)
- class sage.structure.coerce_dict.ObjectWrapper#
Bases:
object
A simple fast wrapper around a Python object. This is like a 1-element tuple except that it does not keep a reference to the wrapped object.
- class sage.structure.coerce_dict.TripleDict#
Bases:
object
This is a hashtable specifically designed for (read) speed in the coercion model.
It differs from a python dict in the following important ways:
All keys must be sequence of exactly three elements. All sequence types (tuple, list, etc.) map to the same item.
Any of the three key components that support weak-refs are stored via a weakref. If any of these components gets garbage collected then the entire entry is removed. In that sense, this structure behaves like a nested
WeakKeyDictionary
.Comparison is done using the ‘is’ rather than ‘==’ operator.
There are special cdef set/get methods for faster access. It is bare-bones in the sense that not all dictionary methods are implemented.
INPUT:
data
– optional iterable defining initial data, as dict or iterable of (key, value) pairs.weak_values
– optional bool (default False). If it is true, weak references to the values in this dictionary will be used, when possible.
IMPLEMENTATION:
It is implemented as a hash table with open addressing, similar to python’s dict.
EXAMPLES:
sage: from sage.structure.coerce_dict import TripleDict sage: L = TripleDict() sage: a = 'a'; b = 'b'; c = 'c' sage: L[a,b,c] = 1 sage: L[a,b,c] 1 sage: L[c,b,a] = -1 sage: sorted(L.items()) [(('a', 'b', 'c'), 1), (('c', 'b', 'a'), -1)] sage: del L[a,b,c] sage: list(L.items()) [(('c', 'b', 'a'), -1)] sage: len(L) 1 sage: for i in range(1000): ....: L[i,i,i] = i sage: len(L) 1001 sage: L = TripleDict(L) sage: L[c,b,a] -1 sage: L[a,b,c] Traceback (most recent call last): ... KeyError: ('a', 'b', 'c') sage: L[a] Traceback (most recent call last): ... KeyError: 'a' sage: L[a] = 1 Traceback (most recent call last): ... KeyError: 'a'
AUTHORS:
Robert Bradshaw, 2007-08
Simon King, 2012-01
Nils Bruin, 2012-08
Simon King, 2013-02
Nils Bruin, 2013-11
- copy()#
Return a copy of this
TripleDict
as Python dict.EXAMPLES:
sage: from sage.structure.coerce_dict import TripleDict sage: L = TripleDict() sage: L[1,2,3] = 42 sage: L.copy() {(1, 2, 3): 42}
- items()#
Iterate over the
(key, value)
pairs of thisTripleDict
.EXAMPLES:
sage: from sage.structure.coerce_dict import TripleDict sage: L = TripleDict() sage: L[1,2,3] = None sage: L.items() <...generator object at ...> sage: list(L.items()) [((1, 2, 3), None)]
- class sage.structure.coerce_dict.TripleDictEraser#
Bases:
object
Erases items from a
TripleDict
when a weak reference becomes invalid.This is of internal use only. Instances of this class will be passed as a callback function when creating a weak reference.
EXAMPLES:
sage: from sage.structure.coerce_dict import TripleDict sage: class A: pass sage: a = A() sage: T = TripleDict() sage: T[a,ZZ,None] = 1 sage: T[ZZ,a,1] = 2 sage: T[a,a,ZZ] = 3 sage: len(T) 3 sage: del a sage: import gc sage: n = gc.collect() sage: len(T) # indirect doctest 0
AUTHOR:
Simon King (2012-01)
Nils Bruin (2013-11)