[Python-Dev] More compact dictionaries with faster iteration

[Raymond Hettinger]

On Dec 10, 2012, at 7:04 PM, Mark Shannon <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.  
Further sniping and unsubstantiated FUD would not.


Raymond
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20121210/ddd3765c/attachment.html>