PEP 805 – Safe Parallel Python | peps.python.org

The synchronization quadrant diagram

The table above shows the four synchronization quadrants. It is only when objects can be mutated and accessed from parallel threads, that race conditions can occur. This PEP has three main goals:

• to provide mechanisms to move execution from the dangerous quadrant into either of the adjacent quadrants,
• to guarantee that execution in the dangerous quadrant is properly synchronized, and
• to provide means to move gradually from a single thread to parallel threads, retaining safety.

Immutability allows safe execution without synchronization, so this PEP provides mechanisms for making objects immutable. Where immutability is not possible, this PEP offers mechanisms for safe execution by ensuring that the object is visible only to one thread (the top-left quadrant), or that it is protected by a mutual exclusion lock (mutex). The PEP also proposes changes to CPython to prevent unsafe execution when mutable objects are shared. Finally, the PEP provides a generalization of the GIL to allow incrementally moving away from the GIL.

This PEP is inspired by ideas from OCaml, specifically Data Freedom à la Mode, and the Pyrona project. Many of the necessary technologies, such as biased and deferred reference counting, have been developed for PEP 703.

Object states

All objects will gain a __shared__ state, which will be used the Python VM to ensure that objects are used safely. The state can be queried by looking at the __shared__ attribute of an object.

An object’s __shared__ state can be one of the following:

• Immutable: Cannot be modified, and can be safely shared between threads.
• Local: Only visible to a single thread^*, and can be freely mutated by that thread.
• Stop-the-world mutable. Mostly immutable, but can be mutated by acquiring the stop-the-world lock.
• Protected: Object is mutable, and is protected by a mutex.
• Synchronized: A special state for some builtin objects. All operations on the object are protected by an internal mutex, so no external synchronization is needed.

* Strictly, a single “super thread”. See SuperThread objects below.

The __shared__ attribute is read-only.

All classes, modules and functions will be stop-the-world mutable initially, but can be made immutable. Views, iterators and other objects that depend on the internal state of other mutable objects will inherit the state of those objects. For example, a listiterator of a local list will be local, but a listiterator of a protected list will be protected. Views and iterators of immutable (including stop-the-world mutable) objects will be local when created.

All objects that are not inherently immutable (like tuples or strings) will be created as local. These local objects can later be made immutable or protected.

Dictionaries and lists will support the ability to be made stop-the-world mutable on a per-object basis. This is to maintain the necessary immutability for performance and mutability for backwards compatibility for objects like sys.modules and sys.path.

The stop-the-world lock

A new, internal lock is added to CPython, the “stop the world” lock. When this lock is acquired, all other threads are stopped until the lock is released. If two threads attempt to acquire the stop-the-world lock at the same time, in such a way that deadlock would occur, then an exception is raised.

SuperThread objects

A new class SuperThread will be added to help port applications using the GIL and sub-interpreters. All threads sharing a SuperThread will be serialized, in the same way as all threads are currently serialized by the GIL. SuperThreads offer much the same capabilities as sub-interpreters, but more efficiently and with the ability to share more objects.

There is a many-to-one relationship between threads and SuperThreads. If no super thread is explicitly specified when creating a thread, a new super thread will be created specifically for that thread. The super thread of a thread cannot be changed.

All threads that share a SuperThread are treated as the same thread for local objects. They are still treated as distinct for all locks, and thus for protected objects.

New API

This PEP proposes adding the following:

• A __freeze__() method, added to most classes, which freezes the object making it immutable.
• The __protect__(self: Self, obj: T) -> T method to mark the self object as protecting obj.
• The __mutex__ context manager property, added to all objects, for critical sections.
• The Channel class for passing mutable objects from one thread to another.

class ImmutablePoint:

    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.__freeze__()

def func1(a, b):
    with a.__mutex__ + b.__mutex__:
        ...

def func2(a, b):
    with b.__mutex__ + a.__mutex__:
        ...

Deadlock detection

The addition of the stop-the-world lock, and the requirements for locking on all synchronized objects, may lead to more deadlocks. Since it is the goal of this PEP to avoid confusing behavior, a deadlock detector will be added to CPython. There are well known techniques for detecting deadlocks and they can implemented without undue overhead.

Semantics

Although it is performing operations on an object that leads to race conditions, checking every operation on every object would be prohibitively expensive. Instead, the cost can be reduced hugely by preventing threads having any access to objects which could cause race conditions. This means that it is only when a thread reference is created from a heap reference, does that operation need to be checked. If we do that, then all other operations become safe.

1. If the mutex held by the thread matches the mutex that protects the object.
2. If supported for that class.
3. The argument to __protect__ must the sole reference to the object.

