On 1/25/2015 7:00 AM, Steven D'Aprano wrote:
What happens inside the dictionary? Dictionaries are "hash tables", so they
are basically a big array of cells, and each cell is a pair of pointers,
one for the key and one for the value:
[dictionary header]
[blank]
[blank]
[ptr to the string 'y', ptr to the int 42]
At the moment, for CPython, each entry has 3 items, with the first being
the cached hash of the key. Hash comparison is first used to test
whether keys are equal.
[hash('y'), ptr('y'), ptr(42)]
[blank]
[ptr to 'x', ptr to 23]
[blank]
[blank]
[blank]
[ptr to 'colour', ptr to 'red']
[blank]
As you say, these are implementation details. CPython dicts for the
instances of at least some classes have a different, specialized
structure, with two arrays.
In the above, [blank] entries, which are about 1/2 to 2/3 of the
entries, take the same space as real entries (12 to 24 bytes). Raymond
H. has proposed that the standard dict have two arrays like so:
1. the first array is a sparse array of indexes into the second array:
[b, b, 2, b, 0, b, b, b, 1, b] (where b might be -1 interpreted as
<blank>), using only as many bytes as needed for the maximum index.
2. the second array is a compact array of entries in insertion order,
such as
[hash, ptr to 'x', ptr to 23]
[hash, ptr to 'colour', ptr to 'red']
[hash, ptr to the string 'y', ptr to the int 42]
Iteration would use the compact array, making all dicts OrderedDicts.
Pypy has already switched to this. It seems that on modern processors
with multilevel on-chip caches, the space reduction leads to cache-miss
reductions that compensate for the indirection cost.
--
Terry Jan Reedy
--
https://mail.python.org/mailman/listinfo/python-list
