cameron314

Yes, it is essentially an abstraction over a collection of SPMC queues (when using tokens to dequeue, it is actually a bit smart in that it tries to pair producers with consumers where possible).

If you wrapped every enqueue operation in a lock and used the same producer token, then you'd essentially have a single SPMC queue, and it would be fully FIFO. But obviously this defeats the purpose somewhat, so yes, it's not a good solution if you need that guarantee.

I honestly didn't consider external inter-thread ordering at all while I was designing the queue. I guess I was picturing more of a producer-consumer model, than a message passing system (where this dependence between messages across threads/producers is far more common, it seems).

I'd change this constraint if I could, but I can't. It's the fundamental assumption the very heart of the entire design. I'd have to start from scratch (which I'm not prepared to do, at this point). But I've changed the README to make this limitation crystal clear (you're not the only one with reservations with regards to this aspect).

I think it's still useful, perhaps not for all applications, but for many. Sorry if I came across as trying to purport it as something that it wasn't; that was not my intention at all.

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.

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.

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.

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.

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!

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.