I have been in touch with Mark Moir (he was one of the transactional memory speakers at boostcon), wrt the boost lockfree library. As an expert in the field, he was kind enough to do a mini-review. I am posting his comments here and am hoping that these don't get lost in the usual fray of activity, as he is one of the few bona-fide experts in the field that will take the time to actually review the submission. His comments are below: ==== This is mostly a matter of taste, but I don't much care for the approach of having CAS increment the version number, rather than having this explicit in the algorithm, for at least the following reasons: - it is not in keeping with standard cas operations, so an important part of the algorithm appears to be missing; at a minimum, cas should be renamed to cas_and_bump_version or something. - not all algorithms need to increment the version number on every CAS, for example, the stack algorithm is correct provided we increment the version number of every pop; it does not need to be done on push. This is only a (probably minor) performance concern in the stack algorithm, but one can imagine cases in which it would be important not to increment the version every time, and for such cases, a different library would be needed. - There is an awkward mix of handling version numbers in the fifo code. The node constructor explicitly increments the version number, whereas all other dealing with the version number are hidden behind cas, etc. Furthermore, this explicit incrementing is unnecessary, as far as I can tell. To avoid a "late" enqueue accidentally succeeding, the version number of a node's next pointer should be incremented once for each time it goes through the queue. But this is done by the cas of the enqueue that installs a node after it, and I think this is sufficient. I don't like "just in case" code. The authors should understand whether it's really necessary, and if so, document the reason. If (as I suspect), it's not, they should get rid of it. - I also think there should be more comments about these kinds of subtle issues, especially because the Michael & Scott paper played a little fast and loose with this. (Although they do confess to using a free list, there is a strong suggestion that nodes can be "freed" (as opposed to being put in a type-stable free list), and also no discussion of the importance of preserving version numbers of nodes in the free list. - I think there is a bug in the empty method of the fifo, at least for some memory models. (Note too that M*S did not present an empty method, so again additional comments would be appropriate IMO.) The problem is that the order of the reads is critical to ensure correctness, but there is no memory barrier to enforce this ordering. (Note that if either the compiler or the processor reorders the two loads, it is possible for empty to read tail while the queue is nonempty, then another enqueue happens, then all items that were in the queue when tail was read are removed. Now head has the same value as was read from tail previously, so the comparison can succeed and empty can return true, but the queue was never empty.) Again, I think a comment would be appropriate. ====== Hope this is helpful. Best wishes, Tom PS: It was a real pleasure meeting everyone at the conference.