[boost] Boostcon followup - Boost Lockfree review - On behalf of Mark Moir

Subject: [boost] Boostcon followup - Boost Lockfree review - On behalf of Mark Moir
From: Tomas Puverle (tomas.puverle_at_[hidden])
Date: 2010-05-18 14:15:20

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.