A few comments.

The loops firstly using "j" to cull the composite numbers from the "nonprime" array up to its maximum limit and secondly

the final "i" loop scanning the "nonprimes" array for the remaining primes are where all the time is spent and those are optimized by the C# compiler to

eliminate the range check when the correct form of specification is used. This was an early optimization which has been documented for C#.

Thus,

they **do** in fact differ in that if one writes the loops as I did in my C# equivalent with a "lim" limit set to exactly the "buf.Length", the bounds

check is removed. However, for either of the imperative loop forms in F# imperative code, the bounds check is still there. You can find a lot of this

for yourself by using the Red Gate Reflector program or disassembling the resulting code.

I may be misunderstanding what you are saying, but the C# compiler *can't* remove bounds checks (which are inserted by the CLR JIT compiler), so

looking at the IL won't help you determine when they are present. It is true that loops going up to the last element in an array will have the

bounds check removed (or rather, not inserted) by the JIT compiler, but this also happens for F# loops of the form

1
2
3

for i in 0 .. 

myArr.Length - 1 do ...

. Unfortunately, the code generated for loops of the form

1
2
3

for i in 0 .. step .. 

myArr.Length - 1 do ...

is significantly worse.

You are correct; I misspoke - it's the JIT compiler that (sometimes) adds the array bounds checks, and I guess I determined that from disassembly of the

JIT output code and not from the IL. What is true is that the imperative F# mutable while .. do loop isn't as efficient as the C# forms for doing the

same thing by about 25%. The second "for .. in" form you state is actually using the F# runtime library's version of a sequence, in this case a Range

object, and thus has a terrible relative performance, which is my gripe.

A few comments.

This isn't the biggest problem with the current version of F#, as if one is trying to write very much tight imperative

code using F# they have probably picked the wrong language; F# is intended for the functional non-imperative style.

I don't want to speak for the language designers, but I don't think that this is true. I believe that F# is intended to be a multi-

paradigm language, and there is nothing wrong with using an imperitave style within F# when performance requires it.

You are correct that there is some capability in F# to write imperative code but it is quite limited in flexibility: the basic for loop only steps up

or down by incrementing and decrementing, no continue, no break, etcetera - at least as yet. So yes, while one can try to use an imperative style where

one must, the current language specification doesn't make it easy. That wouldn't matter so much if the built in implementations of sequences, etcetera,

were made more efficient.

A few comments.

Once one is using iterators by preference for clarity of style, the extra overhead of the range checks becomes relatively

negligible compared to the overhead of using the IEnumerator interface, even when it is implemented as efficiently as C# does.

As I have shown in my latest edits for my post to which you refer here, if the standard run time library objects intended to supply the IEnumerator

interface implementations were written more efficiently, F# would be just as fast as C# for anything other than tight imperative loops. Even for most

imperative loops, the overhead of range checking won't more than double the time per loop for extremely tight loops.

I agree that it's unfortunate that the F# IEnumerator implementation isn't more performant; perhaps that's something that could be addressed in a

future version of the language. However, I think that your other point is quite relevant, too: if performance is critical, then use a different

collection type such as an array or mutable list. For instance, getting rid of the seq {} block in the code in this

thread in favor of a mutable list yields a huge speedup on my machine:

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

let primes max =
  let nonprimes = Array.zeroCreate((max - 3)/2 + 1)
  let culllim = int ((sqrt (double max) - 3.) / 2.)
  

for i = 0 to culllim do
    if not nonprimes.[ i] then
      let prime = i + i + 

3
      (* for j in (prime * prime - 3) / 2 .. prime .. nonprimes.Length 

do
           nonprimes.[j] <- true *)
      let mutable j = (prime 

* prime - 3) / 2
      while j < nonprimes.Length do
        nonprimes.[j] <- 

true
        j <- j + prime
  let mutable ct = 0
  let results = ResizeArray()
  for i 

in 0 .. nonprimes.Length - 1 do
    if not nonprimes.[ i] then results.Add(i + i + 3)
  results

Yes, this poor implementation of the sequence objects is one of the more serious problems for the current implementation of F#. I have submitted this

improvement as a suggestion to Microsoft, to which they replied "We have an open suggestion for improving the performance of some of the functions in

the Seq module. Your report will increase the priority of this work for our next release. We are now tracking this as 843498 in our database.";

however, that was over eight months ago and so far there have been no really new releases addressing this issue.

As you show in your code snippet above and as I show in my self-implementation of IEnumerable/IEnumerator, **any** other implementations that avoid

using the Core built-in sequences are much faster. The advantage of redefining Range sequence objects for oneself as compared to using most other types

of collection objects is that sequences don't have any memory overhead and don't require that one generate the collection and then scan it (again) to

output the results.

In order to exactly parallel the C# IEnumerable implementation, we would really like to use a sequence expression to behave the same as the C# code loop

containing the "yield return" statement as follows:

1

  seq { for i = 0 to LSTNDX do if not nonprimes.[�i] then yield i + i + 3 }

Unfortunately, the performance of this with the current version CTP 2.0 of F# absolutely stinks!!!

We would be perfectly happy to use the following filtered range statement if performance were reasonable:

1

  seq { 0 .. LSTNDX } |> Seq.filter (fun i -> not nonprimes.[�i]) |> Seq.map (fun i -> i + i + 3)

But the performance of that stinks almost as bad!! Again, this is partly due to the lousy implementation of sequences and sequence support in the

current version of F# but also due to that the sequence needs to be called for every possible index value and not just for the pre-filtered prime

indexes as con be done with the "yield return" form or with the first form above if the same code were generated.

If we want performance and style, we either have to sacrifice using more memory for an existing real DotNet collection as you have done or for more

efficiency in both computational speed and memory requirements to implement our own sequences. In the following code, I use nested object expressions

to implement an IEnumerable/IEnumerator pair that has the same result as the "yield return" sequence producing loop of the C# code with about the same

speed:

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

type internal State =


  |Reset = 0


  |Running = 1


  |Finished = 2

let GetOddPrimes max =


  let LSTNDX = (max - 3) / 2


  let LSTCULNDX = (int (sqrt (double max)) - 3) / 2


  let nonprimes = Array.zeroCreate (LSTNDX + 1)


  //create a yield sequence based on the nonprimes array using nested object expressions


  let yieldseq =


    let seqienum =


      let i = ref 0


      let st = ref State.Reset


      { new IEnumerator<int> with


          member this.Dispose() = ()


          member this.Current with get() = (!i <<< 1) + 3


        interface IEnumerator with


          member this.Reset() = i := 0; st := State.Reset


          member this.MoveNext() =


            if !st = State.Running then i := !i + 1


            if !st <>  State.Finished then st := State.Running


            while !i <= LSTNDX && nonprimes.[&#0;!i] do i := !i + 1


            if !i > LSTNDX then st := State.Finished; false


            else true


          member this.Current with get() = (!i <<< 1) + 3 :> obj


      }


    { new IEnumerable<int> with


        member this.GetEnumerator() = seqienum


      interface IEnumerable with


        member this.GetEnumerator() = seqienum :> IEnumerator


    }


  for i = 0 to LSTCULNDX do


    if not nonprimes.[&#0;i] then


      let mutable j = (((i + 3) * i) <<< 1) + 3


      let p = i + i + 3


      while j < nonprimes.Length do


        nonprimes.[&#0;j] <- true


        j <- j + p


// Equivalent to the C# IEnumerable solution, but performance absolutely stinks at 45 times slower!!!


//  seq { for i = 0 to LSTNDX do if not nonprimes.[&#0;i] then yield i + i + 3 }


// The way one might also like to do it, but performance stinks almost as bad at about 20 times slower!!


//  seq { 0 .. LSTNDX } |> Seq.filter (fun i -> not nonprimes.[&#0;i]) |> Seq.map (fun i -> i + i + 3)


  yieldseq.GetEnumerator().Reset(); // not really required if only running once


  yieldseq // quite high performance from the implementing object expressions

Note that if one wants to call this repetitively, one requires the "...Reset" before enumeration since only one enumerator object is created and reused

as necessary. The above code is just slightly about the same speed as the equivalent C# code, although that is still approximately twice as slow as the

imperative approach due to iterator method call overheads. Note that the current (2010) C# compiler is very efficient at generating iterators using the

yield statement, which should be equivalent to the seq expression with the yield keyword in F# if implemented correctly. As it is, the F# version is

approximately 45 times slower than the iterator object created automatically by the C# compiler or that I have created by hand here!!!

Also note that although the F# language designer people recommend preceding a sequence expression with the "seq" keyword as above to be consistent with

other forms of computational expressions (enforced for the "yield" type expression for sequences), the current compiler generates an additional MakeSeq

call that adds a redundant level of indirection in calling the resulting sequence and slightly slows the implementation even further. Upon further

thinking about this, I realize that the seq expression is a modified special version of computational expressions, but that this botched implementation

does even more stacked virtual method calls than just computational expressions and is thus completely unsuitable for use with sequences for fast

iterative loops.

No one would have any problems with the performance of F# if the run time library and compiler were optimized to run at the speed (or slightly better

with slight more loop optimizations) of the above code as they should be able to do.

[EDIT-ADD:] Analysis of why these implementations are so slow:

A/ For the ordinary sequence processing chain as per:

1

  seq { 0 .. LSTNDX } |> Seq.filter (fun i -> not nonprimes.[�i]) |> Seq.map (fun i -> i + i + 3)

Other than adding one extra unnecessary level of indirection as mentioned above for the first "seq" (which isn't currently required), this

implementation suffers from two time-consuming problems, as follows:

1. The inefficient built-in implementation of the range { 0 .. LSTNDX }: this can be replaced with a custom implementation of an

IEnumerable/IEnumerator object for a time saving of almost 300% from about 35 times slower than an imperative loop doing the same to about 10 times

slower.

2. The rest of the extra time is spent in manipulating the call stack for the levels of indirection required to call the nested levels of functions for

the Seq.filter and especially Seq.map, which takes about 75% of the remaining extra time.

B/ For the sequence expression as per:

1

  seq { for i = 0 to LSTNDX do if not nonprimes.[�i] then yield i + i + 3 }

This is converted by the F# compiler to a "computational expression" equivalent of the following:

1

  { 0 .. LSTNDX } |> Seq.collect (fun i -> if not nonprimes.[�i] then Seq.singleton (i + i + 3) else Seq.empty)

Which is so very slow for the following reasons:

1. Due to the inefficient implementation of the { 0 .. LSTNDX } range sequence as per the above, with some alleviation of the performance burden by a

custom version. However, the following takes the majority of the time.

2. Due to the extremely long extra processing for the Seq.collect of multiple singleton sequences generated by the test condition as implied by the use

of the F# "yield" keyword, which is extremely inefficient as compared to using the C# "yield return" statement that just causes the C# compiler to

insert the continuation code directly into the MoveNext() method of the resulting iterator implementing the IEnumerable/IEnumerator pair. Just this

Seq.collect processing takes approximately 20 times the time required to do this imperatively. In order to have competitive preformance to the C#

"yield return" statement, the F# compiler would need to automatically emit equivalent code, which saves time on several fronts for this type of

application in that the condition branching logic is inside the MoveNext() method, meaning that there are less calls to the method which greatly reduces

the method calling overhead

Conclusion: if one requires C# type iterator (sequences in F#) performance, then one avoids the yield keyword and does a custom IEnumerable/IEnumerator

object implementation. For the ultimate in speed in tight loops, one avoids functional style programming altogether in favour of the inperative style.

Thanks to all who responded to this thread. The speed and quality of support on HubFS has proved excellent. You all get a metion in Martin's writeup here [link:blogs.msdn.com]