[C API] Add PyDict_NewPresized() function

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

pythongh-139772: Add PyDict_NewPresized() function

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.

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?

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.

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().

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.

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

Preallocation is really tempting. Some users loving microbenchmarks want it even though there are no guarantee about keys uniqueness.

How about adding PyDict_NewPresized(Py_ssize_t expected_size, int unicode_keys) that is same to dict_new_presized()?
_PyDict_NewPresized(minsize) would be deprecated.

I'd be happy to have a PyDict_FromItems(PyObject *const *keys, PyObject *const *values, Py_ssize_t length) instead that creates a dict from C arrays of keys and values.

There's _PyDict_FromItems() which allows defining steps for the keys and values arrays, but I doubt that that'd be commonly useful as a public API. The simpler form seems to cover the main use cases.

To be sure that it matches Python's semantics, I just tested the following in Py3.12:

>>> class HashBoom:
...     n = 2
...     def __init__(self):
...         print("create", self.n)
...         self.c = self.n
...         HashBoom.n -= 1
...     def __hash__(self):
...         print("hash", self.c)
...         if self.c == 0:
...             raise RuntimeError()
...         return self.c
...     def __eq__(self, other):
...         print("eq", self.c)
...         return self.c == other.c
... 
>>> d = {
...     HashBoom(): 2,
...     HashBoom(): 1,
...     HashBoom(): 0,
...     HashBoom(): -1,
... }
create 2
create 1
create 0
create -1
hash 2
hash 1
hash 0
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 10, in __hash__
RuntimeError

So it's "first create all, then insert all", as the proposed C-API function would implement.

pythongh-139772: Add PyDict_FromItems() function

pythongh-139772: Add PyDict_NewPresized() function

How about adding PyDict_NewPresized(Py_ssize_t expected_size, int unicode_keys) that is same to dict_new_presized()?
_PyDict_NewPresized(minsize) would be deprecated.

Ok, I updated #139773 to add unicode_keys parameter.

For API users' point of view, PyDict_NewPresized(size, unicode_keys) is more useful than PyDict_FromItems(). Not all users have keys and values array.

I think the two APIs serve different use cases that are both valid. The first is more low-level, the other more high-level (from a C point of view).

High-level APIs are only useful when they match typical use cases.

In CPython, _PyDict_FromItems() is used when building map from stack.
How third parties use _PyDict_FromItems() if we have PyDict_NewPresized(size, unicode_keys) too?

How third parties use _PyDict_FromItems() if we have PyDict_NewPresized(size, unicode_keys) too?

So, I looked through a bit of code and with vectorcalls taking many keyword dicts away, constant sized dicts have become a lot less important these days, apart from literals. The "FromItems" function is really mostly for convenience (thus, high-level) and therefore not required. It does have the advantage, though, that the Python runtime can see the full set of keys and values upfront and might decide to use a specifically adapted dict layout or implementation. PyPy might benefit from that, for example, as might other Python implementations.

If the intention is to keep the API small, then PyDict_NewPresized() with the additional unicode_keys option would cover the immediate need. Type knowledge about the keys will often be available on user side, so being able to pass that in seems the right approach. A question is then whether this will remain the only relevant configuration option and whether "unicode keys or not" will remain relevant for future dict implementations. I don't know. Maybe. But the dict implementation has already gone through several iterations and I could imagine future specialisations for other types of keys, e.g. integers. C doesn't easily allow extending the interface here.

What do you think of allowing the Py_TPFLAGS_XXX_SUBCLASS flags as option values to specify a known homogeneous key type? They could even be |-ed if the keys are a mix of more than one type, in case the runtime can ever make use of that.

Using Py_TPFLAGS wouldn't be future-friendly: we can't add new flags to that field any more.
Also, I don't think we want to allow subclasses -- the optimizations I can imagine will want to erase the Python type, so they'll need exact str or exact small int.

I guess that argument should be a type object -- you can't | those together, but it would make for more regular API.
And I think it should be a hint, not a promise (unless that hurts performance). Putting in a subclass instance should be fine (though perhaps slow), so we'd need type checks anyway.

pythongh-139772: Add PyDict_FromItems() function

cext: remove `_dict_new_presized` util

After months of exploring different PyDict APIs, I decided to give up on this optimization: see capi-workgroup/decisions#90 (comment).

In msgspec we get two-digit percents speed-up from using _PyDict_NewPresized() API.
I was expecting that new PyDict_NewPresized(size, unicode) API would be available soon :(
But, instead I found that this issue is now closed.

See msgspec/msgspec#1243

Navigation Menu

Repository navigation

[C API] Add PyDict_NewPresized() function #139772

Linked PRs

Minsize issue

Unicode issue

Distinct-keys issue

The false size header problem

2 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

[C API] Add PyDict_NewPresized() function #139772

Description

Linked PRs

Activity

methane commented on Oct 9, 2025

vstinner commented on Oct 9, 2025

methane commented on Oct 10, 2025

methane commented on Oct 10, 2025

Minsize issue

Unicode issue

Distinct-keys issue

The false size header problem

methane commented on Oct 10, 2025

methane commented on Oct 10, 2025

methane commented on Oct 11, 2025

scoder commented on Oct 11, 2025

2 remaining items

vstinner commented on Oct 12, 2025

scoder commented on Oct 17, 2025

methane commented on Oct 18, 2025

scoder commented on Oct 19, 2025

encukou commented on Oct 20, 2025

vstinner commented on May 29, 2026

sobolevn commented on Oct 11, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions