API pattern for “setdefault”-like operations

[encukou]

IMO, we need an API pattern for “setdefault”-like operations, which would be safer under nogil.

I was thinking about these proposed new APIs:

• PyDict_Pop
• PyImport_ImportOrAddModule

The first case is like dict.get. IMO, it's good to return 0 and set *result to NULL if the item is not found. If the caller needs a default value, they can create it when needed. However, if they then want to insert the default back into the dict, in nogil they run into a race condition: the item might have already been inserted.

The second case is like dict.setdefault, doing some non-trivial work if the item is not found (in this case, creating a new module and putting it in sys.modules). That should be atomic, so it makes sense to me to use a default -- either take it as an argument, or us an implied empty value. Taking a default argument is not free, though: the caller needs to create it even if it's unused.

The trouble with PyImport_ImportOrAddModule (and other “setdefault”-style API with implied defaults) is that the newly created default sometimes needs further customization, and that will not be atomic under nogil: other threads have a chance to see a uninitialized module.

IMO, we need an API pattern for “setdefault”-like operations that allows creating a custom new value only if needed, and either

• locks the container while that value is being constructed (which sounds like a deadlock magnet), or
• handles the race by discarding a losing thread's newly made default:

# rough pseudocode
value = get(key)
if value is NULL:
    new = create_a_default()
    value = setdefault(key, new)   # note that `value == new` is not guaranteed
    ddecref(new)

