[boost] Re: live_ptr (Was: Libraries requested or underconstruction)

From: Andy Glew (glew_at_[hidden])
Date: 1999-07-24 22:53:01

>I have a related question: How would you use all these smart pointers in
>multithreaded environments? (It's not a provocation but a very practical
>issue - some kind of automatic garbage collection is usually essential in
>multi-threaded programs e.g. dealing with GUIs.)

I usually have the opposite problem: my simulators are single threaded
(because the network batcher that allows me to use 100s of CPUs only
handles single threads), and I would really like to have versions of libraries
such as the STL that are *NOT* thread safe, since the thread mutexing
often significantly impacts performance.

But apart from that, I don't see any terribly hard issues with the various smart 
pointers in a multithreaded environment, apart from the annoyance of having 
to code and validate them, and the continued annoyance of having to tune
the implementation.

Certainly, both reference counts and mark/sweep garbage collection have
been done any number of times in a multithreaded environment. That doesn't
mean it's easy to do when starting from scratch, but it proves that it is possible.

I see no reason why the live_ptr and regd_ptr I discussed in earlier email
are any harder to do.

You start off by mutexing everything. This has two problems: lousy performance,
and livelock/deadlock. The lousy performance we attack in an evolutionary manner,
as described in the next few paragraphs. The livelock/deadlock is attacked by 
the Banker's algorithm for ordered resource allocation - creating a hierarchy of data
structures, so that cycles waiting on blocked mutexes don't arise.  So far, the STL
has done a pretty good job of avoiding such cycles, so as long as BOOST data
structures are built in a DAG layered manner we should be safe.  Extra credit to anyone
who wants to implement a deadlock detection and backoff mechanism - unlikely
to be very workable in a C++ environment without many more layers of libraries,
or, more likelily, a Herlihy style guaranteed non-blocking and wait-free algorithm.

By the way, the last mentioned Herlihy style guaranteed non-blocking and wait-free
algorithms have been shown to be theta(log N) slower than normal blocking algorithms,
emphasizing the performance cost.

As for performance: okay, we start off with mutexes or, even worse (performance wise)
Herlihy. Use, profile, and optimize. The typical path for optimization is to use fine grain
locks or, more interestingly, to use parallel data structures when possible.

For example, for the registered pointers I discussed in my original mail:

* the naive thing would be to provide a mutex for the registry, and a mutex for the
live_ptr itself (since potentially two threads may be accessing the live_ptr - a thread
writing it in normal operation, and a thread attempting to zero it as the pointee
is deallocated.  This could lead to a deadlock cycle.

* break the cycle by hierarchy: always require the registry lock to be acquired before
a pointee lock.

* improve performance by using a parallel access list, e.g. using atomic fetch-and-add,
so that no mutexing is required on normal list additions and deletions.

* observe that the deallocation of an object is done in one place only in correct programs
- correct programs do not deallocate an object twice - so that the list traversal on deletion
does not need to be mutexed against other deallocations, only against other additions
and deletions reflecting copying of existing live pointers by other threads.

* finally, if you are feeling really aggressive wrt multithreaded performance, implement
the versioned_pointer approach, which requires considerably less mutexing.

Straightforward. Annoying as all hell. A "simple matter of programming".

===

More importantly, you raise the issue of whether BOOST libraries should be multithread
safe from the outset, or what.

As mentioned above, I myself have little inclination to work on thread safe libraries;
in fact, I want single threaded, non-thread-safe, versions of libraries whenever possible
to improve performance of my applications.  

(Related: does anyone know where I can get non-thread-safe versions of the STL for
use with G++?  I don't know if G++'s STL is fully thread safe, but, as I have been debugging
code using it, I see an awful lot of thread garbage which seems to be slowing down my code.
I have not proven it yet, but this overhead seems to be part of the reason that implementations
of my simulator using STL are approximately 2X worse than non-STL C implementations
using C preprocessor macro inlining.)

But I am sympathetic to the needs of programmers in threaded environments.
I definitely agree that we should prohibit APIs that cannot be made thread safe
--- errno, just say no.