New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
buybackoff opened this Issue Jan 20, 2016 · 5 comments

Comments

Projects
None yet
3 participants
@buybackoff
Contributor

buybackoff commented Jan 20, 2016

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

This comment has been minimized.

Contributor

forki commented Jan 20, 2016

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

@buybackoff

This comment has been minimized.

Contributor

buybackoff commented Jan 20, 2016

@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

This comment has been minimized.

Contributor

buybackoff commented Jan 28, 2016

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

This comment has been minimized.

Contributor

dsyme commented Jan 28, 2016

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

This comment has been minimized.

Contributor

buybackoff commented Jan 30, 2016

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.

@buybackoff buybackoff closed this Jan 30, 2016

@buybackoff buybackoff referenced this issue Dec 19, 2016

Closed

Migrate from F# to C# when possible #68

2 of 4 tasks complete
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment