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 CounterEventLets 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 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()(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 |
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.