#13394: Write a WeakValueDictionary with safer key removal
-------------------------------+-------------------------
Reporter: nbruin | Owner: rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.13
Component: memleak | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
-------------------------------+-------------------------
Comment (by SimonKing):
I have attached a proof of concept. I think the class `WVD` defined in the
attachment is feature-complete. According to my benchmarks, it is faster
than `weakref.WeakValueDictionary`, and it is safer.
__Performance__
{{{
sage: def test_dict(D,L):
....: for k,v in L:
....: D[k] = v
....: for k,v in L:
....: if k not in D:
....: raise RuntimeError("containment")
....: for k,v in L:
....: D[k] = v
....: for k in D.iterkeys():
....: if k not in D:
....: raise RuntimeError("second containment")
....: for k,v in L:
....: assert D.get(k)==v
....: del D[k]
....: for k,v in L:
....: if k in D:
....: raise RuntimeError("anti-containment")
....:
sage: L = [(p,GF(p)) for p in prime_range(2*10^4)]
sage: from weakref import WeakValueDictionary
sage: D = WeakValueDictionary()
sage: %timeit test_dict(D,L)
10 loops, best of 3: 43.2 ms per loop
sage: D = WVD()
sage: %timeit test_dict(D,L)
10 loops, best of 3: 29.4 ms per loop
}}}
Hence, the WVD is faster than the `weakref.WeakValueDictionary`.
__Safety__
{{{
sage: class Vals(object): pass
sage: class Keys:
....: def __init__(self, val):
....: self.val = weakref.ref(val)
....: def __hash__(self):
....: return hash(self.val())
....: def __eq__(self, other):
....: return self.val() == other.val()
....:
sage: ValList = [Vals() for _ in range(10)]
sage: D = WeakValueDictionary()
sage: for v in ValList:
....: D[Keys(v)] = v
....:
sage: len(D)
10
sage: del ValList
Exception KeyError: (<__main__.Keys instance at 0xdcfc96c>,) in <function
remove at 0xdcb9df4> ignored
Exception KeyError: (<__main__.Keys instance at 0xdcfc90c>,) in <function
remove at 0xdcb9df4> ignored
Exception KeyError: (<__main__.Keys instance at 0xdcfcc2c>,) in <function
remove at 0xdcb9df4> ignored
Exception KeyError: (<__main__.Keys instance at 0xdcfc9ec>,) in <function
remove at 0xdcb9df4> ignored
Exception KeyError: (<__main__.Keys instance at 0xdcfca4c>,) in <function
remove at 0xdcb9df4> ignored
Exception KeyError: (<__main__.Keys instance at 0xdcfc9cc>,) in <function
remove at 0xdcb9df4> ignored
Exception KeyError: (<__main__.Keys instance at 0xdcfc98c>,) in <function
remove at 0xdcb9df4> ignored
Exception KeyError: (<__main__.Keys instance at 0xdcfccac>,) in <function
remove at 0xdcb9df4> ignored
Exception KeyError: (<__main__.Keys instance at 0xdcfca0c>,) in <function
remove at 0xdcb9df4> ignored
sage: len(D)
10
}}}
Hence, the `weakref.WeakValueDictionary` is unsafe.
{{{
sage: ValList = [Vals() for _ in range(10)]
sage: D = WVD()
sage: for v in ValList:
....: D[Keys(v)] = v
....:
sage: len(D)
10
sage: del ValList
sage: len(D)
1
sage: del v
sage: len(D)
0
}}}
Hence, the WVD is safe (or at least: safer...)
I suppose I should add tests and documentation to the proof of concept,
put into sage.misc and rename `WVD` into
`sage.misc.weak_dict.WeakValueDictionary`. And then we should see if we
can really smoothly replace `weakref.WeakValueDictionary` in Sage.
--
Ticket URL: <http://trac.sagemath.org/ticket/13394#comment:5>
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.
