[Raymond]
> ...
> * The ordering we have for dicts uses a hash table that indexes into a
> sequence.
> That works reasonably well for typical dict operations but is unsuitable for
> set
> operations where some common use cases make interspersed additions
> and deletions (that is why the LRU cache still uses a cheaply updated doubly-l
> linked list rather that deleting and reinserting dict entries).
I'm going to take a stab at fleshing that out a bit: ideally, an
ordered dict stores hash+key+value records in a contiguous array with
no "holes". That's ("no holes") where the memory savings comes from.
The "holes" are in the hash table, which only hold indices _into_ the
contiguous array (and the smallest width of C integer indices
sufficient to get to every slot in the array).
"The problem" is that deletions leave _two_ kinds of holes: one in
the hash table, and another in the contiguous vector. The latter
holes cannot be filled with subsequent new hash+key+value records
because that would break insertion order.
So in an app that mixes additions and deletions, the ordered dict
needs to be massively rearranged at times to squash out the holes left
behind by deletions, effectively moving all the holes to "the end",
where they can again be used to reflect insertion order.
Unordered dicts never had to be rearranged unless the total size
changed "a lot", and that remains true of the set implementation. But
in apps mixing adds and deletes, ordered dicts can need massive
internal rearrangement at times even if the total size never changes
by more than 1.
Algorithms doing a lot of mixing of adds and deletes seem a lot more
common for sets than for dicts, and so the ordered dict's basic
implementation _approach_ is a lot less suitable for sets. Or, at
least, that's my best attempt to flesh out Raymond's telegraphic
thinking there.
Note: the holes left by deletions _wouldn't_ be "a problem" _except_
for maintaining insertion order. If we were only after the memory
savings, then on deletion "the last" record in the contiguous array
could be moved into the hole at once, leaving the array hole-free
again. But that also changes the order. IIRC, that's what the
original "compact dict" _did_ do.
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at
https://mail.python.org/archives/list/python-dev@python.org/message/QQXSSJWHKTUNHSMSHVM7XLMDBMUV7BDX/
Code of Conduct: http://python.org/psf/codeofconduct/
