Re: [boost] Nonlocking data structures.

From: Lance.Diduck_at_[hidden]
Date: 2008-04-21 10:36:08

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_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Tim Blechmann
Sent: Saturday, April 19, 2008 6:00 AM
To: boost_at_[hidden]
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_at_[hidden]
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.