[Caml-list] Multicore runtime

[Caml-list] Multicore runtime

[Jiten Pathy]

Hello,
Nice work by stephen et al. on multicore runtime. Just had some questions:-
1. What's the mapping between os threads and domains?
2. How does blocked fibers on a domain work? Does a blocked os thread
running a fiber creates new os thread for that domain?
3. Is there anyway for a fiber to relinquish a domain, for the ones
that do loops for a significant period of time without blocking other
fibers?

Re: [Caml-list] Multicore runtime

[Stephen Dolan]

On Sun, Sep 7, 2014 at 10:47 PM, Jiten Pathy <jpathy@fssrv.net> wrote:
> Hello,
> Nice work by stephen et al. on multicore runtime. Just had some questions:-
> 1. What's the mapping between os threads and domains?

One-to-one.

> 2. How does blocked fibers on a domain work? Does a blocked os thread
> running a fiber creates new os thread for that domain?

Fibers blocked on internal events (e.g. waiting for another fiber to
fill in an mvar) don't block anything - the system just runs some
other fiber. Fibers blocked on long-running / blocking C calls do
block the domain. If they do so for long enough, other fibers on the
domain will be moved to active domains.

Generally, we're going to try to avoid blocking C calls and instead
use select/poll/kqueue/epoll to handle blocking I/O. From the fiber's
point of view, this looks like normal blocking I/O, except if a system
call returns EWOULDBLOCK we'll switch to another fiber until the I/O
is ready.

> 3. Is there anyway for a fiber to relinquish a domain, for the ones
> that do loops for a significant period of time without blocking other
> fibers?

There's a yield function that can be called explicitly. Currently,
compute-bound fibers that don't yield do tie up a domain.

Stephen

Re: [Caml-list] Multicore runtime

[Peter Zotov]

On 2014-09-08 14:05, Stephen Dolan wrote:
> On Sun, Sep 7, 2014 at 10:47 PM, Jiten Pathy <jpathy@fssrv.net> wrote:
>> Hello,
>> Nice work by stephen et al. on multicore runtime. Just had some 
>> questions:-

I have some questions as well.

Most importantly, why are there fibers at all? We already have Async/Lwt
fragmentation. Would fibers add a third option?

Would it not be enough to teach the GC how to interact with multiple
threads/domains?

-- 
Peter Zotov

Re: [Caml-list] Multicore runtime

[Roberto Di Cosmo]

I believe a lot of code written using lightweight threads takes
advantage of the fact that only one "thread" at a time has access to
the state, as this provides us with the huge plus of writing code that
does not need locks to prevent data races. In other words, while there
is the illusion of having concurrent code running, we only have a big
sequential piece of code under execution, and we rely on this fact.

To take advantage of multicore, it would be IMHO very dangerous to
change the behaviour of lwt/async to allow real concurrent execution,
so the need of a separate mechanisms is real, and the proposed
approach using domains and fibers seems quite sensible to me, even if
others are possible (and various has been tried already).

I am more worried about the unexpected behaviours that will arise once
one starts to write code mixing these new abstractions with code using
lightweight threads: time will tell :-)


2014-09-08 12:27 GMT+02:00 Peter Zotov <whitequark@whitequark.org>:
> On 2014-09-08 14:05, Stephen Dolan wrote:
>>
>> On Sun, Sep 7, 2014 at 10:47 PM, Jiten Pathy <jpathy@fssrv.net> wrote:
>>>
>>> Hello,
>>> Nice work by stephen et al. on multicore runtime. Just had some
>>> questions:-
>
>
> I have some questions as well.
>
> Most importantly, why are there fibers at all? We already have Async/Lwt
> fragmentation. Would fibers add a third option?
>
> Would it not be enough to teach the GC how to interact with multiple
> threads/domains?
>
> --
> Peter Zotov
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs



-- 
Roberto Di Cosmo

