[C API] Add PyDict_NewPresized() function

[vstinner]

There is a private _PyDict_NewPresized() function which is used by 11 projects of the PyPI top 15,000 projects:

• Nuitka (2.7.16)
• cython (3.1.4)
• frozendict (2.4.6)
• gevent (25.9.1)
• mercurial (7.1.1)
• mypy (1.18.2)
• mypy_dev-1.19.0a2
• numba (0.62.0)
• orjson (3.11.3)
• ormsgpack (1.10.0)
• serpyco_rs (1.17.1)

I propose to make the function public.

Linked PRs

• gh-139772: Add PyDict_NewPresized() function #139773
• gh-139772: Add PyDict_FromItems() function #139963
• gh-139772: Add PyDict_FromKeysAndValues() function #141682

[methane]

I don't want to make this API public. Most users either overestimate its effectiveness or don't fully understand how it operates.
I will check how this API is used in the modules you listed.

[vstinner]

Most users either overestimate its effectiveness or don't fully understand how it operates.

Do you mean that it's not efficient to preallocate enough entries in the dictionary?

The strange thing about _PyDict_NewPresized() is that it's not used in Python.

Should we deprecate the function instead, and guide users towards PyDict_New() instead?

[methane]

• Nuitka (2.7.16), cython (3.1.4): They generate code. I don't know how they are used.
• frozendict (2.4.6): It just copies cpython source code. It doesn't use this API.
• gevent (25.9.1): cython generated code uses the API. No performance gain.
• mercurial (7.1.1): They seem to be using that API in the wrong way.
• mypy (1.18.2), mypy_dev-1.19.0a2: same to gevent. No performance gain.
• numba (0.62.0): idk how it have performance gain. it have unicode issue I will explain later.
• orjson (3.11.3), ormsgpack (1.10.0), serpyco_rs (1.17.1): They have unicode and distinct-keys issue.

[methane]

As a C programmer, it's natural to want to use a presized constructor to avoid reallocations. But preallocating a dict is not as straightforward as for a list.

Minsize issue

Dict minsize is 8 (5 entries). For size <= 5, _PyDict_NewPresized() calls _PyDict_New(). It is just an overhead.

gevent and mypy has this issue.

Unicode issue

Current dict implementation has optimization for all keys are unicode. But _PyDict_NewPresized() doesn't provide information about all keys are unicode or not.
On the other hand, PyDict_New() doesn't allocate hashtable. First PyDict_SetItem() allocates minsize keys table with information the first key is unicode or not.

This is the main reason why CPython itself doesn't use _PyDict_NewPresized().
CPython uses _PyDict_FromItems() instead.

Most of libraries listed above have this issue.

Distinct-keys issue

Using _PyDict_NewPresized() without counting distinct-keys would waste much RAM.

>>> j = '{' + ','.join(['"foo":1']*1000)+ '}'
>>> import orjson
>>> import sys
>>> d=orjson.loads(j)
>>> len(d)
1
>>> sys.getsizeof(d)
36952

The false size header problem

msgpack includes the size in the container header for preallocation.
But by crafting a false size header, you can request the preallocation of a dict with 100 million elements using just 10 bytes of msgpack data.

This is a problem for lists as well, but it becomes more serious for dicts because they have a larger memory overhead per element.
That's why in msgpack-python, which I maintain, we don't use _PyDict_NewPresized().

[methane]

I created an issue to mercurial.
https://foss.heptapod.net/mercurial/mercurial-devel/-/issues/10029

Despite its over-allocation, it seems mercurial doesn't have unicode-issue because they use bytes for paths.

[methane]

I created an issue to Cython.
cython/cython#7201