[issue13903] New shared-keys dictionary implementation

[Jim Jewett]

Jim Jewett <jimjjewett at gmail.com> added the comment:

As of Feb 28, 2012, the PEP mentions an additional optimization of storing the values in an array indexed by (effectively) key insertion order, rather than key position. ("Alternative Implementation")

It states that this would reduce memory usage for the values array by 1/3.  1/3 is a worst-case measurement; average is 1/2.  (At savings of less than 1/3, the keys would resize, to initial savings of 2/3.  And yes, that means in practice, the average savings would be greater than half, because the frequency of dicts of size N decreases with N.)

It states that the keys table would need an additional "values_size" field, but in the absence of dummies, this is just ma_used.

Note that this would also simplify resizing, as the values arrays would not have to be re-ordered, and would not have to be modified at all unless/until that particular instance received a value for a position beyond its current size.

----------
nosy: +Jim.Jewett

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue13903>
_______________________________________