[Patches] [ python-Patches-671454 ] Optimize dictionary resizing
SourceForge.net
noreply@sourceforge.net
Mon, 05 May 2003 15:30:18 -0700
Patches item #671454, was opened at 2003-01-20 18:08
Message generated for change (Comment added) made by rhettinger
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=671454&group_id=5470
Category: Core (C code)
Group: Python 2.3
>Status: Closed
>Resolution: Accepted
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
Assigned to: Neal Norwitz (nnorwitz)
Summary: Optimize dictionary resizing
Initial Comment:
Revisiting Oren’s fastnames patch, I think a simpler
approach is warranted. Using a setitem macro skips
a function call but doesn’t get to the root of problem.
Likewise, a pointer search is not helpful because
lookupstring() already attempts a pointer
comparison first and a hash comparison as a
fallback (also, a pointer search fails to find non-
interned comparisons). There is more promise in
optimizing the search/fail/fallback sequence of
looking for locals, globals, and builtins, but the
approach of using custom look-ups and having
negative entries is too invasive.
The real issue is that the dictionaries are too full.
Whenever, it hits 2/3’s full, a resize is triggered which
doubles the size of the dictionary, still leaving it
relatively full and relatively close to the next
(expensive) resize operation.
This patch makes the setitem resize operation
quadruple the size of the dictionary. This leads to
fewer total resize operations and leaves the dictionary
more sparsely populated (not only leading to fewer
collisions, but allowing immediate detection of NOT IN
without doing *any* comparisons of pointers or
hashcodes).
The patch is minimally invasive. It is only one line!
However, is does change the order of dictionaries, so
doctest style test code will sense the change
immediately.
Four timing suites are attached. Two, directly
measure speed-ups for accessing globals and
__builtins__. The other two are real world apps
which tap into all facets of python including
subclassing, lambdas and functionals, large and
small dicts, a wide array of data structures, heavy
processing of strings, tuples, and numbers. Each of
the suites shows improvements ranging from 5% to
25%. PyStone also shows a marginal improvement
which is surprising because it is dominated by fast
locals.
----------------------------------------------------------------------
>Comment By: Raymond Hettinger (rhettinger)
Date: 2003-05-05 17:30
Message:
Logged In: YES
user_id=80475
Discussed on python-dev.
Added a limit at 50k entries.
Applied as Objects/dictobject.c 2.145.
Documented remaining research
Objects/dictnotes.txt
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2003-02-11 20:59
Message:
Logged In: YES
user_id=80475
I timed many different dictionary tune-ups and found that
the optimal combination varies depending on the
benchmark and needs of the application (uniquifying is
store intensive and membership testing is retrieve
intensive). The results also vary from processor to
processor, and they depend on the amount/type of cache
memory available.
The tuning options include varying the dict resize trigger
ratio from 2/3, altering the size of smalldict, quadrupling
space upon resize, and special casing smaller dictionaries.
At some point, I'll post the best of these and everyone can
try it with their own apps and machine. All of the above
parameters can be set arbitrarily and there is no reason to
think that the current settings are the optimum for most
time critical applications.
The attached patch is simple and gives some
improvement to many applications. I hesitate to push it
forward with more independent timings in different
environments.
----------------------------------------------------------------------
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=671454&group_id=5470