Why is the range of F # ranges much slower than for loops?

Question

I am surprised how slow the List range is for the example below. On my machine, the for loop is a factor of 8 or faster.

Is the actual list of 10,000,000 items created first? And if so, is there a reason (other than it has not yet been done) why is it impossible to optimize the compiler?

open System open System.Diagnostics let timeFunction fv = let sw = Stopwatch.StartNew() let result = fv 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 main steps:

• RangeInt32 creates IEnumerable (which is inexplicably wrapped by CreateSequence )
• SeqModule.ToList builds a list from this sequence
• listIter@17 instance (your lambda) updated
• ListModule.Iterate moves the list calling lambda for each item

vs forLoop , which is not much different from what you wrote:

 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 is automatically built-in) or list creation. There is a potentially significant difference in the amount of work performed.

EDIT

For curiosity, here are the FSI time slots for list , seq and for 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 seq for reference:

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

Answer 2

Using {1..length} |> Seq.iter certainly faster since you are not creating a complete list in memory.

A little faster than your for loop:

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

Interestingly, the code for the recursive function comes down to the following:

 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 a few more lines that could be deleted, namely:

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