Hey all,

I've been using Threading Building Blocks for the past year, and I'm
very happy with it.  Lately I have been researching wait-free
algorithms, and have been reading "The Art of Multiprocessor
Programming".  I would like to cooperate to implement some wait-free
algorithms using TBB as a basis.  I fully appreciate the difficulty of
developing wait-free algorithms, so if anyone has a source of
algorithms that could just be coded into TBB in C++ I would be happy
to do so... although I suspect many algorithms may require fine tuning
to use the cache effectively.

Looking forward to helping.  Also, I have an SVN repository setup as
part of "TBB Community Code" which hosts open source libraries
licensed under the same open source license as TBB itself.

I lurk on #tbb on irc.freenode.net, so come on out and chat.

AJ

hi all,

i have been releasing some c++ implementations of lock-free data
structures under a boost-style license ... maybe some of this code is
interesting for some list-members ...
it mainly provides an implementation of a lockfree fifo, but the
framework also provides utility classes (e.g. a tagged_ptr) and
low-level functions (memory barriers, compare-and-swap) ...

i am curious, if someone from this list is interested in contributing,
code reviewing, porting, testing, etc ...
for now, linux, >=gcc-4.2, x86/x86_64 is the only tested setup ...
untested code for msvc & gcc/osx is available, though

there is a public git repository:
http://tim.klingt.org/git?p=boost_lockfree.git;a=summary
git://tim.klingt.org/boost_lockfree.git

best, tim

--
tim@...
http://tim.klingt.org

The aim of education is the knowledge, not of facts, but of values
   William S. Burroughs

Is it available as an eBook?

Chance

Maurice Herlihy wrote:
> Dear Friends:
>
> Morgan Kaufmann has just released our book, ``The Art of
> Multiprocessor Programming''
>
> 
http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/01237059\
16
>
> Lecture slides and (soon!) exercise solutions available at
>
>  http://books.elsevier.com/companions/defaultindividual.asp?isbn=9780123705914
>
> Feedback and reactions welcome.
>
>      Maurice Herlihy and Nir Shavit
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>

Dear Friends:

Morgan Kaufmann has just released our book, ``The Art of
Multiprocessor Programming''

 
http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/01237059\
16

Lecture slides and (soon!) exercise solutions available at

  http://books.elsevier.com/companions/defaultindividual.asp?isbn=9780123705914

Feedback and reactions welcome.

      Maurice Herlihy and Nir Shavit

Hey all,

	 I just wanted to update everyone on the latest developments in C++0x
(hopefully that will be C++08!). Lawrence Crowl, one of the members of
the committee gave a talk to google back in may about the developments:

http://video.google.com/videoplay?docid=3528799355371049884

One of the most important things is that C++ will have built-in
support for threads, including a memory model, synchronization and
atomics. Since he gave his talk, the committee has decided to add
limited support for fences as well.

Note that GCC currently has intrinsic support for atomic operations
(http://gcc.gnu.org/onlinedocs/gcc-4.1.0/gcc/Atomic-Builtins.html
) and even fences, so it's possible to build such types now that's at
least compatible with gcc. I'm going to write a prototype for and
atomic int for GCC if anyone is interested -- should be pretty simple
with those intrinsics, but who knows.

Lawrence sent me this. The papers are a bit hard to find, but knowing
which ones to look for helps a lot:

You can keep up at the C++ standards committee web site:

http://www.open-std.org/JTC1/SC22/WG21/

Under the link 'papers' you can find the latest papers in each area of
threading:

2007 N2427 C++ Atomic Types and Operations
2007 N2429 Concurrency memory model (final revision)
2007 N2440 Abandoning a Process
2007 N2459 Allow atomics use in signal handlers
2007 N2480 A Less Formal Explanation of the Proposed C++ Concurrency
Memory Model
2008 N2492 C++ Data-Dependency Ordering: Atomics and Memory Model
2008 N2493 C++ Data-Dependency Ordering: Function Annotation
2008 N2497 Multi-threading Library for Standard C++ (Revision 1)
2008 N2513 Dynamic Initialization and Destruction with Concurrency
2008 N2514 Implicit Conversion Operators for Atomics
2008 N2516 Threads API Review Committee Report
2008 N2519 Library thread-safety from a user's point of view, with
wording
2008 N2528 Timed_mutex in C++0x

