F# Performance Tips and Tricks

Using tail-recursion for efficient iteration

Coming from imperative languages many developers wonder how to write a for-loop that exits early as F# doesn’t support break, continue or return. The answer in F# is to use tail-recursion which is a flexible and idiomatic way to iterate while still providing excellent performance.

Say we want to implement tryFind for List. If F# supported return we would write tryFind a bit like this:

let tryFind predicate vs =
  for v in vs do
    if predicate v then
      return Some v
  None

This doesn’t work in F#. Instead we write the function using tail-recursion:

let tryFind predicate vs =
  let rec loop = function
    | v::vs -> if predicate v then 
                   Some v 
               else 
                   loop vs
    | _ -> None
  loop vs

Tail-recursion is performant in F# because when the F# compiler detects that a function is tail-recursive it rewrites the recursion into an efficient while-loop. Using ILSpy we can see that this is true for our function loop:

internal static FSharpOption<a> loop@3-10<a>(FSharpFunc<a, bool> predicate, FSharpList<a> _arg1)
{
  while (_arg1.TailOrNull != null)
  {
    FSharpList<a> fSharpList = _arg1;
    FSharpList<a> vs = fSharpList.TailOrNull;
    a v = fSharpList.HeadOrDefault;
    if (predicate.Invoke(v))
    {
      return FSharpOption<a>.Some(v);
    }
    FSharpFunc<a, bool> arg_2D_0 = predicate;
    _arg1 = vs;
    predicate = arg_2D_0;
  }
  return null;
}

Apart from some unnecessary assignments (which hopefully the JIT-er eliminates) this is essentially an efficient loop.

In addition, tail-recursion is idiomatic for F# as it allows us to avoid mutable state. Consider a sum function that sums all elements in a List. An obvious first try would be this:

let sum vs =
  let mutable s = LanguagePrimitives.GenericZero
  for v in vs do
    s <- s + v
  s

If we rewrite the loop into tail-recursion we can avoid the mutable state:

let sum vs =
  let rec loop s = function
    | v::vs -> loop (s + v) vs
    | _ -> s
  loop LanguagePrimitives.GenericZero vs

For efficiency the F# compiler transforms this into a while-loop that uses mutable state.

Measure and Verify your performance assumptions

This example is written with F# in mind but the ideas are applicable in all environments

The first rule when optimizing for performance is to not to rely assumption; always Measure and Verify your assumptions.

As we are not writing machine code directly it is hard to predict how the compiler and JIT:er transform your program to machine code. That’s why we need to Measure the execution time to see that we get the performance improvement we expect and Verify that the actual program doesn’t contain any hidden overhead.

Verification is the quite simple process that involves reverse engineering the executable using for example tools like ILSpy. The JIT:er complicates Verification in that seeing the actual machine code is tricky but doable. However, usually examining the IL-code gives the big gains.

The harder problem is Measuring; harder because it’s tricky to setup realistic situations that allows to measure improvements in code. Still Measuring is invaluable.

Analyzing simple F# functions

Let’s examine some simple F# functions that accumulates all integers in 1..n written in various different ways. As the range is a simple Arithmetic Series the result can be computed directly but for the purpose of this example we iterate over the range.

First we define some useful functions for measuring the time a function takes:

// now () returns current time in milliseconds since start
let now : unit -> int64 =
  let sw = System.Diagnostics.Stopwatch ()
  sw.Start ()
  fun () -> sw.ElapsedMilliseconds

// time estimates the time 'action' repeated a number of times
let time repeat action : int64*'T =
  let v = action ()  // Warm-up and compute value

  let b = now ()
  for i = 1 to repeat do
    action () |> ignore
  let e = now ()

  e - b, v

time runs an action repeatedly we need to run the tests for a few hundred milliseconds to reduce variance.

Then we define a few functions that accumulates all integers in 1..n in different ways.

// Accumulates all integers 1..n using 'List'
let accumulateUsingList n =
  List.init (n + 1) id
  |> List.sum

// Accumulates all integers 1..n using 'Seq'
let accumulateUsingSeq n =
  Seq.init (n + 1) id
  |> Seq.sum

// Accumulates all integers 1..n using 'for-expression'
let accumulateUsingFor n =
  let mutable sum = 0
  for i = 1 to n do
    sum <- sum + i
  sum

// Accumulates all integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach n =
  let mutable sum = 0
  for i in 1..n do
    sum <- sum + i
  sum

// Accumulates all integers 1..n using 'foreach-expression' over list range
let accumulateUsingForEachOverList n =
  let mutable sum = 0
  for i in [1..n] do
    sum <- sum + i
  sum

// Accumulates every second integer 1..n using 'foreach-expression' over range
let accumulateUsingForEachStep2 n =
  let mutable sum = 0
  for i in 1..2..n do
    sum <- sum + i
  sum

// Accumulates all 64 bit integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach64 n =
  let mutable sum = 0L
  for i in 1L..int64 n do
    sum <- sum + i
  sum |> int

// Accumulates all integers n..1 using 'for-expression' in reverse order
let accumulateUsingReverseFor n =
  let mutable sum = 0
  for i = n downto 1 do
    sum <- sum + i
  sum

// Accumulates all 64 integers n..1 using 'tail-recursion' in reverse order
let accumulateUsingReverseTailRecursion n =
  let rec loop sum i =
    if i > 0 then
      loop (sum + i) (i - 1)
    else
      sum
  loop 0 n

We assume the result to be the same (except for one of the functions that uses increment of 2) but is there difference in performance. To Measure this the following function is defined:

let testRun (path : string) =
  use testResult = new System.IO.StreamWriter (path)
  let write   (l : string)  = testResult.WriteLine l
  let writef  fmt           = FSharp.Core.Printf.kprintf write fmt

  write "Name\tTotal\tOuter\tInner\tCC0\tCC1\tCC2\tTime\tResult"

  // total is the total number of iterations being executed
  let total   = 10000000
  // outers let us variate the relation between the inner and outer loop
  //  this is often useful when the algorithm allocates different amount of memory
  //  depending on the input size. This can affect cache locality
  let outers  = [| 1000; 10000; 100000 |]
  for outer in outers do
    let inner = total / outer

    // multiplier is used to increase resolution of certain tests that are significantly
    //  faster than the slower ones

    let testCases =
      [|
    //   Name of test                         multiplier    action
        "List"                              , 1           , accumulateUsingList
        "Seq"                               , 1           , accumulateUsingSeq
        "for-expression"                    , 100         , accumulateUsingFor
        "foreach-expression"                , 100         , accumulateUsingForEach
        "foreach-expression over List"      , 1           , accumulateUsingForEachOverList
        "foreach-expression increment of 2" , 1           , accumulateUsingForEachStep2
        "foreach-expression over 64 bit"    , 1           , accumulateUsingForEach64
        "reverse for-expression"            , 100         , accumulateUsingReverseFor
        "reverse tail-recursion"            , 100         , accumulateUsingReverseTailRecursion
      |]
    for name, multiplier, a in testCases do
      System.GC.Collect (2, System.GCCollectionMode.Forced, true)
      let cc g = System.GC.CollectionCount g

      printfn "Accumulate using %s with outer=%d and inner=%d ..." name outer inner

      // Collect collection counters before test run
      let pcc0, pcc1, pcc2 = cc 0, cc 1, cc 2

      let ms, result       = time (outer*multiplier) (fun () -> a inner)
      let ms               = (float ms / float multiplier)

      // Collect collection counters after test run
      let acc0, acc1, acc2 = cc 0, cc 1, cc 2
      let cc0, cc1, cc2    = acc0 - pcc0, acc1 - pcc1, acc1 - pcc1
      printfn "  ... took: %f ms, GC collection count %d,%d,%d and produced %A" ms cc0 cc1 cc2 result

      writef "%s\t%d\t%d\t%d\t%d\t%d\t%d\t%f\t%d" name total outer inner cc0 cc1 cc2 ms result

The test result while running on .NET 4.5.2 x64:

We see dramatic difference and some of the results are unexpectedly bad.

Let’s look at the bad cases:

List

// Accumulates all integers 1..n using 'List'
let accumulateUsingList n =
  List.init (n + 1) id
  |> List.sum

What happens here is a full list containing all integers 1..n is created and reduced using a sum. This should be more expensive than just iterating and accumulating over the range, it seems about ~42x slower than the for loop.

In addition, we can see that the GC ran about 100x during the test run because the code allocated a lot of objects. This also costs CPU.

Seq

// Accumulates all integers 1..n using 'Seq'
let accumulateUsingSeq n =
  Seq.init (n + 1) id
  |> Seq.sum

The Seq version doesn’t allocate a full List so it’s a bit suprising that this ~270x slower than the for loop. In addition, we see that the GC has executed 661x.

Seq is inefficient when the amount of work per item is very small (in this case aggregating two integers).

The point is not to never use Seq. The point is to Measure.

(manofstick edit: Seq.init is the culprit of this severe performance issue. It is much more efficent to use the expression { 0 .. n } instead of Seq.init (n+1) id. This will become much more efficient still when this PR is merged and released. Even after the release though, the original Seq.init ... |> Seq.sum will still be slow, but somewhat counter-intuitively, Seq.init ... |> Seq.map id |> Seq.sum will be quite fast. This was to maintain backward compatibility with Seq.inits implementation, which doesn’t calculate Current initially, but rather wraps them in a Lazy object - although this too should perform a little better due to this PR. Note to editor: sorry this is kind of rambling notes, but I don’t want people to be put off Seq when improvement is just around the corner… When that times does come it would be good to update the charts that are on this page.)

foreach-expression over List

// Accumulates all integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach n =
  let mutable sum = 0
  for i in 1..n do
    sum <- sum + i
  sum

// Accumulates all integers 1..n using 'foreach-expression' over list range
let accumulateUsingForEachOverList n =
  let mutable sum = 0
  for i in [1..n] do
    sum <- sum + i
  sum

The difference between these two function is very subtle but the performance difference is not, roughly ~76x. Why? Let’s reverse engineer the bad code:

public static int accumulateUsingForEach(int n)
{
  int sum = 0;
  int i = 1;
  if (n >= i)
  {
    do
    {
      sum += i;
      i++;
    }
    while (i != n + 1);
  }
  return sum;
}

public static int accumulateUsingForEachOverList(int n)
{
  int sum = 0;
  FSharpList<int> fSharpList = SeqModule.ToList<int>(Operators.CreateSequence<int>(Operators.OperatorIntrinsics.RangeInt32(1, 1, n)));
  for (FSharpList<int> tailOrNull = fSharpList.TailOrNull; tailOrNull != null; tailOrNull = fSharpList.TailOrNull)
  {
    int i = fSharpList.HeadOrDefault;
    sum += i;
    fSharpList = tailOrNull;
  }
  return sum;
}

accumulateUsingForEach is implemented as an efficient while loop but for i in [1..n] is converted into:

FSharpList<int> fSharpList =
  SeqModule.ToList<int>(
    Operators.CreateSequence<int>(
      Operators.OperatorIntrinsics.RangeInt32(1, 1, n)));

This means first we create a Seq over 1..n and finally calls ToList.

Expensive.

foreach-expression increment of 2

// Accumulates all integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach n =
  let mutable sum = 0
  for i in 1..n do
    sum <- sum + i
  sum

// Accumulates every second integer 1..n using 'foreach-expression' over range
let accumulateUsingForEachStep2 n =
  let mutable sum = 0
  for i in 1..2..n do
    sum <- sum + i
  sum

Once again the difference between these two functions are subtle but the performance difference is brutal: ~25x

Once again let’s run ILSpy:

public static int accumulateUsingForEachStep2(int n)
{
  int sum = 0;
  IEnumerable<int> enumerable = Operators.OperatorIntrinsics.RangeInt32(1, 2, n);
  foreach (int i in enumerable)
  {
    sum += i;
  }
  return sum;
}

A Seq is created over 1..2..n and then we iterate over Seq using the enumerator.

We were expecting F# to create something like this:

public static int accumulateUsingForEachStep2(int n)
{
  int sum = 0;
  for (int i = 1; i < n; i += 2)
  {
    sum += i;
  }
  return sum;
}

However, F# compiler only supports efficient for loops over int32 ranges that increment by one. For all other cases it falls back on Operators.OperatorIntrinsics.RangeInt32. Which will explain the next suprising result

foreach-expression over 64 bit

// Accumulates all 64 bit integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach64 n =
  let mutable sum = 0L
  for i in 1L..int64 n do
    sum <- sum + i
  sum |> int

This performs ~47x slower than the for loop, the only difference is that we iterate over 64 bit integers. ILSpy shows us why:

public static int accumulateUsingForEach64(int n)
{
  long sum = 0L;
  IEnumerable<long> enumerable = Operators.OperatorIntrinsics.RangeInt64(1L, 1L, (long)n);
  foreach (long i in enumerable)
  {
    sum += i;
  }
  return (int)sum;
}

F# only supports efficient for loops for int32 numbers it has to use the fallback Operators.OperatorIntrinsics.RangeInt64.

The other cases performs roughly similar:

The reason the performance degrades for larger test runs is that the overhead of invoking the action is growing as we doing less and less work in action.

Looping towards 0 can sometimes give performance benefits as it might save a CPU register but in this case the CPU has registers to spare so it doesn’t seem to make a difference.

Conclusion

Measuring is important because otherwise we might think all these alternatives are equivalent but some alternatives are ~270x slower than others.

The Verification step involves reverse engineering the executable helps us explain why we did or did not get performance we expected. In addition, Verification can help us predict performance in the cases it’s too difficult to do a proper Measurement.

It’s hard to predict performance there always Measure, always Verify your performance assumptions.

Comparison of different F# data pipelines

In F# there are many options for creating data pipelines, for example: List, Seq and Array.

What data pipeline is preferable from memory usage and performance perspective?

In order to answer this we’ll compare performance and memory usage using different pipelines.

Data Pipeline

In order to measure the overhead, we will use a data pipeline with low cpu-cost per items processed:

let seqTest n =
  Seq.init (n + 1) id
  |> Seq.map    int64
  |> Seq.filter (fun v -> v % 2L = 0L)
  |> Seq.map    ((+) 1L)
  |> Seq.sum

We will create equivalent pipelines for all alternatives and compare them.

We will variate the size of n but let the total number of work be the same.

Data Pipeline Alternatives

We will compare the following alternatives:

Imperative code
Array (Non-lazy)
List (Non-lazy)
LINQ (Lazy pull stream)
Seq (Lazy pull stream)
Nessos (Lazy pull/push stream)
PullStream (Simplistic pull stream)
PushStream (Simplistic push stream)

Although not a data pipeline we will compare against Imperative code since that most closely match how the CPU executes code. That should be that fastest possible way to compute the result allowing us to measure the performance overhead of data pipelines.

Array and List compute a full Array/List in each step so we expect memory overhead.

LINQ and Seq are both based around IEnumerable<'T> which is lazy pull stream (pull means that the consumer stream is pulling data out of the producer stream). We therefore expect the performance and memory usage to be identical.

Nessos is a high-performance stream library that supports both push & pull (like Java Stream).

PullStream and PushStream are simplistic implementations of Pull & Push streams.

Performance Results from running on: F# 4.0 - .NET 4.6.1 - x64

The bars show the elapsed time, lower is better. The total amount of useful work is the same for all tests so the results are comparable. This also means that few runs implies larger datasets.

As usual when Measuring one see interesting results.

List performance poor is compared to other alternatives for large data sets. This can be because of GC or poor cache locality.
Array performance better than expected.
LINQ performs better than Seq, this is unexpected because both are based around IEnumerable<'T>. However, Seq internally is based around a generic impementation for all algorithms while LINQ uses specialized algorithms.
Push performs better than Pull. This is expected since the push data pipeline has fewer checks
The simplistic Push data pipelines performs comparable to Nessos. However, Nessos supports pull and parallelism.
For small data pipelines the performance of Nessos degrades possible because pipelines setup overhead.
As expected the Imperative code performed the best

GC Collection count from running on: F# 4.0 - .NET 4.6.1 - x64

The bars shows the total number of GC collection counts during the test, lower is better. This is a measurement of how many objects are created by the data pipeline.

As usual when Measuring one see interesting results.

List is expectedly creating more objects than Array because a List is essentially a single linked list of nodes. An array is a continous memory area.
Looking at the underlying numbers both List & Array forces 2 generation collections. These kind of collection are expensive.
Seq is triggering a surprising amount of collections. It’s surprisingly even worse than List in this regard.
LINQ, Nessos, Push and Pull triggers no collections for few runs. However, objects are allocated so the GC eventually will have to run.
As expected since the Imperative code allocate no objects no GC collections were triggered.

Conclusion

All data pipelines do the same amount of useful work in all test cases but we see significant differences in performance and memory usage between the different pipelines.

In addition, we notice that the overhead of data pipelines differ depending on the size of data processed. For example, for small sizes Array is performing quite well.

One should keep in mind the amount of work performed in each step in the pipeline is very small in order to measure the overhead. In “real” situations the overhead of Seq might not matter because the actual work is more time consuming.

Of more concern is the memory usage differences. GC isn’t free and it is beneficial for long running applications to keep GC pressure down.

For F# developers concerned about performance and memory usage it’s recommended to check out Nessos Streams.

If you need top-notch performance strategically placed Imperative code is worth considering.

Finally, when it comes to performance don’t make assumptions. Measure and Verify.

Full source code:

module PushStream =
  type Receiver<'T> = 'T -> bool
  type Stream<'T>   = Receiver<'T> -> unit

  let inline filter (f : 'T -> bool) (s : Stream<'T>) : Stream<'T> =
    fun r -> s (fun v -> if f v then r v else true)

  let inline map (m : 'T -> 'U) (s : Stream<'T>) : Stream<'U> =
    fun r -> s (fun v -> r (m v))

  let inline range b e : Stream<int> =
    fun r ->
      let rec loop i = if i <= e && r i then loop (i + 1)
      loop b

  let inline sum (s : Stream<'T>) : 'T =
    let mutable state = LanguagePrimitives.GenericZero<'T>
    s (fun v -> state <- state + v; true)
    state

module PullStream =

  [<Struct>]
  [<NoComparison>]
  [<NoEqualityAttribute>]
  type Maybe<'T>(v : 'T, hasValue : bool) =
    member    x.Value        = v
    member    x.HasValue     = hasValue
    override  x.ToString ()  =
      if hasValue then
        sprintf "Just %A" v
      else
        "Nothing"

  let Nothing<'T>     = Maybe<'T> (Unchecked.defaultof<'T>, false)
  let inline Just v   = Maybe<'T> (v, true)

  type Iterator<'T> = unit -> Maybe<'T>
  type Stream<'T>   = unit -> Iterator<'T>

  let filter (f : 'T -> bool) (s : Stream<'T>) : Stream<'T> =
    fun () ->
      let i = s ()
      let rec pop () =
        let mv = i ()
        if mv.HasValue then
          let v = mv.Value
          if f v then Just v else pop ()
        else
          Nothing
      pop

  let map (m : 'T -> 'U) (s : Stream<'T>) : Stream<'U> =
    fun () ->
      let i = s ()
      let pop () =
        let mv = i ()
        if mv.HasValue then
          Just (m mv.Value)
        else
          Nothing
      pop

  let range b e : Stream<int> =
    fun () ->
      let mutable i = b
      fun () ->
        if i <= e then
          let p = i
          i <- i + 1
          Just p
        else
          Nothing

  let inline sum (s : Stream<'T>) : 'T =
    let i = s ()
    let rec loop state =
      let mv = i ()
      if mv.HasValue then
        loop (state + mv.Value)
      else
        state
    loop LanguagePrimitives.GenericZero<'T>

module PerfTest =

  open System.Linq
#if USE_NESSOS
  open Nessos.Streams
#endif

  let now =
    let sw = System.Diagnostics.Stopwatch ()
    sw.Start ()
    fun () -> sw.ElapsedMilliseconds

  let time n a =
    let inline cc i       = System.GC.CollectionCount i

    let v                 = a ()

    System.GC.Collect (2, System.GCCollectionMode.Forced, true)

    let bcc0, bcc1, bcc2  = cc 0, cc 1, cc 2
    let b                 = now ()

    for i in 1..n do
      a () |> ignore

    let e = now ()
    let ecc0, ecc1, ecc2  = cc 0, cc 1, cc 2

    v, (e - b), ecc0 - bcc0, ecc1 - bcc1, ecc2 - bcc2

  let arrayTest n =
    Array.init (n + 1) id
    |> Array.map    int64
    |> Array.filter (fun v -> v % 2L = 0L)
    |> Array.map    ((+) 1L)
    |> Array.sum

  let imperativeTest n =
    let rec loop s i =
      if i >= 0L then
        if i % 2L = 0L then
          loop (s + i + 1L) (i - 1L)
        else
          loop s (i - 1L)
      else
        s
    loop 0L (int64 n)

  let linqTest n =
    (((Enumerable.Range(0, n + 1)).Select int64).Where(fun v -> v % 2L = 0L)).Select((+) 1L).Sum()

  let listTest n =
    List.init (n + 1) id
    |> List.map     int64
    |> List.filter  (fun v -> v % 2L = 0L)
    |> List.map     ((+) 1L)
    |> List.sum

#if USE_NESSOS
  let nessosTest n =
    Stream.initInfinite id
    |> Stream.take    (n + 1)
    |> Stream.map     int64
    |> Stream.filter  (fun v -> v % 2L = 0L)
    |> Stream.map     ((+) 1L)
    |> Stream.sum
#endif

  let pullTest n =
    PullStream.range 0 n
    |> PullStream.map     int64
    |> PullStream.filter  (fun v -> v % 2L = 0L)
    |> PullStream.map     ((+) 1L)
    |> PullStream.sum

  let pushTest n =
    PushStream.range 0 n
    |> PushStream.map     int64
    |> PushStream.filter  (fun v -> v % 2L = 0L)
    |> PushStream.map     ((+) 1L)
    |> PushStream.sum

  let seqTest n =
    Seq.init (n + 1) id
    |> Seq.map    int64
    |> Seq.filter (fun v -> v % 2L = 0L)
    |> Seq.map    ((+) 1L)
    |> Seq.sum

  let perfTest (path : string) =
    let testCases =
      [|
        "array"       , arrayTest       
        "imperative"  , imperativeTest  
        "linq"        , linqTest        
        "list"        , listTest        
        "seq"         , seqTest         
#if USE_NESSOS
        "nessos"      , nessosTest      
#endif
        "pull"        , pullTest        
        "push"        , pushTest        
      |]
    use out                   = new System.IO.StreamWriter (path)
    let write (msg : string)  = out.WriteLine msg
    let writef fmt            = FSharp.Core.Printf.kprintf write fmt

    write "Name\tTotal\tOuter\tInner\tElapsed\tCC0\tCC1\tCC2\tResult"

    let total   = 10000000
    let outers = [| 10; 1000; 1000000 |]
    for outer in outers do
      let inner = total / outer
      for name, a in testCases do
        printfn "Running %s with total=%d, outer=%d, inner=%d ..." name total outer inner
        let v, ms, cc0, cc1, cc2 = time outer (fun () -> a inner)
        printfn "  ... %d ms, cc0=%d, cc1=%d, cc2=%d, result=%A" ms cc0 cc1 cc2 v
        writef "%s\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d" name total outer inner ms cc0 cc1 cc2 v

[<EntryPoint>]
let main argv =
  System.Environment.CurrentDirectory <- System.AppDomain.CurrentDomain.BaseDirectory
  PerfTest.perfTest "perf.tsv"
  0