#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:
u/SimonKing/ticket/13394 | f0ed60fbdf5f2b1c7cd15f6bab98099f4ff8b822
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by nbruin):
Replying to [comment:11 SimonKing]:
> I wonder: Is it really a good idea to have a dictionary storing one list
for each hash value?
Well, it's not entirely optimal of course. Python's own dict already has a
mechanism to deal with hash collisions, so having the lists stored is,
strictly speaking, an unnecessary indirection. However, breaking open
python's dict implementation to access the hash buckets there is going to
be a very hard to maintain solution (you'd basically be patching python
and implement an extra "delete by hash and value id" routine. Entirely
doable, but we'd be stuck with a patched python to eternity).
There are two solutions:
- benefit from Python's insanely optimized dict and swallow the cost of
an extra indirection
- abandon Python's dict entirely and implement your own hash table.
We followed the latter for !MonoDict and !TripleDict because the key
semantics there are so different that borrowing python's dict wasn't
really an option. For !WeakValueDictionary it is an option to borrow from
dict. I suspect you'd have to work pretty hard to come close to that
performance.
Note that almost all of your lists are just going to be pairs. Python
internally is making such things all the time: arguments tend to be
packaged and copied as tuples.
I guess that brings us to a third possibility: Finish the proof of
concept, show the python community what the problem is with
!WeakValueDictionary, and suggest the extra hook we need to make it safe.
Then we might end up with a safe and fast !WeakValueDictionary in python
proper. That would only be in Python3+, though, so we'd have to backport
to Python2.7.
--
Ticket URL: <http://trac.sagemath.org/ticket/13394#comment:12>
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.
