I remain unconvinced by geneverov's reply: unless I am mistaken, it still appears that idiomatic F# could benefit quite a bit by applying techniques from the Stream Fusion paper.

Let's look at the native x86 code generated for the following, rewritten from the example above so that it compiles on F# CTP (1.9.6.2).

1
2
3
4
5
6
7
8
9
10
11
12

#light

let test (xs : int seq) =
    System.Diagnostics.Debugger.Break()
    xs
    |> Seq.map (fun x -> x * 2)
    |> Seq.filter (fun x -> x < 100)
    |> Seq.reduce (+)

let v = test ( seq {for i in 1..6 do yield i} )
printfn "%i" v

Stepping through the optomized code shows the following disassembly for the map call:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

let test (xs : int seq) =
    System.Diagnostics.Debugger.Break()
    xs
    |> Seq.map (fun x -> x * 2)
00000000  push        esi  
00000001  push        eax  
00000002  mov         dword ptr [esp],ecx 
00000005  mov         esi,edx 
00000007  cmp         dword ptr ds:[000D2E08h],0 
0000000e  je          00000015 
00000010  call        79D47B47 
>00000015  nop              
00000016  mov         eax,esi 
00000018  add         eax,eax 
0000001a  pop         ecx  
0000001b  pop         esi  
0000001c  ret 

Stepping again shows the following code for the filter:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

let test (xs : int seq) =
    System.Diagnostics.Debugger.Break()
    xs
    |> Seq.map (fun x -> x * 2)
    |> Seq.filter (fun x -> x < 100)
00000000  push        esi  
00000001  push        eax  
00000002  mov         dword ptr [esp],ecx 
00000005  mov         esi,edx 
00000007  cmp         dword ptr ds:[000D2E08h],0 
0000000e  je          00000015 
00000010  call        79D47B17 
>00000015  nop              
00000016  cmp         esi,64h 
00000019  setl        al   
0000001c  movzx       eax,al 
0000001f  pop         ecx  
00000020  pop         esi  
00000021  ret              

And, finally, the reduce:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

let test (xs : int seq) =
    System.Diagnostics.Debugger.Break()
    xs
    |> Seq.map (fun x -> x * 2)
    |> Seq.filter (fun x -> x < 100)
    |> Seq.reduce (+)
00000000  push        esi  
00000001  push        eax  
00000002  mov         dword ptr [esp],ecx 
00000005  mov         esi,edx 
00000007  cmp         dword ptr ds:[000D2E08h],0 
0000000e  je          00000015 
00000010  call        79D47A8F 
00000015  nop              
00000016  mov         eax,dword ptr [esp+0Ch] 
0000001a  add         eax,esi 
0000001c  pop         ecx  
0000001d  pop         esi  
0000001e  ret         4    

This appears to clearly depict overhead for each independent stage in the pipeline. I think the CLR does some magic, by pushing most of the sequence on the stack up front, then unwinding the stack as it calculates each stage and leaving some intermediate values in registers. None-the-less, unnecessary overhead (compared to ideal native code) does clearly exist here.

IMHO, the core concept from the Stream Fusion paper is to transform lists into streams (similar to sequences), yes, but then to <i>also <i>combine (fuse) all the pipeline stages into a <i>single <i>function call that is optomized as a whole. This is possible due to the way each stream "element" is normalized into essentially an "element option", as in Some(element) or None, allowing reduction of filtering down to an if guard. By fusing the pipeline, it should be possible to eliminate the setup for two out of the three calls on each loop iteration, including a number of pushes, pops, and calls. I suspect that inlining and standard optomization could further improve the pipeline performance. Finally, while I did not directly witness superflous objects getting created in this simple example, given the fact that each pipeline stage appeared independent leads me to suspect that there are optomizations and attendent performance gains to be had here, too, for a Stream Fusing compiler. -- Jay

The paper presents a technique for eliminating intermediate results in a composition of list functions by transforming list functions into stream functions. For the most part, streams from this paper are seq/IEnumerables in F#. Since F# programmers commonly and directly program in terms of streams, having the compiler transform and optimize list code in terms of streams is a little extravagant for the complexity it adds.

Even if your underlying data structure is an array or list you can still process it as a stream in F# through sub-typing, hence avoiding intermediate results.

1
2
3
4
5
6

let test seq  =
    seq
    |> Seq.map (fun x -> x * 2)
    |> Seq.filter (fun x -> x < 100)
    |> Seq.fold (+) 0
test [| 1..6 |]

The compiler optimizations that make this paper work are not primarily user-defined rewrite rules, but rather standard general-purpose optimizations performed internally by GHC. It is not really feasible for FSC to perform many of these optimizations because it is not a pure language.

IEnumerable's MoveNext and Current are analogous to the stepper functions in this paper. The purpose of Skip is to make the stepper functions non-recursive to enable inlining optimizations. For IEnumerable, MoveNext can be recurisve because we can't optimize it in the same way anyway. Additionally the combination of MoveNext and Current avoid the need to construct an intermediate Step value.

So it's a good idea for Haskell, but not so much for F#. Essentially it's the same old trade-off between imperative and functional. Functional makes code easier to analyse for optimizations, imperative means you can just make the code faster yourself.