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

[Raymond Hettinger]

On Jun 18, 2012, at 12:35 PM, Antoine Pitrou wrote:

> You are right. I was thinking 50 nanoseconds (which for a - relatively
> high-end - 3GHz CPU puts us at 150 cycles).

The last guidance I read from Intel said that
a cache miss was roughly as expensive as a floating-point divide.

When a dictionary is less sparse, it has more collisions
which means there are more cache misses.

Resizing into a dictionary growing at 2x means that we're going
from 2/3 full to 1/3 full and resizing at 4x means going from 2/3
full to 1/6 full.  That latter will have fewer collisions (that said,
one-third full is still very good).  So, the performance is worse
but not much worse.

For dictionaries large enough to require multiple resizes,
the 4x factor cuts the number of resizes in half and makes
each resize faster (because of few collisions).   Only the 
growth phase is affected though.

It is more problematic for use cases such as caching where
a dict is constantly deleting old entries to make space for
new ones.  Such a dict never reaches a steady-state
because the dummy entries accumulate and trigger a resize.
Under the 2x scheme this happens much more often.

Under the 4x scheme, some dicts are left larger (more sparse)
than they otherwise would be (i.e. formerly it grew 8, 32, 128, ...)
and now it grows to (8, 16, 32, 64, ...).  Some dicts will end-up
the same dicts.  Others might fit in 16 rather than 32.  That
decreases their sparsity, increases the number of collisions,
and slows the lookup speed.  The effect is not large though
(the number of collisions between 1/4 full and 1/2 full is better
but 1/2 is still pretty good).

In the timings, I had done a few years ago, the results were that
just about anything that increased the number of collisions or
resizings would impact performance.   I expect that effect will
be accentuated on modern processors but I'll have to do updated
tests to be sure.

From a high-level view, I question efforts to desparsify dictionaries.
When you have a bucket of water, the weight is in the water, not
in the bucket itself.   The actual keys and values dominate dict size
unless you're reusing the same values over and over again.

That said, the 4x growth factor was capped at 50,000.  For larger
dicts it fell back to 2x.  Some the only dicts affected by the 2x vs 4x
decision lie by in the 6 to 50k ranges.  The only apps that see any
noticeable difference in memory size are ones that have many
dicts of that size range alive at the same time.

Sorry I can make a more detailed post right now.  I'll make time in
the next couple of weeks to post some code and timings that
document the collision counts, total memory size, and its affect
on various dict use cases.


Raymond






-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20120618/87da0f69/attachment.html>