Skip to content

Instantly share code, notes, and snippets.

@JaggerJo
Last active July 2, 2023 18:44
Show Gist options
  • Save JaggerJo/6f1a7af9698ca54cdae443c0c260a98d to your computer and use it in GitHub Desktop.
Save JaggerJo/6f1a7af9698ca54cdae443c0c260a98d to your computer and use it in GitHub Desktop.
A 1000x improvement in performance

A 1000x improvement in performance

We recently had to provide (near) live data to a set of views in our application. After considering the most common ways to build this we decided to go with long polling. Our entire app is event based, so we know if a certain event happed the data might have changed. Lets assume the following types represent what can happen in our application:

type CounterEvent =
  | CounterWasIncremented byValue: int
  | CounterWasDecremented: byValue: int
  | CounterWasReset

type AppEvent =
  | Counter of CounterEvent

Lets say two users view a counter. If a user increments the counter a AppEvent.Counter (CounterEvent.CounterWasIncremented 1) is returned by the designated workflow and is translated to SQL statements which will then be run which results in the DB being updated.

All users that view the a counter use long polling to get updated data as soon as an event that affects the data they view happend. In code this is expressed like this:

async {
  (* wait for event we care about to happend, or return after 20s max *)
  do! LongPollingService.Instance.Listen (
    listenFor = [ "AppEvent.Counter.*" ],
    timeoutSeconds = 20
  )

  (* fetch state and return *)
  return! Query.fetchCounterState ()
}

Because we run multiple instances of our app we need a way of letting all instances know "event x happend", but we don't actually care about what's in the event. We just want to be able to specify what events we are interested in by providing a dot separated string of the nested Discriminated Union.

So we want to be able to provide a string like this:

"AppEvent.Counter.*"

And turn an instance of AppEvent into a string:

let instance = AppEvent.Counter (CounterEvent.CounterWasIncremented 1)

let dotSeparatedString (i: AppEvent): string = ?

dotSeparatedString instance => "AppEvent.Counter.CounterWasIncremented"

Implementing the dotSeparatedString function is quite easy - a simple implementation could look like this:

[<RequireQualifiedAccess>]
module EventKind_Baseline =

    let createDotSeparatedTypeString (instance: 't) : string =

        let rec impl(path: string list, instance: obj) : string list =
            let instanceType = instance.GetType()

            if FSharpType.IsUnion instanceType then

                let case, _ = FSharpValue.GetUnionFields(instance, instanceType)
                let path =
                    if path.IsEmpty
                    then case.Name :: case.DeclaringType.Name :: path
                    else case.Name :: path

                match case.GetFields () with
                | [| field |] when FSharpType.IsUnion field.PropertyType ->
                    impl (path, field.GetValue instance)

                | _ ->
                    path
            else
                path

        (List.Empty, instance)
        |> impl
        |> List.rev
        |> String.concat "."

The Problem with performance

The EventKind_Baseline.createDotSeparatedTypeString takes around ~1ms per call. This is terribly slow if you are dealing with a lot of events. The implementation above is not optimal, but what's really slow about it is the use of reflection. We used DotnetBenchmark and even an optimized implementation takes ~700µs (microseconds).

The obviouse solution would be to just implement the createDotSeparatedTypeString by hand. It's just a match expression after all. This is IMHO the best solution - but not if you have > 1000 event types.

What if we could only use reflection once to generate an efficient implementation at runtime?

Luckily this is quite simple using Linq Expressions as they can be compiled to a delegate.

The code below is around 1000x faster than the reflection based implementation.

[<RequireQualifiedAccess>]
module EventKind_Generative  =

    let rec private generateForType
      ( instanceType: Type,
        stringBuilder: ParameterExpression,
        instance: ParameterExpression ) : Expression =

        Expression.Condition(
            test = Expression.Equal(instance, Expression.Constant(null)),
            ifTrue = Expression.Empty (),
            ifFalse = (
                let tag = Expression.Variable(typeof<int>, "tag")
                let expressions: seq<Expression> = [|

                    if FSharpType.IsUnion instanceType then
                        Expression.Assign(
                            tag,
                            Expression.Call (
                                Expression.Convert(instance, instanceType),
                                "get_Tag",
                                null
                            )
                        )

                        Expression.Switch(
                            switchValue = tag,
                            defaultBody = Expression.Empty(),
                            cases = [|
                                for unionCase in FSharpType.GetUnionCases(instanceType) do
                                    let caseValue = Expression.Variable (typeof<obj>, "caseValue")

                                    Expression.SwitchCase(
                                        testValues = [| Expression.Constant(unionCase.Tag, typeof<int>) :> Expression |],
                                        body = Expression.Block (
                                            variables = [| caseValue |],
                                            expressions = [|

                                                Expression.Call (
                                                    stringBuilder,
                                                    typeof<StringBuilder>.GetMethod("Append", types = [| typeof<string> |]),
                                                    [| Expression.Constant("." + unionCase.Name) :> Expression |]
                                                ) :> Expression


                                                match unionCase.GetFields() with
                                                | [| field |] ->
                                                    Expression.Assign (
                                                        caseValue,
                                                        Expression.Convert(
                                                            Expression.PropertyOrField(Expression.Convert(instance, field.DeclaringType), field.Name),
                                                            typeof<obj>
                                                        )

                                                    ) :> Expression

                                                    generateForType (field.PropertyType, stringBuilder, caseValue)

                                                | _ ->
                                                    ()

                                                Expression.Empty()
                                            |]
                                        )
                                    )

                            |]
                        )
                    else
                        ()

                    Expression.Empty()
                |]

                Expression.Block(
                    variables = [| tag; |],
                    expressions = expressions
                )
            )
        )

    let generate<'t>() : Func<'t, string> =
        let instance = Expression.Parameter(typeof<'t>, "instance")
        let stringBuilder = Expression.Variable(typeof<StringBuilder>, "stringBuilder")

        let ``stringBuilder := new StringBuilder()`` : Expression =
            Expression.Assign(
                stringBuilder,
                Expression.New(typeof<StringBuilder>)
            )

        let ``stringBuilder.ToString()`` : Expression =
            Expression.Call(
                stringBuilder,
                typeof<StringBuilder>.GetMethod("ToString", types = [| |])
            )

        let methodBody = Expression.Block(
            typeof<string>,
            variables = [| stringBuilder |],
            expressions = [|
                ``stringBuilder := new StringBuilder()``

                Expression.Call (
                    stringBuilder,
                    typeof<StringBuilder>.GetMethod("Append", types = [| typeof<string> |]),
                    [| Expression.Constant(typeof<'t>.Name) :> Expression |]
                ) :> Expression

                generateForType (typeof<'t>, stringBuilder, instance)

                ``stringBuilder.ToString()``
            |]
        )

        let lambda = Expression.Lambda<Func<'t, string>>(methodBody, [| instance |])
        lambda.Compile()

Benchmarks

(Run on an Apple M1 Chip)

Method Mean Ratio Gen0 Gen1 Allocated Alloc Ratio
Benchmark_Generative 170.7 ns 0.000 0.0739 - 464 B 0.001
Benchmark_Base 1,101,063.4 ns 1.000 76.1719 1.9531 480408 B 1.000
@Happypig375
Copy link

@JaggerJo Just do source inspection for the DU type. A good formatting would start with type DUName = followed by lines starting with |.

@JaggerJo
Copy link
Author

JaggerJo commented Jul 2, 2023

@JaggerJo Just do source inspection for the DU type. A good formatting would start with type DUName = followed by lines starting with |.

All easy to say 😉

Also it's not one DU - it's one DU that references other DU's as case fields (that might reference other DU's as case fields... )

Show me an implementation that after considering all of that is still simpler. Talk is cheap, show me the code.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment