Re: [Caml-list] OC4MC : OCaml for Multicore architectures

[Philippe Wang <philippe.wang@lip6.fr>]

On Sep 24, 2009, at 18:02 GMT+02:00, Pascal Cuoq wrote:

> On Sep 24, 2009, at 5:47 PM, Philippe Wang wrote:
>
>>> Is the copy operation parallelized?
>>
>> Nope. When the world is stopped for the collection, everything is  
>> done
>> sequentially until the world is resumed.
>> I don't think it's relevant to parallelize the copy operation (hell  
>> to
>> implement&debug, then I don't think that performance would be very
>> interesting because we would probably need a write mutex on the
>> destination heap)
>
> Well, you could start copying to the bottom of the next heap with
> one thread going up and to the top of it with another going down.
> Assume optimistically that the two threads will not reach the same
> cacheline at the end of the copies, and you don't need any
> synchronisation at all between them, except joining at the end.
>
> After checking, if they have reached the same cacheline,
> you need to reallocate the destination heap anyway.
>
> You still get a single unfragmented free block as a result.
>
> Even better: stop the world just before there remains less that one
> cacheline of free space and you don't need to check if the two  
> threads have
> met. You still need to reallocate the destination heap sometimes  
> though.

A concurrent copy means that there would be bad overhead for single  
core. It also means putting bottleneck to memory bandwidth as memory  
copy operations are clearly quickly limited by this bandwidth, not by  
CPU. It may hopefully become false in a few years, but hardware  
manufacturers don't seem to be excited by that, they seem to prefer  
making the marketing on the number of cores. Look at GPUs : they have  
very fast graphical RAM, but they have a huge number of processing  
units. I don't really see the point in that (i.e. having a huge number  
of PU) anyway (except "marketing").

Ok, back to GC stuff. A stop&copy algorithm needs to have a set of  
roots to make the copy of living values.
Each thread has its stack, so it has its subset of roots. Then what ?  
Parallelize the copy from each thread ? Ok we have to determine the  
best number of threads according to number of cores but more  
importantly according to memory bandwidth given per core. (what a  
nightmare!)
Then there are shared values (in the shared heap for instance, but  
what if there are lateral pointers due to mutable values?). (We are  
leaving the nightmare for hell! but some people have been there.)  
Copying a living value means that if later you encounter something  
pointing to its old address, you have to know the new one. This means  
writing at the old address. I don't see how we can make *today*  
something very interesting in concurrent with a stop&copy algorithm. I  
believe (but I'm *not* a GC expert at all) concurrent GCs are not  
based on stop&copy algorithm but rather some mark&{do-some-stuff-such- 
as-"sweep"}.


> Oh, and I meant to say, but everyone else was faster than me:
> well done!

Thank you, and thanks everyone else who appreciate this work. :-)

Philippe Wang