Re: [boost] threadpool lockfree_channel

Subject: Re: [boost] threadpool lockfree_channel
From: Anthony Williams (anthony.ajw_at_[hidden])
Date: 2009-03-16 09:37:21

Tim Blechmann <tim_at_[hidden]> writes:

>> Firstly, I'd like to help with this. I have a couple of lock-free queue
>> implementations lying around from my book. I've attached a sample
>> implementation that uses atomic reference-counting --- it would need to
>> be "boostified", as it's written for C++0x, but that should be
>> relatively straightforward. I don't make any claims for performance, but
>> I believe it to be "correct", with no data races or undefined behaviour
>> --- I *really* want to know if that's not the case, so I can correct it
>> before the book goes to press.
>
> while the implementation of your queue looks good to me, i am a bit
> concerned about the use of dynamic memory allocation ... it is
> `lockfree' in terms of the data structure implementation, but allocating
> memory from the os (for node and T), its behavior is depending on the
> new/delete implementation.

Yes, with a poor allocator there will be a performance hit and
potentially locking inside the allocator. I would just replace the
global allocator with a proper MT allocator such as Hoard in the first
instance, and I hope that the C++0x compilers ship with such an
allocator.

If the allocator performance is still an issue it can easily be
replaced with a custom allocator designed for the specific use case.

> in my implementation pop is lockfree in any case, while push is lockfree
> as long as the number of nodes does not exceed the preallocated node
> count ...
> while this may be negligible for an average-case scenario, it is quite
> significant for the worst-case ...

Yes. You could amortize the cost by allocating chunks of nodes rather
than single nodes, but then you need to track the chunks...

Anthony
-- 
Anthony Williams
Author of C++ Concurrency in Action | http://www.manning.com/williams
Custom Software Development | http://www.justsoftwaresolutions.co.uk
Just Software Solutions Ltd, Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK