In what situations lists in F# are optimized by the compiler?

Question

In what situations lists in F# are optimized by F# compiler to arrays, to for-loops, while loops, etc. without creating actual list of single linked data?

For example:

[1..1000] |> List.map something

Could be optimized to for-loop without creating actual list. But I don't know if the compiler is doing that actually.

Mapping over lists that are less in size could be optimized with loop-unfolding, etc.

Answer 1

In what situations lists in F# are optimized by F# compiler to arrays, to for-loops, while loops, etc. without creating actual list of single linked data?

Never.

Your later comments are enlightening because you assume that this is a flaw in F#:

...it should be smart enough to do it. Similar to Haskell compiler...

Somewhat true.

...Haskell compiler is doing a lot of such optimizations...

True.

However, this is actually a really bad idea. Specifically, you are pursuing optimizations when what you really want is performance. Haskell offers lots of exotic optimizations but its performance characteristics are actually really bad. Moreover, the properties of Haskell that make these optimizations tractable require massive sacrifices elsewhere:

• Purity makes interoperability much harder so Microsoft killed Haskell.NET and Haskell lives on only with its own incompatible VM.
• The GC in Haskell's VM has been optimized for purely functional code at the expense of mutation.
• Purely functional data structures are typically 10× slower than their imperative equivalents, sometimes asymptotically slower and in some cases there is no known purely functional equivalent.
• Laziness and purity go hand-in-hand ("strict evaluation is a canonical side effect") and laziness not only massively degrades performance but makes it wildly unpredictable.
• The enormous numbers of optimizations added to Haskell in an attempt to combat this poor performance (e.g. strictness analysis) render performance even less predictable.
• Unpredictable cache behaviour makes scalability unpredictable on multicores.

For a trivial example of these optimizations not paying off look no further than the idiomatic 2-line quicksort in Haskell which, despite all of its optimizations, remains thousands of times slower than Sedgewick's quicksort in C. In theory, a sufficiently smart Haskell compiler could optimize such source code into an efficient program. In practice, the world's most sophisticated Haskell compilers cannot even do this for a trivial two-line program much less real software.

The source code to the Haskell programs on The Computer Language Benchmarks Game provide some enlightening examples of just how horrific Haskell code becomes when you optimize it.

I want a programming language to:

• Have a simple method of compilation that keeps performance predictable.
• Make it easy to optimize by hand where optimization is required.
• Have a high ceiling on performance so that I can get close to optimal performance when necessary.

F# satisfies these requirements.

Answer 2

I think "never" is the answer.

Answer 3

It is easy to see if you look at the disassembly - which is quite easy to read

    // method line 4
    .method public static
           default void main@ ()  cil managed
    {
        // Method begins at RVA 0x2078
    .entrypoint
    // Code size 34 (0x22)
    .maxstack 6
    IL_0000:  newobj instance void class Test2/clo@2::'.ctor'()
    IL_0005:  ldc.i4.1
    IL_0006:  ldc.i4.1
    IL_0007:  ldc.i4 1000
    IL_000c:  call class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> class [FSharp.Core]Microsoft.FSharp.Core.Operators/OperatorIntrinsics::RangeInt32(int32, int32, int32)
    IL_0011:  call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0> class [FSharp.Core]Microsoft.FSharp.Core.Operators::CreateSequence<int32> (class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>)
    IL_0016:  call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0> class [FSharp.Core]Microsoft.FSharp.Collections.SeqModule::ToList<int32> (class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>)
    IL_001b:  call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!1> class [FSharp.Core]Microsoft.FSharp.Collections.ListModule::Map<int32, int32> (class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!0,!!1>, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0>)
    IL_0020:  pop
    IL_0021:  ret
    } // end of method $Test2::main@

  } // end of class <StartupCode$test2>.$Test2
}

You can see that at 000c and 0011 the enumerable is created, and then at 0016 the sequence is converted to a list

So in this case the optimisation doesn't happen. In fact it would be very hard for the compiler to make such an optimisation as there could be any number of differences between Seq.Map and List.Map (which is the simplest optimisation as it would avoid the temporary list).