[Python-Dev] Tunable parameters in dictobject.c (was dictnotes.txt out of date?)

[Mark Shannon]

Raymond Hettinger wrote:
> 
> On Jun 13, 2012, at 10:35 AM, Eli Bendersky wrote:
> 
>> Did you mean to send this to the list, Raymond?
> 
> 
> Yes.  I wanted to find-out whether someone approved changing
> all the dict tunable parameters.   I thought those weren't supposed
> to have changed.  PEP 412 notes that the existing parameters
> were finely tuned and it did not make recommendations for changing them.

The PEP says that the current (3.2) implementation is finely tuned.
No mention is made of tunable parameters.

> 
> At one point, I spent a full month testing all of the tunable parameters
> using dozens of popular Python applications.  The values used in Py3.2
> represent the best settings for most apps.  

Best in terms of speed, but what about memory use?

> They should not have been
> changed without deep thought and substantial testing.

I have thought about it, a lot :)
I have also tested it, using the Unladen Swallow benchmarks.
Additional (realistic) tests would be appreciated.

> 
> The reduction of the dict min size has an immediate impact on code
> using multiple keyword arguments.

There is no change to the minimum size for combined-table (old style)
dictionaries.

> 
> The reduced growth rate (from x4 to x2) negatively impacts apps that
> have a dicts with a steady size but constantly changing keys
> (removing an old key and adding a new one).  The lru_cache is
> an example.   The reduced growth causes it to resize much more
> frequently than before.

Resizing was probably the part of the implementation that took the most 
time.

I had gained the impression from comments on this list,
comments on the tracker and the web in general that the memory 
consumption of CPython was more of an issue than its performance.
So my goal was to minimise memory usage without any significant slowdown
(< 1% slowdown).

The problem with resizing is that you don't know when it is going to 
stop. A bigger growth factor means fewer resizes, but more of a 
potential overshoot (a larger final size than required).
So in order to reduce memory use a growth factor of x2 is required.

Split-table dicts are (to a first-order approximation) never resized
so the growth factor for them should as small as possible; x2.

Combined-table dicts are more challenging. Reducing the growth rate to 
x2 increases the number of resizes by x2 or (x2-1) *and* increases the 
number of items per resize by about 50%.
But it is not the number of resizes that matters, it is the time spent 
performing those resizes.
I went to considerable effort to improve the performance of dictresize()
so that even benchmarks that create a lot of short-lived medium-to-large 
  sized combined-table dicts do not suffer impaired performance.

It would be possible to split the growth factor into two: one for 
split-tables (which would be x2) and one for combined tables.

But which is better for combined tables, x4 or x2?
What is the relative value of speed and memory consumption?
50% less memory and 1% slower is good. 1% less memory and 50% slower is 
bad. But what about intermediate values?

I think that for combined tables a growth factor of x2 is best,
but I don't have any hard evidence to back that up.

> 
> I think the tunable parameters should be switched back to what they
> were before.  Tim and others spent a lot of time getting those right
> and my month of detailed testing confirmed that those were excellent
> choices.

They may have been excellent choices for the previous implementation.
They are not necessarily the best for the new implementation.

The current parameters seem to be the best for the new implementation.
When Django and Twisted run on Python3, then it might be worthwhile to
do some more experimentation.

> 
> The introduction of Mark's shared-key dicts was orthogonal to the
> issue of correct parameter settings.  Those parameters did not have
> to change and probably should not have been changed.

Parameters for tuning code and the code itself are unlikely to be
orthogonal. While I did strive to minimise the impact of the changes on
combined-table dicts, the performance characteristics have necessarily
changed.

Cheers,
Mark.