Subj : Re: Memory reordering problem (or is it?)
To   : comp.programming.threads
From : Giancarlo Niccolai
Date : Wed Jun 15 2005 06:18 pm

Joe Seigh wrote:

> Giancarlo Niccolai wrote:
>> Maciej Sobczak wrote:
> ...
>>>I'm not an expert in today's GC technology, but considering the fact
>>>that it has a lot to do with threads, I would like to ask you whether
>>>this is considered to be a problem and what GC (or the language and its
>>>runtime) can do to avoid this.
>>>
>>>Regards,
>>>
>> 
>> 
>> The most common solution, and not one of the worst, is to stop all
>> threads in a safe "stop point" and start collection, allowing the threads
>> to resume again after the collection is done. This is called "sequential
>> mark-sweep". Another approach, which may or may not be better, depending
>> on which situations and requirements you face, is that of never stopping
>> the threads and using a "competitive" garbage collector. The most common
>> is the "three color" approach, in which the GC thread scan endlessly the
>> memory in search of unreachable nodes (the description is imprecise, but
>> it gives the idea). The algorithm is less efficient than a mark-sweep,
>> but it never stop threads, which may be good if you need high
>> responsiveness, and on a massive parallel machine being finetuned with
>> your program (i.e. a SMP with the a number of CPU nearing the number of
>> your threads), it may end in higher overall performances.
>> 
>> More can be found at: http://www.memorymanagement.org/
>> 
> 
> I don't think any of them will be as efficient as RCU or SMR.  Some of
> those GC algorithms seem to have horrific overhead that make SMR even with
> its full
> memory barriers look efficient.   They seem to have this attitude that it
> is
> important to GC *everything* no matter what the cost.  The only one that
> comes nearest is distributed reference counting where they just scan the
> thread
> stacks and refcount the heap.  The problem with that is the only place
> it's safe to examine the stack is from the thread itself which has some
> problems.
> 

More MODERN approaches (and generally, but not always, more efficient ones)
uses heuristic strategies (i.e. generational approaches) to determine where
the garbage is most likely to be, or i.e. partial reference counting to
provide the GC with an hint on what is more likely to need collections.
This all is explained at the pointer I gave; here I just explained the very
basic set of the very basic techniques used in the field... 

What is clear today is that probably there isn't the "perfect" collector,
and any collecting strategy that has been developed up to date has at least
one area of application in which it outperforms the others... or even in
the case that it is less efficient (algoritmically) than others, where it
is more "suited" to "do the job".

G.N.

.