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:
from runtime.runtime cimport SequentialMailBox, BatchMailBox, NullResult, Scheduler
cdef cypclass Greeter activable:
int identifier
__init__(self, lock Scheduler scheduler, int identifier):
self._active_result_class = NullResult
self._active_queue_class = consume BatchMailBox(scheduler)
self.identifier = identifier
void hello(self):
with gil:
print("Hello from greeter %d" % self.identifier)
def main():
cdef lock Scheduler scheduler
with nogil:
scheduler = Scheduler()
# Create 3 Greeters
g0 = Greeter(scheduler, 0)
g1 = Greeter(scheduler, 1)
g2 = Greeter(scheduler, 2)
# Consume two of them into active Greeters
# g1 and g2 will now be NULL
# a1 and a2 are actors that can only be accessed asynchronously
a1 = <active Greeter> consume g1
a2 = <active Greeter> consume g2
# Call a1 and a2 asynchronously: the calls will be executed later
# Call g0 synchronously: the call will be executed immediately
# Asynchronous calls can take an additional predicate argument, NULL here.
a1.hello(NULL)
a2.hello(NULL)
g0.hello()
# Wait until all the actors have no more tasks
scheduler.finish()
Possible output:
Hello from greeter 0
Hello from greeter 2
Hello from greeter 1