Added structure-based code and times to the first post. Results are the same as with the sequence-based code.

I would have hoped that since we have simple objects that are consumed as they are produced, there would be no allocations, only register operations. For example, it's my assumption, doing the same stuff with a sequence of ints could be faster than using array as temporary. I was just looking into a way to use sequences as using global arrays is ugly. Unfortunately this cannot be done by generating two sequences - one for first element, another - for the second - of the tuple.

To make the comparison more fair, I changed the array sequence generator to:
let genseq2 k =
for i = 0 to k-1 do
let p = (i, i+1)
a.[i] <- (fst p)
b.[i] <- (snd p) ;;
and ran without optimizations. So apparently now the object is created in all cases. Still this code runs 5 times faster than the sequence-based code.

Seqs are much slower than arrays, as you noticed yourself. Everytime you iterate over a seq an enumerator needs to be created, and then you need two interface calls (MoveNext + Current) for every single item you iterate over. Compare that with a simple indirect memory fetch for an array. I haven't looked at your sample in detail, but I'd guess that the JIT doesn't eliminate the bounds checks. So you could make the array version even faster by coding it such that the JIT recognizes the array iteration and eliminates the bounds checking (for at least one of the arrays), though that is currently difficult to do in F#.

As Brian notes below, the performance of your seq implementation could be significantly improved. However, I'd still expect that a simple iteration over a seq is slower by at least a factor of 10 relative to an optimized array iteration. Hence, if you have a "tight loop" with a relatively small loop body and you need optimal performance, you should prefer an array.

I would add a little to the above in that the reason that the array code is faster is that it is using direct coding and not functional coding, thus completely avoiding parameter passing and stack manipulations necessary for the indirect method table calls needed for MoveNext() and Current. Once you realize that the extra time is being used by the enumeration, there is no point to writing the values out to arrays and then reading them back as you may as well combine the operations into one pass as follows, which is slightly over twice as fast as the direct array technique:

1
2
3
4
5
6

let testseq n =
  let mutable maximum = 0
  for i = 0 to n do
    for j = 0 to 1000 do
      maximum <- max maximum (max j (j + 1))
  maximum

Basically, the answer to the subject line is that sequences aren't suitable for tight loops as compared to using imperative code due to the overheads of the IEnumerator interface, just as Stephan said. The current F# core library version 2.0.0.0 implementation of sequences is very inefficient due to being written too general and internally doing even more calling of internal methods per iteration loop. If you really want to use sequences, you can make them run a tight loop about six times as fast as the built in range sequence by wrapping your iteration function in your own enumeration as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

//enum used internally
type internal State =
  |Reset = 0
  |Running = 1
  |Finished = 2

//the sequence function
let inline doit i = i

//The enclosing implementation of the IEnumerator interface
type sequ(k) =
  let mutable i = 0
  let mutable st = State.Reset
  interface IEnumerator<int*int> with
    member this.Dispose() = ()
    member this.Current with get() = doit i
  interface IEnumerator with
    member this.Reset() =
      i <- 0

      st <- State.Reset
    member this.MoveNext() =
      if st = State.Running then
        i <- i + 1
        if i >= k then
          st <- State.Finished
        true
      elif st = State.Finished then false
      else
        st <- State.Running
        true
    member this.Current with get() = doit i :> obj

//implemented using an object expression
let genseq k =
  { new IEnumerable<int*int> with
      member this.GetEnumerator() = (new sequ(k) :> IEnumerator<int*int>)
    interface IEnumerable with
      member this.GetEnumerator() = ((new sequ(k)) :> IEnumerator)
  }

The above code is very similar to built-in library's Seq.init function but is still many times faster due to the custom optimization of not doing any extra calls. This is still about four times slower than the ultimate imperative coding loop, which is just the problem with functional programming unless the compiler optimizes away the function calls and makes everything inline. The extra indirect calls through the object's method table still eat up about 21 extra clock cycles. C#, which is a little better at optimizing than the current CTP version of F#, reduces the time to run a sequence as implemented above in F# by a little, but the functional call still takes about four times longer than doing something similar not using the enumeration coding.

The Seq.unfold is still many times slower than using the above code.

Using sequences to implement functional code brings up the usual argument of "Why use functional programming?" in that functional programming will always trade off the ultimate in speed for time critical tight loops for elegance of expression and ease of prototyping.

EDIT ADD:

Even the F# version 2.0 CTP released with Visual Studio 2010 still is not very efficient as to running tight loops, primarily due to inefficiencies in the FSharp.Core runtime library. For instance, for reasonably fast loops, F# should be able to run an integer sequence such as {0 .. 1000000000} (one billion) in a reasonable amount of time other than for the IEnumerator overheads of calling the MoveNext() method and (possibly, if the results are required), the Current property. Minimum time including the overheads would be something like 30 clock times per loop, so about 10 seconds on a modern processor for a "do nothing" loop which just say adds them all together. It takes much longer than that, and a little investigation with the Red Gate Reflector program reveals why:

The FSharp.Core library implements the integer IEnumerator sequence by calling the following virtual property from the necessary MoveNext() method as a *virtual* method (calling virtual methods takes longer than calling regular methods), which in turn makes multiple virtual method calls to the Before and Equal virtual methods in order to do it's work. The implementation of Current also makes a virtual call to Result in order to do it's work. The following is in C# format as Reflector does not yet support F# code forms:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

public override bool CanStep


{


  get


  {


    TState z = this.z;


    TState local2 = this.Step(this.z);


    if (!this.Before(local2, z))


    {


      if (this.Equal(local2, z))


      {


        return false;


      }


      if (this.Before(z, local2) && this.Before(local2, this.m))


      {


        this.z = local2;


        return true;


      }


      if (this.Equal(local2, this.m))


      {


        this.z = local2;


        return true;


      }


    }


    return false;


  }


}

These extra virtual calls mean that the minimum tight loop that can be run with an integer sequence takes about three times longer than it would without all the (virtual) method calls.

Even functions that have sequences as arguments and return sequences as would be used in "chained" calculations such as Seq.map or Seq.filter use some virtual calls internally in order to do their work.

All of these functions are written for general use without respect to the amount of extra overhead time they may use, which makes F# even more unsuitable for using for tight iterative calculations using the immutable forms of expression even more than would be just to use the IEnumerator inteface directly. This means that the only ways to write these types of loops is to use imperative mutable coding and avoiding the IEnumerable interface implied by "for _ in _ do" loops (fastest) or wrapping the functions in our own IEnumerator interface which does not make virtual calls and which minimizes the number of levels of method calls as in my previous post, but which still takes about three to four times longer than the mutable imperative form.

using seq { for _ to _ do yield ... } forms of sequence should be faster as it implies wrapping your own sequence, but is incredibly slower due to making even more levels of indirect virtual calls.

As an aside, there are also compiler quirks, in that it is recommended that one form sequences with a leading "Seq" as in "Seq { 0 .. 2 .. 25 }" but by using the "seq" there is an additional unnecessary CreateSequence call to the library, as the Range is already a sequence. This Makseq call should be recognized as unnecessary an eliminated by the compiler, not that it make s much difference to speed. Also the shortcut form of "seq { for i in { 0 .. 10 } -> i }" is accepted by the compiler but not "seq { for i = 0 to 10 -> i }" which must be written as "seq { for i = 0 to 10 do yield i }". Signs of unpolished work, and therefore presumably the reason the product still has "CTP" status.

In short, until the first of the following two functions is no slower than about three times than the second instead of the current about ten times slower, the built in IEnumerator's of F# are particularily unsuitable for writing tight loops, in particular when using the immutable forms of enumeration as wrapped in the FSharp.Core runtime library:

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

let test1 = { 0 .. 1000000000 } |> Seq.length

let test2 =


  let mutable count = 0


  for i = 0 to 1000000000 do


    count <- count + 1


  count