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 |
@Happypig375
Yes, using an extra build script to generate the implementation using a F# script would work. I don't see why it would be simpler to build as you still need to generate a F# function by inspecting a type.
This would also mean that we need a way to get the type information. So we'd either need to extract the type to a different assembly that we can build separately and then load the type from or extract the type information in some other way.
I definitely agree with you that it would be easier to debug the generated code as you can just set breakpoints and read the actual code.
It is still quite easy to work around this limitation, as we can write a test that ensures our fast implementation behaves the same as our slow implementation.