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@ubs.com> 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@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Patrick Twohig Sent: Friday, April 18, 2008 11:32 AM To: boost@lists.boost.org 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@gmail.com> wrote:
On Thu, Apr 17, 2008 at 5:24 PM, Patrick Twohig <p-twohig@ieee.org> wrote:
Theoretically, the CAS should atomically compare and swap the value in one clock cycle. However, with multiple cores/processors/hyper
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
will have written to but you read stale data. To combat this, you enforce a memory barrier, which guarantees that all pending memory
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
On Fri, Apr 18, 2008 at 3:09 AM, Cory Nelson <phrosty@gmail.com> wrote: threading where process transactions before 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