------------------------------------------------------------------
Professeur               En delegation a l'INRIA
PPS                      E-mail: roberto@dicosmo.org
Universite Paris Diderot WWW  : http://www.dicosmo.org
Case 7014                Tel  : ++33-(0)1-57 27 92 20
5, Rue Thomas Mann
F-75205 Paris Cedex 13   Identica: http://identi.ca/rdicosmo
FRANCE.                  Twitter: http://twitter.com/rdicosmo
------------------------------------------------------------------
Attachments:
MIME accepted, Word deprecated
      http://www.gnu.org/philosophy/no-word-attachments.html
------------------------------------------------------------------
Office location:

Bureau 320 (3rd floor)
Batiment Sophie Germain
Avenue de France
Metro Bibliotheque Francois Mitterrand, ligne 14/RER C
-----------------------------------------------------------------
GPG fingerprint 2931 20CE 3A5A 5390 98EC 8BFC FCCA C3BE 39CB 12D3

Re: [Caml-list] Multicore runtime

[Leonardo Laguna Ruiz]

Hi,

I have only one question. Will it work on the windows MSVC port?

Leonardo

On 9/8/2014 12:05 PM, Stephen Dolan wrote:
> On Sun, Sep 7, 2014 at 10:47 PM, Jiten Pathy <jpathy@fssrv.net> wrote:
>> Hello,
>> Nice work by stephen et al. on multicore runtime. Just had some questions:-
>> 1. What's the mapping between os threads and domains?
> One-to-one.
>
>> 2. How does blocked fibers on a domain work? Does a blocked os thread
>> running a fiber creates new os thread for that domain?
> Fibers blocked on internal events (e.g. waiting for another fiber to
> fill in an mvar) don't block anything - the system just runs some
> other fiber. Fibers blocked on long-running / blocking C calls do
> block the domain. If they do so for long enough, other fibers on the
> domain will be moved to active domains.
>
> Generally, we're going to try to avoid blocking C calls and instead
> use select/poll/kqueue/epoll to handle blocking I/O. From the fiber's
> point of view, this looks like normal blocking I/O, except if a system
> call returns EWOULDBLOCK we'll switch to another fiber until the I/O
> is ready.
>
>> 3. Is there anyway for a fiber to relinquish a domain, for the ones
>> that do loops for a significant period of time without blocking other
>> fibers?
> There's a yield function that can be called explicitly. Currently,
> compute-bound fibers that don't yield do tie up a domain.
>
> Stephen
>

Re: [Caml-list] Multicore runtime

[Adrien Nader]

Hi,

On Mon, Sep 08, 2014, Leonardo Laguna Ruiz wrote:
> Hi,
> 
> I have only one question. Will it work on the windows MSVC port?

Windows has the corresponding support so it could.

Howerver... it does things _very_ differently so I'd urge the
contributors to the multicore runtime to take a look at it and check the
implementation they're going for can be ported. It's not about doing the
port right now, it's about checking the concepts can match early on.

(note that Windows has itself a concept of fibers so it might be of some
use, or it might be a complete horror to use too)

-- 
Adrien Nader

Re: [Caml-list] Multicore runtime

[Jesper Louis Andersen]

[-- Attachment #1: Type: text/plain, Size: 1653 bytes --]

On Mon, Sep 8, 2014 at 12:05 PM, Stephen Dolan <stephen.dolan@cl.cam.ac.uk>
wrote:

> Generally, we're going to try to avoid blocking C calls and instead
> use select/poll/kqueue/epoll to handle blocking I/O. From the fiber's
> point of view, this looks like normal blocking I/O, except if a system
> call returns EWOULDBLOCK we'll switch to another fiber until the I/O
> is ready.
>

This doesn't work for a (portable) implementation of File I/O which is why
everyone else (Go, Erlang, Haskell, ...) either has a pool of threads for
handling these (Erlang), or they just create another thread for handling
it, up to a point (Go). Network I/O is simple however, since you can batch
those on a standard epoll/kqueue/poll/select loop.

The problem is that for file descriptors representing (kernel) file
objects, they never return EWOULDBLOCK since you can always write to them
(rather subtle semantics). But once you write to them, that thread is off
to kernelspace and you only get it back milliseconds later when the write
is complete. In the meantime that thread is placed in uninterruptible
sleep. The async File I/O implementations are not portable either, which is
why everyone ends up with having process pools for this or ends up spawning
threads. Go's rationale is that file I/O is probably going to take so long
anyway that it doesn't really cost too much to create another thread (given
that you also run a thread cache of where to hand off the domain). This URI
has a high-level overview of the Go style:

