4

I am working on a parser combinator library and found some behavior I couldn't explain. The first time I run the combinator it runs significantly slower than the second time that I run it. I repo'd the behavior with this small app (running Release with optimizations on)

let (>>=) first callback state = 
    let reply = first state
    callback reply state

let time f = 
    let start = System.DateTime.Now
    f()
    printfn "%s" ((System.DateTime.Now - start).ToString())

[<EntryPoint>]
let main args = 

    let x1 state = "foo"

    let compound = 
        x1 >>= fun i ->
        x1 >>= fun j ->
        x1 >>= fun a ->
        x1 >>= fun b ->
        x1 >>= fun c ->
        x1 >>= fun d ->
        x1 >>= fun e ->
        x1 >>= fun f ->
        x1 >>= fun j ->                
               fun _ -> [i;j;a;b;c;d;e;f]


    time (fun () -> compound "a" |> ignore)
    time (fun () -> compound "b" |> ignore)
    time (fun () -> compound "c" |> ignore)


    0

Running this output I get

00:00:00.0090009
00:00:00.0010001
00:00:00

Why is the first iteration so much slower than the second or third?

Edit, so I tried this out in C# as well. It runs faster, but the results are similar. 

using System;

namespace fssharp
{
    public delegate string Parser(string state);

    public delegate Parser Callback(string result);

    public class Combinator
    {
        public static Parser Combine(Parser p, Callback callback)
        {
            Parser r = state =>
            {
                var result = p(state);
                return callback(result)(state);
            };

            return r;
        }

        public static string X1(string state)
        {
            return "foo";
        } 
    }
    class Program
    {
        static void Main(string[] args)
        {
            Parser comb = state => 
                                Combinator.Combine(Combinator.X1, result  =>
                                Combinator.Combine(Combinator.X1, result2 =>
                                Combinator.Combine(Combinator.X1, result3 =>
                                Combinator.Combine(Combinator.X1, result4 =>
                                Combinator.Combine(Combinator.X1, result5 =>
                                Combinator.Combine(Combinator.X1, result6 =>
                                Combinator.Combine(Combinator.X1, result7 =>
                                Combinator.Combine(Combinator.X1, result8 =>
                                Combinator.Combine(Combinator.X1, result9 => s => result + result2 + result3 +result4 +result5 +result6 +result7+result8+result9)))
                                ))))))(state);

            var now = DateTime.Now;

            comb("foo");

            Console.WriteLine(DateTime.Now - now);

            now = DateTime.Now;

            comb("foo2");

            Console.WriteLine(DateTime.Now - now);
        }
    }
}

This prints out

00:00:00.0030003
00:00:00

I'm now curious why C# is faster here

4

1 回答 1

5

Even tough I can't tell for sure, it is either:

  1. JIT: The function is JIT'ed the first time it runs, and then it uses the already compiled version

  2. It detects that the same function is called with the same parameters and cache the result.

Try to call it with a different parameter. If the time stays the same it's 2, if time is different it's 1

于 2013-09-06T21:09:30.197 回答