__bases__ misleading error message

[Terry Reedy]

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