Define a concurrency model (aka memory model) for Python

Ideas
1

Over the years there have been attempts to define a memory model, notably PEP 583 and many questions both on the bug tracker and here about expected semantics and atomicity of operations, e.g. What is Thread Safety as applied to Python? and What is the Long-Term Vision for a Parallel Python Programming Model?

Despite that, there is AFAICT, nothing in the docs.
We have an object model but there is no mention of concurrent access.

We should write down concurrency models for both with-GIL and free-threading Python.

It doesn’t need to be super precise and ultra rigorous, just reasonably complete and unambiguous.
To start with it doesn’t even need to be that. Once we have a core, details can be filled out:

Sticking with the with GIL build, the basic threading model should cover:

  • What is the GIL.
  • Properties of the GIL
  • The state of threads when releasing or acquiring the GIL
  • Which of the most common operations are atomic
  • How to describe the behavior of non-atomic operations
  • Comparison to archetypal memory models, like Sequential Consistency.
  • How much leeway other implementations, like MIcroPython and GraalPython have

and other things as necessary.

15 Likes
2

Do you see this as being language-level guarantees, or specific to the CPython implementation? In my view, it’s better to keep things simple and get something documented, so focusing on CPython seems like a better bet.

You touched on this with your last point, so maybe you see this more as language level - but I can’t reconcile that with the comments about the GIL, which is a CPython implementation detail.

2 Likes
3

Thanks, this is a great idea!

I’ve just started playing around with free-threading and was surprised how little detail there was on the wiki as to how it works.

1 Like
4

Would part of the desired specification / documentation look like this “Thread Safety Guarantees” page?

1 Like
5

It seems like most of this is implementation detail, and not something users can rely on when writing python code unless they are going to say they only support CPython. I don’t even think users should directly rely on the GIL for new extension code written only for CPython at this point, just use the limited ABI and critical sections, and the same code can have wheels shipped for both GIL and FT builds.

6

I would love to see a concurrency model written down for CPython. I expect that some guarantees may be applicable to the language as a whole and some may be CPython implementation details. So it may make sense to put some of it in the language reference and some in the CPython-specific documentation.

Among other benefits, having a clear concurrency/memory model would enable the creation of much more powerful tooling to check for data races and other concurrency issues. Rust has Loom and Shuttle which are quite useful in testing the safety of concurrent code.

7

As a user, I would like to see such a memory model to be descriptive at first, in that it states what the current (C)Python behavior has been, and as far as I understand that’s @markshannon’s goal right now. The prescriptive aspect of the memory model, that is whether such behavior ought to be preserved, guaranteed or changed in the future, is another matter entirely.

I also think we need to emphasize that the motivation for a memory model doesn’t arise all of a sudden. In the past people have repeatedly proposed to write down such a memory model, but these suggestions weren’t keenly taken up mainly because there wasn’t much demonstrated need to do so relative to the effort required, and of the fear that writing it down will constrain future implementation freedom (that’s why we need to emphasize the descriptive nature of the currently proposed effort). What has changed is that now the Python community has gained experience in implementing free-threading and other forms of shared execution context concurrency (and that experience clearly indicates the need for something better than playing whack-a-mole), I think we now have a much better case and knowledge base than ever for actually getting it right.

4 Likes
8

I disagreed quite strongly with this statement, but it is redeemed by “at first”. The points @matthewyu0311 makes subsequently (history, implementation experience, whack-a-mole fixes) make make me hope someone could write down a feasible, desirable target behaviour.

Record what we have by all means, but don’t stop there.

9

I disagree. I think it is intended to apply to Python the language, but it is let down by taking its first examples from the C-API.

After that it settles down to Python examples. I began writing about these in detail but am deleting that in favour of:

  • I think this covers Mark’s points 4 and 5 (and 7, I would say).
  • These are guarantees we always see a valid object.
  • That’s not enough[1] to make a correct program without explicit locks too.

Some people consider that last point a failure but I think that’s just how threads are.

  1. or I’m not smart enough ↩︎

10

Historical fun fact[1]: we’ve been through that exercise before. One of the most important and long-lasting byproducts of Jim Hugunin’s invention of JPython was (mostly Guido) resolving various ambiguities and corner cases falling on the language definition side of the fence or the CPython implementation side of the fence.

  1. as I remember it :smiley: ↩︎

3 Likes
11

This seems rather focused on the GIL, at a point in time where the goal for CPython seems to be removing the GIL, and the language reference doesn’t require an implementation have the GIL.

I share some thoughts about this being something that seems like time that could be spent just getting to the point where people aren’t relying on the GIL anymore.

The point about atomic operations might be possible to specify for the language, but there’s some significant holes in what people expect here even in CPython as an implementation provides, as almost no operations are actually atomic, and those that are, still have data race potential when considering the actual application.

For example, the interpreter doesn’t protect dict subclasses when it comes to implementing setdefault in python, and setdefault being atomic for the builtin implementation of dict doesn’t prevent data races on it’s own.

The actual atomicity isn’t provided by the language, or even the use of a specific operator, but the specific implementation of dict.setdefault.

The details you’ve posed as important seem like things that might belong in the section of documentation for extension authors, and specific to CPython, but that I don’t think currently, are possible to say are true for the language.

1 Like
12

Did anything get written down?

13

This leaves me thinking on the issue of how much of concurrency support really is of the business of the language versus of that the implementation.