-----------------------------
Bjorn Roche
XO Wave
Digital Audio Production and Post-Production Software
http://www.xowave.com
http://blog.bjornroche.com
http://myspace.com/xowave

hi all,

did someone on this list already have a look at securuslib
(http://www.securuslib.com/)?

best, tim

--
tim@...
http://tim.klingt.org

The composer makes plans, music laughs.
   Morton Feldman

--- In liblf-dev@yahoogroups.com, "Chris Purcell"
<chris.purcell.39@...> wrote:
>
> Pass-the-Buck requires a hardware primitive not avalable on many
> platforms (DWCAS). Michael's SMR requires only reads and writes (and
> memory barriers for correctness).
>

Yes the original PTB algo requires DCAS which as Chris pointed out
available on almost none modern chips; there is an "alternative" algo,
however, which reuires only one-word CAS primitive and thus therotical
"obstruction free"; I personally used this alternative algo for
operation descriptor reclamation purpose in my own draft code of
Multi-word CAS package (hopefully I could finish it soon and present
it somewhere as open source library)

As to SMR or Hazard Pointer GC, I have my own opinion of its practical
use. For small-scaled, short-lived operation descriptors, I prefer the
alternative of PTB; for more general dynamic memory GC, Fraiser's
Eopboch-based Reclamation is actually an flexible and extensible means
- I have a brief implementation using C++ template of EBR GC, coded
and tested on Intel Core Quad chips and Linux 2.6.23; personally I'd
like to see wide application of EBR gc in C++ application.

> Cheers,
> Chris
>

Thanks,

Lxguru Sinonuck

----- Original Message -----
From: "Chris Purcell" <chris.purcell.39@...>
To: <liblf-dev@yahoogroups.com>
Sent: Sunday, January 06, 2008 8:59 PM
Subject: Re: [liblf-dev] Re: Valois' algorithm of memory reclamation


> Pass-the-Buck requires a hardware primitive not avalable on many
> platforms (DWCAS). Michael's SMR requires only reads and writes (and
> memory barriers for correctness).
>
> Cheers,
> Chris
>
> On Dec 26, 2007 3:07 AM, lxgurus <lxgurus@...> wrote:
>> I am not sure if some people had evaluated Michael&Scott's memory
>> reclamation (RC), Michael's Hazard Point, against Herlihy's ROP
>> Pass-the-Buck. My initial appreciation is Herlihy's way superior.
>>
>>
>>  Lxguru Sinonuck
>>
>>
>>
>>
>>
>>
>> Yahoo! Groups Links
>>
>>
>>
>>
>
>
>
> Yahoo! Groups Links
>
>
>
>

Pass-the-Buck requires a hardware primitive not avalable on many
platforms (DWCAS). Michael's SMR requires only reads and writes (and
memory barriers for correctness).

Cheers,
Chris

On Dec 26, 2007 3:07 AM, lxgurus <lxgurus@...> wrote:
> I am not sure if some people had evaluated Michael&Scott's memory
> reclamation (RC), Michael's Hazard Point, against Herlihy's ROP
> Pass-the-Buck. My initial appreciation is Herlihy's way superior.
>
>
>  Lxguru Sinonuck
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>

I am not sure if some people had evaluated Michael&Scott's memory
reclamation (RC), Michael's Hazard Point, against Herlihy's ROP
Pass-the-Buck. My initial appreciation is Herlihy's way superior.

  Lxguru Sinonuck

Hi guys,

Michael & Scott's algorithm works instead. The important assumption is
nodes in free pool(stack) must have refct_claimbit as 1! Sorry for the
confusion. Thanks.

Lxguru Sinonuck

Hi people,

