Boost logo

Boost :

From: Michael Dickey (mike_at_[hidden])
Date: 2008-04-18 12:40:23

I for one would LOVE to see support in Boost for lock-free data
structures. I imagine that if these were more readily available, a
lot of C++ programmers would want to use them.

I took a (brief) look at the TSTL code (from /. on Freshmeat), and it
does not appear to be lock-free. Rather, it looks like a collection
of primitives for thread-safe programming (which overlaps the
Boost.Thread functionality) combined with some thread-safe data
structures that use these primitives.

Tim seems to have a great lock-free FIFO implementation, although I
see that it uses a GPL license rather than Boost. Any chance we could
convince you to change the license, Tim? (nudge, nudge, wink, wink) =)

I'd like to help make such a library part of Boost, but the more I
learn about lock-free coding, the more I discover that I have yet to
learn =)

I think that for now the most I can offer is enthusiastic
encouragement! =)

Take care,

On Apr 18, 2008, at 8:50 AM, <Lance.Diduck_at_[hidden]> wrote:

> If the CAS is prefixed with 'lock' (intel) then this emits a two way
> barrier. Virtually all compiler built ins of CAS do this. In my
> implementation of queue I did not need barriers other than those
> already
> used by the CAS.
> I am interested in developing some lock-free libs for boost, if other
> are willing to help. I have a working unbounded MS Queue (relies on
> at the moment, but I have ideas on how to just support Single CAS
> (e.g.
> the node allocator could always align on 64 byte boundaries, leaving
> space for a counter with a reasonable range). I have a linearized
> smart_ptr (which makes STM much much easier in C++). I have a
> std::allocator --compatible lockfree allocator (reduced contention
> inside of container quite a bit) and of course a stack.
> Lance
> -----Original Message-----
> From: boost-bounces_at_[hidden]
> [mailto:boost-bounces_at_[hidden]] On Behalf Of Patrick Twohig
> Sent: Friday, April 18, 2008 11:32 AM
> To: boost_at_[hidden]
> Subject: Re: [boost] Nonlocking data structures.
> Another article talks about writing on the Xbox360, which is what I
> needed a queue for:
> On Fri, Apr 18, 2008 at 3:51 AM, Giovanni Piero Deretta
> <gpderetta_at_[hidden]>
> wrote:
>> On Fri, Apr 18, 2008 at 3:09 AM, Cory Nelson <phrosty_at_[hidden]>
> wrote:
>>> On Thu, Apr 17, 2008 at 5:24 PM, Patrick Twohig <p-twohig_at_[hidden]>
>> wrote:
>>>> Theoretically, the CAS should atomically compare and swap the
>>> value
>> in one
>>>> clock cycle. However, with multiple cores/processors/hyper
>> threading where
>>>> multiple instructions are being executed simultaneously over
>> arbitrary
>>>> numbers of clock cycles. There can be writes pending while you
>>> want
>> to read
>>>> from memory. As a result, when you go to read something another
>> process
>>>> will have written to but you read stale data. To combat this,
>>> you
>> enforce a
>>>> memory barrier, which guarantees that all pending memory
>> transactions before
>>>> the barrier have completed before moving on with the program.
>> Additionally,
>>>> some architectures (like x86) allow for unaligned access of
> memory.
>> When an
>>>> unaligned value is accessed, it sets an exception then it
>>> replaces
>> the
>>>> single read/write operation with multiple bus operations which
>> wreaks havoc
>>>> on any compare/swap operations.
>>> They don't happen in a single cycle, I don't think there is
>>> anything specifying that they should. Barriers aren't needed on
>>> x86 or x64, other than compile-time only ones to make sure the
>>> compiler doesn't reorder something.
>> Well, you actually need StoreLoad memory barriers on x86. All other
>> barriers are always implicit (unless you use non temporal SSE
>> store/loads).
>> StoreLoad is also implicit if you use locked operations, otherwise
>> you
>> need an explicit mfence.
>> See, for example,
>> --
>> gpd
>> _______________________________________________
>> Unsubscribe & other changes:
> _______________________________________________
> Unsubscribe & other changes:
> Visit our website at
> This message contains confidential information and is intended only
> for the individual named. If you are not the named addressee you
> should not disseminate, distribute or copy this e-mail. Please
> notify the sender immediately by e-mail if you have received this
> e-mail by mistake and delete this e-mail from your system.
> E-mails are not encrypted and cannot be guaranteed to be secure or
> error-free as information could be intercepted, corrupted, lost,
> destroyed, arrive late or incomplete, or contain viruses. The sender
> therefore does not accept liability for any errors or omissions in the
> contents of this message which arise as a result of e-mail
> transmission.
> If verification is required please request a hard-copy version. This
> message is provided for informational purposes and should not be
> construed as a solicitation or offer to buy or sell any securities
> or related financial instruments.
> _______________________________________________
> Unsubscribe & other changes:

Boost list run by bdawes at, gregod at, cpdaniel at, john at