[boost] Lockfree review

Subject: [boost] Lockfree review
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-07-28 15:14:41

Dear All,

Here is a quick review of the proposed Boost.Lockfree library.

Utility
-------

For some proposed libraries their utility is beyond doubt because they 
are already being used in some significant application.  In contrast 
most GSoC projects are developed more in the "hope that they will be 
useful" without a motivating application.  So we have to ask ourselves, 
does this library meet a need?  To me, lock free algorithms and data 
structures have always seemed appealing at first sight but, apart from 
some trivial cases like counters, on close inspection they turn out to 
be too complicated to bother with.  (They also lack required features, 
i.e. waiting for non-empty; I don't think I've ever written a 
producer-consumer application that didn't need the consumer to block on empty.)

The author acknowledges that these structures will typically be slower 
than conventional implementations using mutexes, but claims that their 
benefit comes in terms of better worst-case latency.  Specifically, if 
a thread is pre-empted while it holds a lock, another thread will have 
to wait until the first thread is re-scheduled and can unlock before it 
can itself lock.  But this case is exactly the one that priority 
inversion is supposed to address: when the second thread tries to lock, 
the kernel immediately re-schedules the first thread.  Yes, because of 
the kernel involvement this will probably still be slower than the 
lock-free approach, but perhaps not by much.  It seems to me that the 
author should present benchmarks to demonstrate the actual worst-case 
latency difference between this code and a lock-based implementation.

Design
------

I am happy with the design of the interface, as far as it goes; there 
are a few things that could be added though:

- Debug modes that check the thread requirements.
- Other combinations of single/multiple producer/consumer.

Implementation
--------------

I have looked only at the implementation of the ringbuffer class 
template.  It lacks comments.  There are some oddities like this:

         size_t ret = read_index - write_index - 1;
         if (write_index >= read_index)
           ret += max_size;
         return ret;

Here, a negative value may be assigned to the unsigned size_t.  I think 
this is actually safe, but it looks odd.  I have not found any bugs.

It looks like every call to enqueue() and dequeue() will access both 
the read and write indexes.  Won't this cause poor performance due to 
cache issues?  I would have been tempted to avoid this by keeping local 
'available' counts: (PSEUDO_CODE)

private:
   atomic<size_t> read_index_;
   atomic<size_t> write_index_;
   size_t read_available_;
   size_t write_available_;

public:
   bool enqueue(...) {
     if (write_available_==0) {
       // In this case, we access read_index_ which is probably cached 
by the consumer thread,
       // which is expensive.  But this is rare.
       write_available_ = (read_index_ + max_size - write_index_ - 1) % max_size;
     }
     if (!write_available_) return false;  // full
     buffer[write_index_.load(memory_order_relaxed)] = data;
     write_index_.store((write_index_+1)%max_size);
     --write_available_;
   }

   // dequeue similarly...

Documentation
-------------

I'm not impressed by the documentation.  It lacks rationale and 
information about the implementation.  It has some formatting issues 
and typos (e.g. lose/loose).  Platform requirements (i.e. the 
Boost.Atomic and/or std::atomic requirements and supported 
architectures) should be explained.

The reference documentation involves more clicks than I would expect to 
reach the actual content.

Some functions are marked as "for debugging only", e.g. the empty() and 
reset() [which should probably be called clear()] methods.  It's not 
clear to me why these methods must be unsafe; for example, for the 
ringbuffer, I would expect the consumer thread to safely be able to 
call empty() and the producer to safely be able to call full() (which 
is not provided).  Rationale for these restrictions (or relaxations of 
them) would be useful.

- Did you try to use the library?  With what compiler?  Did you have 
any problems?

I considered exercising the library on my ARM systems, but I realised 
that it requires 64-bit atomics; currently, Boost.Atomic only provides 
32-bit atomics on ARM.  (This raises the whole issue of the 
Boost.Atomic dependency.  I'm presuming that Tim intends not to bundle 
a Boost.Atomic snapshot with the library if approved.  If that changes, 
we really need another review.)

- How much effort did you put into your evaluation? A glance? A quick 
reading? In-depth study?

A few hours reading the docs and code.

- Are you knowledgeable about the problem domain?

I know a certain amount about atomics and lock-based concurrent 
programming, but not much about lock-free data structures.

- Please always state in your review, whether you think the library 
should be accepted as a Boost library!

I think it should be accepted provided that:
* The author demonstrates some measurable benefit over lock-based data structures.
* The documentation is improved to describe the implementation and to 
provide rationale for design decisions.
* The library is not added to Boost until Boost.Atomic has been 
reviewed and approved (or, available std::atomic implementations work 
with it).

Regards,  Phil.