Array/Seq.Average and similar functions do not use foreach

[buybackoff]

Here F# always gets an enumerator and uses it to iterate over a sequence. This throws away compiler optimizations for foreach loop.

In this example calculating average of double array generates the largest amount of allocations via .GetEnumerator(). It was surprising to find it here.

LINQ uses foreach which eliminates allocations. As the linked SO question indicates, F# compiler supports the same foreach optimization as C# compiler and .GetEnumerator() calls should be eliminated where possible in favor of foreach.

For Arrays it is better to use for.. loop because Arrays do not have a struct enumerator as shown here. Only for.. loop like here completely eliminates allocations and this would be nice to have in the core library.

[forki]

I think @dsyme already said that such PRs are welcome.

[buybackoff]

@forki I will be glad to fix this when I learn how to build this repo on my old MacBookAir :) A year ago I couldn't.

BTW, I have tested LINQ .Average() and F# foreach, and LINQ version shows a lot of enumerator allocations, while F#'s foreach loop is equivalent to for i in 0..(len-1) loop. So there is no need for special treatment of arrays and foreach in Seq module will work.

[buybackoff]

Given that I have reverted my pull request regarding foreach in seqs, I want to either close this issue or to keep it open as a question about foreach optimization. Is it possible to make it work with any IEnumarable, or this optimization could only work at JIT level (hopefully sometimes), or one should just forget about it for a general case and work with concrete types that have value type enumerators? I think I have misinterpreted C# compiler behavior just based on SO questions/answers.

[dsyme]

OK, thanks

Just to mention that it may be possible to get some generic doing struct-enumerator iteration using statically resolved type variables, e.g. see below. This technique doesn't easily generalize to map, collect etc. but may be enough for your purposes

module FastIter = 
    let inline iter (f : ^V -> unit) (xs : ^C) : unit when ^E : struct =
        let enum = (^C : (member GetEnumerator : unit -> ^E) (xs))
        while (^E : (member MoveNext : unit -> bool) (enum)) do 
            f (^E : (member get_Current : unit -> ^V) (enum))


let vs = System.Collections.Generic.List<int>( [ 1 .. 10000 ] )

#time "on"

let testA() = 
    // Real: 00:00:06.960, CPU: 00:00:06.937, GC gen0: 1, gen1: 0, gen2: 0
    for i in 0 .. 100000 do
       vs |> FastIter.iter (fun x -> ())

let testB() = 
    // Real: 00:00:09.933, CPU: 00:00:10.000, GC gen0: 4, gen1: 2, gen2: 1
    for i in 0 .. 100000 do
       vs |> Seq.iter (fun x -> ())


let vs2 = seq { 1 .. 4 }
vs2 |> FastIter.iter (fun x -> ()) // can't iterate seq<int> using this since it use no value type enumerator

let vs3 = [| 1 .. 5 |]
vs3 |> FastIter.iter (fun x -> ()) // can't iterate int[] using this Array doesn't have the right methods

let vs4 = System.Collections.Generic.Dictionary<int,int>()
vs4 |> FastIter.iter (fun x -> ()) // can iterate Dictionary<_,_>

let vs5 = System.Collections.Generic.Dictionary<int,int>()
vs5 |> FastIter.iter (fun x -> ()) // can iterate Dictionary<_,_>


let vs6 = System.Collections.Generic.HashSet<int>()
vs6 |> FastIter.iter (fun x -> ()) // can iterate HashSet<_,_>

[buybackoff]

Thanks! That is very interesting. I thought about generics with type constraints that will allow to use constrained call for structs. But both approaches require knowing the type at compile time.