While I was implementing multi-word CAS, I used memory pool for those
operation descriptors (of DCSS/CCAS and MCAS). The memory reclamation
algorithm I used is from ERRTA Lock-Free Linked Lists Using
Compare-and-Swap by John Valois. Relevant pseudo code listed:
    Release(p: pointer)
      1.  c-<Fetch&Add(p->refct, -2)
      2.  if (c!=3) then
      3.      return
      4.  if CAS(p->refct, 1, 0) then
      5.      Reclaim(p)

    SafeRead(p)
      1.  loop
      2.     q = *p
      3.     if (q == NULL) then
      4.         return NULL
      5.     AtomicAdd(q->refct, 2)
      6.     if (q == *p) then
      7.         return q
      8.     else
      9.         release(q)

    Alloc()
      1.   repeat
      2.      q = SafeRead(Freelist)
      3.      if (q == NULL) then
      4.         return NULL
      5.      r = CAS(Freelist, q, q->next)
      6.      if (r == FALSE) then
      7.         Release(q)
      8.   until r == TRUE
      9.   ResetClaimbit(q->refct)    //use AtomicSub
      10.  return q

However, under some race condition, a just allocated node would be
reclaimed incorrectly. Here is the sequence to trigger:
      thread 1             thread 2           refct (Freelist->q)
                                                0
      call Alloc().2                            2
                           call Alloc().2       4
      call Alloc().5                            4 (pop off)
      call Alloc().9                            3
                           call Alloc().5       3 (failed)
                           call Alloc().7       0 (!->q reclaimed!)
      call Alloc().10                           0 (!q node alloc!)
                           ...

I'm probably not first or only person to notice this, but:

Intel Software Dispatch have announced the availability of the
<http://threadingbuildingblocks.org/>Threading Building Blocks (TBB)
template library under the GPL v2 with the run-time exception

http://threadingbuildingblocks.org/
--------------------------------------------------------------------------------\
-
Aaron Oxford   -   aaron+hardwarehookups .com .au
Director, Innovative Computer Solutions (Aust) Pty. Ltd.
49 Maitland Rd, Mayfield, NSW 2304 Australia
http://www.ic-solutions.com.au
Developer, SourceForge project VioLet Composer
http://sourceforge.net/projects/buzz-like

Hello Chris

I am not a lawyer but I think your attitude towards patents is not a
particularly productive one. There are many ways to legally use patented IP
and there are many ways in which patent holders respond to IP infringement.
To give one example, I understand that the RCU lock-free algorithm used in
the Linux kernel has been provided free of charge by the patent holder (IBM)

Many of the algorithms we are discussing are already implemented in
available systems on at least one platform and none of those implementations
have attracted any legal attackes (let alone fatal ones).

It would also be helpful if you stated which algorithms you know/believe to
be patented rather than simply stating that "most lock free algorithms are
patented." Since you seem to be well informed about these things perhaps you
could help us identify which algorithms are not patented. To the best of my
knowledge SMR and a derivived memory manager are the only algorithms
discussed here which have active patents on them.

Best wishes

Ross.


----- Original Message -----
From: "Chris Thomasson" <cristom@...>
To: <liblf-dev@yahoogroups.com>
Sent: Saturday, March 31, 2007 6:33 PM
Subject: [liblf-dev] BEWARE! most lock-free algorithms are patented!


> How many developers in this group understand that most lock-free
> algorithms
> are patented, or have patents pending?
>
> This group sounds like your all going to be using stuff that will get you
> SUED TO DEATH!
>
>
>
> BTW, I can be reached at USENET: comp.programming.threads
>
>
>
>
> Yahoo! Groups Links
>
>
>

How many developers in this group understand that most lock-free algorithms
are patented, or have patents pending?

This group sounds like your all going to be using stuff that will get you
SUED TO DEATH!



BTW, I can be reached at USENET: comp.programming.threads

--- In liblf-dev@yahoogroups.com, "Greg Herb" <greg_herb@...> wrote:
>
>
> New poster here...
>
> Has anyone checked out Intel's Thread Building Blocks?  I understand
it's
> not open source but it looks pretty cheap.  I would love to see an
> open-source version of this.  Any thoughts or opinions?

http://groups.google.com/group/comp.programming.threads/msg/a96f9472846b
d543

in addition to that, there is no way your going to see free opensource
for it... Do a patent search.