Concurrency is a function of the language, the implementation and the environment. It’d be fine to describe how multithreading concurrency works in general, but I think our memory model need not touch upon non-POSIX/Windows implementations. I don’t think it’s CPython’s businesss to describe — much less prescribe — a memory model for platforms so different as MicroPython which by its nature already does a list of things differently from CPython (like not having true locals()or __del__()) and doesn’t claim pure-Python code interoperability. AFAIK MicroPython _thread support has remained experimental for the past years, and not widely adopted partly because full concurrency support on microcontrollers is mostly regarded as more appropriately in the proper of actual native RTOSes[1].

We have:

but not on topics such as happens-before relations, memory visibility and sequential consistency which other memory models typically cover. Thread safety involves more than just putting a lock on each individual object. Does CPython actually provide sequential consistency guarantees across multiple reads and writes? I don’t really know, and the answer is probably mostly but not always, but if it’s not written down that CPython does or doesn’t, people including me will assume it always does.

  1. Personal anecdote: I recently picked up a couple ESP32 microcontrollers, and I chose C/C++ over MicroPython partly for this reason. ↩︎

14

Hi all, I’ve been doing some work in this area as part of working on a thread-sanitizer for python. As part of this I’ve “defined” simple GIL and FT memory models based on analysis of the CPython reference implementation. Here is the basic set of rules I’m working from in case that proves helpful.

gil-ri ft-ri
Individual accesses Sequentially consistent within an interpreter. Stores to modeled reference storage have release semantics; loads have acquire semantics for the publication associated with the reference they observe. Note, RA is weaker than sequential consistency.
Concurrency/Preemption Preemption is allowable at interpreter safe points: calls, loop back edges, coroutine/generator resumptions—including implicit calls through properties or operators. Threads can execute in parallel between accesses, regardless of safe points.
Atomicity of compound operations, i.e. count += 1 An exact-integer/integer update with no intervening safe point is atomic. Anything more exotic than that can experience preemption and be non-atomic. Compound operations are non-atomic and can lose updates; the read and write being individually ordered does not protect the whole increment.
Native storage Python-visible accesses to built-in native data structures, are assumed to be serialized. Python-visible accesses to built-in native data-structures are assumed to be serialized. Opaque C scalar fields on those data-structures may remain unordered.

To me this is a simple enough model for developers to be able to reason about, except for the allowance for unordered C scalars (that I’d love to see get upgraded to ordered). I do think FT’s RA model while not sequentially consistent is the right compromise and for all but the most advanced cases is sufficiently close to sequentially consistent to allow devs to treat it as such.

Ultimately while it would be best for the language itself to have a memory model, a great start is having the RI define one (or two). While I hate the idea of the RI having two it also seems to be the reasonable compromise given the fast amount of code which unknowingly relies on the GIL and shouldn’t all of the sudden be declared “unsafe”. In my thread-santizer I thus can ask the question if a body of code is FT safe or just GIL safe, and being FT safe thankfully does imply that it is also GIL safe.

3 Likes
15

Would you unpack “RA” and “RI” for me? (A link might be enough.)

16

I think this is what Mark means by the abbreviations:

RI: Reference implementation, i.e. CPython
RA: Release-Acquire std::memory_order - cppreference.com

2 Likes
17

I think your models can be improved a bit:

GIL

Preemption can also occur on entry to a function, during exception unwinding, at the end of finally blocks, and immediately after some assignments (if an object being freed has a finalizer)

A much wider range of operations are atomic. Here are some I’ve noted down so far:

  • Arithmetic on floats, bytes, complex, str as well as ints.
  • Loading and storing an attribute to a plain Python object
  • Indexing lists, indexing dicts provided all keys are of the above types.
  • Construction of list, set, dict literals.
  • Addition on lists and tuples

(Note that construction of list, set and dict comprehensions is not atomic)

FT

I think the consensus among those working on it is that SC is the goal, not just RA. Maybe someone working on FT can elaborate?

To me this is a simple enough model for developers to be able to reason about

I think these models are too complex to expect developers to reason about without making mistakes. That’s not the fault of the models, but of the hard to reason about semantics that they are modelling.

I’d be in favor of reducing the number of possible context switching points for the GIL model. It would simplify that model and not be too hard to implement.

1 Like
18

If I understand correctly, there’s currently no way in free-threaded CPython for pure-Python code to achieve the kind of ordering across multiple accesses, akin to Java volatile or C++ std::memory_order without relying on some extensions?

19

FWIW, Java has quite a few more competing implementations than Python, and yet the Java language makes quite strong guarantees along the lines of what Mark is suggesting here. Indeed, they’re getting progressively tightened with the multi-year drive towards “integrity by default”, which I think is a great (if expensive[1]) goal to have for a high-level language.

This is mostly intended as a meta-comment, not that (C)Python should do one thing or another. Just that it’s possible in principle to disentangle these questions from a specific implementation.

  1. in terms of effort to design & implement ↩︎

1 Like
20

I’m only skimming this discussion, I don’t have a deep understanding, but I think I’m missing a nuance here. If I have

obj.a = 12

then I would consider that to be a case such as you describe. But it potentially executes a __setattr__ method on the class of obj, or runs the set method of a descriptor attached to obj.a. So I’m not clear how those operations can be atomic.

Maybe you’re intending “plain Python object” to mean something less general? But I’m not completely clear what, in that case.

1 Like