[Python-Dev] More compact dictionaries with faster iteration

[Raymond Hettinger]

On Jan 6, 2013, at 1:40 PM, Kristján Valur Jónsson <kristjan at ccpgames.com> wrote:

> The memory part is also why I am interested in this approach.
> Another thing has been bothering me.  This is the fact that with the default implementation, the smll table is only ever populated up to a certain percentage, I cant recall, perhaps 50%.  

Dicts resize when the table is over two-thirds full.   Small dicts contain zero to five keys.

> Since the small table is small by definition, I think it ought to be worth investigating if we cannot allow it to fill to 100% before growing, even if it costs some collisions.  A linear lookup in a handful of slots can't be that much of a bother, it is only with larger number of entries that the O(1) property starts to matter.

I looked at this a few years ago and found that it hurt performance considerably.   Uncle Timmy (and others) had done a darned fine job of tuning dictionaries. 


Raymond

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