A Fast General-Purpose Lock-Free Queue for C++

1. It is complicated, and, of course, with any complex code comes the possibility of bugs (especially when threads are involved!). I'd love to have a formal proof myself, but it's not a simple undertaking -- the sheer number of possible codepaths at execution time would make an exhaustive check infeasible. (And expressing the entire thing as a formal model is beyond my means.) What I've done instead is to try to test individual subsystems in isolation (you can check out the tests if you're interested): There's a free-list, a thread-local storage map, an add-only lock-free list, two block mapping methods, and the core algorithm itself. Then I wrote a series of unit tests (that are really more like integration tests, I suppose) that test individual functions, and everything together (and boy did those tests ever catch bugs during development!). There's never too many tests. There's never too much model-checking. But I only have limited time :-) So in the meantime, I made an initial release when I thought it was stable and correct to the best of my knowledge, with a reasonable amount of testing that I feel is reasonably thorough. I'd gladly accept more tests contributed by somebody else.

2. It is meant to be 100% portable to any system that has a C++11 compiler. I was very careful about the orderings I wrote, so yes, it should work on CPUs with weaker memory models.

3. The factor depends on what part of the API is used, and with how many threads. I absolutely agree that a fast queue itself probably won't buy you much in terms of application performance. But if you're going to write a data structure, why not write a high-performance one? Much more fun, IMO, and certainly can't hurt. 4. Here I must disagree. The number of lines of code of a heavily templated data structure are entirely unrelated to the compiled size :-) In particular, if you use either only producer tokens or only no producer tokens, then a large portion of the code is unused and will be optimized out. Same for the bulk methods.

It's not a proof of concept, it's an actual thing that's designed to be used. If you read the README, it's clear that there are a variety of nonessential features included which you may or may not want, but I see no evidence it's "over-architected."

The code has a huge amount of opportunities for re-factoring and cleanup. Some functions are massive.

Br, Robert C. Martin

You're certainly right that it's not the minimum amount of complexity. But it's not that hard to implement a simple MPMC queue (e.g. if you can assume DCAS on your platform) -- what's hard is making it fast. So part of the complexity derives from a design that calls for blocks of elements instead of a simlpe linked list, for example; but a lot of the speed comes from that design too.

The rest of the code size (and complexity) arises from the feature set (which I intended to be fairly complete): Users can provide tokens for better performance -- but don't have to. There's bulk methods. There's a move constructor and assignment operator (for the tokens too!). There's traits so that you can override the malloc/free that's used, and all the constants. There's memory debugging machinery (hidden in an #ifndef NEBUG). It all adds up, but not without reason, I think :-)

I will add a "how to read the code" section to the README later on when I have a minute. I think it would be instructive for those curious.

The code does have fence instructions. I have no idea if it is correct, I just took a look at the source code.

Of course it requires fences. It wouldn't be correct otherwise, and would probably not pass the tests even on x86, thanks to compiler re-ordering.

I consider it a queue, despite its non-linearizability. I'll quote from my README where I addressed this concern:

One particular consequence of this design (which seems to be non-intuitive) is that if two producers enqueue at the same time, there is no defined ordering between the elements when they're later dequeued. Normally this is fine, because even with a fully linearizable queue there'd be a race between the producer threads and so you couldn't rely on the ordering anyway. However, if for some reason you do extra explicit synchronization between the two producer threads yourself, thus defining a total order between enqueue operations, you might expect that the elements would come out in the same total order, which is a guarantee my queue does not offer. At that point, though, there semantically aren't really two separate producers, but rather one that happens to be spread across two threads. In this case, you can still establish a total ordering with my queue by creating a single producer token, and using that from both threads to enqueue (taking care to synchronize access to the token, of course, but there was already extra syncrhonization involved anyway). I expect this use case to be fairly rare, though!

Yes. I hadn't looked at the disruptor pattern until yesterday, and I still don't fully understand it. I designed this queue from scratch.

Not the author, but since the whole thing is defined in a header, everything has to be declared inline to avoid violating the one definition rule.

Inline hasn't had anything to do with performance for years (compilers just do what they want anyway), but it's somewhat confusing that the meaning was changed.

It's a matter of personal coding style preference. That's all :-) I like to document which functions I'd prefer to be inlined.

It should make no difference in the output, since I believe all the methods are implicitly 'inline' anyway. And it certainly doesn't affect correctness.