[Python-Dev] Python 3.6 dict becomes compact and gets a private version; and keywords become ordered

[INADA Naoki]

On Tue, Sep 13, 2016 at 1:35 AM, Guido van Rossum <guido at python.org> wrote:
> 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.

Maybe, it can.
But current implementation may be faster on iteration, thanks to
hardware prefetch of CPU.
When sizeof(entry) is 24 (amd64), only 2.66... entries can be on cache line.


> But we'd have to add a new API to reveal the order (in effect just
> what Nick wanted). How much of the OrderedDict can be implemented just
> by adding new methods (IOW without changing the data structure)?

Current data structure uses fixed capacity, mostly append only array
for entries.

To implement `OrderedDict.move_to_end(last=False)`, OrderedDict should be
implement more hack. (e.g. use the array as ring.)