Note that this get+setdefault is different from get+set (which we use in a bunch of places, for example in https://github.com/python/cpython/blob/d2f305dfd183025a95592319b280fcf4b20c8694/Python/pylifecycle.c#L2276-L2285 -- didn't check if that instance is safe).
With get+set, if there's a race, the first thread's value is discarded -- but that value might already have been retrieved by other code.

cc @colesbury

[pitrou]

• ``

The first case is like dict.get. IMO, it's good to return 0 and set *result to NULL if the item is not found. If the caller needs a default value, they can create it when needed. However, if they then want to insert the default back into the dict, in nogil they run into a race condition: the item might have already been inserted.

This does not make sense to me. This case is actually like dict.pop, just like the function name implies. It has nothing to do with dict.get or dict.setdefault.

The use case of dict.pop with a default value is not to insert the default back into the dict. In addition to being convoluted, it would also be less efficient than directly calling dict.__setitem__ or dict.setdefault.

[encukou]

Yes, pop got me on this train of thought, but isn't too relevant -- except that it should be consistent with get.

[gvanrossum]

The trouble with PyImport_ImportOrAddModule (and other “setdefault”-style API with implied defaults) is that the newly created default sometimes needs further customization, and that will not be atomic under nogil: other threads have a chance to see a uninitialized module.

But that’s already not thread-safe in most cases (the GIL is likely to be releasable during the further customization, if it is at all significant. And in general import is not atomic.

[encukou]

But that’s already not thread-safe in most cases (the GIL is likely to be releasable during the further customization, if it is at all significant. And in general import is not atomic.

Indeed.
The question is for the future -- do we want a setdefault API pattern that is thread-safe, as part of “evolution” rather than “revolution”? If so, we should think about it now, as these APIs are getting added.

[pitrou]

The question is for the future -- do we want a setdefault API pattern that is thread-safe, as part of “evolution” rather than “revolution”? If so, we should think about it now, as these APIs are getting added.

This is not a C API question, as it also affects the Python dict API.

[zooba]

The import API here isn't a setdefault or a pop case - it's a "get-or-create" situation. A "get" would take a default value that is returned but not added to the collection, and a "setdefault" would take a default value that is added to the collection.

My immediate proposal for designing these APIs (I'll expand below):

PyObject *get(collection, key, PyObject *default, bool *was_not_found);
PyObject *setdefault(collection, key, PyObject *default, bool *was_set);
PyObject *get_or_create(collection, key, bool *was_created);

Key design points I considered:

• the first two arguments match in all three cases
• the return type can be NULL to indicate failure
• the bool * (more realistically int *) parameter consistently indicates "collection did not have the key", and can be NULL if you don't care (this also matches APIs like PyUnicode_AsUTF8AndSize)
• returned value cannot be pre-allocated (compared to, say, copying into a char * buffer, where a strcpy pattern would make more sense)

One thing I've liked from other languages is where the "get or create" API takes a callable to do the creation, so you can lazily create the value to be inserted, but still under whatever locks are required by the collection. I don't think that's something we would eagerly design for though - double-checked locking ought to be enough for our API.

[encukou]

This is not a C API question, as it also affects the Python dict API.

The difference is that Python will give you TypeError if you get the wrong type. Or SystemError if it's really bad. C will segfault.

My immediate proposal for designing these APIs (I'll expand below):

PyObject *get(collection, key, PyObject *default, bool *was_not_found);
PyObject *setdefault(collection, key, PyObject *default, bool *was_set);
PyObject *get_or_create(collection, key, bool *was_created);

A PyObject *create_default(void) is implied, and the get_or_create is redundant (though perhaps useful).
And I'd shuffle the parameters/return values, but that's another issue.

I would get rid of the default for get, though, getting what Victor's been adding lately:

int get(collection, key, PyObject **result); (returns -1 on error, 0 not found, 1 if found; result is set to found item or NULL).

IMO, it's easy enough to use a default value if you get the 0.

One thing I've liked from other languages is where the "get or create" API takes a callable to do the creation, so you can lazily create the value to be inserted, but still under whatever locks are required by the collection. I don't think that's something we would eagerly design for though - double-checked locking ought to be enough for our API.

Yeah. Also, I'd rather avoid calling user code while a lock is held.

But to enable double-checked locking, we need to provide:

• get and create_default whenever we provide setdefault (so users can skip init in the happy case)
• get, create_default and setdefault whenever we provide get_or_create (and then, get_or_create becomes redundant -- perhaps even a trap nudging people toward exposing half-initialized objects)

[zooba]

A PyObject *create_default(void) is implied,

I'd imply PyObject *create_default(key) rather than taking void, but that's probably an implementation detail.

I would get rid of the default for get, though

Fair, it was the last parameter I added, and only really because it felt inconsistent compared to setdefault.

Also, I'd rather avoid calling user code while a lock is held.

That's going to be impossible. We already have borderline security issues due to this (which nogil ought to fix, by holding the lock while calling user code 😉 ).

But I am okay with not calling back into user code. It's just going to be very tough due to how the interpreter has been designed (e.g. overridable __getitem__).

[colesbury]

To the extent that this is related to nogil, I'm fairly confused about what the concrete use cases are. There a few comments here that suggest that the original two examples are not good example use cases. Is it possible to provide one or two concrete examples for each of the proposed patterns?

@zooba wrote:

One thing I've liked from other languages is where the "get or create" API takes a callable to do the creation...

I have an open PR for an internal-only one-time initialization API that follows this pattern (but it's for "call_once", not "get_or_create"). python/cpython#111956

@encukou wrote:

Also, I'd rather avoid calling user code while a lock is held.

In cases where we are using the nogil per-object locks, which are acquired/released through the critical section API, this is safe and does not risk deadlock. If the user code is simple, plain C code then the everything is atomic. If the user code makes arbitrary calls to the Python API then the callback may not be atomic (we might temporarily release the lock, just like we might temporarily release the GIL), but it wont' deadlock.

I can't think of public C-APIs that follow this pattern, but from an implementation perspective we do this for things like list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse). EDIT: another example is the internal-only function _PyDict_DelItemIf(PyObject *mp, PyObject *key, int (*predicate)(PyObject *value)). We call the predicate with the dictionary lock held.

It's not really appropriate for PyImport_ APIs, because the import mechanism has it's own locks.

[colesbury]

I think this discussion is mostly about general "setdefault"-like operations, but for the --disable-gil builds, there is a more immediate issue with PyDict_SetDefault returning a borrowed reference. I wrote up the specific nogil issue here: python/cpython#112066.

[encukou]

I have an open PR for an internal-only one-time initialization API that follows this pattern (but it's for "call_once", not "get_or_create").

That sounds like a good approach -- hammer out the primitives in internal API, and as the next step, decide what to expose and how :)

If the user code makes arbitrary calls to the Python API then the callback may not be atomic (we might temporarily release the lock, just like we might temporarily release the GIL), but it wont' deadlock.

So the “double-checked locking” still sounds like a good default pattern. If the operation ends up not being atomic, possibly due to something the user doesn't control, then losing thread might do extra work (and it should cleanly discard the result).