From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 2D7037F8F2 for ; Tue, 3 Jun 2014 18:29:22 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of dhouse@janestreet.com) identity=pra; client-ip=38.105.200.112; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dhouse@janestreet.com"; x-sender="dhouse@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of dhouse@janestreet.com designates 38.105.200.112 as permitted sender) identity=mailfrom; client-ip=38.105.200.112; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dhouse@janestreet.com"; x-sender="dhouse@janestreet.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mxout1.mail.janestreet.com) identity=helo; client-ip=38.105.200.112; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dhouse@janestreet.com"; x-sender="postmaster@mxout1.mail.janestreet.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkoBACX3jVMmachwnGdsb2JhbABZhDGCbL90AYEECBYOAQEBAQEGFgk8giUBAQEDARIRBBkBATcBBAsLCwM0AgIhARIBBQEcBhMiiAwDCQgDAqEWaoowd4R/AQWaOg2FQhEGjDyCFgeCdYFLlgaCD4F5jT6EBBgphGk X-IPAS-Result: AkoBACX3jVMmachwnGdsb2JhbABZhDGCbL90AYEECBYOAQEBAQEGFgk8giUBAQEDARIRBBkBATcBBAsLCwM0AgIhARIBBQEcBhMiiAwDCQgDAqEWaoowd4R/AQWaOg2FQhEGjDyCFgeCdYFLlgaCD4F5jT6EBBgphGk X-IronPort-AV: E=Sophos;i="4.98,966,1392159600"; d="scan'208";a="77860859" Received: from mxout1.mail.janestreet.com ([38.105.200.112]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 03 Jun 2014 18:29:21 +0200 Received: from tot-smtp.delacy.com ([172.27.22.15] helo=tot-smtp) by mxout1.mail.janestreet.com with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.82) (envelope-from ) id 1WrraR-00049V-SM for caml-list@inria.fr; Tue, 03 Jun 2014 12:29:19 -0400 Received: from tot-dmz-mxgoog1.delacy.com ([172.27.224.14] helo=mxgoog2.janestreet.com) by tot-smtp with esmtps (TLSv1:AES256-SHA:256) (Exim 4.72) (envelope-from ) id 1WrraR-0000YL-Pn for caml-list@inria.fr; Tue, 03 Jun 2014 12:29:19 -0400 Received: from mail-qa0-f51.google.com ([209.85.216.51]) by mxgoog2.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1WrraR-0008BW-OA for caml-list@inria.fr; Tue, 03 Jun 2014 12:29:19 -0400 Received: by mail-qa0-f51.google.com with SMTP id w8so5136557qac.38 for ; Tue, 03 Jun 2014 09:29:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Oi9QT9Z4X8K9NepDhvy01wb3SeI+8mmlteYNtuupV8E=; b=uc3RixheRZOP54tyv94ih3uaftziVoy1SFsDBxVk5wFk0FYbHRkWiXf0rP+AkMNiE8 J/aRkS1V1IR8qHKA1b67WueSXYfITjSpGsfDjSIkcpda/7E+V6v3LZLAlztIziqpfFun k58nDSLRmolt6Z6n6tiDn8RMEUbVbk3Q6qhvA= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=Oi9QT9Z4X8K9NepDhvy01wb3SeI+8mmlteYNtuupV8E=; b=NowBu/Az6UuIThA5SXCV8i1aQ8gTKyKG/p4jWDZJLNGpud50177KvOcjLtkQrsFtis Q+PPKrxjqQ9Mx9qQshUaPcKJnC2zkvabB9kNaGqAXX4cskb0Zri17E6udz/CFiuzAt9t Z24bqtFjMpgtkO+0xzgRpiAdqX3TmLSYCYTXbniZtJotK6+HffCjdqq3JtvX5eTCHtWB y9qjZVQjl+dzGNlp4m/CLD7EkMud/0aOphnQvr6jmoRbEHRyEZbDoFc0DfKX0xbABNbl TbHiAsYdh4pBwhCGlM2T2RJFsItdxtHq5WX7ul1frC74STyHgx/+T+makJSuP0N2gYQK OggQ== X-Gm-Message-State: ALoCoQkbGGl+bDxpNkwiJmFHLtSEQfk8XIL60xzKBVOZZYh4Twee2AAQ/MhE2RL+fQ5jeDv2cKLcYRc3ue3ChK4oLzFe+S43eMza4EEjymHr62/HJ9mXMeE4Ql6Mwo02b7FOGaI6LR/n X-Received: by 10.140.20.144 with SMTP id 16mr58104038qgj.114.1401812959583; Tue, 03 Jun 2014 09:29:19 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.140.20.144 with SMTP id 16mr58104022qgj.114.1401812959492; Tue, 03 Jun 2014 09:29:19 -0700 (PDT) Received: by 10.140.30.98 with HTTP; Tue, 3 Jun 2014 09:29:19 -0700 (PDT) In-Reply-To: References: Date: Tue, 3 Jun 2014 17:29:19 +0100 Message-ID: From: David House To: Dan Stark Cc: OCaml Mailing List Content-Type: multipart/alternative; boundary=001a11c126327e159004faf10350 Subject: Re: [Caml-list] How is Async implemented? --001a11c126327e159004faf10350 Content-Type: text/plain; charset=UTF-8 There is a queue of jobs in the scheduler. The scheduler runs the jobs one by one. Jobs may schedule other jobs. A job is a pair of ['a * 'a -> unit]. There's a thing called a deferred. ['a Deferred.t] is an initially empty box that may become filled later with something of type ['a]. There is a similar type called ['a Ivar.t] -- the difference is that ivars have a function to actually fill in the value, whereas deferreds do not: a deferred is a "read-only" view on an ivar. You can wait on a deferred using bind. Doing [x >>= f] mutates the deferred x to add f as a "handler". When a deferred is filled, it adds a job to the scheduler for each handler it has. Doing [Deferred.return 1] allocates a deferred which is already filled and has no handlers. Binding on that will immediately schedule a job to run your function. (The job is still scheduled though, rather than being run immediately, to ensure that you don't have an immediate context switch -- in async, the only context switch points are the binds.) The primitive operations that block are replaced with functions that return deferreds, and go do their work in a separate thread. There's a thread pool to make sure you don't use infinity threads. (I think the default cap is 50 threads.) I think yes, async does depend on -thread. There is an important optimisation: if you want to read or write to certain file descriptors, that doesn't use a thread. Instead there's a central list of such file descriptors. There's also a central list of all "timer events" (e.g. deferreds that become deferred after some amount of time). The scheduler actually is based around a select loop: it does the following: run all the jobs if more jobs have been scheduled, run those too keep going until there are no more jobs, or we hit the maximum-jobs-per-cycle cap sleep using select until one read fd is read, or a write fd is ready, or a timer event is due to fire do that thing There's also a way to manually interrupt the scheduler. Blocking operations other than reading/writing to fds do this: they run in a thread, grab the async scheduler lock, fill in an ivar, then wake up the scheduler to ensure timely running of the jobs they just scheduled. The async scheduler lock is necessary because the scheduler itself is not re-entrant: you cannot have multiple threads modifying the scheduler's internals. On 3 June 2014 16:39, Dan Stark wrote: > Hi all > > I am trying to get a rough overview of how Async is implemented (or the > idea behind it) before I really dig into its source code. > > I have the following questions: > > *Q1:* Is Async event-loop like? > > From the API and some docs for Async's usage, I feel it is quite like a > event-loop. > > You create Deferred.t and it might be added to a queue and a scheduler > behind might be adjusting the order of running for all Deferred.t in the > queue. > > Am I correct? > > *Q2:* Deferred.return and Deferred.bind > > If I say > > Deferred.return 1 > > > It will returns me a Deferred.t, but inside the function *return* or > *bind* somehow an "event" is implicitly added to the default queue for > scheduling, right? > > If I am correct above, > > *Q3:* Is Async depending on -thread? The queue or scheduler needs > compiler support? > > I just need to understand the whole picture in a rough way first. > > Thanks > > Dan > > > > > > > > > > > > > --001a11c126327e159004faf10350 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
There is a queue of jobs in the scheduler. The scheduler r= uns the jobs one by one. Jobs may schedule other jobs. A job is a pair of [= 'a * 'a -> unit].

There's a thing called = a deferred. ['a Deferred.t] is an initially empty box that may become f= illed later with something of type ['a]. There is a similar type called= ['a Ivar.t] -- the difference is that ivars have a function to actuall= y fill in the value, whereas deferreds do not: a deferred is a "read-o= nly" view on an ivar.

