[New-bugs-announce] [issue23971] dict(list) and dict.fromkeys() doesn't account for 2/3 fill ratio
report at bugs.python.org
Thu Apr 16 01:35:44 CEST 2015
New submission from Larry Hastings:
Matt Mackall brought this over to me today.
If list "l" has one million pairs and you do
it creates the dict, then resizes it to a million elements, then starts adding name/value pairs. But since it's sized to a million elements, it gets beyond its "fill ratio" comfort level of 666k and resizes. And when you're up to a million elements, the resize is quite slow. It should have internally resized the dict correctly from the beginning such that no resize was necessary.
The same is true for dict.fromkeys--passed in a list of 1m elements, it uses an initial size of 1m, not 1.5m.
Attached is a sample patch to change the behavior of both these operations so no resizes are needed during the insertions. I haven't checked that it actually fixes the behavior, I just made the change and ran the regression test. (I'm oversubscribed here at the sprints, and am kind of rushing this diff out just to get the conversation rolling.)
Benjamin: what do you think? Would it be appropriate to make a change like this in 2.7?
Python 3 (or at least 3.5 trunk) is fancy here. It starts with the minimum size of a dict, then iterates until the new size is > 1.5*the number of elements. This means the dicts it creates are of the same size as they would be if we'd started with a minsize dict and inserted one element at a time. This might help minimize wear and tear on the small block allocator for smaller dicts.
BTW, the internal function _PyDict_NewPresize should really have taken the fill ratio into account too. But, even though it's an internal-only function, it's probably too late to change its behavior.
components: Interpreter Core
nosy: benjamin.peterson, larry, marmoute, mpm
stage: patch review
title: dict(list) and dict.fromkeys() doesn't account for 2/3 fill ratio
versions: Python 2.7
Python tracker <report at bugs.python.org>
More information about the New-bugs-announce