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 |
Cool idea!
Q1: Why doing long polling on event presence vs just timeout?
I've built several polling apps in the past and in the end always ended up with doing the simple thing of a set polling timeout (5-10s). Adding event search / conditionals seemed to add a lot of overhead / complexity vs just lowering the timeout itself which gets most of the benefits w very little added complexity.
Curious what the decision point was that made the extra complexity worth it.
Q2: Curious about performance for solution 1 if you naively cached the solution?
I get that solution 2 is probably the faster solution regardless but it's also a lot more complex with like 3x the code and functions. It strikes me that a big difference between Solution 1 and 2 is that 2 computes once whereas 1 seems to recompute everything each time it's called.
I wonder if Solution 1 was simply wrapped in memoization (Lazy or maybe a simple dict<t, string>) if it would amortize to be more reasonable.
Also side note: I've never seen anyone use Gist as a blog platform - seems pretty useful and w built-in comments!