F# Benchmarking

Read Time: 6 minutes

Occasionally the need arises in an F# project to perform benchmarking. BenchmarkDotNet is a powerful tool made exactly for this purpose. Today’s post provides an introductory look into the process.

Although #time and Stopwatch are useful for quick and dirty checks, BenchmarkDotNet allows a more comprehensive look at performance characteristics. This post will use sort for a case study to display a sample of what can be done. Before getting started ensure you have .NET Core version 2.2. Select SDK for your platform. After that create a console F# project and install the BenchmarkDotNet package.

1
2
3
dotnet new console --language F# --name BenchmarkSort
cd BenchmarkSort 
dotnet add package BenchmarkDotNet --version 0.11.3

First, the initial stuff. One note here is that I decided to use a complex type Foo for my sorting benchmark. I could’ve used int, but .NET has highly optimized methods for sorting native types like int. To the level the playing field a bit I wanted to take this out of the equation.

1
2
3
4
5
6
7
8
9
module Program

open System
open BenchmarkDotNet.Attributes
open BenchmarkDotNet.Running

let rand = new Random()

type Foo = { Id: int; Name: string }

Time to create the test functions. The comparison targets will be .NET’s built in List.sort, then a hand-written QuickSort, and BubbleSort.

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
let listSort (l :Foo list) =
  List.sort l

let rec quickSort (l :Foo list) =
  match l with 
  | []   -> []
  | h::t -> let (smaller, larger) = List.partition (fun x -> x.Id <= h.Id) t
            List.concat [ quickSort smaller; [h]; quickSort larger ]

let bubbleSortMutable (l :Foo list) = 
  let mutable l' = l |> Array.ofList
  let mutable keepGoing = true
  while keepGoing do
    keepGoing <- false
    for i in [1..(Array.length l' - 1)] do
      if l'.[i-1] > l'.[i] then
        let t = l'.[i-1]
        l'.[i-1] <- l'.[i]
        l'.[i] <- t
        keepGoing <- true
  l' |> List.ofArray

let bubbleSortRecursive (l :Foo list) = 
  let rec bubbleSort' a rev l =
    match l, rev with
    | [], true     -> List.rev a
    | [], false    -> List.rev a |> bubbleSort' [] true
    | h1::h2::t, _ -> if h1 > h2 
                      then bubbleSort' (h2::a) false (h1::t)
                      else bubbleSort' (h1::a) rev (h2::t)
    | h::t, _      -> bubbleSort' (h::a) rev t
  bubbleSort' [] true l

let initList n = 
  [1..n] 
  |> List.map (fun _ ->
    let id = rand.Next(10*n)
    { Foo.Id = id; Name = id.ToString() })

Now it is time to setup the benchmarking methods. First, I make a type SortComparison. I have attached a MemoryDiagnoser attribute so that I’ll get GC statistics back from the benchmarking run. The sorting methods will be tested against different list sizes (10, 1000, and 10000). This is defined in ListSize, where the Params attribute defines what BenchmarkDotNet should use for parameterization during the tests. Next, it is time to define what will be compared. To do this there are member functions marked with the Benchmark attribute. That’s all there is to setting up the tests.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[<MemoryDiagnoser>]
type SortComparison () =

  [<Params (10,1000,10000)>] 
  member val ListSize :int = 0 with get, set

  member self.mainList = initList self.ListSize
  
  [<Benchmark>]
  member self.ListSort() = listSort self.mainList

  [<Benchmark>]
  member self.ListQuickSort () = quickSort self.mainList

  [<Benchmark>]
  member self.ListBubbleSortMutable () = bubbleSortMutable self.mainList
  
  [<Benchmark>]
  member self.ListBubbleSortRecursive () = bubbleSortRecursive self.mainList

In Main, all that is needed is a simple runner.

1
2
3
[<EntryPoint>]
let Main args =
  BenchmarkRunner.Run typeof<SortComparison> |> ignore

Once everything is together, they just need to run.

1
~/Benchmark(master)$ dotnet run -c release

Time to look at the results. The benchmark spews a ton of data, but I’ll just focus on the final results here.

Results

The test results aren’t too surprising. .NET’s built in sort is more efficient for large lists, although QuickSort holds its own as long as the list isn’t too large. Both are faster than BubbleSort. With the GC stats, we can also see where additional GC’s start to hinder some of the algorithms.

This is great, and time to make it a bit more advanced. Multiple benchmarks can be placed and run in the same file. Here I add FakeComparison and add a selector when the application is run. This is helpful when you want to keep different sets of benchmarking tests.

1
2
3
4
5
6
7
8
9
10
11
12
type FakeComparison () =
  [<Benchmark>]
  member self.Fake1 () = 1
  
  [<Benchmark>]
  member self.Fake2 () = 2

let defaultSwitch () = BenchmarkSwitcher [| typeof<SortComparison>; typeof<FakeComparison> |]

[<EntryPoint>]
let Main args =
  defaultSwitch().Run args |> ignore

Now, when running, a prompt is provided.

1
2
3
4
5
6
7
8
~/Benchmark(master)$ dotnet run -c release
Available Benchmarks:
  #0 SortComparison
  #1 FakeComparison

You should select the target benchmark(s). Please, print a number of a benchmark (e.g. '0') or a contained benchmark caption (e.g. 'SortComparison'):
If you want to select few, please separate them with space ` ` (e.g. `1 2 3`)
You can also provide the class name in console arguments by using --filter. (e.g. '--filter *SortComparison*'):

There is one more aspect of reporting, and that is the final results. What I’ve shown has been part of the console output, but there is more. A BenchmarkDotNet.Artifacts directory contains a detailed run log. It also contains specially formatted results, namely: csv, html, and github markdown. All of these being very useful for more advanced reporting or just simply dropping into a repo.

This provides the basis to explore BenchmarkDotNet in your next performance comparison endeavor. Be sure to check out the BenchmarkDotNet site for additional documentation. Until next time.

Related Posts: