Tim Blechmann wrote:
if the algorithm is patented, i hope, the holder won't sue a developer of a gpl implementation Suing is expensive. More likely they would issue an injunction ESPECIALLY if it is gpl. In any case it is a very unpleasant experience ( I did some work as an intellectual property expert witness, and that was unpleasant enough!! Imagine being an actual party in litigation Ugh.)
i am not sure, whether the algorithm for memory reclamation is patented The one I used is based on a stack, and I am sure it is not patented, given that is it common practice. There is even an example in TC++PL. The stack implementation is textbook material. The drawback is that it requires, at the moment, DCAS (e.g. cmpxchg8b). This can be shortened to CAS with a few capacity assumptions, and using pointer compression.
there are no boost/c++-style atomic operations, something like an implementation of n2427 I think that boost only requires portability only between several compiler implementations, and not platforms. While we wait the several years for std::atomic to be ubiquitous, we could rely on either compiler built ins, assembler, etc. for the few platforms we would support at the outset. And just like std::atomic, not every platform will have lockfree implementation of everything. For example, DCAS on 64 bit Solaris is a locked based emulation. But portability is a moot issue if there is nothing to port...
with building blocks for lockfree containers (atomic primitives, aba-safe smart pointers, memory reclamation schemes, ...) These are the most important. Most researchers would prefer to use C++ instead of Java/C#, but they have to know assembler at the moment to get started. And they don't care if it is portable everywhere, just on machines they are likely to have available, which is of course Windows/Linux on Intel. (If they really need something that runs on platform X, then example code is available in the atomic_ops library (on Debian or something like that) which is ported everywhere)
afaict, boost's smart pointer classes are not thread-safe They are not. I have a version that is, as long as you don't care about weak pointers. It still needs a lot of work however. The interesting thing about a ref counted lock-free smart ptr is that it is possible to easily make any program lock free. Not that it will be more efficient than a lock based one, but for small objects it works great.
Lance -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Tim Blechmann Sent: Saturday, April 19, 2008 6:00 AM To: boost@lists.boost.org Subject: Re: [boost] Nonlocking data structures. On Fri, 18 Apr 2008 13:55:35 -0700, Michael Dickey wrote:
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 would consider to change the license for my fifo implementation to a boost-style license, if there would be a demand to use it for a boost.lockfree library ... however there might be some issues, though ... - i am not sure, whether the algorithm for memory reclamation is patented, i am not a lawyer, nor do i know of the legal status of american software patents in europe ... i somewhere read that maged michael's hazard pointers are patented, not sure about the pass-the-buck algorithm, that i used - if the algorithm is patented, i hope, the holder won't sue a developer of a gpl implementation - there are no boost/c++-style atomic operations, something like an implementation of n2427 ... ... as long as these issues are not resolved, i prefer a gpl license :) i would like to see a boost.lockfree library, with building blocks for lockfree containers (atomic primitives, aba-safe smart pointers, memory reclamation schemes, ...), several containers (queue, set, ...) and a lock-free reference counting smart pointer class (afaict, boost's smart pointer classes are not thread-safe) ... of course it would be wonderful to have both dynamic-sized and fized- sized containers, which can be used in hard real-time systems ... cheers, tim -- tim@klingt.org http://tim.klingt.org I must say I find television very educational. The minute somebody turns it on, I go to the library and read a good book. Groucho Marx _______________________________________________ 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.