Boost logo

Boost :

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




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk