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

[Hugo Ferreira <hmf@inescporto.pt>]

On 03/25/2011 12:25 PM, Gerd Stolpmann wrote:
> Am Freitag, den 25.03.2011, 10:51 +0000 schrieb Hugo Ferreira:
>> 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.

I was assuming that this would not be possible given the construction
of non-mutable data.

> 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.

Ok, circularity would certainly complicate assigning ownership to a
thread GC.

>
> 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.
>

Which seems to bring us back to the initial issue: it would be
difficult if not impossible to manipulate and change shared complex data
structure manually.

I am now wondering if disallowing sharing that causes cycles would make 
things easier. A sort of FILO stack of sharing. A thread may only share
to its descendants. Problem: how to ensure only one of these remains
owner. Going to give this some more thought.

Thanks for the feedback.

R,
Hugo F.

> 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,
>>
>>
>
>