[Python-Dev] More compact dictionaries with faster iteration

[Mark Shannon]

On 11/12/12 03:45, Raymond Hettinger wrote:
>
> On Dec 10, 2012, at 7:04 PM, Mark Shannon <mark at hotpy.org
> <mailto:mark at hotpy.org>> wrote:
>
>>> Another approach is to pre-allocate the two-thirds maximum
>>> (This is simple and fast but gives the smallest space savings.)
>>
>> What do you mean by maximum?
>
> A dict with an index table size of 8 gets resized when it is two-thirds
> full,
> so the maximum number of entries is 5.  If you pre-allocate five entries
> for the initial dict, you've spent 5 * 24 bytes + 8 bytes for the indices
> for a total of 128 bytes.  This compares to the current table of 8 * 24
> bytes
> totaling 192 bytes.
>
> Many other strategies are possible.  The proof-of-concept code
> uses the one employed by regular python lists.
> Their growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ....
> This produces nice memory savings for entry lists.
>
> If you have a suggested allocation pattern or other
> constructive suggestion, it would be would welcome.
It seems like a reasonable starting point.
Trying to avoid resizing the index array and the entries array at the 
same time is probably a good idea.

> Further sniping and unsubstantiated FUD would not.

Is asking that you back up your claims with some analysis
that unreasonable?

When you make claims such as
"""
The memory savings are significant (from 30% to 95%
compression depending on the how full the table is).
Small dicts (size 0, 1, or 2) get the most benefit.
"""
is it a surprise that I am sceptical?

I like you idea. I just don't want everyone getting their
hopes up for what may turn out to be a fairly minor improvement.

Don't forget Unladen Swallow :)

Cheers,
Mark.