ABI breakage

This PEP will require a one time ABI breakage, much like PEP 703, as the PyObject struct will need to be changed.

Deferred reclamation

Immutable (including stop-the-world mutable) objects may have their reclamation deferred. In other words, they may not be reclaimed immediately that their are no more references to them.

This is because these objects may be referred to from several threads simultaneously, and the overhead of serializing the reference count operations would be too high. PEP 703 also does this.

Local objects, visible to only one thread, will still be reclaimed immediately that they are no longer referenced.

New Exceptions

Two new exception classes will be added:

• IllegalThreadAccessException for when a thread attempts to acquire a reference to a local object belonging to another thread.
• UnprotectedAccessException for when a thread attempts to acquire a reference to a protected object without holding the necessary mutex.

With the GIL enabled

If all threads belong to the GIL SerializedThreadGroup then the JIT can completely eliminate checks for local objects (as these checks will always pass), resulting in performance very close to the current with-gil build.

With threads

Single threaded performance should exceed that of free-threading. Expected performance is within two or three percent of the with-gil build.

Examples

class ThreadSafeIter:
    "For thread-safe iterables, only"

    __slots__ = "_iterator",

    def __init__(self, iterable):
        self._iterator = self.__protect__(iter(iterable))
        self.__freeze__()

    def __iter__(self):
        return self

    def __next__(self):
        with self.__mutex__:
            return self._iterator.__next__()

class ThreadSafeList:

    __slots__ = "_list",

    def __init__(self):
        self._list = self.__protect__([])
        self.__freeze__()

    def append(self, val):
        with self.__mutex__:
            self._list.append(val)

    def __getitem__(self, index):
        with self.__mutex__:
            self._list[index]

    def __iter__(self):
        with self.__mutex__:
            return ThreadSafeListIterator(self)

    ...

class ThreadSafeListIterator:

    __slots__ = "_list", "_iter"

    def __init__(the_list):
        self._list = the_list
        with the_list.__mutex__:
            self._iter = the_list._list.__iter__()

    def __next__(self):
        with self._list:
            return self._iter.__next__()

Object state

Recording object state requires space in the object header, at least 3 bits but no more than a byte. Each object also needs additional space to refer to its thread, or protecting mutex. With these fields, the PyObject header should be the smaller than is currently implemented for PEP 703, although larger than for the default (with GIL) build.

A possible object header:

uint32_t ref_count_local;
uint32_t ref_count_shared; // For biased reference counting
uint32_t owner_id;
uint8_t  shared_state;
uint8_t  other_flags;
uint8_t  mutex;
uint8_t  gc_bits;
PyTypeObject *ob_type;

or if we use atomic reference counting for non-local objects, we can use pointers for owners:

uintptr_t owner;
uint32_t ref_count;
uint8_t  shared_state;
uint8_t  other_flags;
uint8_t  mutex;
uint8_t  gc_bits;
PyTypeObject *ob_type;

Reference counting

Local objects (including immutable objects that are known to be only locally referenced) can use non-atomic reference counting for speed. Any object shared between threads would use either biased or atomic reference counting.

Shared objects will use deferred reference counting where possible.

Checking object states

CPython is a stack machine. That means that for a thread to acquire a reference to an object, that object must come from the heap or an API call and be pushed to the stack. In order to prevent C extensions seeing objects they should not, all C API calls will need to check their return value. In addition, the interpreter will need to check any values it gets direct from the heap before pushing them to the stack.

This is potentially a lot of new checks so, to avoid a large performance impact, we need to keep the cost of these checks down. We can do that by:

• Making the checks cheap. Checks should consist of only one or two simple comparisons with minimal memory accesses.
• Removing as many checks as possible in both the specializing interpreter and the JIT compiler.

Specialization means that we can perform only one check for the most likely state, rather than checking all legal states. If we expect a local object, we just check the object’s thread ID against the current thread ID. If, instead, we expect an immutable object, we can just check that the object is immutable.

The JIT compiler can remove redundant checks on the same object.

Deep freezing and deep transfers

Freezing a single object could leave a frozen object with references to mutable objects, and transferring of single objects could leave an object local to one thread, while other objects that it refers to are local to a different thread. Either of these scanarios are likely to lead to runtime errors. To avoid that problem we need “deep” freezing.

Deep freezing an object would freeze that object and the transitive closure of other mutable objects referred to by that object. Deep transferring an object would transfer that object and the transitive closure of other local objects referred to by that object, but would raise an exception if one of the those objects belonged to a different thread.

Similar to freezing, a “deep” put mechanism could be added to Channels to move a whole graph of objects from one thread to another.