[Python-Dev] More compact dictionaries with faster iteration

[Mark Shannon]

On 10/12/12 23:39, Raymond Hettinger wrote:
>
> On Dec 10, 2012, at 4:06 AM, Mark Shannon <mark at hotpy.org
> <mailto:mark at hotpy.org>> wrote:
>
>>> Instead, the 24-byte entries should be stored in a
>>> dense table referenced by a sparse table of indices.
>>
>> What minimum size and resizing factor do you propose for the entries
>> array?
>
> There are many ways to do this.  I don't know which is best.
> The proof-of-concept code uses the existing list resizing logic.
> Another approach is to pre-allocate the two-thirds maximum

What do you mean by maximum?

> (This is simple and fast but gives the smallest space savings.)
> A hybrid approach is to allocate in two steps (1/3 and then 2/3
> if needed).

I think you need to do some more analysis on this. It is possible that 
there is some improvement to be had from your approach, but I don't 
think the improvements will be as large as you have claimed.

I suspect that you may be merely trading performance for reduced memory
use, which can be done much more easily by reducing the minimum size
and increasing the load factor.

Cheers,
Mark.