GC, the simple solution

[Bruno Medeiros]

Sean Kelly wrote:
> Bruno Medeiros wrote:
>> Sean Kelly wrote:
>>> Bruno Medeiros wrote:
>>>> Walter Bright wrote:
>>>>>> Only if the reference is stored,
>>>>>> the ref counter has to be incremented. This is only possible if 
>>>>>> this is
>>>>>> done by the compiler. No smart pointer can do this :)
>>>>>>
>>>>>>> 3) in a multithreaded app, the incs and decs must be synchronized
>>>>>>
>>>>>> Isn't a atomic inc/dec enough?
>>>>>
>>>>> That requires synchronizing.
>>>>>
>>>>
>>>> Are you sure? It says in 
>>>> http://www.iecc.com/gclist/GC-algorithms.html#Reference%20counting 
>>>> that:
>>>> "In a multi-threaded system, if threads are preemptively scheduled, 
>>>> reference counting requires additional care to ensure that the 
>>>> updates to reference counts are atomic. This is straightforward 
>>>> using hardware primitives such as fetch-and-add, compare-and-swap, 
>>>> or load-linked/store-conditional, but it is definitely necessary to 
>>>> pay attention to this detail." ?
>>>
>>> These are synchronizing operations.
>>
>> By "That requires synchronizing." I thought Walter meant stuff with 
>> mutexes, etc. (i.e., non-trivial stuff), because, can't those hardware 
>> synchronizing operations be called "atomic inc/dec" ?
> 
> For the most part.  There are really two issues here.  First, the 
> operation must be atomic with respect to other threads.  The x86 
> actually guarantees this for all load/store operations on aligned data 
> <= the bus size.  Second, the operations must be observed in the proper 
> order by other threads--ie. the compiler and all involved CPUs (reader 
> and writer) are not allowed to reorder the operations or do any other 
> fancy tricks that may result in a load/store order that isn't the same 
> as program order.  For the compiler, this is where volatile comes in, 
> and at the hardware level, a synchronizing operation may be required 
> depending on the situation and on the hardware involved.  Again, with 
> x86 you can get away without a LOCK a lot of the time, but not always. 
> So you really must assume that any competing operation has a worst case 
> cost of... well, a lot.
> 
> 
> Sean

Ah, I see. I had recently read about relative out-of-order execution 
problems in the Memory Barrier wikipedia entry, and I got the impression 
(out of nowhere) that the hardware took care of that transparently 
(i.e., without program intervention), but then, that is not the case, 
not allways at least?

-- 
Bruno Medeiros - CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D