Re: [Caml-list] Efficient OCaml multicore -- roadmap?

[Gerd Stolpmann <info@gerd-stolpmann.de>]

Am Freitag, den 25.03.2011, 10:51 +0000 schrieb Hugo Ferreira:
> Hello,
> 
> First and foremost just let me say that I am not an expert on this
> issue but I have a vested interest in Ocaml's support for parallel
> execution, hence my comment.
> 
> On 03/24/2011 11:13 PM, Fabrice Le Fessant wrote:
> > Hi,
> >
> >    Actually, I had a discussion two weeks ago with Xavier and Damien
> > about this issue. There is some kind of agreement that the ocaml way of
> > supporting multicore would be to have several runtimes running in the
> > same process, in different threads. That way, the GC would still be
> > mono-threaded, so almost no speed loss for mono-threaded programs (i.e.
> > currently all OCaml programs ;-) ). There would be some kind of "fork"
> > function, that would create a new thread running a function in a new
> > heap, probably generated by a copy-on-need algorithm. The different
> > threads would not share heap memory, but would be allowed to share
> > structures outside of their heaps, probably for simple types like
> > strings and int/float arrays (or using the Ancient library).
> >
> 
> I see the restriction that shared data be simple data types as a 
> significant disadvantage. 

Well, Fabrice was mentioning Ancient which is a code word for putting
complex values to non-GC-managed memory. It's only that the application
programmer is finally responsible for managing that memory (especially
when to deallocate).

> In my experience being able to access complex 
> data structure is crucial. Whenever I see this constraint I keep asking: 
> why not bite the bullet? Why not take the bull by the horns and do it as 
> well as possible? If not, I believe its a waste of precious time.
> 
> That being said, I have a question: why will the proposal below not work?
> 
> Assuming all shared data structures are immutable is it possible to:
> 
> 1) Use a GC that is thread aware.
> 2) Let each thread have its own thread-aware GC.
> 4) Mark the shared data by tagging it with the owner of the data and 
> counting the number of threads using this data.
> 5) Each thread has it own local GC. This GC only manages the thread's
> local data that is not shared with any other.
> 6) If data is shared, the thread that shares immediately marks it as 
> shared.
> 7) If a thread terminates before the shared data can be collected (that 
> is when the shared counter is not 0), the ownership is reverted to any 
> one of the sharing threads.
> 8) The last thread to hold a shared data structure is responsible for GC.
> 
> Am I totally off the mark here?

It would be a bit more complicated. You have two possible pointers:

(1) From thread-specific memory to shared memory
(2) From shared memory to shared memory

Pointers from shared memory to thread-specific memory would be
forbidden, of course. The problem is now that you can manage (1) with
reference counting (where the counter would need some protection for
concurrent accesses), but for (2) you would need, at least in the
general view, a garbage collector that is able to deal with circular
pointers.

So, probably there is a solution to this, but it is very complex. You
would need to extend the header of Ocaml values with counters when they
are allocated in the shared space (or the counters are put elsewhere,
but this would make it more costly to access them). There needs to be a
special version of the garbage collector for the shared space.

This is probably all possible, but the effort is not low to get this
level of automatism. If we restrict ourselves to manually managed shared
space (i.e. the app has to decide when to delete something), we can
maybe get something soon.

Gerd

> 
> Regards,
> Hugo F.
> 
> P.S: Note that the above can be "enhanced" by for example identifying 
> read-only data in order to facilitate GC.
> 
> 
> >    Now, there are still two problems:
> > (1) We don't know yet how to implement that in a portable way. TLS
> > (Thread-local storage) is only available on a few architectures. And not
> > using TLS implies non-backward compatible changes to the FFI
> > (Foreign-Functions Interface), i.e. all stub libraries would have to be
> > rewritten.
> > (2) As Gerd pointed it, there are not so many programs that would
> > benefit from that. So it is not currently on the top of our priority
> > list, although I am planning to give it a try in the next months, at
> > least for the TLS version.
> >
> > Cheers,
> 
> 


-- 
------------------------------------------------------------
Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------