Re: [boost] Nonlocking data structures.

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,
-Mike

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  
> DCAS
> 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:
> http://msdn2.microsoft.com/en-us/library/bb310595(VS.85).aspx
>
>
>
> 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, http://g.oswego.edu/dl/jmm/cookbook.html
>>
>> --
>> gpd
>> _______________________________________________
>> Unsubscribe & other changes:
>> http://lists.boost.org/mailman/listinfo.cgi/boost
>>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
> Visit our website at http://www.ubs.com
>
> 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: http://lists.boost.org/mailman/listinfo.cgi/boost
>