GC, the simple solution

[Sean Kelly]

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