How to create lock-free Array<int> or std::vector<int>?


#1

So I’ve been reading about atomics and I tried to use Juce’s equivalent to create Atomic<Array> and I also tried Atomic<std::vector> but neither of those work. Is there a straightforward way to create a lock-free dynamic array? Google wasn’t very helpful to me in this matter.


#2

A “lock-free dynamic array” doesn’t exist. By definition, a dynamic array is capable of allocating to increase its capacity, and that’s an expensive operation that cannot be done “lock-free”.

However, there are certain operations, like getting the value at a given index, that can be done lock-free, as long as you can guarantee that the array is not reallocating. So what operations do you need to be lock-free?


#3

Gotcha. Well I have a GUI thread that is updating the array and the ProcessorBlock accesses it so it knows which midi notes at what volumes to play. It seems to work fine but every once in a while I notice problems and I have this little devil whispering in my ear that it’s because they are asynchonrously accessing the array.


#4

Certainly, if you are doing things like resizing the array without taking care of thread safety. Accessing individual elements can be thread safe if only one thread is accessing the particular elements. (Of course there is the caveat that if the elements happen to be or contain for example pointers pointing to objects used by other threads, then it is not thread safe.)

Trying to make things absolutely lock and wait free is extremely complicated. You should investigate if just using a mutex lock (CriticalSection or SpinLock if you want to use the JUCE classes) around the relevant operations can work. You obviously should not do things like allocate or deallocate memory inside the mutex lock, though.


#5

Correct me if I’m wrong, but isn’t it true that I should never lock something with mutex or otherwise in such a way that prevents the ProcessorBlock from accessing it? Couldn’t that create problems in playback?

If I restructure my code to use a fixed size array, not a dynamically changing one, could I change all the ints inside to atomic and wouldn’t that help when the ints are being changed by different threads?


#6

If I restructure my code to use a fixed size array, not a dynamically changing one, could I change all the ints inside to atomic and wouldn’t that help when the ints are being changed by different threads?

One scheme is to use double-buffering (sometimes called ping-pong buffering), where your audio thread isn’t accessing the same array of integers as your other threads. To exchange the two you use an atomic pointer swap.

There are also things like lock-free queues, such as a Treiber Stack or Michael-Scott Queue you can use for sending data between threads. Imho it’s more useful to think in terms of producing/consuming data rather than sharing it.


#7

Sure, that’s the ideal, but it’s very difficult to implement that properly. You will likely get better results by just using mutexes unless you have access to some ready-made lock-free code that has been proven to work correctly. (You can get away with mutexes if your operations are likely to happen very quickly and predictably. So obviously no stuff like memory allocations and deallocations or disk access…)


#8

Well I’ll give that a go then, thanks!