[Python-Dev] More compact dictionaries with faster iteration

[Raymond Hettinger]

On Dec 10, 2012, at 4:06 AM, Mark Shannon <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
(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).  

Since hash tables aren't a new problem, there may
already be published research on the best way to handle
the entries array. 


Raymond



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