Wouldn't attempting to reuse DUMMY entries be expensive? You'd have to search forward in the array. Just keeping a count of DUMMY entries and compacting when there are too many seems better somehow.
On Mon, Sep 12, 2016 at 10:00 AM, Victor Stinner <victor.stin...@gmail.com> wrote: > 2016-09-12 18:35 GMT+02:00 Guido van Rossum <gu...@python.org>: >> Couldn't we use the order in the actual hash table (which IIUC now >> contains just indexes into the ordered vector of key/value/hash >> structs)? That would probably simulate the pre-3.6 order quite >> effectively. > > From what I understood, Python 3.6 dict got two *different* changes: > > * modify the dict structure to use two tables instead of only one: an > "index" table (the hash table) and a second key/value table > * tune the dict implementation to only append to the key/value table > > The second change depends on the first change. > > When a key is deleted, the entry is marked as DUMMY. When we add a new > item, DUMMY entries are skipped and we only append at the end of the > key/value table. Sometimes, the key/value table is compacted to free > memory: all DUMMY entries are removed. > > It would be possible to add a flag to allow to reuse DUMMY entries, > which means loosing the order. The order would only be lost when we > add the first item after we removed at least one entry (when the first > DUMMY entry is reused). > > The OrderedDict would set the flag to preserve the order. > > So technically, it is possible. The question is more what should be > the "default" dict :-) Ordered or not? :-) > > Victor -- --Guido van Rossum (python.org/~guido) _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
