Performance for composition in F#

In a previous post I talked about how we at work simplified composition in an F# project because we found that we took a performance hit when we used monadic binds in our code.

I was a bit surprised how expensive the construct was so I wanted to dig deeper into it with this article.

The setup

Composition in F# can take a number of forms. Below we will take a closer look at the simple straight forward pipe (|>) operator and compare it to the Kleisli composition and monadic bind composition operating on the Result type.

In other words, we will compare the following operators:

// Monadic bind
let (>>=) m f =
    Result.bind f m 

// Monadic bind inline
let inline (>>==) m f =
    Result.bind f m 

// Kleisli
let inline (>=>) a b x =
    match a x with
    | Ok v -> b v
    | Error e -> Error e

To test we compose five different functions. All the functions do is copy some data structure:

type Data =
    { Property1: string
      Property2: int
      Property3: DateTime 
      Property4: float
      Property5: decimal }

let processA data = { data with Property1 = "some new string" }
let processB data = { data with Property2 = 100 }
let processC data = ...

let processResultA data = Ok { data with Property1 = "some new string" }
let processResultB data = Ok { data with Property2 = 100 }
let processResultC data = ...

We use function processData for testing |> and processDataResult for testing the compositions that operate on Result.

Now we can create the functions we wish to time:

let withPiping data =
    data
    |> processA
    |> processB
    |> processC
    |> processD
    |> processE

let withBinding data =
    data
    |> processResultA
    |> Result.bind processResultB
    |> Result.bind processResultC
    |> Result.bind processResultD
    |> Result.bind processResulte

let withOperatorWithoutInlining data =
    data
    |> processResultA
    >>= processResultB
    >>= processResultC
    >>= processResultD
    >>= processResultE

let withOperatorWithInlining data =
    data
    |> processResultA
    >>== processResultB
    >>== processResultC
    >>== processResultD
    >>== processResultE

let withKleisli data =
    data
    |> (processResultA
    >=> processResultB
    >=> processResultC
    >=> processResultD
    >=> processResultE)

Note that withBinding, withOperatorWithoutInlining and withOperatorWithInlining are essentially the same but as we will see later there is a difference in performance between them.

Let's also define a function for timing a number of calls to a function f:

let timeFunction f data =
    let sw = Stopwatch()

    sw.Start()

    [1 .. 10_000_000]
    |> List.iter (fun _ -> f data |> ignore)

    sw.Stop()
    sw.Elapsed.TotalMilliseconds

That way we can time 10 million calls to a function like so:

data |> timeFunction withKleisli

To get a smaller variance on those 10 millions calls, let us define a run function that runs timeFunction a number of times and prints the average:

let run f fName =
    let data =
        { Property1 = "some string"
          Property2 = 42
          Property3 = DateTime.Today
          Property4 = 23.2
          Property5 = 23m }

    [1 .. 100]
    |> List.averageBy (fun i -> timeFunction f data)
    |> print fName

Now we can write the final setup:

run withPiping (nameof withPiping)
run withBinding (nameof withBinding)
run withOperatorWithInlining (nameof withOperatorWithInlining)
run withOperatorWithoutInlining (nameof withOperatorWithoutInlining)
run withKleisli (nameof withKleisli)

Granted, the setup is a bit lame but it does give some indication of differences in performance between the different types of composition.

The results are in

They say that an image is worth a thousand words, so here is a graph for you. I set withPiping as index 100, so the graph shows how the other methods compare to withPiping.

It shouldn't come as a surprise that withPiping is the fastest.

I am a bit surprised that withBinding is that much faster than withOperatorWithoutInlining, i.e. the >>= operator.

Kleisli composition is surprisingly slow, but monadic bind is more useful in F# anyways so you would probably not use Kleisli that often.

Code

I put the code on Github if you want to have a look. I created it on .NET 6 RC using the preview of Visual Studio 2022.

t4rzsan / fsharp-performance-testing

Comments

[Scott Hutchinson]

Have you considered using github.com/dotnet/BenchmarkDotNet for this comparison? There's a bit of a learning curve to get started with it, and it can take a while to run, but the reward is more robust, statistically significant results.

[Jakob Christensen]

Nice, thank you. I did not know about that one.