LLQ: A wait-free SPSC linked-list queue with recyclable nodes

Last year, I published a Rust library called basedrop, which implements a memory reclamation system tailored to the constraints of real-time audio scenarios. The purpose of basedrop is to make it easy to share dynamically allocated memory with a real-time audio thread while ensuring that no allocations or deallocations happen on that thread. This is accomplished by providing a set of smart pointers (analogous to Box and Arc from the Rust standard library) which do not directly free their associated allocation when dropped, but instead automatically push it onto a lock-free queue to be collected later on another thread.

Basedrop's design has some compelling benefits: it frees you from having to write code by hand every time you want to transfer an object to another thread to be freed, and if you restrict yourself to its vocabulary of smart pointers, it eliminates the possibility of accidentally dropping an allocation on the real-time thread (a mistake which can easily remain invisible if you don't have something like assert_no_alloc to catch it). However, after talking with some developers trying to make use of basedrop in real projects, it became clear to me that these benefits come at the cost of a somewhat opinionated API, making it difficult to integrate with certain program architectures. I decided that a stripped-down version of the core linked-list queue would probably have some value, and the end result of that was the llq crate.

Basedrop: A garbage collector for real-time audio in Rust

In real-time audio, deadlines are critical. Your code has on the order of several milliseconds to fill a buffer with samples to be shipped off to the DAC, milliseconds which it may be sharing with a number of other audio plugins. If your code takes too long to produce those samples, there are no second chances; they simply won't get played, and the user will hear an objectionable glitch or stutter instead.

In order to prevent this, real-time audio code must avoid performing any operations that can block the audio thread for an unbounded or unpredictable amount of time. Such operations include file and network I/O, memory allocation and deallocation, and the use of locks to synchronize with non-audio threads; these operations are not considered "real-time safe." Instead, operations like I/O and memory allocation should be performed on other threads, and synchronization should be performed using primitives that are wait-free for the audio thread. A more thorough overview of the subject can be found in Ross Bencina's now-classic blog post "Time Waits for Nothing".

Given that audio software generally does need to allocate memory and make use of it from the audio thread, the question becomes how to accomplish this in a manageable and efficient way while subject to the above constraints. Basedrop is my attempt at providing one answer to this question.

The amplitwist, the conjugate transpose, and the complex derivative

Complex numbers have a representation as $2\times 2$ matrices, which can serve to illuminate some initially non-obvious aspects of how they work. A real number $a$ can be represented as a multiple of the identity matrix:

$$aI=\left[\begin{array}{cc}a& 0\\ 0& a\end{array}\right]$$

with addition and multiplication given by the corresponding matrix operations. In order to extend this representation to the complex numbers, we need a matrix $J$ such that $J^2=-I$:

$${\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]}^2=\left[\begin{array}{cc}-1& 0\\ 0& -1\end{array}\right]$$

We can thus represent any complex number $a+bi$ as:

$$aI+bJ=\left[\begin{array}{cc}a& -b\\ b& a\end{array}\right]$$

It can be verified that addition and multiplication of these matrices is equivalent to addition and multiplication of the complex numbers they represent (meaning that matrices of this form comprise a field isomorphic to $\mathbb{C}$).

A rotated video of a cube

The following is a video of a rotating cube:

This can be visualized as a plane sweeping through a cube of spacetime, or a flipbook: