Re: [boost] Nonlocking data structures.

From: Michael Dickey (mike_at_[hidden])
Date: 2008-04-18 16:55:35

It does sound like an interesting project to me, but unfortunately I  
feel my "free (non-work) time" is already over-tasked with working on  
http support for a boost network library.  Perhaps once that project  
is done I can lend a hand to help out with this.

Take care,
-Mike

On Apr 18, 2008, at 10:23 AM, <Lance.Diduck_at_[hidden]> <Lance.Diduck_at_[hidden] 
 > wrote:
> 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
>