Concurrency

Cython+ has been experimenting with various approaches to safe concurrency. Our latest idea is a type and effect system inspired by Pony and Rust. It's still very much a Work In Progress and may evolve substantially.

This type and effect system arises from a simple observation:

• When data is only reachable from a single thread, it can safely be read and modified freely.
• When data is shared between threads, all accesses should follow a common synchronisation strategy (such as always acquiring a mutex) to avoid data races.

We introduce a special operator consume and three type qualifiers iso, active and lock that apply to individual cypclass references (a bit like const or volatile in C/C++).

The qualifiers active and lock both denote that a specific synchronisation strategy is used by all references to the cypclass object, and that it is therefere safe to share it with another thread:

• an active cypclass reference reifies all methods calls and puts them in a queue for asynchronous execution.
• a lock cypclass reference denotes that an object lock must be acquired around all accesses to its data it.

The type and effect system is there to ensure that a program that tries to bypass the synchronisation strategy to directly access the internal data of an active or a lock cypclass object will simply fail to compile.

But before looking at either of these, we must explain what iso and consume mean.

iso

The central concept of this type and effect system is the notion of isolation. It's related to what Rust calls ownership.

Isolation relates to the structure formed by all the cypclass objects allocated in the heap: the heap contains all the allocated cypclass objects, and these objects can have references to each other (when the field of a cypclass is a reference to another cypclass object), forming complex directed graphs where the nodes are the cypclass objects and the arrows linking them are references to each other.

The data reachable from an single object is therefore the sum total of all the data that can be reached by following zero or more references from the starting object. We'll call this the transitive closure of the cypclass object.

Now let's consider all the data that can be reached by only following reference that aren't active or lock. We'll call this the owned closure. That's all the data that can be reached without requiring a synchronisation strategy.

A reference is isolated when the is owned closure is only reachable through this single reference. In other words, if an isolated reference were deleted, its owned closure including the object itself would become forever unreachable and would end up being garbage collected.

The iso qualifier denotes the fact that a reference is isolated.

The type and effect system will then ensure that this contract is kept:

cdef cypclass Node activable:
    int data
    Node _next

    __init__(self, int data, Node _next):
        self.data = data
        self._next = _next

def main():

    cdef iso Node n1 = consume Node(1, Node(2, NULL))

    # This won't compile,
    # since it breaks the isolation guarantee made by n1
    n2 = n1._next

consume

The consume operator takes a cypclass reference as operand and returns it if it is isolated. If the operand is a named reference (a reference that can be assigned to), it will receive the value NULL after the consume operation (otherwise the reference would no longer be isolated). If the compiler is unable to ascertain at compile-time that the operand is indeed isolated, it will generate a runtime isolation check and raise an exception at runtime if this check fails. This isolation check is essentially the same algorithm as the one used by the CPython cyclic garbage collecter to detect isolated reference cycles.

Let's clarify things with a simple example:

def main():

    cdef Node n1 = Node(1, NULL)

    # n1 is not iso, so consume will generate a runtime check
    # after this line:
    # - n2 will be the old value of n1
    # - n1 will be NULL
    cdef iso Node n2 = consume n1

    # n2 is already iso, so consume won't issue a runtime check
    # after this line:
    # - n3 will be the old value of n2
    # - n2 will be NULL
    cdef iso Node n3 = consume n2

When the consume operand is not actually isolated, an exception is raised:

def main():

    cdef Node n1 = Node(1, Node(2, NULL))

    cdef Node n2 = n1._next

    # n1._next is reachable from n2
    # n1 is no longer isolated
    # This will raise an exception
    n = consume n1

The consume operand makes it possible to transfer an unsynchronized reference from one thread to another: the compiler will prohibit sharing an unsychronized reference to a cypclass with another thread, but if the reference is consumed just before passing it to the other thread, the compiler is able to determine that only one thread at a time will have access to the data: the second thread will receive a reference only after the first thread has given up its own reference (or that an exception will occur instead).

With consume, it also becomes possible to transition a cypclass object between the unsychronised state, active and the lock synchronisation strategy, and the iso guarantee:

def main():

    cdef Node n1 = Node(1, NULL)

    cdef iso Node i1 = consume i1

    cdef active Node a1 = consume n1

    cdef lock Node l1 = consume a1

    cdef Node n2 = consume a1

Indeed, that is the only way to change the qualifier of a reference: going through consume lets the compiler guarantee that the cypclass object and its owned closure cannot be simultaneously seen as active and lock, for instance. Directly assigning a reference to a variable with a different qualifier will simply result in a compilation error.

lock

The lock qualifier tells the compiler to automatically acquire a lock around method calls and attribute accesses.

The type and effect system will also ensure that the owned closure of a lock cypclass object can only be accessed by taking its object lock:

def main():

    cdef lock Node l1 = consume Node(1, Node(2, NULL))

    # This won't compile,
    # since n2 could then be accessed without synchronisation
    n2 = l1._next

If we do need to alias a field in such a way, we can mark the _next field as lock directly in the class:

cdef cypclass Node activable:
    int data
    lock Node _next

    __init__(self, int data, lock Node _next):
        self.data = data
        self._next = _next

def main():

    cdef lock Node l1 = consume Node(1, consume Node(2, NULL))

    n2 = l1._next

The following is not yet implemented, but it would be nice to allow temporarily aliasing the fields of a lock cypclass in such a way:

cdef cypclass Node activable:
    int data
    Node _next

    __init__(self, int data, Node _next):
        self.data = data
        self._next = _next

def main():

    cdef lock Node n1 = consume Node(1, Node(2, NULL))

    with wlocked n1:
        # l1 and unqualified references from outside are not reachable here

        # inside this block n1 is unqualified
        n2 = n1._next

        # do stuff with n2

        # n1 and n2 go out of scope here

active

The active qualifier means that all method calls will be reified, stored in the object's own dedicated queue, and executed asynchronously in its own dedicated thread one after the other. The cypclass fields can therefore not be accessed directly (that would mean synchronous access). It introduces a version of the actor model to Cython+.

No special annotation is required on the methods to indicate they can be called asynchronously. Rather, all the methods that can be called synchronously on a passive cypclass can be called asychronously with an active reference.

To avoid generating unrequired reification code, a cypclass can be seen as active only if the keyword activable is used it its class declaration:

cdef cypclass Node activable

The asynchronous versions of the methods take an additional first argument that can either be NULL, or can be a predicated used to defer the execution of the method until a given condition is met.

The most quirky thing about this qualifier is that there is not built-in runtime that handles taking messages out of the queue and processing them. Rather, Cython+ provides a framework of abstract base classes that can be overriden to let the programmer provide their own runtime. This framework is still a Work In Progress and its usage is currently a bit clunky.

The first step is to provide a value for the built-in _active_queue_class attribute that will be the message queue object, and function pointer value for the built-in _active_result_class attribute that can construct a kind of promise objects to be returned immediatly and on which we can block waiting for the asycnhronous call to be processed and return the underlying value. Or it can just sytematically return NULL if we don't care about the return value. These attributes are implicitly declared by the activable keyword.

cdef cypclass Node activable:
    int data
    Node _next

    __init__(self, int data, Node _next):
        # self._active_result_class = ...
        # self._active_queue_class = ...
        self.data = data
        self._next = _next

An example implementation can be found in https://lab.nexedi.com/xavier_thompson/scan-filesystem/tree/master/cython.

The runtime provided in https://lab.nexedi.com/xavier_thompson/scan-filesystem/tree/master/cython/runtime can be copied and reused directly like in the small demo below:

Possible output: