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

Tue, 06 May 2003 16:46:44 -0700

Patches item #729395, was opened at 2003-04-29 03:03
Message generated for change (Comment added) made by rhettinger
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: Closed
Resolution: Accepted
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
Assigned to: Raymond Hettinger (rhettinger)
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: Raymond Hettinger (rhettinger)
Date: 2003-05-06 18:46

Message:
Logged In: YES 
user_id=80475

Yes, in both places, the resize argument of mp-
>ma_used*3/2 should be changed to mp->ma_used*2.

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

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-05-05 19:36

Message:
Logged In: YES 
user_id=80475

Most likely, yes, but I would like a day to think about the 
use cases and implications before saying for certain.

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

Comment By: Guido van Rossum (gvanrossum)
Date: 2003-05-05 19:16

Message:
Logged In: YES 
user_id=6380

Should the other calls to dictresize() also be changed?

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

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-05-05 17:23

Message:
Logged In: YES 
user_id=80475

Applied to Objects/dictobject.c 2.145
Closing patch.

Thanks to all who contributed, timed, or encouraged.

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

Comment By: Guido van Rossum (gvanrossum)
Date: 2003-05-05 15:29

Message:
Logged In: YES 
user_id=6380

I say, check it in, it can't hurt. A comment in the code
should explain the considerations though.

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

Comment By: Skip Montanaro (montanaro)
Date: 2003-05-05 15:21

Message:
Logged In: YES 
user_id=44345

Using Guido's version I saw a consistent improvement in pystone numbers.
I ran it five times each with and without the patch.  Every "after" run was
faster than every "before" run and comparing the fastest run of each showed
a 5.4% improvement (13587 vs. 14326.6 pystones).  I also ran the pystone
benchmark using python -i and then used ps to examine the memory usage
after completion.  VM and RSS both increased modestly (VM by 0.2%, from
27936 to 27984 and 2.2%, RSS from 3520 to 3600).  Not a big deal in my
book, but I'm one of those people w/ 1GB of RAM Tim referred to. ;-)

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

Comment By: Guido van Rossum (gvanrossum)
Date: 2003-04-29 05: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 05: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