How many developers in this group understand that most lock-free algorithms
are patented, or have patents pending?

This group sounds like your all going to be using stuff that will get you
SUED TO DEATH!



BTW, I can be reached at USENET: comp.programming.threads

How many developers in this group understand that most lock-free
algorithms
are patented, or have patents pending?

This group sounds like your all going to be using stuff that will get
you
SUED TO DEATH!



BTW, I can be reached at USENET: comp.programming.threads

Hey all,

	 I've started a subversion repo here: http://liblf.xowave.com/. It is
publicly readable, and I'm happy to give people write access to folks
who want to contribute. It's pretty sloppy at the moment, but I think
it's a start.

Here's a quick description of the files:

Atomic.h - has atomic primitives for things needed in the rest of the
code. Conditional compiling should make this extensible to any
platform, but right now it works on Mac OS X and might be good enough
for Linux. I'd love to see the Linux side fixed up, not to mention
some windows work.

Fifo.h - your basic non-blocking fifo. Generically typed. There is
also some old commented code that could be used as a blocking Fifo.

Async.cc
Async.h - implement an asynchronous Queue of "operations" that can be
performed in a separate thread. Useful for reading from or to a file
in the background. A nice improvement on this would be an interface
for reclaiming completed operations.

sleep.cc
sleep.h - just for short sleeps. Useful for testing and also the few
functions that "block".


ThreadSafeList.h - a Queue that can (in theory) be edited from one
thread while iterated through in another.

makefile - building and cleaning and running the test program. I
think this requires gmake.

test.cc - some tests.

	 bjorn

-----------------------------
Bjorn Roche
XO Wave
Digital Audio Production and Post-Production Software
http://www.xowave.com
http://blog.bjornroche.com
http://myspace.com/xowave

Hey all,

	 I've started a subversion repo here: http://liblf.xowave.com/. It is
publicly readable, and I'm happy to give people write access to folks
who want to contribute. It's pretty sloppy at the moment, but I think
it's a start.

Here's a quick description of the files:

Atomic.h - has atomic primitives for things needed in the rest of the
code. Conditional compiling should make this extensible to any
platform, but right now it works on Mac OS X and might be good enough
for Linux. I'd love to see the Linux side fixed up, not to mention
some windows work.

Fifo.h - your basic non-blocking fifo. Generically typed. There is
also some old commented code that could be used as a blocking Fifo.

Async.cc
Async.h - implement an asynchronous Queue of "operations" that can be
performed in a separate thread. Useful for reading from or to a file
in the background. A nice improvement on this would be an interface
for reclaiming completed operations.

sleep.cc
sleep.h - just for short sleeps. Useful for testing and also the few
functions that "block".


ThreadSafeList.h - a Queue that can (in theory) be edited from one
thread while iterated through in another.

makefile - building and cleaning and running the test program. I
think this requires gmake.

test.cc - some tests.

	 bjorn

-----------------------------
Bjorn Roche
XO Wave
Digital Audio Production and Post-Production Software
http://www.xowave.com
http://blog.bjornroche.com
http://myspace.com/xowave

Hey all,

	 I've started a subversion repo here: http://liblf.xowave.com/. It is
publicly readable, and I'm happy to give people write access to folks
who want to contribute. It's pretty sloppy at the moment, but I think
it's a start.

Here's a quick description of the files:

Atomic.h - has atomic primitives for things needed in the rest of the
code. Conditional compiling should make this extensible to any
platform, but right now it works on Mac OS X and might be good enough
for Linux. I'd love to see the Linux side fixed up, not to mention
some windows work.

Fifo.h - your basic non-blocking fifo. Generically typed. There is
also some old commented code that could be used as a blocking Fifo.

Async.cc
Async.h - implement an asynchronous Queue of "operations" that can be
performed in a separate thread. Useful for reading from or to a file
in the background. A nice improvement on this would be an interface
for reclaiming completed operations.

sleep.cc
sleep.h - just for short sleeps. Useful for testing and also the few
functions that "block".


ThreadSafeList.h - a Queue that can (in theory) be edited from one
thread while iterated through in another.

makefile - building and cleaning and running the test program. I
think this requires gmake.

test.cc - some tests.

	 bjorn

-----------------------------
Bjorn Roche
XO Wave
Digital Audio Production and Post-Production Software
http://www.xowave.com
http://blog.bjornroche.com
http://myspace.com/xowave

Hey gang,

	 I'm reworking some of the code in my app, but it seems I'm already a
bit rusty on this lock-free stuff -- or maybe it never really sank
in. Anyway, I've already got a single-thread read/single-thread write
as part of PortAudio, and I'd like to c++-ify that. I also want a
linked list that can be safely iterated from one thread and modified
from another (in fact, I think I've got that working, but I'm still
unsure of the barriers and I don't have adequate test cases). A few
other things would be handy, too, (a red-black tree would be sweet).
I want to keep it as simple as possible, 'cause my old code is a
freakin' mess.

	 Is anyone interested in working on this stuff with me?

	 bjorn

-----------------------------
Bjorn Roche
XO Wave
Digital Audio Production and Post-Production Software
http://www.xowave.com
http://blog.bjornroche.com
http://myspace.com/xowave

On Mar 22, 2007, at 11:22 AM, t o b e wrote:

> Free is also theoretically unbounded in time since it needs to take
> the same global lock that malloc does whilst manipulating the heap.
>
> Since it seems that a different thread already mallocs your blocks
> why not use the same thread to free them ?
>

Thanks for the responses. I'd like to free in that thread because
it's convenient to do so, and it will require a bit of extra
bookkeeping otherwise.

	 bjorn

-----------------------------
Bjorn Roche
XO Wave
Digital Audio Production and Post-Production Software
http://www.xowave.com
http://blog.bjornroche.com
http://myspace.com/xowave

Hey all,

I know I can't malloc data in the audio thread of my app (since it
is unbounded in time), but can I call free? It would simplify my
implementation if I could free data in my audio thread, and I can't
find much info using google.

thanks,

bjorn

-----------------------------
Bjorn Roche
XO Wave
Digital Audio Production and Post-Production Software
http://www.xowave.com
http://blog.bjornroche.com
http://myspace.com/xowave

Hey all,

	 I know I can't malloc data in the audio thread of my app (since it
is unbounded in time), but can I call free? It would simplify my
implementation if I could free data in my audio thread, and I can't
find much info using google.

	 thanks,

	 bjorn

-----------------------------
Bjorn Roche
XO Wave
Digital Audio Production and Post-Production Software
http://www.xowave.com
http://blog.bjornroche.com
http://myspace.com/xowave

New poster here...

Has anyone checked out Intel's Thread Building Blocks?  I understand it's
not open source but it looks pretty cheap.  I would love to see an
open-source version of this.  Any thoughts or opinions?

http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm

Thanks!

-Greg

_________________________________________________________________
Find a local pizza place, movie theater, and more….then map the best route!
http://maps.live.com/?icid=hmtag1&FORM=MGAC01

