Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments

[Thomas Fischbacher <tf@functionality.de>]

Quôc Peyrot wrote:

> It's funny that you speak about this, because I recently (few days  ago) 
> used
> a pattern similar to yours, but to actually improve performances.
> I had something like that (which is quite different than my actual  
> code, but
> the idea is the same):
> 
> let encrypt str =
>   let len = String.length str in
>   let encrypted = String.create len in
>   (* ... *)
>   encrypted

vs.

 > let encrypt ?encrypted str =
 >   let len = String.length str in
 >   let result = 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 call a  
> simple:
> let encrypted = 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).

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 <thingy>
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.

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 =
   let _known_factorials = ref [|1.0;1.0;2.0;6.0;24.0;120.0;720.0|] in
   (fun n ->
     let known_factorials = !_known_factorials in
     let nr_known = Array.length known_factorials in
     if n < nr_known
     then
       known_factorials.(n)
     else
       let new_known_factorials = Array.make (n+1) 0.0 in
       begin
	for i=0 to nr_known-1 do
	  new_known_factorials.(i) <- known_factorials.(i)
	done;
	(let rec fill f_pos pos =
	  if pos > n then ()
	  else
	    let () = new_known_factorials.(pos) <- f_pos in
	    fill (f_pos *. (float_of_int (pos+1))) (pos+1)
	in
	fill (known_factorials.(nr_known-1)*.(float_of_int nr_known)) nr_known);
	_known_factorials := new_known_factorials;
	new_known_factorials.(n)
       end)
;;

A corresponding

(let ((buffer (make-array ...)))
  (defun float-factorial (n)
     ...))

just plainly does not work with CMU CL/SBCL. :-(

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 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.

-- 
best regards,
Thomas Fischbacher
tf@functionality.de