From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 10366BBBB for ; Thu, 9 Feb 2006 18:49:04 +0100 (CET) Received: from mail.barettadeit.com (h213-255-109-130.albacom.net [213.255.109.130] (may be forged)) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k19Hn1xX021726 for ; Thu, 9 Feb 2006 18:49:02 +0100 Received: from [10.1.0.20] (unknown [10.1.0.20]) by mail.barettadeit.com (Postfix) with ESMTP id 6D5A3A49F2; Thu, 9 Feb 2006 18:50:15 +0100 (CET) Message-ID: <43EB7E39.2010804@barettadeit.com> Date: Thu, 09 Feb 2006 18:39:05 +0100 From: Alessandro Baretta User-Agent: Debian Thunderbird 1.0.7 (X11/20051017) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Christophe TROESTLER Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] How to write efficient threaded programs on OCaml References: <20060208192118.1755d70f.ocaml-erikd@mega-nerd.com> <20060208.153809.249505014.Christophe.Troestler@umh.ac.be> <43EA0B8D.6090906@inria.fr> <20060208.231335.161803011.Christophe.Troestler@umh.ac.be> In-Reply-To: <20060208.231335.161803011.Christophe.Troestler@umh.ac.be> Content-Type: multipart/mixed; boundary="------------090301010608030902070601" X-Miltered: at nez-perce with ID 43EB808D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; baretta:01 baretta:01 barettadeit:01 caml-list:01 ocaml:01 christophe:01 troestler:01 ocaml:01 mlton:01 threading:01 userland:01 scheduler:01 speedup:01 threading:01 okasaki:01 X-Attachments: type="application/x-extension-ml" name="chameneos_alex.ml" name="chameneos_alex.ml" X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO autolearn=disabled version=3.0.3 This is a multi-part message in MIME format. --------------090301010608030902070601 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Christophe TROESTLER wrote: > On Wed, 08 Feb 2006, Xavier Leroy wrote: > >>Could you please tell us where to find the OCaml code you're >>discussing? I haven't seen it anywhere on the Web page you posted. > > > Sorry. You get the code by clicking on the language name: > http://shootout.alioth.debian.org/gp4/benchmark.php?test=chameneos&lang=all > The task description is at the bottom of the page. > > The one similar to MLton is: > http://shootout.alioth.debian.org/gp4/benchmark.php?test=chameneos&lang=ocaml&id=0 Wow! It's incredible to see just how slow an algorithm can become when threading is used. A vanilla userland scheduler can produce a three-order of magnitude speedup over a threading library. I'm attaching an implementation of chameneos which uses a batched queue à la Okasaki to schedule chameneos meetings. Obviously, this algorithms is absolutely deterministic, while the implementation using threads follows a random execution path, which is in general different at every execution of the program. Yet the program satifies the benchmark specification and is about 700 times faster than http://shootout.alioth.debian.org/gp4/benchmark.php?test=chameneos&lang=ocaml&id=0 I have used this approach to write my Schopenhauer software PLC in Ocaml. This is one of the key design factors for achieving realtime performance without hogging the CPU. Yet, what conclusion should I draw? Is the GNU/Debian/Linux-2.6 threading support creepingly slow, or does ocaml have an insurmountable aversion for threads? Alex -- ********************************************************************* Ing. Alessandro Baretta Studio Baretta http://studio.baretta.com/ Consulenza Tecnologica e Ingegneria Industriale Technological Consulting and Industrial Engineering tel. +39 02 370 111 55 fax. +39 02 370 111 54 --------------090301010608030902070601 Content-Type: application/x-extension-ml; name="chameneos_alex.ml" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="chameneos_alex.ml" KCoKICogQWxlc3NhbmRybyBCYXJldHRhCiAqIFN0dWRpbyBCYXJldHRhCiAqIGh0dHA6Ly9z dHVkaW8uYmFyZXR0YS5jb20vCiAqKQoKCgoKbGV0ICgrKykgeCBmID0gZiB4Cgptb2R1bGUg USA9IHN0cnVjdAogIHR5cGUgJ2EgcXVldWUgPSAnYSBsaXN0ICogJ2EgbGlzdAoKICBleGNl cHRpb24gSXNfZW1wdHkKCiAgbGV0IGVtcHR5ID0gW10sIFtdCiAgbGV0IGlzX2VtcHR5IChm LCByKSA9IGYgPSBbXQoJCQkgICAgCiAgbGV0IGNoZWNrZiA9IGZ1bmN0aW9uCiAgICB8IChb XSBhcyBmcm9udCAscmVhcikgLT4gTGlzdC5yZXYgcmVhciwgZnJvbnQKICAgIHwgcSAtPiBx IAogIGxldCBtYWtlIGwgPSAobCwgW10pCiAgbGV0IGFkZCB4IChmcm9udCwgcmVhcikgPSBj aGVja2YgKGZyb250LCB4IDo6IHJlYXIpCiAgbGV0IHRvcCA9IGZ1bmN0aW9uCiAgICB8IGhk IDo6IHRsLCBfIC0+IGhkCiAgICB8IF8gLT4gcmFpc2UgSXNfZW1wdHkKCiAgbGV0IHBvcCA9 IGZ1bmN0aW9uCiAgICB8IGhkIDo6IHRsLCBsMiAtPiBjaGVja2YgKHRsLCBsMikKICAgIHwg XyAtPiByYWlzZSBJc19lbXB0eQplbmQKCnR5cGUgY29sb3IgPSAgQiB8IFIgfCBZCnR5cGUg bGl2ZV9jaGFtZW5lb3MgPSB7CiAgY29sb3IgOiBjb2xvcjsKICBtZWV0aW5nX2NvdW50IDog aW50Owp9CnR5cGUgZmFkZWRfY2hhbWVuZW9zID0gaW50CgpsZXQgY29tcGwgYzEgYzIgPSBt YXRjaCBjMSwgYzIgd2l0aAogIHwgQiwgQiAtPiBCIHwgUiwgUiAtPiBSIHwgWSwgWSAtPiBZ CiAgfCBCLCBSIHwgUiwgQiAtPiBZICAgfCBCLCBZIHwgWSwgQiAtPiBSICAgfCBSLCBZIHwg WSwgUiAtPiBCCgoKbGV0IGZhZGUgY2ggOiBmYWRlZF9jaGFtZW5lb3MgPSBjaC5tZWV0aW5n X2NvdW50CgpsZXQgcmVxdWVzdGVkX21lZXRpbmdfY291bnQgPSBpbnRfb2Zfc3RyaW5nIFN5 cy5hcmd2LigxKQoKbGV0IHJlYyBtZWV0aW5nX3BoYXNlIChxdWV1ZSA6IGxpdmVfY2hhbWVu ZW9zIFEucXVldWUpIG1lZXRpbmdfcG9pbnQgbWVldGluZ19jb3VudCA9CiAgaWYgbWVldGlu Z19jb3VudCA8IHJlcXVlc3RlZF9tZWV0aW5nX2NvdW50IHRoZW4KICAgIG1hdGNoIG1lZXRp bmdfcG9pbnQgd2l0aAogICAgICB8IE5vbmUgLT4gbWVldGluZ19waGFzZSAoUS5wb3AgcXVl dWUpIChTb21lIChRLnRvcCBxdWV1ZSkpIG1lZXRpbmdfY291bnQKICAgICAgfCBTb21lIGNo MSAtPgogICAgICAgICAgbGV0IGNoMiA9IFEudG9wIHF1ZXVlIGluCiAgICAgICAgICBsZXQg Y29sb3IgPSBjb21wbCBjaDEuY29sb3IgY2gyLmNvbG9yIGluCiAgICAgICAgICBsZXQgcXVl dWUnID0gIHF1ZXVlICsrIFEucG9wCiAgICAgICAgICAgICsrIChRLmFkZCB7IGNvbG9yID0g Y29sb3I7IG1lZXRpbmdfY291bnQgPSBzdWNjIGNoMS5tZWV0aW5nX2NvdW50fSkKICAgICAg ICAgICAgKysgKFEuYWRkIHsgY29sb3IgPSBjb2xvcjsgbWVldGluZ19jb3VudCA9IHN1Y2Mg Y2gyLm1lZXRpbmdfY291bnR9KQogICAgICAgICAgaW4gbWVldGluZ19waGFzZSBxdWV1ZScg Tm9uZSAoc3VjYyBtZWV0aW5nX2NvdW50KQogIGVsc2UgYmVnaW4KICAgIGFzc2VydChtZWV0 aW5nX3BvaW50ID0gTm9uZSk7CiAgICBmYWRpbmdfcGhhc2UgcXVldWUgW10gMAogIGVuZAoK YW5kIGZhZGluZ19waGFzZSBxdWV1ZSBmYWRlZF9jaGFtZW5lb3MgcmVwb3J0ZWRfbWVldGlu Z3MgPQogIGlmIFEuaXNfZW1wdHkgcXVldWUgdGhlbiByZXBvcnRlZF9tZWV0aW5ncyBlbHNl CiAgICBsZXQgY2ggPSBRLnRvcCBxdWV1ZSBpbgogICAgICBmYWRpbmdfcGhhc2UgKFEucG9w IHF1ZXVlKSAoKGZhZGUgY2gpOjpmYWRlZF9jaGFtZW5lb3MpIChyZXBvcnRlZF9tZWV0aW5n cyArIGNoLm1lZXRpbmdfY291bnQpCgpsZXQgY2ggPSB7IGNvbG9yID0gQjsgbWVldGluZ19j b3VudCA9IDAgfQpsZXQgY2hfbGlzdCA9IFsgY2g7IHsgY2ggd2l0aCBjb2xvciA9IFIgfTsg eyBjaCB3aXRoIGNvbG9yID0gWSB9OyBjaCBdIAoKbGV0IHJlcyA9IG1lZXRpbmdfcGhhc2Ug KFEubWFrZSBjaF9saXN0KSBOb25lIDAgCgpsZXQgKCkgPSBwcmludF9pbnQgcmVzOyBwcmlu dF9uZXdsaW5lICgpCg== --------------090301010608030902070601--