Yes. The algorithm doesn't work without memory management, as it's not
safe to free an element of the list until all concurrent readers have
stopped looking at it (which the basic list algorithm doesn't verify).
Reread Michael's paper for one solution (SMR).

Chris

On 2/27/07, Tim Blechmann <tim@...> wrote:
> hi chris,
>
> i haven't implemented any memory management, this would have to be done
> from the user of the data structures ...
> i'm guess, this is no problem, if the user of the data structures is
> aware of this and takes care of the memory management himself, or am i
> missing a problem there?
>
> thanks, tim
>
>
> On Tue, 2007-02-27 at 09:12 +0000, Chris Purcell wrote:
> > At a brief glance, you appear to be missing memory management, e.g.
> > SMR, reference counting or a garbage collector.
> >
> > Cheers,
> > Chris Purcell
> >
> > On 2/26/07, Tim Blechmann <tim@...> wrote:
> > > hi all,
> > >
> > > thomas grill and i were working on c++ implementations of two
> > lockfree
> > > data structures, the scott&michael queue and michael's list-based
> > set.
> > >
> > > they are implemented as c++ data structures, using the atomic
> > operations
> > > from the atomic_ops project and can be downloaded from my subversion
> > > repository at http://svn.klingt.org/pnpd/trunk/libs/lockfree/
> > >
> > > the queue implementation has been tested on multicore processors and
> > > seems to work very well.
> > > the michael set, which is based on his paper "High Performance
> > Dynamic
> > > Lock-Free Hash Tables and List-Based Sets", works fine on single
> > > processor systems, but thomas's tests on his dualcore computer show,
> > > that the implementation is not smp-safe.
> > >
> > > it would be great if someone of the lockfree gurus on this list
> > could
> > > have a brief look at the implementations ...
> > >
> > > cheers ... tim
> > >
> > > --
> > > tim@... ICQ: 96771783
> > > http://tim.klingt.org
> > >
> > > Question: Then what is the purpose of this "experimental" music?
> > > Answer: No purposes. Sounds.
> > > John Cage
> > >
> > >
> >
> >
> >
> >
> --
> tim@...    ICQ: 96771783
> http://tim.klingt.org
>
> Every word is like an unnecessary stain on silence and nothingness
>   Samuel Beckett
>
>

hi chris,

i haven't implemented any memory management, this would have to be done
from the user of the data structures ...
i'm guess, this is no problem, if the user of the data structures is
aware of this and takes care of the memory management himself, or am i
missing a problem there?

thanks, tim


On Tue, 2007-02-27 at 09:12 +0000, Chris Purcell wrote:
> At a brief glance, you appear to be missing memory management, e.g.
> SMR, reference counting or a garbage collector.
>
> Cheers,
> Chris Purcell
>
> On 2/26/07, Tim Blechmann <tim@...> wrote:
> > hi all,
> >
> > thomas grill and i were working on c++ implementations of two
> lockfree
> > data structures, the scott&michael queue and michael's list-based
> set.
> >
> > they are implemented as c++ data structures, using the atomic
> operations
> > from the atomic_ops project and can be downloaded from my subversion
> > repository at http://svn.klingt.org/pnpd/trunk/libs/lockfree/
> >
> > the queue implementation has been tested on multicore processors and
> > seems to work very well.
> > the michael set, which is based on his paper "High Performance
> Dynamic
> > Lock-Free Hash Tables and List-Based Sets", works fine on single
> > processor systems, but thomas's tests on his dualcore computer show,
> > that the implementation is not smp-safe.
> >
> > it would be great if someone of the lockfree gurus on this list
> could
> > have a brief look at the implementations ...
> >
> > cheers ... tim
> >
> > --
> > tim@... ICQ: 96771783
> > http://tim.klingt.org
> >
> > Question: Then what is the purpose of this "experimental" music?
> > Answer: No purposes. Sounds.
> > John Cage
> >
> >
>
>
>
>
--
tim@...    ICQ: 96771783
http://tim.klingt.org

Every word is like an unnecessary stain on silence and nothingness
   Samuel Beckett

At a brief glance, you appear to be missing memory management, e.g.
SMR, reference counting or a garbage collector.

Cheers,
Chris Purcell

On 2/26/07, Tim Blechmann <tim@...> wrote:
> hi all,
>
> thomas grill and i were working on c++ implementations of two lockfree
> data structures, the scott&michael queue and michael's list-based set.
>
> they are implemented as c++ data structures, using the atomic operations
> from the atomic_ops project and can be downloaded from my subversion
> repository at http://svn.klingt.org/pnpd/trunk/libs/lockfree/
>
> the queue implementation has been tested on multicore processors and
> seems to work very well.
> the michael set, which is based on his paper "High Performance Dynamic
> Lock-Free Hash Tables and List-Based Sets", works fine on single
> processor systems, but thomas's tests on his dualcore computer show,
> that the implementation is not smp-safe.
>
> it would be great if someone of the lockfree gurus on this list could
> have a brief look at the implementations ...
>
> cheers ... tim
>
> --
> tim@...    ICQ: 96771783
> http://tim.klingt.org
>
> Question: Then what is the purpose of this "experimental" music?
> Answer: No purposes. Sounds.
>   John Cage
>
>