From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 572FBBC57 for ; Mon, 13 Dec 2010 16:45:49 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnYBAA7OBU2GnQCBkWdsb2JhbACkBBUBAQEBCQsKBxEDJsIehUoEkBOGCg X-IronPort-AV: E=Sophos;i="4.59,336,1288566000"; d="scan'208";a="70408672" Received: from shiva.jussieu.fr ([134.157.0.129]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 13 Dec 2010 16:45:49 +0100 Received: from hydrogene.pps.jussieu.fr (hydrogene.pps.jussieu.fr [134.157.168.1]) by shiva.jussieu.fr (8.14.4/jtpda-5.4) with ESMTP id oBDFjhwc039586 ; Mon, 13 Dec 2010 16:45:44 +0100 (CET) X-Ids:165 Received: from strontium.pps.jussieu.fr (Debian-exim@strontium.pps.jussieu.fr [134.157.168.38]) by hydrogene.pps.jussieu.fr (8.13.4/jtpda-5.4) with ESMTP id oBDFjZoZ008959 ; Mon, 13 Dec 2010 16:45:35 +0100 Received: from vouillon by strontium.pps.jussieu.fr with local (Exim 4.72) (envelope-from ) id 1PSAal-0007wJ-Ez; Mon, 13 Dec 2010 16:45:35 +0100 Date: Mon, 13 Dec 2010 16:45:35 +0100 From: Jerome Vouillon To: Yitzhak Mandelbaum Cc: Jerome Vouillon , caml-list@yquem.inria.fr Subject: Re: [Caml-list] [ANN] Js_of_ocaml version 1.0 Message-ID: <20101213154535.GA30270@pps.jussieu.fr> References: <20101213130645.GA27585@pps.jussieu.fr> <0C2C6562-3389-4B61-B0E2-69EF3EAB1418@cs.princeton.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <0C2C6562-3389-4B61-B0E2-69EF3EAB1418@cs.princeton.edu> User-Agent: Mutt/1.5.20 (2009-06-14) X-Miltered: at jchkmail.jussieu.fr with ID 4D063FA7.009 by Joe's j-chkmail (http : // j-chkmail dot ensmp dot fr)! X-j-chkmail-Enveloppe: 4D063FA7.009/134.157.168.1/hydrogene.pps.jussieu.fr/hydrogene.pps.jussieu.fr/ X-Spam: no; 0.00; vouillon:01 vouillon:01 ocaml:01 yitzhak:01 mandelbaum:01 recursion:01 ocaml:01 recursion:01 trampoline:01 expansive:01 trampoline:01 1.0:98 wrote:01 wrote:01 compilers:01 On Mon, Dec 13, 2010 at 09:58:27AM -0500, Yitzhak Mandelbaum wrote: > One small question: could you expand on your last comment: > > On Dec 13, 2010, at 8:06 AM, Jerome Vouillon wrote: > > > > > > > Ocamljs optimizes tail recursion, but this comes at a large > > performance cost. > > Do you mean all tail-calls come a large cost, or only those outside > of plain tail-recursion? Either way, could you give us some more > intuition as to why this happens, and why js_of_ocaml doesn't suffer > from the same problem (assuming it applies to tail-recursion)? I meant tail calls, indeed. Tail recursion (when a function calls itself recursively in tail position) can be optimized efficiently by wrapping the function body inside a loop. This is what Js_of_ocaml does. For optimizing tail calls in general, you need to use trampolines. Instead of calling a function in tail position, you return this function and its arguments. Then, a piece of code called a trampoline takes care of invoking repeately the functions it receives this way until a final result is returned. This is expansive. You have to make sure that this piece of code is there whenever a function is invoked in tail position. Also, the JIT compilers cannot optimize the trampoline, as the functions it will have to call, and their number of arguments, are unknown. -- Jerome