DependentTypes

Benchmarks 1

Let's benchmark...

DependentType option

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 

open DependentTypes

module PercentType =
    let validatePercent _ n = 
        match n >= 0. && n <= 1. with
        | true -> Some n
        | false -> None

    type PercentValidator() = 
        inherit Pi<unit, float, float option>((), validatePercent)

    type PairPercentValidator() = 
        inherit Sigma<unit, float, float option>((), validatePercent)

type Percent = SomeDependentType<PercentType.PercentValidator, unit, float, float>

let runPctOption() =
    [|
        PercentType.validatePercent () 0.5
        PercentType.validatePercent () 2.5
    |] 

let runLiftedPctDependentType() =
    [|
        Percent.TryCreate 0.5
        Percent.TryCreate 2.5
    |]
  • Create a percent DependentType option compared to creating a simple float option using the same validation logic.
  • Each benchmark instance creates 1 Some option and 1 None option in both cases.
  • Benchmark 1,000,000 instances, hence 2M option instances.
1: 
2: 

Validated option is faster than TryCreate DependentType option. 
f1 (21.9484 ± 2.5478 ms) is ~96% faster than f2 (607.0490 ± 15.8352 ms).

Not surprisingly validation and creation of a simple option is faster, 28X faster.

And it scales nearly linearly, as we see when executing the benchmark 10X instead of 1MX.

1: 
2: 

(10X) validated option is faster than TryCreate DependentType option. 
f1 (0.0006 ± 0.0000 ms) is ~94% faster than f2 (0.0091 ± 0.0002 ms).

Considering in our first benchmark DependentType created 2M option instances in less than 700 ms, and creates 20 in 9 micro-seconds, this is probably acceptable performance for all but the most demanding network applications.

The validation logic adds little overhead. Even comparing creating DependentType to "naked" options (not run through the validation logic) makes little difference in the performance ratio.

1: 
2: 

Naked option is faster than TryCreate DependentType option. 
f1 (18.3340 ± 0.1073 ms) is ~97% faster than f2 (601.7315 ± 4.2582 ms).

Can we squeeze even more performance from DependentType creation? Let's use Create instead of TryCreate so we eliminate the overhead of "lifting" the 'T2 base type element option result to the DependentType element.

1: 
2: 

Validated option is faster than Create DependentType. 
f1 (17.0064 ± 0.3517 ms) is ~93% faster than f2 (256.9292 ± 2.3419 ms).

Validate option is now only 15X faster, so the "lift" overhead of DependentType is noticeable at large scales (2M creations).

We expect from these results Create DepeendentType option is twice as fast as TryCreate, because it does not lift the option from the value to the DependentType. And we see if we do a Create to TryCreate direct comparison, that is roughly true.

1: 
2: 

Create DependentType is faster than TryCreate DependentType. 
f1 (258.6811

Consuming (reading) DependentType.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 

let readDependentType (xs : Percent option []) =
    xs
    |> Array.map ( fun x ->
        match x with
        | Some _ -> Some x.Value
        | None -> None )

let readVanillaOption (xs : float option[]) =
    xs
    |> Array.map ( fun x ->
        match x with
        | Some pct -> Some pct
        | None -> None )

1: 
2: 

Read Option is faster than Option DependentType. 
f1 (17.9776 ± 0.2142 ms) is ~33% faster than f2 (27.0092 ± 0.3793 ms).
  • Reading 2M float options is only 33% faster than read/extract value operation on DependentTypes.

Substituting the verbose Some pct.Value.Value for the helper function someValue almost erases any advantage of float option.

1: 
2: 

Read Option is faster than Option DependentType Value.Value. 
f1 (19.5531 ± 0.1250 ms) is ~4% faster than f2 (20.2828 ± 0.1295 ms).

UtcDateTime DependentType

Benchmarking a type that is not an option, we compare UtcDateTime in the DomainLib to an implementation validating a DateTime.

This time 1M benchmark runs is also 1M instances.

1: 
2: 

Validated DateTime is faster than Create DependentType DateTime. 
f1 (278.7760 ± 3.3103 ms) is ~28% faster than f2 (385.8573 ± 0.6970 ms).

1: 
2: 

Read DateTime is faster than DependentType DateTime. 
f1 (7.3626 ± 0.0496 ms) is ~7% faster than f2 (7.9543 ± 0.0946 ms).

In this case the create and read performance differences are barely meaningful.

DependentPair

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 

type PercentPair = DependentPair<PercentType.PairPercentValidator, unit, float, float option>

let runPctPair() =
    [|
        (0.5, PercentType.validatePercent () 0.5)
        (2.5, PercentType.validatePercent () 2.5)
    |] 

let runPctDependentPair() =
    [|
        PercentPair.Create 0.5
        PercentPair.Create 2.5
    |]

Benchmarks comparing a validated pair to DependentPair yields similar performance ratios to option DependentType.

1M runs again creates 2M instances.

1: 
2: 

Pair is faster than Create DependentPair. 
f1 (30.2823 ± 0.0807 ms) is ~86% faster than f2 (223.3536 ± 0.9640 ms).

1: 
2: 

Read pair is faster than DependentPair. 
f1 (28.5499 ± 0.0862 ms) is ~2% faster than f2 (29.0964 ± 0.1033 ms).

Creation of a simple validated pair is 7X faster than creating a DependentPair, but read/consume performance is so similar we sometimes see the benchmark test failing because DependentPair performs faster.

Notes

1 The usual caveats about benchmarking apply. You should benchmark your own situation on your own system, etc. There is variance in running the benchmarks multiple times. The variance I saw was typically in absolute run time for each scenario, and not so much in the DependentType / control run time ratios. By and large these results are representative of typical benchmark runs on my system, FSharp.Core 4.5.3, net45 DependentTypes.dll
namespace DependentTypes
module Helpers

from DependentTypes
val validatePercent : 'a -> n:float -> float option
val n : float
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
Multiple items
type PercentValidator =
  inherit Pi<unit,float,float option>
  new : unit -> PercentValidator

--------------------
new : unit -> PercentValidator
Multiple items
type Pi<'Config,'T,'T2> =
  new : config:'Config * pi:('Config -> 'T -> 'T2) -> Pi<'Config,'T,'T2>
  member Create : x:'T -> 'T2

--------------------
new : config:'Config * pi:('Config -> 'T -> 'T2) -> Pi<'Config,'T,'T2>
type unit = Unit
Multiple items
val float : value:'T -> float (requires member op_Explicit)

--------------------
type float = System.Double

--------------------
type float<'Measure> = float
type 'T option = Option<'T>
Multiple items
type PairPercentValidator =
  inherit Sigma<unit,float,float option>
  new : unit -> PairPercentValidator

--------------------
new : unit -> PairPercentValidator
Multiple items
type Sigma<'Config,'T,'T2> =
  new : config:'Config * pi:('Config -> 'T -> 'T2) -> Sigma<'Config,'T,'T2>
  member Create : x:'T -> 'T * 'T2

--------------------
new : config:'Config * pi:('Config -> 'T -> 'T2) -> Sigma<'Config,'T,'T2>
type Percent = SomeDependentType<PercentType.PercentValidator,unit,float,float>
Multiple items
union case SomeDependentType.SomeDependentType: 'T2 -> SomeDependentType<'Pi,'Config,'T,'T2>

--------------------
type SomeDependentType<'Pi,'Config,'T,'T2 (requires 'Pi :> Pi<'Config,'T,'T2 option> and default constructor)> =
  | SomeDependentType of 'T2
    override ToString : unit -> string
    member Value : 'T2
    static member ConvertTo : x:SomeDependentType<'x,'y,'q,'r> -> SomeDependentType<'a,'b,'r,'s> (requires 'x :> Pi<'y,'q,'r option> and default constructor and 'a :> Pi<'b,'r,'s option> and default constructor)
    static member Create : x:'T -> SomeDependentType<'Pi,'Config,'T,'T2>
    static member Extract : x:SomeDependentType<'Pi,'Config,'T,'T2> -> 'T2
    static member TryCreate : x:'T -> SomeDependentType<'Pi,'Config,'T,'T2> option
module PercentType

from Benchmarks
Multiple items
type PercentValidator =
  inherit Pi<unit,float,float option>
  new : unit -> PercentValidator

--------------------
new : unit -> PercentType.PercentValidator
val runPctOption : unit -> float option []
val runLiftedPctDependentType : unit -> SomeDependentType<PercentType.PercentValidator,unit,float,float> option []
static member SomeDependentType.TryCreate : x:'T -> SomeDependentType<'Pi,'Config,'T,'T2> option
val readDependentType : xs:Percent option [] -> Percent option []
val xs : Percent option []
module Array

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> array:'T [] -> 'U []
val x : Percent option
property Option.Value: Percent
val readVanillaOption : xs:float option [] -> float option []
val xs : float option []
val x : float option
val pct : float
module Option

from Microsoft.FSharp.Core
type PercentPair = DependentPair<PercentType.PairPercentValidator,unit,float,float option>
Multiple items
union case DependentPair.DependentPair: 'T * 'T2 -> DependentPair<'Sigma,'Config,'T,'T2>

--------------------
type DependentPair<'Sigma,'Config,'T,'T2 (requires 'Sigma :> Sigma<'Config,'T,'T2> and default constructor)> =
  | DependentPair of 'T * 'T2
    member Value : 'T * 'T2
    static member Create : x:'T -> DependentPair<'Sigma,'Config,'T,'T2>
Multiple items
type PairPercentValidator =
  inherit Sigma<unit,float,float option>
  new : unit -> PairPercentValidator

--------------------
new : unit -> PercentType.PairPercentValidator
val runPctPair : unit -> (float * float option) []
val runPctDependentPair : unit -> DependentPair<PercentType.PairPercentValidator,unit,float,float option> []
static member DependentPair.Create : x:'T -> DependentPair<'Sigma,'Config,'T,'T2>
F# Project
Fork me on GitHub