http://morsmachine.dk/go-scheduler

and there are nice isomorphisms to the concept of fiber (G) and domain (P)
and thread (M).


-- 
J.

[-- Attachment #2: Type: text/html, Size: 2382 bytes --]

[Caml-list] format of .annot files

[Francois Berenger]

Hello,

Is the format described somewhere?

Thanks,
F.

Re: [Caml-list] Multicore runtime

[Anil Madhavapeddy]

On 8 Sep 2014, at 15:49, Jesper Louis Andersen <jesper.louis.andersen@gmail.com> wrote:

> 
> On Mon, Sep 8, 2014 at 12:05 PM, Stephen Dolan <stephen.dolan@cl.cam.ac.uk> wrote:
> Generally, we're going to try to avoid blocking C calls and instead
> use select/poll/kqueue/epoll to handle blocking I/O. From the fiber's
> point of view, this looks like normal blocking I/O, except if a system
> call returns EWOULDBLOCK we'll switch to another fiber until the I/O
> is ready.
> 
> 
> The problem is that for file descriptors representing (kernel) file objects, they never return EWOULDBLOCK since you can always write to them (rather subtle semantics). But once you write to them, that thread is off to kernelspace and you only get it back milliseconds later when the write is complete. In the meantime that thread is placed in uninterruptible sleep. The async File I/O implementations are not portable either, which is why everyone ends up with having process pools for this or ends up spawning threads. Go's rationale is that file I/O is probably going to take so long anyway that it doesn't really cost too much to create another thread (given that you also run a thread cache of where to hand off the domain). This URI has a high-level overview of the Go style:
> 
> http://morsmachine.dk/go-scheduler
> 
> and there are nice isomorphisms to the concept of fiber (G) and domain (P) and thread (M).


Indeed, our fiber model is compatible with filesystem I/O, but does not
*mandate* that implementations support threads if a better-than-POSIX
model is available on the target operating system.  Async I/O works fine
on Windows for instance, and does not require a thread-per-operation.

Much of the platform portability code (which requires excruciating testing
and is not something we want to replicate) for async filesystem I/O is
already present in libuv upstream:

  https://github.com/joyent/libuv

I'd be most interested in hearing from anyone that would like to work on
a Ctypes binding to libuv, since that could provide the basis for an
excellent platform-independent I/O library as an alternative to the Unix
module.

best,
Anil

Re: [Caml-list] Multicore runtime

[Jesper Louis Andersen]

[-- Attachment #1: Type: text/plain, Size: 605 bytes --]

On Mon, Sep 8, 2014 at 5:56 PM, Anil Madhavapeddy <anil@recoil.org> wrote:

> Indeed, our fiber model is compatible with filesystem I/O, but does not
> *mandate* that implementations support threads if a better-than-POSIX
> model is available on the target operating system.  Async I/O works fine
> on Windows for instance, and does not require a thread-per-operation.
>

I fully agree with this point! The trick is to take the view from fibers
and down rather than from a (specific) kernel and up. And you can easily
make this run asynchronously on systems where it is really possible to do
so.


-- 
J.

[-- Attachment #2: Type: text/html, Size: 993 bytes --]

Re: [Caml-list] Multicore runtime

[Yotam Barnoy]

[-- Attachment #1: Type: text/plain, Size: 983 bytes --]

I have another question about the runtime. I believe it was mentioned in
the talk that there would be work-stealing between the domains. But how can
we have any work-stealing when the fibers are integrated deeply inside the
domains' local heaps?

-Yotam

On Mon, Sep 8, 2014 at 1:32 PM, Jesper Louis Andersen <
jesper.louis.andersen@gmail.com> wrote:

>
> On Mon, Sep 8, 2014 at 5:56 PM, Anil Madhavapeddy <anil@recoil.org> wrote:
>
>> Indeed, our fiber model is compatible with filesystem I/O, but does not
>> *mandate* that implementations support threads if a better-than-POSIX
>> model is available on the target operating system.  Async I/O works fine
>> on Windows for instance, and does not require a thread-per-operation.
>>
>
> I fully agree with this point! The trick is to take the view from fibers
> and down rather than from a (specific) kernel and up. And you can easily
> make this run asynchronously on systems where it is really possible to do
> so.
>
>
> --
> J.
>

[-- Attachment #2: Type: text/html, Size: 1736 bytes --]

Re: [Caml-list] Multicore runtime

[Stephen Dolan]

On Tue, Sep 9, 2014 at 3:24 AM, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
> I have another question about the runtime. I believe it was mentioned in the
> talk that there would be work-stealing between the domains. But how can we
> have any work-stealing when the fibers are integrated deeply inside the
> domains' local heaps?

With great care.

Stephen

Re: [Caml-list] Multicore runtime

[Yotam Barnoy]

[-- Attachment #1: Type: text/plain, Size: 1003 bytes --]

With great care is right :) But seriously, work stealing is a huge
undertaking in this model, and may not be feasible at all as far as I can
tell. Every private heap object accessed by a thread has to be copied
either to the shared heap or to the stealer's heap. This is the downside of
not having one shared heap for everything. Of course there are huge upsides
as well, but I don't see how work stealing could work efficiently. The only
exception would be for a thread that hasn't started running at all, or has
allocated very little.

On Tue, Sep 9, 2014 at 11:06 AM, Stephen Dolan <stephen.dolan@cl.cam.ac.uk>
wrote:

> On Tue, Sep 9, 2014 at 3:24 AM, Yotam Barnoy <yotambarnoy@gmail.com>
> wrote:
> > I have another question about the runtime. I believe it was mentioned in
> the
> > talk that there would be work-stealing between the domains. But how can
> we
> > have any work-stealing when the fibers are integrated deeply inside the
> > domains' local heaps?
>
> With great care.
>
> Stephen
>

[-- Attachment #2: Type: text/html, Size: 1481 bytes --]

Re: [Caml-list] Multicore runtime

[Stephen Dolan]

On Tue, Sep 9, 2014 at 4:26 PM, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
> With great care is right :) But seriously, work stealing is a huge
> undertaking in this model, and may not be feasible at all as far as I can
> tell. Every private heap object accessed by a thread has to be copied either
> to the shared heap or to the stealer's heap. This is the downside of not
> having one shared heap for everything. Of course there are huge upsides as
> well, but I don't see how work stealing could work efficiently. The only
> exception would be for a thread that hasn't started running at all, or has
> allocated very little.

It's implemented, and was demoed last week in the talk you mention.
Work-stealing is the only reason the silly example program ran faster
on more cores. Still lots of work to be done, but closer to fait than
infeasible.

Moving objects from a private to the shared heap is not a big deal.
This happens anyway during minor garbage collection. Stealing a fiber
that refers to objects in a private heap essentially involves doing
some of the minor GC work before the next minor GC would otherwise
occur.

Stephen

Re: [Caml-list] Multicore runtime

[Yotam Barnoy]

[-- Attachment #1: Type: text/plain, Size: 1552 bytes --]

Maybe I misunderstood something. Does each domain only have a minor private
heap (ie. copying gc) or do they each also have a major private heap/older
generation (mark and sweep)? If they have an older generation, then a
thread could potentially have a lot of data there, no?

On Wed, Sep 10, 2014 at 6:01 PM, Stephen Dolan <stephen.dolan@cl.cam.ac.uk>
wrote:

> On Tue, Sep 9, 2014 at 4:26 PM, Yotam Barnoy <yotambarnoy@gmail.com>
> wrote:
> > With great care is right :) But seriously, work stealing is a huge
> > undertaking in this model, and may not be feasible at all as far as I can
> > tell. Every private heap object accessed by a thread has to be copied
> either
> > to the shared heap or to the stealer's heap. This is the downside of not
> > having one shared heap for everything. Of course there are huge upsides
> as
> > well, but I don't see how work stealing could work efficiently. The only
> > exception would be for a thread that hasn't started running at all, or
> has
> > allocated very little.
>
> It's implemented, and was demoed last week in the talk you mention.
> Work-stealing is the only reason the silly example program ran faster
> on more cores. Still lots of work to be done, but closer to fait than
> infeasible.
>
> Moving objects from a private to the shared heap is not a big deal.
> This happens anyway during minor garbage collection. Stealing a fiber
> that refers to objects in a private heap essentially involves doing
> some of the minor GC work before the next minor GC would otherwise
> occur.
>
> Stephen
>

[-- Attachment #2: Type: text/html, Size: 2080 bytes --]

Re: [Caml-list] Multicore runtime

[Stephen Dolan]

On Wed, Sep 10, 2014 at 11:42 PM, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
> Maybe I misunderstood something. Does each domain only have a minor private
> heap (ie. copying gc) or do they each also have a major private heap/older
> generation (mark and sweep)? If they have an older generation, then a thread
> could potentially have a lot of data there, no?

Only a private minor heap. The major heap is the shared heap.

Re: [Caml-list] Multicore runtime

[Malcolm Matalka]

[-- Attachment #1: Type: text/plain, Size: 936 bytes --]

Is there a detailed description of the memory model somewhere?  For example
what does it mean for two domains to modify the same reference?  Apologies
if I missed it in the thread.
Den 11 sep 2014 10:40 skrev "Stephen Dolan" <stephen.dolan@cl.cam.ac.uk>:

> On Wed, Sep 10, 2014 at 11:42 PM, Yotam Barnoy <yotambarnoy@gmail.com>
> wrote:
> > Maybe I misunderstood something. Does each domain only have a minor
> private
> > heap (ie. copying gc) or do they each also have a major private
> heap/older
> > generation (mark and sweep)? If they have an older generation, then a
> thread
> > could potentially have a lot of data there, no?
>
> Only a private minor heap. The major heap is the shared heap.
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 1501 bytes --]

Re: [Caml-list] Multicore runtime

[Yotam Barnoy]

[-- Attachment #1: Type: text/plain, Size: 2056 bytes --]

Ah OK. I didn't realize that the original Leroy & Doligez paper dealt only
with a copying GC, and that this was the intent here as well. In that case,
work stealing does indeed makes sense.

Thinking about it some more, I understand why it's not possible to just
fork off a suspended thread for synchronous IO as haskell does -- that
thread would then modify the local heap, breaking the invariant. So that IS
a limitation of the current model, right?

Malcolm: the description is here (
http://www.cl.cam.ac.uk/~sd601/multicore.md). As far as I understand, two
domains modifying the same reference on the shared heap is the same as in
any other language -- it's a write-write conflict, and it needs to be
guarded by the user using some primitive. If the reference is in a local
heap of another domain, that reference must first have something done to it
using a message sent from one domain to another. Unless they go with the
model where all mutables sit on the shared heap, meaning that there is no
such case.

On Thu, Sep 11, 2014 at 4:53 AM, Malcolm Matalka <mmatalka@gmail.com> wrote:

> Is there a detailed description of the memory model somewhere?  For
> example what does it mean for two domains to modify the same reference?
> Apologies if I missed it in the thread.
> Den 11 sep 2014 10:40 skrev "Stephen Dolan" <stephen.dolan@cl.cam.ac.uk>:
>
>> On Wed, Sep 10, 2014 at 11:42 PM, Yotam Barnoy <yotambarnoy@gmail.com>
>> wrote:
>> > Maybe I misunderstood something. Does each domain only have a minor
>> private
>> > heap (ie. copying gc) or do they each also have a major private
>> heap/older
>> > generation (mark and sweep)? If they have an older generation, then a
>> thread
>> > could potentially have a lot of data there, no?
>>
>> Only a private minor heap. The major heap is the shared heap.
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>

[-- Attachment #2: Type: text/html, Size: 3094 bytes --]

Re: [Caml-list] Multicore runtime

[Stephen Dolan]

On Thu, Sep 11, 2014 at 9:53 AM, Malcolm Matalka <mmatalka@gmail.com> wrote:
> Is there a detailed description of the memory model somewhere?  For example
> what does it mean for two domains to modify the same reference?  Apologies
> if I missed it in the thread.

Not yet! Being worked on.

Stephen