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@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Michael Dickey Sent: Friday, April 18, 2008 12:40 PM To: boost@lists.boost.org 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@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
_______________________________________________ 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.