[Patches] [ python-Patches-729395 ] Dictionary tuning
SourceForge.net
noreply@sourceforge.net
Mon, 05 May 2003 13:21:06 -0700
Patches item #729395, was opened at 2003-04-29 03:03
Message generated for change (Comment added) made by montanaro
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: 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