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: Daniel Larimer (dlarimer_at_[hidden])
Date: 2011-07-28 10:48:40

I have used boost::lockfree in an early version of my
https://github.com/bytemaster/Boost.CMT library because I needed a lock-free
producer-consumer queue for sending tasks to my scheduler.  So this review
comes with some "real world" use.

*What is your evaluation of the design?*

The API is relatively straight forward and simple to use.  It gives the user
flexibility in how internals operate.

*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.

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

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.  In other words, if your queue contains polymorphic elements
then you are already calling new once and calling new a second time to
create a node containing a pointer a lot of unnecessary overhead and
blocking.  Furthermore, accessing the 'free list' is not free.

*What is your evaluation of the documentation?*

The documentation is sufficient and easy to understand.

*What is your evaluation of the potential usefulness of the library?*

This library obviously has potential usefulness as I needed lock free data
structures for my scheduler; however, the library, as implemented, was not
useful in my application.  I suspect that there are places where it could be
useful, as implemented, as an alternative to using locks around stl
containers, but fear people will expect more from being 'lock free' than
this implementation can provide considering the heap is the biggest source
of lock contention in most multi-threaded applications.

This library would be much more useful if it provided a lock free linked
list and priority queue.

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

I tried to use the library on Mac OS X using gcc 4.2 and 4.5.  My problems
were mostly related to excessive overhead related to
construction/destruction times and cached free-list implementation.

*How much effort did you put into your evaluation? A glance? A quick
reading? In-depth study?*
Attempted to use in real life, profiled code using lock free fifos,
determined causes of performance problems, and ultimately spun my own
solution.  All in all probably 8 to 16 hours of development using lock
free.

*Are you knowledgeable about the problem domain?*
Knowledgeable enough to roll my own lock-free solutions, but not
knowledgeable enough to be aware of issues like 'false sharing' and other
concerns that were obviously considered in the design and implementation of
boost::lockfree.

*Do you think the library should be accepted as a Boost library?*
*
*
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.
*
*
*
*
On Thu, Jul 28, 2011 at 8:41 AM, Hartmut Kaiser <hartmut.kaiser_at_[hidden]>wrote:

> All,
>
> Today is the last day of the review of Tim Blechmann's Lockfree library. If
> you're interested in this library, please consider contributing a review!
> If you need more time, please contact me privately.
>
>
> Please see the original (slightly corrected) announcement below:
>
> -----------------------------------------------------
>
> About the library:
>
> Boost.Lockfree provides implementations of lock-free data structures.
> Lock-free data structures can be accessed by multiple threads without the
> necessity of blocking synchronization primitives such as guards. Lock-free
> data structures can be used in real-time systems, where blocking algorithms
> may lead to high worst-case execution times, to avoid priority inversion,
> or
> to increase the scalability for multi-processor machines.
>
> The following data structures are provided:
>
> - boost::lockfree::fifo, a lock-free fifo queue
> - boost::lockfree::stack, a lock-free stack
> - boost::lockfree::ringbuffer, a wait-free single-producer/single-consumer
> ringbuffer.
>
> The library is accessible from here:
> http://tim.klingt.org/boost_lockfree.tar.gz.
>
> Boost.Lockfree depends on C++0x atomics. They are not well supported with
> current compilers yet. For this reason Boost.Lockfree depends on the
> *unreviewed* Boost.Atomic library, that emulates C++0x atomics for C++98.
> This review is about Boost.Lockfree and not about Boost.Atomic, although it
> is included in the tarball and the git repository.
>
> If Boost.Lockfree will be accepted, it won't be merged into trunk before
> Boost.Atomic is accepted.
>
> ---------------------------------------------------
>
> Please always state in your review, whether you think the library should be
> accepted as a Boost library!
>
> Additionally please consider giving feedback on the following general
> topics:
>
> - What is your evaluation of the design?
> - What is your evaluation of the implementation?
> - What is your evaluation of the documentation?
> - What is your evaluation of the potential usefulness of the library?
> - Did you try to use the library?  With what compiler?  Did you have any
> problems?
> - How much effort did you put into your evaluation? A glance? A quick
> reading? In-depth study?
> - Are you knowledgeable about the problem domain?
>
> Regards Hartmut
> Review Manager
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>