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.