Re: [boost] Nonlocking data structures.

From: Lance.Diduck_at_[hidden]
Date: 2008-04-18 11:50:22

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.