> In addition to space savings, the new memory layout makes iteration faster.
> Currently, keys(), values, anditems() loop over the sparse table, skipping-over free slots in the hash table.
> Now, keys/values/items can loop directly over the dense table, using fewer memory accesses.
The "dense table" is the array of values. The "sparse table" is the actual hash table, only the values index into the values array.
I thought the insertion ordering was implemented at around the same time as a result of it. The data structure ensures it pretty much for free, seemed like the obvious next step. It appears I was mistaken about that.
They did implement insertion ordering at that time, but they didn't want to commit to adding it to the official language semantics until having enough experience to know whether they wanted to back out the change to the implementation which provided that guarantee for free.
In case anyone is curious about it:
https://mail.python.org/pipermail/python-dev/2012-December/1...
> In addition to space savings, the new memory layout makes iteration faster.
> Currently, keys(), values, anditems() loop over the sparse table, skipping-over free slots in the hash table.
> Now, keys/values/items can loop directly over the dense table, using fewer memory accesses.
The "dense table" is the array of values. The "sparse table" is the actual hash table, only the values index into the values array.
I thought the insertion ordering was implemented at around the same time as a result of it. The data structure ensures it pretty much for free, seemed like the obvious next step. It appears I was mistaken about that.