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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id B7DCEBC6B for ; Wed, 27 Jun 2007 17:06:53 +0200 (CEST) Received: from smtp21.orange.fr (smtp21.orange.fr [80.12.242.47]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RF6rhr029625 for ; Wed, 27 Jun 2007 17:06:53 +0200 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf2112.orange.fr (SMTP Server) with ESMTP id 2FADA1C000A8 for ; Wed, 27 Jun 2007 17:06:53 +0200 (CEST) Received: from [192.168.1.162] (ALagny-153-1-98-23.w90-3.abo.wanadoo.fr [90.3.145.23]) by mwinf2112.orange.fr (SMTP Server) with ESMTP id E93ED1C000A4 for ; Wed, 27 Jun 2007 17:06:52 +0200 (CEST) X-ME-UUID: 20070627150652955.E93ED1C000A4@mwinf2112.orange.fr Mime-Version: 1.0 (Apple Message framework v752.2) In-Reply-To: <46826C69.5060802@functionality.de> References: <200706271314.35134.jon@ffconsultancy.com> <1A1D6F56-B3DB-4552-969C-9859482175AC@lrde.epita.fr> <46826C69.5060802@functionality.de> Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: quoted-printable From: =?ISO-8859-1?Q?Qu=F4c_Peyrot?= Subject: Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments Date: Wed, 27 Jun 2007 17:06:51 +0200 To: caml-list@yquem.inria.fr X-Mailer: Apple Mail (2.752.2) X-Miltered: at concorde with ID 46827D0D.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; lrde:01 speedup:01 buffer:01 allocating:01 ocaml:01 ocaml:01 factorial:01 computations:01 high-level:01 low-level:01 runtime:01 high-level:01 compilation:01 2007,:98 1.0:98 On Jun 27, 2007, at 3:55 PM, Thomas Fischbacher wrote: > Qu=F4c Peyrot wrote: [...] > > let encrypt ?encrypted str =3D > > let len =3D String.length str in > > let result =3D match encrypted with > > | None -> String.create len > > | Some s -> s > > in > > (* ... *) > > result > >> Which gave me more than a 2x speedup while still being able to =20 >> call a simple: >> let encrypted =3D encrypt str >> during normal usage > > I use this strategy a lot and found that it eventually pays to use > uniform conventions for that: all my functions that can benefit from > having space pre-allocated where to write a result to use ?target > as their very first named optional argument (and also return that > target buffer afterwards). Ah, thanks, I was actually trying to find a common name too, but didn't really like "result". "target" is nice :p > However, unless I am mistaken, I fear that this also does introduce > some intrinsic/unavoidable inefficiency, as providing a ?target > argument will (presuambly?) require dynamic consing of a > option cell - so not a good idea for a very small function that is > called very very often. > > There are many many way more advanced tricks one would want to play > with the idea of "allocating buffers at the appropriate time". For > example, if this were LISP, one could often use dynamically scoped (in > the sense of (declare (dynamic-extent buffer-stack))) contextual > variables for great benefit (and these gory details often can also be > hidden quite conveniently under a few (maybe even in-place macrolet) > macros...), but unfortunately, OCaml does not support anything like > that. Of course, re-entrantness of your code may always become an > issue if you move buffers to higher scopes. I didn't get that part, but I'm not familiar with Lisp. > One thing OCaml can do better than, say, CMU CL, is to define globally > visible functions that depend on some otherwise inaccessible context, > as in the following example: > > let float_factorial =3D > let _known_factorials =3D ref [|1.0;1.0;2.0;6.0;24.0;120.0;720.0|] = in > (fun n -> I encountered this pattern today while reading extlib's OptParse.Opt =20 code: let value_option metavar default coerce errfmt =3D let data =3D ref default in { option_metavars =3D [metavar]; option_defhelp =3D None; option_get =3D (fun _ -> !data); option_set_value =3D (fun x -> data :=3D Some x); (*...*) I was a little bit surprised at first that we could do that =20 (let ...ref... in) but it's really nice. To me it seems that the common feature which enables us to do all =20 these tricks is the fact that we have a garbage collector (correct me =20= if I am wrong). It's really powerful, and I find it fascinating. I mean, for someone like me, with quite some experience in the asm/c/c=20= ++ world (i.e. a garbage collector-less world) but not much in other =20 languages, it's easy to naively think of a garbage collector as a =20 fancy feature to prevent from having to call "free/delete". But I'm =20 starting to realize there is a whole new set of powerful design =20 patterns which come along. It has been said multiple times on this =20 mailing list, but I think we really miss a book about these design =20 patterns and optimization tricks often specific to a given (or a set =20 of) feature (functional, lazy computations, garbage collector...). I find it ironical that high-level languages (such as ocaml) are =20 intended (of course that's my interpretation of it) to hide low-level =20= details and give you more expressiveness in your code, which should =20 naively make you more productive, and make it easier to program =20 something. But requires therefore tons of new knowledges and deep =20 understanding of advanced concepts to be able to actually code =20 efficient (runtime and memory-wise) code. I mean, in asm/c/c++ there isn't much feature to learn, you pretty =20 much do everything yourself. It's therefore quite easy (comparing to =20 OCaml) to actually see what is efficient and what is not. OCaml is so =20= high-level, and is doing so much for you, that you really need to =20 learn a lot more about compilation theory to be able to actually feel =20= at ease when you are looking for efficiency without giving up too =20 much code elegance. But don't get me wrong, I love it, it's =20 fascinating, but still ironical from my point of view. > Other advanced optimization techniques that can be used for benefit > in very specialized situations include (explicit) continuation coding: > rather than returning a value (e.g. a tuple), you take as an argument > a function to which you then pass on your return value(s). This is =20 > quite > useful whenever "execution flow branches out into multiple paths that > have to be taken", and may sometimes (though rarely) also be used for > good as a poor man's VALUES/MULTIPLE-VALUE-BIND substitute. I didn't get that part at all. I think I would need an example to =20 understand why it is interesting to pass the function instead of just returning =20 the tuple and processing it. --=20 Best Regards, Qu=F4c