Re: [boost] boost.lockfree update

Subject: Re: [boost] boost.lockfree update
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-08-15 07:53:05

sry for the delay, the mail got lost in my inbox ...

> 1. It seems to me that supporting only POD types makes this whole
> exercise largely academic, since the things most people would want to
> put in the queue will be _not_ be POD.  And storing pointers may not be
> an acceptable option either, since, presumably, if someone's looking for
> a lock free queue his main concern is performance. I had to disable the
> is_pod check  just to be able to benchmark it. My understanding is that
> fifo stores pointers to nodes which off from the heap. Is an
> impossibility on all platforms to have a node with a non-pod type and
> preserve the lock free semantics?

i've relaxed the requirement a bit. the type is actually just required to 
have a trivial assignment, it doesn't need to be a full POD. this 
requirement is specific for the algorithm.

btw, some people use this for real-time applications, where worst-case 
latency is more important than throughput.

> 2. With VC++ on Windows both 32 and 64 bit, fifo reverts to using
> spinlocks even though there's a 64 bit equivalent of interlocked
> intrinsics in 64bit builds. Intel's implementation, I believe, supports
> lockfree atomic<long long> even on 32 bit systems so this should be
> possible.

true ... there have been some people mentioning this, it shouldn't be hard 
to implement dcas for boost.atomic. unfortunately neither helge nor me seem 
to use msvc and nobody with msvc wants to get his hands dirty to implement 
the specific part ...

> 3. I also think it's important to provide size() method if only for
> monitoring purposes. (unsafe_size() maybe). Most people would want to
> take some action if the size of the queue exceed a reasonable (in their
> domain) limit.

this would have two issues:
- it won't be accurate
- it would either be expensive to call (O(n)) or introduce an overhead of an 
atomic operation per push/pop

> 4. is_lock_free() should be a compile time check. I may want to chose a
> different queue if the lock free version isn't available.

i'd prefer a compile-time check as well, but std::atomic::is_lock_free is a 
run-time check ...

> All this said, I have to say that the fifo performance in our
> environment (64 bit linux with 8 xeon processors, gcc 4.5) was quite
> good. Comparable with tbb::concurrent_queue and way better than all the
> other options we tried.

good to hear. tbb::concurrent_queue is a blocking algorithm (iirc they are 
using spinlocks), while boost::lockfree::fifo is lockfree. so they have 
somewhat different performance characteristics.
the concurrent_queue may have acquire the spinlock and the os decides to 
suspend the thread. this may be rare, but it is not impossible. the 
lockfree::fifo doesn't have this issue ...

cheers, tim

-- 
tim_at_[hidden]
http://tim.klingt.org
Trane was the Father...Pharoah was the son...I am the Holy Ghost.
  Albert Ayler