Lock-free data structures. Queue dissection

A lot of time has passed since the last post in the life of lock-free containers. I expected to quickly write a continuation of the treatise on queues, but there was a hitch: I knew what to write about, but I didn’t have these approaches in C ++. “It’s not good to write that I didn’t try it myself,” I thought, and as a result, I tried to implement new queue algorithms in libcds .
Now the time has come when I can continue my cycle of argumentation. This article ends with the queues.

Briefly recall where I left off. Several interesting algorithms of lock-free queues were considered, and at the end the results of their work on some synthetic tests are presented. The main conclusion is that everything is bad! The hopes that the lock-free approach on the magic compare-and-swap (CAS) will give us, if not linear, but at least some performance increase with an increase in the number of threads, did not materialize. Queues do not scale. What is the reason? .. The

answer to this question lies in the features of the architecture of modern processors. The CAS primitive is a rather heavy instruction, heavily loading the cache and the internal synchronization protocol. With the active use of CAS over the same cache line, the processor is mainly occupied with maintaining cache coherency, as described in more detail by Professor Paul McKenneyI already wrote with my help .

Stacks and queues are very unfriendly to the lock-free approach of data structures, since they have a small number of entry points. For the stack, there is only one such point - the top of the stack, for the queue there are two of them - head and tail. CAS competes for access to these points, while performance drops at 100% processor utilization - all threads are busy with something, but only one will win and gain access to the head / tail. Doesn’t resemble anything? .. This is a classic spin-lock! It turns out that with the lock-free approach on CASs, we got rid of the external synchronization by the mutex, but got the internal synchronization at the processor instruction level and won little.


The problem of effective implementation of competitive queues is still of interest to researchers. In recent years, there has been a growing understanding that various kinds of tricks in the implementation of the lock-free queue “on the forehead” do not give the expected result and some other approaches should be thought up. Further we will consider some of them.

Flat combining

I already described this method in the article on the stack, but flat combining is a universal method, therefore it is applicable to the queue. I am sending readers to the video of my presentation at C ++ User Group, Russia , which is dedicated to the implementation of flat combining.

Array of Queues

An approach that lies on the surface, but nevertheless rather difficult to implement, with many pitfalls, was proposed in 2013 in an article entitled "Replacing competition with cooperation for implementing a scalable lock-free queue" , which is perfectly suited to the topic of this post .
The idea is very simple. Instead of a single queue, an array of size K is built, each element of which is a lock-free queue, represented by a simply connected list. A new element is added to the next (modulo K) slot of the array. Thus, the crowding at the tail of the queue is leveled - instead of one tail we have K tails, so we can expect that we will get linear scalability up to K parallel flows. Of course, we need to have some general atomic monotonically increasing counter of push operations in order to multiplex each insert into its array slot. Naturally, this counter will be a single "sticking point" for all push streams. But the authors claim (according to my observations, not unreasonably) that the instructionxaddatomic addition (in our case - increment) on the x86 architecture is slightly faster than CAS. Thus, we can expect that on x86 we will get a win. On other architectures, atomic is fetch_addemulated by CAS, so the gain will not be so noticeable.
The code for deleting an element from the queue is similar: there is an atomic counter of deleted elements (pop-counter), based on which an array slot is selected modulo K. To eliminate the violation of the main property of the queue - FIFO - each element contains an additional load ( ticket) - the value of the push counter at the time of adding the element, in fact - the serial number of the element. When deleting in the slot, the element with ticket= is searched for the current value of the pop counter, the element found is the result of the operation pop().
An interesting way to solve the problem of removing from an empty queue. In this algorithm, the atomic increment of the deletion counter (pop-counter) is first followed by a search in the corresponding slot. It may well be that the slot is empty. This means that the entire queue is empty. But the pop counter is already incremented, and its further use will lead to violation of FIFO and even to loss of elements. You can’t roll back (decrement) - all of a sudden, at the same time, other threads add or remove elements (in general, “back-play-not-impossible” is an integral property of the lock-free approach). Therefore, when a situation arises pop()from an empty queue, the array is declared invalid, which leads to the creation of a new array with new push and pop counters the next time the element is inserted.

Unfortunately, the authors did not bother (as they write, due to lack of space) the problem of freeing memory, giving it only a few suggestions with a superficial description of the application of the Hazard Pointer scheme to their algorithm. I have not yet been able to decipher their hints, so there is no implementation of this interesting algorithm in the library libcds. In addition, the algorithm is subject to unlimited accumulation of deleted elements if the queue is never empty, that is, if the array is not invalidated, since it is not intended to remove elements from the array slot list. pop()it just searches for the element with the current ticket'th in the corresponding slot, but the physical exclusion of the element from the list does not occur until the entire array is invalidated.

Summing up, we can say: the algorithm is interesting, but memory management is not described clearly enough. Further study is required.

Segmented Queues

Another way to increase the scalability of a queue is to violate its primary first-in property, first-out (FIFO). Is it really so scary? It depends on the task: for some, strict observance of FIFO is mandatory, for others it is quite acceptable within certain limits.
Of course, I don’t really want to violate the main FIFO property completely - in this case we will get a data structure called a pool, in which no order is observed at all: the operation pop()returns any element. This is no longer the turn. For a queue with a FIFO violation, I would like to have some guarantees of this violation, for example: the operation will pop()return one of the first K elements. For K = 2, this means that for a queue with elements A, B, C, D, ... will pop()return A or B. Such queues are calledsegmented or K-segmented to emphasize the importance of the K factor - FIFO violation restrictions. Obviously, for a strict (fair) FIFO queue, K = 1.
As far as I know, for the first time, the simplest segmented queue was considered in detail in 2010 in a work devoted to just the allowable easing of requirements imposed on lock-free data structures. The internal structure of the queue is quite simple (figure from the above article, K = 5):

The queue is a simply connected list of segments, each segment is an array of K elements in size. Headand Tailindicate the first and last segment in the list, respectively. Operation push()inserts a new elementinto an arbitrary free slot in the tail segment, the operation pop()extracts an element from an arbitrary occupied slot in the head segment. With this approach, it is obvious that the smaller the size of the K segment, the less the FIFO property is violated; for K = 1 we get a strict queue. Thus, by varying K, we can control the degree of violation of FIFO.
In the described algorithm, each slot of a segment can be in one of three states: free, busy (contains an element) and “garbage” (an element has been read from the slot). Note that the operation pop()puts the slot in the “garbage” state, which is notthe equivalent of the “free” state: the “garbage” state is the final state of the slot, writing a value to such a slot is not allowed. This is a drawback of the algorithm - a slot in the “garbage” state cannot be reused, which leads to the distribution of new segments even in such a typical sequence of operations as an alternating one push() / pop(). This flaw was fixed in another work at the cost of significant code complexity.

Exploring

So, in libcds there are implementations of two new algorithms for queues - FCQueue and SegmentedQueue. Let's see their performance and try to understand whether it was worth it to deal with them.
Unfortunately, the server on which I ran tests for the previous article was loaded with other tasks, and subsequently crashed. I had to run tests on another server, less powerful - 2 x 12 core AMD Opteron 1.5GHz with 64G of memory running Linux, which was almost free - idle at 95%.

I changed the visualization of the results - instead of the test execution time along the Y axis, I now postpone the number of mega operations per second (Mop / s). Let me remind you that the test is a classic producer / consumer: a total of 20 million operations - 10M push and 10M pop without any payload emulation, that is, stupid queuing. All lock-free queue tests use Hazard Pointer to safely free memory.



First, a digression: what are we striving for? What do we want to get about scalability?

The ideal scaling is a linear increase in Mop / s with an increase in the number of threads, if the iron physically supports such a number of threads. A really good result would be some increase in Mop / s, more like a logarithmic one. If with an increase in the number of threads we get a performance drawdown, then the algorithm is not scalable, or scalable to some limits.

Results for intrusive queues (let me remind you, an intrusive container is characterized by the fact that it contains a pointer to the data itself, and not a copy of it, as in STL; thus, it is not necessary to allocate memory for a copy of the elements, which in the lock-free world is considered a bad manners).

It can be seen that Flat Combining was not implemented in vain - this technique shows a very good result against other algorithms. Yes, it does not increase productivity, but there is no significant subsidence either. Moreover, a significant bonus is that it practically does not load the processor - only one core always works. Other algorithms show 100% CPU utilization with a large number of threads.
A segmented queue proves to be an outsider. Perhaps this is due to the specifics of the implemented algorithm: memory allocation for segments (in this test, the segment size is 16), the inability to reuse segment slots, which leads to permanent allocations, the implementation of the list of segments based on boost :: intrusive :: slist under lock (I tried two types of locks - spin-lock and std :: mutex; the results are practically the same).
I had a hope that the main brake is false sharing. In the implementation of a segmented queue, a segment was an array of pointers to elements. With a segment size of 16, a segment occupies 16 * 8 = 128 bytes, that is, two cache lines. With a constant crowd of flows in the first and last segments, false sharing can prove itself to its full potential. Therefore, I introduced an additional option in the algorithm - the required padding. If padding = cache line size (64 bytes), the segment size increases to 16 * 64 = 1024 bytes, but this way we eliminate false sharing. Unfortunately, it turned out that padding has almost no effect on the performance of SegmentedQueue. Perhaps the reason for this is that the algorithm for finding a segment cell is probabilistic, which leads to many unsuccessful attempts to read busy cells, that is, again, to false sharing. Or false sharing is not at all the main brake for this algorithm and you need to look for the true reason.

Despite the loss, there is one interesting observation: SegmentedQueue does not show performance subsidence when the number of threads increases. This gives hope that the algorithms of this class have some perspective. You just need to implement them differently, more efficiently.

For STL-like queues, with the creation of a copy of the element, we have a similar picture:


Finally, just for fun, I’ll give the result of a bounded queue - an Dmitry Vyukov algorithm based on an array, intrusive implementation:

With the number of threads = 2 (one reader and one writer), this queue shows 32 MOp / s, which did not fit on the chart. With an increase in the number of threads, performance degradation is also observed. As an excuse, it can be noted that for Vyukov's queue, false sharing can also be a very significant inhibitory factor, but the option that includes padding on the cache line is not yet in libcds for it.



In conclusion, I want to note one interesting observation. In the above tests, there is no payload for readers and writers, our goal is simply to push the queue and read from it. In real tasks, there is always some kind of load - we do something with the data read from the queue, and before we put it in the queue, we prepare the data. It would seem that payload should lead to a sagging performance, but practice shows that this is far from always the case. I have repeatedly observed that payload leads to a significant increase in MOp / s parrots . The reason, it seems to me, is to offload the internal cache synchronization protocol; see P.McKenney again. The conclusion suggests itself: you need to test on real tasks.


In this article, I touched on a small part of the work devoted to queues, and only dynamic (unbounded), that is, without limiting the number of elements. As I said, the queue is one of the favorite data structures for researchers, apparently because it is difficult to scale. Many other works remained outside the scope of the review - about limited (bounded) queues, work-stealing queues used in task schedulers, single consumer or single producer queues - the algorithms of such queues are significantly sharpened by one writer or reader, and therefore it is often simpler and / or much more productive - etc. etc.

Я рад, что мне удалось-таки, несмотря на большой временной лаг, довести повествование об очередях и стеках до логического конца, ибо это не самые дружественные для lock-free подхода и современных процессоров структуры данных, да и не очень для меня интересные.
Впереди нас ждут куда более увлекательные структуры — ассоциативные контейнеры (set/map), в частности, hash map, с красивыми алгоритмами и, надеюсь, более благодарные в плане масштабируемости.
Продолжение, думаю, воспоследует…