[Tim Delaney]

...

What is the effect on peak memory usage over "average" programs?

[Raymond Hettinger]

Since the amortized growth is the same, the effect is Nil on average. Special cases can be contrived with a specific number of records where the memory use is doubled, but in general it is nearly unchanged for average programs.

That doesn't make sense. Dicts can be larger after the patch, but never smaller, so there's nothing opposing the "can be larger" part: on average, allocated address space must be strictly larger than before. Whether that *matters* on average to the average user is something we can answer rigorously just as soon as we find an average user with an average program <wink>. I'm not inclined to worry much about it.

...

This might be a worthwhile speedup on small dicts (up to a TBD number of entries) but not worthwhile for large dicts.

Actually, it helps large dictionaries even more that small dictionaries. Collisions in large dicts are resolved through other memory probes which are almost certain not to be in the current cache line.

That part makes sense. Resizing a large dict is an expensive operation too.

...

However, to add this capability in would of course add more code to a very common code path (additional test for current size to decide what factor to increase by).

Your intuition is exactly correct. All experiments to special case various sizes results in decreased performance because it added a tiny amount to some of the most heavily exercised code in python.

This part isn't clear: the changed code is in the body of an if() block that normally *isn't* entered (over an ever-growing dict's life, it's entered O(log(len(dict))) times, and independent of the number of dict lookups). The change cuts the number of times it's entered by approximately a factor of 2, but it isn't entered often even now.

Further, it results in an unpredicable branch which is also not a good thing.

Since the body of the loop isn't entered often, unpredictable one-shot branches within the body shouldn't have a measurable effect. The unpredictable branches when physically resizing the dict will swamp them regardless. The surrounding if-test continues to be predictable in the "branch taken" direction. What could be much worse is that stuffing code into the if-block bloats the code so much as to frustrate lookahead I-stream caching of the normal "branch taken and return 0" path: if (mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2) { if (dictresize(mp, mp->ma_used*2) != 0) return -1; } return 0; Rewriting as if (mp->ma_used <= n_used || mp->ma_fill*3 < (mp->ma_mask+1)*2) return 0; return dictresize(mp, mp->ma_used*2) ? -1 : 0; would help some compilers generate better code for the expected path, and especially if the blob after "return 0;" got hairier. IOW, if fiddling with different growth factors at different sizes slowed things down, we have to look for something that affected the *normal* paths; it's hard to imagine that the the guts of the if-block execute often enough to matter (discounting its call to dictresize(), which is an expensive routine).

I found out that timing dict performance was hard. Capturing memory usage was harder. Checking entry space,space plus unused space, calls to PyMalloc, and calls to the os malloc, only the last is important, but it depends on all kinds of things that are not easily controlled.

In my early Cray days, the Cray boxes were batch one-job-at-a-time, and all memory was real. If you had a CPU-bound program, it took the same number of nanoseconds each time you ran it. Benchmarking was hard then too <0.5 wink>.

[Tim Delaney]

...

What is the effect on peak memory usage over "average" programs?

[Raymond Hettinger]

Since the amortized growth is the same, the effect is Nil on average. Special cases can be contrived with a specific number of records where the memory use is doubled, but in general it is nearly unchanged for average programs.

That doesn't make sense. Dicts can be larger after the patch, but never smaller, so there's nothing opposing the "can be larger" part: on average, allocated address space must be strictly larger than before. Whether that *matters* on average to the average user is something we can answer rigorously just as soon as we find an average user with an average program <wink>. I'm not inclined to worry much about it.

...

This might be a worthwhile speedup on small dicts (up to a TBD number of entries) but not worthwhile for large dicts.

Actually, it helps large dictionaries even more that small dictionaries. Collisions in large dicts are resolved through other memory probes which are almost certain not to be in the current cache line.

That part makes sense. Resizing a large dict is an expensive operation too.

...

However, to add this capability in would of course add more code to a very common code path (additional test for current size to decide what factor to increase by).

Your intuition is exactly correct. All experiments to special case various sizes results in decreased performance because it added a tiny amount to some of the most heavily exercised code in python.

This part isn't clear: the changed code is in the body of an if() block that normally *isn't* entered (over an ever-growing dict's life, it's entered O(log(len(dict))) times, and independent of the number of dict lookups). The change cuts the number of times it's entered by approximately a factor of 2, but it isn't entered often even now.

Further, it results in an unpredicable branch which is also not a good thing.

Since the body of the loop isn't entered often, unpredictable one-shot branches within the body shouldn't have a measurable effect. The unpredictable branches when physically resizing the dict will swamp them regardless. The surrounding if-test continues to be predictable in the "branch taken" direction. What could be much worse is that stuffing code into the if-block bloats the code so much as to frustrate lookahead I-stream caching of the normal "branch taken and return 0" path: if (mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2) { if (dictresize(mp, mp->ma_used*2) != 0) return -1; } return 0; Rewriting as if (mp->ma_used <= n_used || mp->ma_fill*3 < (mp->ma_mask+1)*2) return 0; return dictresize(mp, mp->ma_used*2) ? -1 : 0; would help some compilers generate better code for the expected path, and especially if the blob after "return 0;" got hairier. IOW, if fiddling with different growth factors at different sizes slowed things down, we have to look for something that affected the *normal* paths; it's hard to imagine that the the guts of the if-block execute often enough to matter (discounting its call to dictresize(), which is an expensive routine).

I found out that timing dict performance was hard. Capturing memory usage was harder. Checking entry space,space plus unused space, calls to PyMalloc, and calls to the os malloc, only the last is important, but it depends on all kinds of things that are not easily controlled.

In my early Cray days, the Cray boxes were batch one-job-at-a-time, and all memory was real. If you had a CPU-bound program, it took the same number of nanoseconds each time you ran it. Benchmarking was hard then too <0.5 wink>.