F#: Partial application and precalculation

Question

Looking at a function in my code today, I wondered if it was possible to combine partial combination and optimisation:

let foo (X:float) y1 y2 dx = 
    y1 + (y2 - y1) * dx / X

Basically, just applying a ratio - so the first three parameters are generally the same within a given loop.

I thought maybe if I just did this:

let foo2 (X:float) y1 y2 dx = 
    let dy = (y2 - y1) / X
    y1 + dy * dx

F# would get clever and optimise for me when I partially apply the first three parameters, but it debug mode it doesn't appear to be the case (though I'm not sure that I went about testing for it in the right way).

The question is, should this work? And if not is there a better way of doing it (apart from just writing another function with two parameters)?

Answer 1

I'm not surprised that nothing is apparently different in debug mode. Why don't you actually time N repetitions of it (#time;; at the F# interactive prompt).

As for your hope to share the common computation for fixed values of all but dx, try this:

let fdx = foo2 X y1 y2
for dx in dxes do
    fdx dx

That is, fdx is the partial application. Storing it explicitly outside the loop makes me hope for more from the optimizer.

At least in the interactive prompt (I don't think full optimization is done there, is it?) it looks like my suggestion is only a 15% speedup (it's weird that there's any speedup, because it definitely repeats the full body of foo2). Doing this is much faster:

let fdx = foo3 X y1 y2
for dx in dxes do
    fdx dx

Where foo3 is (from Benjlol):

let foo3 (X:float) y1 y2 =
    let dy = (y2 - y1) / X
    (fun dx -> y1 + dy * dx)

Note that just using foo3 as a 4 argument function in the loop is twice as slow as foo2, but storing the partial application outside the loop, it's 3 times faster.

Answer 2

(This isn't reputation whoring, I honestly hadn't thought of this when I started asking my question)

Here's one solution I've come up with, not sure if it's the best:

let foo3 (X:float) y1 y2 =
    let dy = (y2 - y1) / X
    (fun dx -> y1 + dy * dx)

Works a lot faster.

Answer 3

I think that most such 'magic optimizations' would require 'effects analysis' that is only done by the mythical 'sufficiently smart compiler'.

Ponder this:

let Expensive x y = 
    printfn "I am a side-effect of Expensive"
    x + y  // imagine something expensive

let F x y z =
    let tmp = Expensive x y
    z + tmp

printfn "Least chance of magic compiler optimization"
for i in 1..3 do    
    F 3 4 i

printfn "Slightly better chance"
let Part = F 3 4
for i in 1..3 do    
    Part i

printfn "Now for real"
let F2 x y =
    let tmp = Expensive x y
    (fun z -> z + tmp)

printfn "Of course this still re-does it"
for i in 1..3 do    
    F2 3 4 i

printfn "Of course this finally saves re-do-ing Expensive"
let Opt = F2 3 4
for i in 1..3 do    
    Opt i

(* output

Least chance of magic compiler optimization
I am a side-effect of Expensive
I am a side-effect of Expensive
I am a side-effect of Expensive
Slightly better chance
I am a side-effect of Expensive
I am a side-effect of Expensive
I am a side-effect of Expensive
Now for real
Of course this still re-does it
I am a side-effect of Expensive
I am a side-effect of Expensive
I am a side-effect of Expensive
Of course this finally saves re-do-ing Expensive
I am a side-effect of Expensive

*)

The point is, the language semantics regarding effects require the compiler to behave exactly like this, unless 'Expensive' has no effects and the compiler is really really smart and can discover that on its own.