Re: [boost] [Review] Lockfree review: today (July 28th) is the last day

Subject: Re: [boost] [Review] Lockfree review: today (July 28th) is the last day
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-07-28 11:50:47

hi daniel,

thanks for your review!

> *What is your evaluation of the implementation?*
> In my testing I ultimately removed boost::lockfree::fifo's from my code
> because they were the performance bottleneck. Don't use lock free fifo's
> for short lived 'wait queues' such as a shared future<> object or any
> application that may have 'surges' of demand that allocate large amounts of
> memory that will never be freed until the fifo is destroyed.

i've never argued that boost.lockfree has a high performance (as in throughput), 
but my main concern is lock-freedom. in many cases, lock-based data structures 
can outperform lock-free ones (because atomic operations are usually pretty 
expensive). but in some use cases (e.g. in real-time systems) one wants to use 
data structures that are slow but are guaranteed to be lock-free.

as for the problem of memory reclamation: this is not a trivial issue and 
unfortunately the published algorithms (hazard pointers and pass-the-buck) are 
patented.

> Several use-cases were ignored which have much more efficient lock free
> implementations than the general case.
>    - multiple producer, single consumer.
>    - single producer, single consumer
>    - multiple producer, multiple pop-all
>    - unordered producer-consumer queues

it actually contains a spsc queue (originally named `ringbuffer', but i am 
planing to rename it to `spsc_queue').

> Ultimately I used an intrusive fifo where the elements (tasks) contained
> pointers to the next task (if any).  I then atomically updated the head
> pointer to insert new nodes.  To pop nodes I atomically swap the head node
> to NULL then process all the nodes in the list from tail to head to
> maintain fifo order.

i'd be curious to see the code for this, is it available?

> Despite the problems I had with it, I see no reason not to accept it as a
> good start toward what I hope will be come a larger collection of lock-free
> containers.

i'd be happy to see contributions to the library ;)

cheers, tim