[issue28731] _PyDict_NewPresized() creates too small dict

[INADA Naoki]

INADA Naoki added the comment:

On Fri, Nov 18, 2016 at 9:31 PM, Serhiy Storchaka
<report at bugs.python.org> wrote:
>
> Serhiy Storchaka added the comment:
>
> The condition in the loop in _PyDict_NewPresized() contains the test newsize > 0. This is a check for integer overflow. But it doesn't make much sense. First, the overflow is undefined behavior, and it is too late to detect it when it already is happen. Second, after detecting the negative value just is passed to new_keys_object() which either is crashed in debug build or makes other integer overflow and creates invalid object.
>
> I would add a runtime check that minused is less than PY_SSIZE_MAX/3 (or more strong PY_SSIZE_MAX/3*2/sizeof(Pobject *)). This would guarantee that integer overflow is not possible. The test "newsize > 0" could be removed.
>
> There is similar code in dictresize().
>

Nice idea.  I'll update patch in issue28147.

In case of _PyDict_NewPresized(minused), it would be called from 3rd
party libraries, and there are no strong
guarantee about PyDict_SetItem() won't resize until minused items.
So how about more small, maximum presize?

#define MAX_INITSIZE (128 * 1024)

if (minused > USABLE_FRACTION(MAX_INITSIZE)) {
    newsize = MAX_INITSIZE;
}
else {
    newsize = PyDict_MINSIZE;
    whilie (newsize < minused)
        newsize <<= 1;   // Can't we assume *= 2 is optimized?
};

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue28731>
_______________________________________