Why are F# list ranges so much slower than for loops?

Question

I'm surprised how much slower the List range is for the example below. On my machine the for loop is a factor of 8 or so quicker.

Is an actual list of 10,000,000 elements created first? And if so, is there a reason (other than it has not been done yet) why this can't be optimised away by the compiler?

open System
open System.Diagnostics

let timeFunction f v =
    let sw = Stopwatch.StartNew()
    let result = f v
    sw.ElapsedMilliseconds

let length = 10000000

let doSomething n =
    (float n) ** 0.1 |> ignore

let listIter n =
    [1..length] |> List.iter (fun x -> doSomething (x+n))

let forLoop n = 
    for x = 1 to length do
        doSomething (x+n)

printf "listIter   : %d\n" (timeFunction listIter 1)  // c50
GC.Collect()
printf "forLoop    : %d\n" (timeFunction forLoop 1)  // c1000
GC.Collect()

Answer 1

Using ILSpy, listIter looks like this:

public static void listIter(int n)
{
    ListModule.Iterate<int>(
        new listIter@17(n), 
        SeqModule.ToList<int>(
            Operators.CreateSequence<int>(
                Operators.OperatorIntrinsics.RangeInt32(1, 1, 10000000)
            )
        )
    );
}

Here are the basic steps involved:

1. RangeInt32 creates an IEnumerable (which is inexplicably wrapped by CreateSequence)
2. SeqModule.ToList builds a list from that sequence
3. An instance of listIter@17 (your lambda) is new'd up
4. ListModule.Iterate traverses the list calling the lambda for each element

vs forLoop, which doesn't look much different from what you've written:

public static void forLoop(int n)
{
    for (int x = 1; x < 10000001; x++)
    {
        int num = x + n;
        double num2 = Math.Pow((double)num, 0.1);
    }
}

...no IEnumerable, lambda (it's automatically inlined), or list creation. There's a potentially significant difference in the amount of work being done.

EDIT

For curiosity's sake, here are FSI timings for list, seq, and for loop versions:

listIter - Real: 00:00:03.889, CPU: 00:00:04.680, GC gen0: 57, gen1: 51, gen2: 6  
seqIter  - Real: 00:00:01.340, CPU: 00:00:01.341, GC gen0:  0, gen1:  0, gen2: 0  
forLoop  - Real: 00:00:00.565, CPU: 00:00:00.561, GC gen0:  0, gen1:  0, gen2: 0

and the seq version for reference:

let seqIter n =
    {1..length} |> Seq.iter (fun x -> doSomething (x+n))

Answer 2

Using {1..length} |> Seq.iter is certainly faster as you don't create the full list in memory.

Another slightly faster way than your for loop is:

let reclist n =
    let rec downrec x n =
        match x with 
        | 0 -> ()
        | x -> doSomething (x+n); downrec (x-1) n
    downrec length n

Interesting is that the code for the recursive function boils down to:

while (true)
{
    switch (x)
    {
    case 0:
        return;
    default:
    {
        int num = x + n;
        double num2 = Math.Pow((double)num, 0.1);
        int arg_26_0 = x - 1;
        n = n;
        x = arg_26_0;
        break;
    }
    }
}

Even when using optimization, there are still a few lines that could have been removed, i.e to this:

while (true)
{
    switch (x)
    {
    case 0:
        return;
    default:
    {
        int num = x + n;
        double num2 = Math.Pow((double)num, 0.1);
        x = x - 1;
        break;
    }
    }
}