[Patches] [ python-Patches-729395 ] Dictionary tuning

[SourceForge.net]

Patches item #729395, was opened at 2003-04-29 04:03
Message generated for change (Comment added) made by gvanrossum
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=729395&group_id=5470

Category: Core (C code)
Group: Python 2.3
Status: Open
Resolution: None
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
Assigned to: Nobody/Anonymous (nobody)
Summary: Dictionary tuning

Initial Comment:
The idea is to make dictionaries more sparse on 
average (decreasing the density between 0 and 50%). 
This results in fewer collisions, faster collision 
resolution, fewer memory accesses, and better cache 
performance.  A small side-benefit is halving the 
number of expensive resize operations as the 
dictionary grows and reducing the cost of the resize 
operations.

The patch helps both smaller sized dictionaries and 
large ones.  It entails a one line change to dictobject.c 
resulting in a new schedule of dictionary sizes for a 
given number of entries:

Number of           Current size        Proposed size
Filled Entries      of dictionary       of dictionary
--------------      -------------       -------------
0 to 5                    8                   8
6 to 10                  16                  32
11 to 21                 32                  32
22 to 42                 64                 128
43 to 85                128                 128
86 to 170               256                 512
171 to 341              512                 512
  and so on until 100,000 entries where the old 
schedule takes over.

The 100,000 entry limit was added because of 
python-dev feedback about memory consumption in 
the presence of many large dictionaries.  At 12 bytes 
per entry on a 32-bit box, the switchback occurs at 
1.2 Mb for a single dict.  This ought to allow hundreds 
of large dictionaries on common memory sizes.

Performance improvements vary from application to 
application and across various hardware setups.  So 
far, typical results are from 0 to 5%.


----------------------------------------------------------------------

>Comment By: Guido van Rossum (gvanrossum)
Date: 2003-04-29 06:56

Message:
Logged In: YES 
user_id=6380

However note that I cannot reproduce the speedup on Zope 3
startup any more. It may have been something else in my
system. :-(

----------------------------------------------------------------------

Comment By: Guido van Rossum (gvanrossum)
Date: 2003-04-29 06:49

Message:
Logged In: YES 
user_id=6380

My preferred version, with code reordering suggested by Tim
and further refinement by me (dict2.diff)

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=729395&group_id=5470