You can wait on a deferred using bind. Doing [x >>= ;=3D f] mutates the deferred x to add f as a "handler". When a de= ferred is filled, it adds a job to the scheduler for each handler it has.= =C2=A0

Doing [Deferred.return 1] allocates a deferred which is= already filled and has no handlers. Binding on that will immediately sched= ule a job to run your function. (The job is still scheduled though, rather = than being run immediately, to ensure that you don't have an immediate = context switch -- in async, the only context switch points are the binds.)<= /div>

The primitive operations that block are replaced with f= unctions that return deferreds, and go do their work in a separate thread. = There's a thread pool to make sure you don't use infinity threads. = (I think the default cap is 50 threads.) I think yes, async does depend on = -thread.

There is an important optimisation: if you want to read= or write to certain file descriptors, that doesn't use a thread. Inste= ad there's a central list of such file descriptors. There's also a = central list of all "timer events" (e.g. deferreds that become de= ferred after some amount of time). The scheduler actually is based around a= select loop: it does the following:

run all the jobs
if more jobs have been sched= uled, run those too
keep going until there are no more jobs, or w= e hit the maximum-jobs-per-cycle cap
sleep using select until one= read fd is read, or a write fd is ready, or a timer event is due to fire
do that thing

There's also a way to manua= lly interrupt the scheduler. Blocking operations other than reading/writing= to fds do this: they run in a thread, grab the async scheduler lock, fill = in an ivar, then wake up the scheduler to ensure timely running of the jobs= they just scheduled. The async scheduler lock is necessary because the sch= eduler itself is not re-entrant: you cannot have multiple threads modifying= the scheduler's internals.


On 3 Ju= ne 2014 16:39, Dan Stark <interlock.public@gmail.com> wrote:
Hi all

I= am trying to get a rough overview of how Async is implemented (or the idea= behind it) before I really dig into its source code.

I have the following questions:

Q1:=C2=A0Is Async event-loop like?
From the API and some docs for Async's usage, I feel it is = quite like a event-loop.=C2=A0

You create Deferred= .t and it might be added to a queue and a scheduler behind might be adjusti= ng the order of running for all Deferred.t in the queue.=C2=A0

Am I correct?

Q2: Defer= red.return and Deferred.bind

If I say
Deferred.return 1

It will returns me a Defe= rred.t, but inside the function return=C2=A0or bind somehow a= n "event" is implicitly added to the default queue for scheduling= , right?

If I am correct above,=C2=A0

<= b>Q3:=C2=A0Is Async depending on -thread? The queue or scheduler needs = compiler support?=C2=A0

I just need to understand = the whole picture in a rough way first.

Thanks

Dan













--001a11c126327e159004faf10350--