Re: [Caml-list] optimizing numerical code

[Gerd Stolpmann <info@gerd-stolpmann.de>]

Am Donnerstag, den 19.05.2011, 12:59 +0200 schrieb Alain Frisch:
> On 05/19/2011 10:37 AM, Joel Reymont wrote:
> >
> > On May 19, 2011, at 10:24 AM, Alain Frisch wrote:
> >
> >> Actually, even in this branch, acc would not be unboxed. The new heuristic unboxes float variables unless they are both needed in boxed form AND mutated, which is the case for acc in your function.
> >
> > Shouldn't it be unboxed, though?
> 
> Yes, in this case, it would make a lot of sense to work with an unboxed 
> variable and only box it when needed. But finding a good heuristic is 
> not trivial. Always applying this approach of "on-demand" boxing might 
> have drawbacks: more allocations (if the same value is used several 
> times in boxed form) and less sharing of allocations (the compiler 
> combines adjacent allocations to avoid some overhead). In the example, 
> it is easy to find out that the variable is used only once in boxed form 
> (in a context executed at most once).

Would it make sense to let the developer help when deciding which
occurrences of a variable are important and which not? I'm thinking here
of a function

let rare = identity

with the additional pragma that the argument of rare is considered as an
expression that is rarely evaluated. In our example:

let js_divergence1 v1 v2 =
  let acc = ref 0. in
  for i = 0 to (Array.length v1) - 1 do
    let x = v1.(i)
    and y = v2.(i) in
    let m = 0.5 *. (x +. y) in
    let d1 = x *. log (x /. m) 
    and d2 = y *. log (y /. m) in
    acc := !acc +. d1 +. d2
  done;
  rare (!acc)              (* HERE *)

For the check whether a float can be unboxed, rare occurrences are
simply ignored. Maybe it is also helpful for other decisions, e.g.
register allocation.

> Here is another "lazy" approach that could be worth trying. 

In some sense, this goes into the same direction, only that rare-ness is
determined at runtime.

Gerd

> Consider a 
> float variable x which is assigned and used both in boxed and unboxed 
> form in the same function. Internally, we keep two variants of it: 
> x_boxed and x_unboxed. When x is assigned the result of some float 
> expression e:
> 
> - if e can be computed directly in unboxed form (e.g. it is the result 
> of some numerical operation), assign x_unboxed only;
> 
> - if e comes in boxed form (e.g. it is the result of some function 
> call), assign x_boxed and x_unboxed (by dereferencing x_boxed);
> 
> 
> When x is used an an unboxing context, use x_unboxed. When x is used as 
> a boxed value (e.g. as an argument to a function call, or as the return 
> value of the current function), check (at runtime) if the content of 
> x_boxed is equal to x_unboxed; if yes, return x_boxed; otherwise, box 
> x_unboxed, store the new block in x_boxed and returns it.
> 
> This scheme guarantees that at most one allocation happens between two 
> successive assignment to the variable, and that no allocation happens if 
> it turns out that the current value is never used in boxed form. This 
> comes at the price of some extra equality checks between floats and 
> conditional jumps, but it might be worth trying.
> 
> 
> -- Alain
> 


-- 
------------------------------------------------------------
Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------