Add `PyDict_NewPresized()` function

[vstinner]

Hi,

The private _PyDict_NewPresized(size) function is used by 11 projects of the PyPI top 15,000 projects. The problem is that it miss the unicode_keys parameter which is a hint to announce if keys are Unicode or not. @methane analyzed how _PyDict_NewPresized(size) is used in various projects and suggests adding a public PyDict_NewPresized(size, unicode_keys) function. See python/cpython#139772 for the discussion.

API: PyObject* PyDict_NewPresized(Py_ssize_t size, int unicode_keys)

• Return a new empty dictionary with preallocated items, or NULL on failure.
• size is a hint to preallocate items.
• If unicode_keys is non-zero, optimize lookup for Unicode keys.

Pull request.

Since unicode_keys is an implementation detail, I hesitate to put the function in the PyUnstable category: PyUnstable_Dict_NewPresized(). What do you think?

Vote:

• @erlend-aasland
• @encukou
• @serhiy-storchaka
• @vstinner
• @zooba

[vstinner]

PyDict_NewPresized() is between 1.03x and 1.10x faster than PyDict_New() to create a dictionary with Unicode keys.

[encukou]

11 is not a lot...
For implementation details: why expose unicode_keys, and not for example key-sharing?
Do we guarantee that if you do size insertions, the dict need to reallocate new memory?

PyDict_NewPresized() is between python/cpython#139773 (comment) than PyDict_New() to create a dictionary.

How much faster would it be with non-str keys?

[vstinner]

11 is not a lot...

I'm trying to add public functions for the remaining private functions used by Cython and other projects.

But well, it's a micro-optimization, and some people like to gain 5% when possible :-)

PyO3 expressed interest to use this function if it becomes public. Currently, PyO3 tries to avoid private functions.

For implementation details: why expose unicode_keys, and not for example key-sharing?

I have no idea. @methane: Do you have an opinion on that?

Do we guarantee that if you do size insertions, the dict need to reallocate new memory?

I expect that when you call PyDict_NewPresize(n, unicode_keys), no reallocation is needed to add up to n items. @methane told me that n is just a hint to preallocate, it's not a warranty. But in practice, PyDict_NewPresize() is faster than PyDict_New() is my benchmark.

How much faster would it be with non-str keys?

PyDict_NewPresized() is between 1.04x and 1.10x faster than PyDict_New() to create a dictionary with integer keys. My benchmark only measured the time to create a dictionary.

[methane]

PyDict_NewPresized() is between 1.03x and 1.10x faster than PyDict_New() to create a dictionary with Unicode keys.

This benchmark uses PyUnicode_FromFormat and PyLong_FromLong in the loop.
In real-world use cases like JSON decoding, key or value object creation does happen, but you can expect a bit more benefit in use cases like constructing a dict for kwargs contains a dozen keys.

For implementation details: why expose unicode_keys, and not for example key-sharing?

PyDict_NewPresize() is not suitable for building key-sharing dict.
For that, we need to enumerate use cases and design an API that is easy to use for all of them.
Maybe, csv parser, dbapi dictcursor, structured deserializer (msgspec, pydantic, etc...)

[encukou]

The discussion is ongoing in the issue/PRs; calling for a vote might have been premature.

[vstinner]

The discussion is ongoing in the issue/PRs; calling for a vote might have been premature.

The discussion seems to be idle for 2 weeks.

[vstinner]

@encukou @erlend-aasland: So what do you think about this API?

[encukou]

I cannot support exposing a current CPython implementation detail in the int unicode_keys argument.
I could be convinced to support a PyObject *key_type argument instead, if that becomes a performance win for Cython.

AFAICS, @methane's comment still stands.
From the 11 projects you mentioned, is there any project other that CPython that would use the new API?

[vstinner]

See also #90 which proposes adding PyDict_FromItems() function.