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.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id C5402BC69 for ; Sat, 2 Jun 2007 01:26:43 +0200 (CEST) Received: from ipmail03.adl2.internode.on.net (ipmail03.adl2.internode.on.net [203.16.214.135]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l51NQfE1005867 for ; Sat, 2 Jun 2007 01:26:42 +0200 X-IronPort-AV: E=Sophos;i="4.16,374,1175437800"; d="scan'208";a="97810775" Received: from ppp9-14.lns1.syd7.internode.on.net (HELO [192.168.1.201]) ([59.167.9.14]) by ipmail03.adl2.internode.on.net with ESMTP; 02 Jun 2007 08:56:37 +0930 Subject: Re: [Caml-list] Comparison of OCaml and MLton for numerics From: skaller To: Brian Hurt Cc: Stephen Weeks , caml-list@yquem.inria.fr In-Reply-To: <466033EC.3050909@janestcapital.com> References: <5195a210705302250u6a9e5adey4ed857480f9e5cd8@mail.gmail.com> <891bd3390706010429g2ac722bfmc6932b15393a62b9@mail.gmail.com> <20070601214326.e0a939a6.mle+ocaml@mega-nerd.com> <200706011258.59177.jon@ffconsultancy.com> <604682010706010718x42221e8rde56317905f5c972@mail.gmail.com> <466033EC.3050909@janestcapital.com> Content-Type: text/plain Date: Sat, 02 Jun 2007 09:26:33 +1000 Message-Id: <1180740393.5142.26.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.10.1 Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 4660AB31.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 inlining:01 compiler:01 compiler:01 inlined:01 inlining:01 coefficients:01 recursive:01 inlined:01 recursive:01 messes:01 recursion:01 typeclass:01 typeclass:01 sourceforge:01 On Fri, 2007-06-01 at 10:57 -0400, Brian Hurt wrote: > And the third case, where inlining opens up new > possibilities for optimization- that almost has to be done by the > compiler, as it depends upon what optimizations the compiler can, and > will, apply to the newly inlined function. This is something I trust > the compiler to do more than I trust even me to do correctly. It's NOT so easy to predict how much optimisation will result from inlining. Just think about it, you have a tree of inlining opportunities, if do you really want to attempt to estimate the coefficients on N inlining choices just to decide if you'll inline or not? I doubt it. The compiler will make one guess whether to inline or not based on a some fast heuristic, and then commit. Felix inlines based on the number of statements in a function. The default threshhold is 50. Inlining is done bottom up. Recursive calls to children are inlined, others are not. Tail-rec optimisation is done before each inlining operation. Then, a monormorphisation pass is done, and the inlining process repeated. The HARD problem I haven't solved at all is how to improve the recursive function inlining rule: since only recursive calls to children are inlined, recursive calls to siblings are not. This is really bad, because a self-tail-rec optimisation might apply after a sibling inline, but the opportunity is lost because I don't know how to safely inline siblings. This sounds easy .. just inline until you spot a self call. But it isn't easy, because that doesn't work. This is because inlining a function requires 'cloning' all its children, and a recursive call can be left as a call to the original function .. so the call isn't recursive anymore. Sibling inlining can then spew an infinite expansion. Typeclasses make a real mess here: instances need to be kept around until you're sure they're not needed, which in general is after the post monomorphisation inlining phase, and, replacing a 'virtual' with a concrete call messes up tracking of recursion as well .. I'm not even sure my algorithm is safe in respect of typeclass instantiation if the typeclass instance function is recursive on the typeclass. -- John Skaller Felix, successor to C++: http://felix.sf.net