It turns out that garbage collection makes it way easier for implementing
lock-free data structures. That might be the compelling argument in favor of
garbage collection that I recall was sought after in this forum.

People who are interested might want to write me email. I'll be glad to send
a draft of an article I am writing on the subject to those who participated
to the ongoing discussion on garbage collection.


Thanks,

Andrei



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Andrei Alexandrescu (See Website for Email)" wrote:
>
> It turns out that garbage collection makes it way easier for implementing
> lock-free data structures. That might be the compelling argument in favor of
> garbage collection that I recall was sought after in this forum.
>
> People who are interested might want to write me email. I'll be glad to send
> a draft of an article I am writing on the subject to those who participated
> to the ongoing discussion on garbage collection.
>

You might want to take a look at the RCU stuff by Paul McKenney here
http://www.rdrop.com/users/paulmck/rclock/
particularly his dissertation which has references to other papers on that
subject.  The basic patterns used in RCU can be applied to other forms of
GC as well, such as Michael's hazard pointers, or Boehm GC as you mentioned.

The technique goes way back, but interest has been picking up lately so there
is a ton of research papers on it now if you scan CiteSeer or google for it.

You need to make some guarantees on the read access as we've seen on the DCL
discussion.  DCL is a form of lock-free access.  Something along the lines
of atomic<T> or atomic<*T> to guarantee atomicity and proper memory visiblity
if the particular platform requires it.

Joe Seigh

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Andrei Alexandrescu \(See Website for Email\)" <SeeWebsiteForEmail@moderncppdesign.com> wrote in message news:<2oap1uF8j8t9U1@uni-berlin.de>...
> It turns out that garbage collection makes it way easier for implementing
> lock-free data structures. That might be the compelling argument in favor of
> garbage collection that I recall was sought after in this forum.
> 
> People who are interested might want to write me email. I'll be glad to send
> a draft of an article I am writing on the subject to those who participated
> to the ongoing discussion on garbage collection.
1) What lock-free data structure are you wanting to write for which
reference counting is (a) inadequate (b) inefficient?
2) What are you going to do about the difficulty of standardizing the
necessary infrastructure for lock-free programs?  To write such
programs you need memory barriers, and you need either atomic
compare-and-swap or load-linked/store conditional (most platforms
offer the former, though I think a few offer the latter).  CAS
introduces a whole class of problems of its own.  Common structures
like a lock-free linked singly linked list using a counter to avoid
ABA generally need a CAS that can operate on two pointer-sized values
at once.  So on 32-bit platforms, one needs a 64-bit CAS.  That's not
a problem on 32-bit platforms--most do offer a 64-bit CAS.  The
problem is on 64-bit platforms.  No 64-bit platform (AFAIK) offers a
128-bit CAS.  Itanium offers cmp8xchg16, but that's I think as good as
it gets.

It's possible to fabricate CASn from CAS (i.e. arbitrarily large
CAS)--but that has difficulties of its own.  In particular, spinlocks
can offer better performance.  The lock-free implementation still has
its virtues (it's immune to priority inversions, for instance) but
that's a fairly unusual requirement.  Unless one really needs that
requirement (and there's only one place where it seems truly
essential--in a kernel, where C++ is not a big player anyway, and
garbage collection is unacceptable anyway), lock-free seems hardly
worth it.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Dr Pizza wrote:
 >
 > "Andrei Alexandrescu \(See Website for Email\)" <SeeWebsiteForEmail@moderncppdesign.com> wrote in message news:<2oap1uF8j8t9U1@uni-
berlin.de>...
 > > It turns out that garbage collection makes it way easier for implementing
 > > lock-free data structures. That might be the compelling argument in favor of
 > > garbage collection that I recall was sought after in this forum.
 > >
 > > People who are interested might want to write me email. I'll be glad to send
 > > a draft of an article I am writing on the subject to those who participated
 > > to the ongoing discussion on garbage collection.
 > 1) What lock-free data structure are you wanting to write for which
 > reference counting is (a) inadequate (b) inefficient?
 > 2) What are you going to do about the difficulty of standardizing the
 > necessary infrastructure for lock-free programs?  To write such
 > programs you need memory barriers, and you need either atomic
 > compare-and-swap or load-linked/store conditional (most platforms
 > offer the former, though I think a few offer the latter).  CAS
 > introduces a whole class of problems of its own.  Common structures
 > like a lock-free linked singly linked list using a counter to avoid
 > ABA generally need a CAS that can operate on two pointer-sized values
 > at once.  So on 32-bit platforms, one needs a 64-bit CAS.  That's not
 > a problem on 32-bit platforms--most do offer a 64-bit CAS.  The
 > problem is on 64-bit platforms.  No 64-bit platform (AFAIK) offers a
 > 128-bit CAS.  Itanium offers cmp8xchg16, but that's I think as good as
 > it gets.

Intel's I32-64 has cmpxchg16b which operates on on 128 bits.  AMD's
64 bit processors do not.  Neither does sparc in 64 bit mode.  To
get around it you have to allocate objects you wish to perform those
kind of operations on from a less than 4GB memory pool and use 32 bit
offsets into that pool as pointers.

 >
 > It's possible to fabricate CASn from CAS (i.e. arbitrarily large
 > CAS)--but that has difficulties of its own.  In particular, spinlocks
 > can offer better performance.  The lock-free implementation still has
 > its virtues (it's immune to priority inversions, for instance) but
 > that's a fairly unusual requirement.  Unless one really needs that
 > requirement (and there's only one place where it seems truly
 > essential--in a kernel, where C++ is not a big player anyway, and
 > garbage collection is unacceptable anyway), lock-free seems hardly
 > worth it.

I've played around with RCU in user space and even on a single processor
system you can see dramatic performance under very high contention.  Under
normal contention they perform about the same as mutexes.   You shouldn't
normally need lock-free in most cases but when performance is an issue
lock-free should definitely be considered.

Joe Seigh

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Joe Seigh <jseigh_01@xemaps.com> wrote in message news:<412A8202.2C42B0CA@xemaps.com>...
> Intel's I32-64 has cmpxchg16b which operates on on 128 bits.
Ah, true, I'd forgotten that piece of gratuitous incompatibility.

> AMD's
> 64 bit processors do not.  Neither does sparc in 64 bit mode.  To
> get around it you have to allocate objects you wish to perform those
> kind of operations on from a less than 4GB memory pool and use 32 bit
> offsets into that pool as pointers.
Well, that is _a_ way to get around it.  Not the only way.

> I've played around with RCU in user space and even on a single processor
> system you can see dramatic performance under very high contention.  Under
> normal contention they perform about the same as mutexes.   You shouldn't
> normally need lock-free in most cases but when performance is an issue
> lock-free should definitely be considered.
What kind of a mutex are you talking about?  I can well believe it if
you're talking about a kernel mutex, but for a user-mode spinlock or
spinlock-like device (e.g. Win32 critical section)--which is normally
good enough--is that still the case?

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]