From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.3 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 2A302BB84 for ; Tue, 20 May 2008 02:04:36 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArQDAE+yMUjRVcioZGdsb2JhbACSJBoDBAQJDgaWa4R3 X-IronPort-AV: E=Sophos;i="4.27,512,1204498800"; d="scan'208";a="26370553" Received: from wf-out-1314.google.com ([209.85.200.168]) by mail4-smtp-sop.national.inria.fr with ESMTP; 20 May 2008 02:04:35 +0200 Received: by wf-out-1314.google.com with SMTP id 24so1610038wfg.15 for ; Mon, 19 May 2008 17:04:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; bh=EMI4ZABQym/IgrvBpKU33i/Q9VVBB2FFjIjxJU5vEII=; b=Sj5nduC+WhNCRaK8R51EEXrBXDrqo2F2HnKiN5WGLZuMUTc+oyloVvGLq3/qJOhbsXTzVhiRjQ1JJaxjvL9tUEJJdYQQP34ZcX7w9dfNXcqQLgL0QRsowGYHWhF4ZJ6UpjmJbhpP/NdKIu8v5DRVvyQx9KLXd8EY3RYI2cZfPQ8= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=u2d7brrOtj+n/U7p6J8uTzk6qNy2qYIFmVmnCPXjHHEBoZN+ICu7IOGs6BpHj5AYRhXnBmpwtl7lsI6gy9QqC38/C/9ZSIBMvJhnTaE4iahxxzjJ7LR9ChIiPfBSlYl0Yg5SzNCFKG9Y9+fTFTqA2zwj17W8YRnOmSQw8T2FS7E= Received: by 10.142.99.21 with SMTP id w21mr3076714wfb.55.1211241873109; Mon, 19 May 2008 17:04:33 -0700 (PDT) Received: by 10.142.11.19 with HTTP; Mon, 19 May 2008 17:04:33 -0700 (PDT) Message-ID: <6cb897b30805191704q253aae2dq43a6c0dd8ad3d394@mail.gmail.com> Date: Tue, 20 May 2008 02:04:33 +0200 From: "Pierre-Evariste Dagand" To: raould@gmail.com, caml-list@yquem.inria.fr Subject: Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology? In-Reply-To: <91a2ba3e0805191537g7fec02f9h7c46aa1be4b92270@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <4831686F.8010903@doc.ic.ac.uk> <200805192247.09949.jon@ffconsultancy.com> <91a2ba3e0805191537g7fec02f9h7c46aa1be4b92270@mail.gmail.com> X-Spam: no; 0.00; decremented:01 speedup:01 ocaml:01 ocaml:01 elected:98 ame:98 char:01 caml-list:01 conflicts:01 conflicts:01 precisely:01 ens-cachan:01 semantic:02 explicitly:02 explicitly:02 Hi all, > i am under the impression that STM is harder to optimize since > generally you don't know what the transactions collided on. whereas > with a "hot lock" you can see precisely what code uses that lock and > what it locks. I'm not so sure... In fact, my work in the past 4 months has been to build a toy language to experiment with the Automatic Mutual Exclusion semantic defined in [1]. At the beginning, I was, just like most of you, quite sceptical about STM and its performance. Besides, in this language, *everything* is under a transaction : unless you specify it explicitly with the keyword "unprotected", every access to memory is saved in a transaction. This have the nice property to produce, by default, proven thread-safe code. But, without transactional processors, this have a high performance cost, as you can imagine. The second part of my work has been to develop a kind of profiler that provide the developer with the "hot transactions". And I have just finished it a minute ago, hence I can show you a nice, typical output : Frequency Definition pos. Transactions 80.% 88 { [ 31247 | read ] } <-> { [ 31247 | read ] [ 31318 | write ] } { [ 31247 | read ] } <-> { [ 31247 | read ] [ 31318 | write ] } { [ 31247 | read ] } <-> { [ 31247 | read ] [ 31318 | write ] } { [ 31247 | read ] } <-> { [ 31247 | read ] [ 31318 | write ] } 20.% 49 { [ 31425 | read ] } <-> { [ 31425 | read ] [ 31450 | write ] } Therefore, you first develop your code, with everything in a transaction. Then, you run the profiler. Here, you see that the reference cell defined at character 88 of the source code is a the root of 80% of the conflicts. And you know the conflicting transactions. At that point, you can either change the code to get less contention of this reference cell (my choice here) or shorten the transactions by, explicitly, committing them more frequently. ( this profiles my implementation of a concurrent Queue and the cell at char 88 contains the size of the queue that is incremented/decremented when we push/pop ) Hence, concerning performance, you will be able to, easily, identify "hot transactions" and reduce the number of conflicts. But I see someone in the room arguing that he don't even want to bother with transactions because there is a 4242% decrease in speed. Good news ! With the "unprotected" keyword, you can work out of any transactions, at full speed, *without sacrificing thread-safety* (and this is ensured by the type-system). To sum up, the idea is "thread-safe by default" and then "earn more (speedup) by working more". Some people has been elected with such ideas, I might get the Turing award for that... If someone is interested in this toy language, let me know. But the great and crazy part now is to transfer this technology in OCaml. For the programmer, that's just 3 new keywords in the language. For the guy that will implement AME in OCaml, well... that's a lot of work... Regards, [1]: http://research.microsoft.com/~tharris/papers/2008-popl.pdf -- Pierre-Evariste DAGAND http://perso.eleves.bretagne.ens-cachan.fr/~dagand/