Friday, September 12, 2008

Interlude: Disassembling F# code

No new code in this tutorial. Instead, I thought I would introduce .NET reflector (if you don't already know it). This tools allows to examine any .NET assembly to see what classes and functions it contains. It can also disassemble code into C#.

To refresh our memory, this was the F# code of "simulate":
let simulate intg_func t0 t_fin delta pos0 speed0 =
    let rec repeat t0 t_fin pos0 speed0 =
        if t0 >= t_fin then pos0, speed0
        else
            let t1 = t0 + delta
            let pos1, speed1 = intg_func pos0 speed0 delta in
            repeat t1 t_fin pos1 speed1
    repeat t0 t_fin pos0 speed0


The disassembled code in C# looks approximately as follows (I have simplified and cleaned up the text a bit):
internal static Tuple
simulate@37(FastFunc intg_func, double t0, double t_fin, double delta, double pos0, double speed0)
{
    FastFunc f = new clo@39(intg_func, delta);
    return FastFunc.InvokeFast4(f, t0, t_fin, pos0, speed0);
}

"clo@39" must be some sort of wrapper for the "repeat" inner function I defined in "simulate". Notice how the generated code handles "intg_func" and "delta" differently from the other variables "t0", "t_fin", "pos0" and "speed0". The former are passed once during the construction of "clo@39", the latter are passed as arguments when invoking the "repeat" function.
Looking back to the F# code, notice that "intg_func" and "delta" indeed are special. Although they are used by "repeat", they are not parameters of it. This is called a closure. The reason for using a closure will become clear if you continue reading.

Let us look at "clo@39". It has an "Invoke" method which is called when "repeat" is called in the F# code:
public override Tuple Invoke(double t0, double t_fin, double pos0, double speed0)
{
    while (t0 < t_fin)
    {
        double num = t0 + this.delta;
        Tuple tuple = FastFunc.InvokeFast3(this.intg_func, pos0, speed0, this.delta);
        speed0 = tuple.Item2;
        pos0 = tuple.Item1;
        t_fin = t_fin;
        t0 = num;
    }
    return new Tuple(pos0, speed0);
}
I was not surprised when I noticed it, but the F# compiler has turned my recursive function "repeat" into a non-recursive loop. This is an important optimization that most functional languages support. All tail-recursive functions can easily be turned into non-recursive functions, which saves a lot of stack space.

The result would be beautiful, if it were not for this strange thing: "t_fin = t_fin;". I can see that the original F# code does indeed copy "t_fin" every iteration, and in that sense the generated code remains faithful to the original code. I wish F# had optimized this unnecessary copying away, but it probably has its reasons for not doing so. Happily, there is a work-around, which is to use a closure. This is precisely what I did for "intg_func" and "delta".
One might even say that this work-around is more than that, it actually is the right way of doing things. Constant parameters should not be passed explicitly as parameters to recursive functions.

Let us continue and look into "runge_kutta_4". First, the F# code from the previous tutorial:
let runge_kutta_4 accel_func pos speed delta =
    let half_delta = 0.5 * delta
    let deriv_func = adapt accel_func
    let s1, a1 = deriv_func pos speed
...

The generated code, translated to C#:
internal static Tuple runge_kutta_4@26(FastFunc accel_func, double pos, double speed, double delta)
{
    double num = 0.5 * delta;
    FastFunc f = new clo@28(accel_func);
    Tuple tuple = FastFunc.InvokeFast2(f, pos, speed);
...
Nothing really suprising here, but I just took notice of how the adapted variant of "accel_func" is recreated in each call. That is obviously not very efficient, considering how often this function is called.

In the next tutorial, I will present an optimized version of the code and compare it to implementations in C++ and OCaml.

1 comment:

LLB said...

Hi,

"I wish F# had optimized this unnecessary copying away, but it probably has its reasons for not doing so."

I agree, this line is useless. But I suppose that removing it would add a little complexity in the F# compiler, and I'm not sure the result would be faster: I think the JIT compiler detects it and removes this useless line.