Re: [boost] Nonlocking data structures.

From: patrick.twohig (p-twohig_at_[hidden])
Date: 2008-04-18 13:59:05

Well I guess I ought to set up a project on sf.

--Sent via Gmail mobile.


attached mail follows:

There is lots of ways to help, even if you've never touched lockfree
programming. In the case of queues, stacks and such, these are well
understood, and really need to library-tized. e.g.
1. source code conforms to boost style and repository guidelines
2. test harnesses written and integrated with boost build (e.g. my
system uses regular make and CPPUNIT)
3. docs and example code written
   
All of the above is very important, and does not require any knowledge
of lock free programming, just an interest. There is even much design
work to be done, for instance, this is my queue interface
template<class _Val> //_Val must be bitwise comparable
class michael_scott_queue {
typedef _Val value_type;
//other typedefs
michael_scott_queue() ;
~michael_scott_queue();
void push(value_type const &_val);
bool pop(value_type&return_val);//return false on empty
private:
        volatile node_type m_head;//node_type implements CAS instruction
        volatile node_type m_tail;
        allocators::MTSlab<> m_allocator;//lock free node allocator
(fixed size blocks)
};

Now, without knowing anything about how ctor, dtor, push and pop are
implemented, what can be done? Adding allocator as a parameter just like
a std::container; changing node_type to conform to std::atomic; perhaps
making a version that includes a monitor (so that pop blocks rather than
returns false) and so forth. I havent worked out yet the exception
guarantees. There is lots of stuff, and you can learn lock free
programming on the way. If you have done distributed programming before,
then lock -free SMP programming is simply using loss-free communication
channels that are only a word or two wide, and there is no such thing as
a "intermediate invalid" state -- i.e. all operations (messages)
preserve all invariants. If you have never done distributed programming,
well, then there is a lot to learn indeed!!  

Lance

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Michael Dickey
Sent: Friday, April 18, 2008 12:40 PM
To: boost_at_[hidden]
Subject: Re: [boost] Nonlocking data structures.

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
>

_______________________________________________
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