In what situations are compiler optimized lists in F #?

Question

In what situations lists in F # are optimized by the F # compiler for arrays, for-loops, while loop, etc. without creating an actual list of simply connected data?

For instance:

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

It can be optimized for a loop without creating an actual list. But I don't know if the compiler really does it.

The display of smaller lists can be optimized by deploying a loop, etc.

Answer 1

In what situations lists in F # are optimized by the F # compiler for arrays, for-loops, while loop, etc. without creating an actual list of simply connected data?

Never.

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

... he must be smart enough to do this. Like the Haskell compiler ...

Somewhat true.

... the Haskell compiler makes many such optimizations ...

True

However, this is actually a really bad idea. In particular, you are pursuing optimization when what you really want is performance. Haskell offers many exotic optimizations, but its performance characteristics are actually very poor. Moreover, the Haskell properties that make these optimizations acceptable require massive casualties elsewhere:

• Purity makes interaction more complicated, so Microsoft killed Haskell.NET, and Haskell only lives with its own incompatible virtual machine.
• The HCell VM GC is optimized for purely functional code through mutation.
• Purely functional data structures are usually 10 × slower than their imperative equivalents, sometimes asymptotically slower, and in some cases there is no known purely functional equivalent.
• Laziness and cleanliness go hand in hand ("a strict assessment is a canonical side effect"), and laziness not only significantly impairs performance, but also makes it incredibly unpredictable.
• The sheer number of optimizations added to Haskell in an attempt to counter this poor performance (such as stringency analysis) makes performance even less predictable.
• Unpredictable cache behavior makes scalability unpredictable on multi-codes.

For a trivial example of these optimizations that don't pay off, they look no further than the idiomatic 2-line high-speed sorting in Haskell, which, despite all its optimizations, remains thousands of times slower than the Sedgewick quicksort in C. Theoretically, the fairly smart Haskell Compiler can optimize such source code in an efficient program. In practice, the world's most sophisticated Haskell compilers cannot even do this for a trivial two-line program with much less real software.

The source code for Haskell programs on the Benchmarks Game computer game provides some interesting examples of how the terrible Haskell code gets when you optimize it.

I want a programming language:

• Have an easy compilation method that delivers predictable performance.
• Easy to optimize manually when optimization is required.
• You have a high level of performance, so if necessary, you can approach optimal performance.

F # satisfies these requirements.

Answer 2

I think "never" is the answer.

Answer 3

It's easy to see if you're looking at a showdown - which is pretty 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 in 000c and 0011 an enumeration is created, and then in 0016 sequence is converted to a list

So, in this case, optimization is not performed. In fact, it would be very difficult for the compiler to make such an optimization, since there can be any number of differences between Seq.Map and List.Map (which is the simplest optimization, since this will avoid a temporary list).

Answer 4

Although this question was asked some time ago, the current situation is somewhat different.

Many of the functions of a list module actually use an array inside.

For example, the current implementation is pairwise

  [<CompiledName("Pairwise")>] let pairwise (list: 'T list) = let array = List.toArray list if array.Length < 2 then [] else List.init (array.Length-1) (fun i -> array.[i],array.[i+1]) 

also FoldBack (although for lists longer than 4)

  // this version doesn't causes Qaru - it uses a private stack [<CompiledName("FoldBack")>] let foldBack<'T,'State> f (list:'T list) (acc:'State) = let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f) match list with | [] -> acc | [h] -> f.Invoke(h,acc) | [h1;h2] -> f.Invoke(h1,f.Invoke(h2,acc)) | [h1;h2;h3] -> f.Invoke(h1,f.Invoke(h2,f.Invoke(h3,acc))) | [h1;h2;h3;h4] -> f.Invoke(h1,f.Invoke(h2,f.Invoke(h3,f.Invoke(h4,acc)))) | _ -> // It is faster to allocate and iterate an array than to create all those // highly nested stacks. It also means we won't get stack overflows here. let arr = toArray list let arrn = arr.Length foldArraySubRight f arr 0 (arrn - 1) acc 

Here, foldArraySubRight actually uses an iterative loop to process the array.

Other functions with similar optimizations include almost everything called *Back , as well as all sort* and permute .