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

Raymond Hettinger raymond.hettinger at gmail.com
Mon Jun 18 22:46:25 CEST 2012

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>

More information about the Python-Dev mailing list