FSharpx.Collections


PersistentHashMap - Performance tests

Bulk operations on HashMaps use an internal TransientHashMap in order to get much better performance. The following scripts shows this:

  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: 
 28: 
 29: 
 30: 
 31: 
 32: 
 33: 
 34: 
 35: 
 36: 
 37: 
 38: 
 39: 
 40: 
 41: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
open FSharpx.Collections

let trials = 5
let r = new System.Random()

let initFSharpMapAndPersistentMapFromList n =
    sprintf "Init with n = %d" n |> printInFsiTags
    
    let list = List.sortBy snd [for i in 1..n -> i,r.Next().ToString()]

    averageTime trials "  FSharp.Map.ofSeq" 
        (fun () -> Map.ofSeq list)

    let initPersistentHashMap list = 
        let m = ref PersistentHashMap.empty
        for (key,value) in list do
            m := PersistentHashMap.add key value !m
        !m

    averageTime trials "  Multiple PersistentHashMap.add" 
        (fun () -> initPersistentHashMap list)

    averageTime trials "  PersistentHashMap.ofSeq" 
        (fun () -> PersistentHashMap.ofSeq list)

    let initImmutableDictionary list = 
        let d = ref (System.Collections.Immutable.ImmutableDictionary<int,string>.Empty)
        for (key,value) in list do
            d := (!d).Add(key,value)
        !d

    averageTime trials "  Multiple ImmutableDictionay.add" 
        (fun () -> initImmutableDictionary list)

    let initImmutableDictionary list = 
        let d = ref (System.Collections.Immutable.ImmutableSortedDictionary<int,string>.Empty)
        for (key,value) in list do
            d := (!d).Add(key,value)
        !d

    averageTime trials "  Multiple ImmutableSortedDictionay.add" 
        (fun () -> initImmutableDictionary list)

let lookupInFSharpMapAndPersistentMap n count =
    sprintf "%d Lookups in size n = %d" count n |> printInFsiTags
    let list = [for i in 0..n-1 -> i.ToString(),r.Next()]
    let fsharpMap = Map.ofSeq list
    let map = PersistentHashMap.ofSeq list

    averageTime trials "  FSharp.Map" 
        (fun () -> for i in 1..count do fsharpMap.[r.Next(n).ToString()])

    averageTime trials "  PersistentHashMap" 
        (fun () -> for i in 1..count do map.[r.Next(n).ToString()])

    let dict =
        let d = ref (System.Collections.Immutable.ImmutableDictionary<string,int>.Empty)
        for (key,value) in list do
            d := (!d).Add(key,value)
        !d

    averageTime trials "  ImmutableDictionay" 
        (fun () -> for i in 1..count do dict.[r.Next(n).ToString()])

    let dict' =
        let d = ref (System.Collections.Immutable.ImmutableSortedDictionary<string,int>.Empty)
        for (key,value) in list do
            d := (!d).Add(key,value)
        !d

    averageTime trials "  ImmutableSortedDictionay" 
        (fun () -> for i in 1..count do dict'.[r.Next(n).ToString()])

initFSharpMapAndPersistentMapFromList 10000
initFSharpMapAndPersistentMapFromList 100000
initFSharpMapAndPersistentMapFromList 1000000

lookupInFSharpMapAndPersistentMap 10000 10000
lookupInFSharpMapAndPersistentMap 100000 10000
lookupInFSharpMapAndPersistentMap 1000000 10000
lookupInFSharpMapAndPersistentMap 10000000 10000

Init with n = 10000
  FSharp.Map.ofSeq 16.0ms
  Multiple PersistentHashMap.add 43.6ms
  PersistentHashMap.ofSeq 25.4ms
  Multiple ImmutableDictionay.add 29.6ms
  Multiple ImmutableSortedDictionay.add 15.2ms
Init with n = 100000
  FSharp.Map.ofSeq 233.4ms
  Multiple PersistentHashMap.add 293.2ms
  PersistentHashMap.ofSeq 217.2ms
  Multiple ImmutableDictionay.add 375.0ms
  Multiple ImmutableSortedDictionay.add 222.0ms
Init with n = 1000000
  FSharp.Map.ofSeq 5323.8ms
  Multiple PersistentHashMap.add 5562.4ms
  PersistentHashMap.ofSeq 4489.8ms
  Multiple ImmutableDictionay.add 7061.4ms
  Multiple ImmutableSortedDictionay.add 4685.0ms
10000 Lookups in size n = 10000
  FSharp.Map 5.2ms
  PersistentHashMap 9.6ms
  ImmutableDictionay 4.2ms
  ImmutableSortedDictionay 15.0ms
10000 Lookups in size n = 100000
  FSharp.Map 7.0ms
  PersistentHashMap 10.8ms
  ImmutableDictionay 5.4ms
  ImmutableSortedDictionay 20.2ms
10000 Lookups in size n = 1000000
  FSharp.Map 12.2ms
  PersistentHashMap 12.4ms
  ImmutableDictionay 8.2ms
  ImmutableSortedDictionay 29.6ms
10000 Lookups in size n = 10000000
  FSharp.Map 19.2ms
  PersistentHashMap 15.4ms
  ImmutableDictionay 13.8ms
  ImmutableSortedDictionay 42.0ms
namespace System
val stopTime : f:(unit -> 'a) -> 'a * float


 Stops the runtime for a given function
val f : (unit -> 'a)
val sw : Diagnostics.Stopwatch
namespace System.Diagnostics
Multiple items
type Stopwatch =
  new : unit -> Stopwatch
  member Elapsed : TimeSpan
  member ElapsedMilliseconds : int64
  member ElapsedTicks : int64
  member IsRunning : bool
  member Reset : unit -> unit
  member Restart : unit -> unit
  member Start : unit -> unit
  member Stop : unit -> unit
  static val Frequency : int64
  ...

--------------------
Diagnostics.Stopwatch() : Diagnostics.Stopwatch
Diagnostics.Stopwatch.Start() : unit
val result : 'a
Diagnostics.Stopwatch.Stop() : unit
Multiple items
val float : value:'T -> float (requires member op_Explicit)

--------------------
type float = Double

--------------------
type float<'Measure> = float
property Diagnostics.Stopwatch.ElapsedMilliseconds: int64
val stopAverageTime : count:int -> f:(unit -> 'a) -> float


 Stops the average runtime for a given function and applies it the given count
val count : int
type GC =
  static member AddMemoryPressure : bytesAllocated:int64 -> unit
  static member CancelFullGCNotification : unit -> unit
  static member Collect : unit -> unit + 4 overloads
  static member CollectionCount : generation:int -> int
  static member EndNoGCRegion : unit -> unit
  static member GetGeneration : obj:obj -> int + 1 overload
  static member GetTotalMemory : forceFullCollection:bool -> int64
  static member KeepAlive : obj:obj -> unit
  static member MaxGeneration : int
  static member ReRegisterForFinalize : obj:obj -> unit
  ...
GC.Collect() : unit
GC.Collect(generation: int) : unit
GC.Collect(generation: int, mode: GCCollectionMode) : unit
GC.Collect(generation: int, mode: GCCollectionMode, blocking: bool) : unit
GC.Collect(generation: int, mode: GCCollectionMode, blocking: bool, compacting: bool) : unit
val ignore : value:'T -> unit
val printInFsiTags : s:string -> unit
val s : string
val printfn : format:Printf.TextWriterFormat<'T> -> 'T
val averageTime : count:int -> desc:string -> f:(unit -> 'a) -> unit


 Stops the average runtime for a given function and applies it the given count
 Afterwards it reports it with the given description
val desc : string
val time : float
val sprintf : format:Printf.StringFormat<'T> -> 'T
val trials : int
val r : Random
Multiple items
type Random =
  new : unit -> Random + 1 overload
  member Next : unit -> int + 2 overloads
  member NextBytes : buffer:byte[] -> unit
  member NextDouble : unit -> float

--------------------
Random() : Random
Random(Seed: int) : Random
val initFSharpMapAndPersistentMapFromList : n:int -> unit
val n : int
Multiple items
val list : (int * string) list

--------------------
type 'T list = List<'T>
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
    interface IReadOnlyList<'T>
    interface IReadOnlyCollection<'T>
    interface IEnumerable
    interface IEnumerable<'T>
    member GetSlice : startIndex:int option * endIndex:int option -> 'T list
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    member Length : int
    member Tail : 'T list
    ...
val sortBy : projection:('T -> 'Key) -> list:'T list -> 'T list (requires comparison)
val snd : tuple:('T1 * 'T2) -> 'T2
val i : int
Random.Next() : int
Random.Next(maxValue: int) : int
Random.Next(minValue: int, maxValue: int) : int
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IReadOnlyDictionary<'Key,'Value>
  interface IReadOnlyCollection<KeyValuePair<'Key,'Value>>
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  ...

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
val ofSeq : elements:seq<'Key * 'T> -> Map<'Key,'T> (requires comparison)
val initPersistentHashMap : (seq<'a * 'b> -> 'c)
Multiple items
val list : seq<'a * 'b>

--------------------
type 'T list = List<'T>
val m : 'c ref
Multiple items
val ref : value:'T -> 'T ref

--------------------
type 'T ref = Ref<'T>
val key : 'a
val value : 'b
val initImmutableDictionary : (seq<'a * 'b> -> 'c)
val d : 'c ref
namespace System.Collections
namespace System.Collections.Immutable
Multiple items
type ImmutableDictionary<'TKey,'TValue> =
  member Add : key:'TKey * value:'TValue -> ImmutableDictionary<'TKey, 'TValue>
  member AddRange : pairs:IEnumerable<KeyValuePair<'TKey, 'TValue>> -> ImmutableDictionary<'TKey, 'TValue>
  member Clear : unit -> ImmutableDictionary<'TKey, 'TValue>
  member Contains : pair:KeyValuePair<'TKey, 'TValue> -> bool
  member ContainsKey : key:'TKey -> bool
  member ContainsValue : value:'TValue -> bool
  member Count : int
  member GetEnumerator : unit -> Enumerator<'TKey, 'TValue>
  member IsEmpty : bool
  member Item : 'TKey -> 'TValue
  ...
  nested type Builder
  nested type Enumerator

--------------------
type ImmutableDictionary =
  static member Contains<'TKey, 'TValue> : map:IImmutableDictionary<'TKey, 'TValue> * key:'TKey * value:'TValue -> bool
  static member Create<'TKey, 'TValue> : unit -> ImmutableDictionary<'TKey, 'TValue> + 2 overloads
  static member CreateBuilder<'TKey, 'TValue> : unit -> Builder<'TKey, 'TValue> + 2 overloads
  static member CreateRange<'TKey, 'TValue> : items:IEnumerable<KeyValuePair<'TKey, 'TValue>> -> ImmutableDictionary<'TKey, 'TValue> + 2 overloads
  static member GetValueOrDefault<'TKey, 'TValue> : dictionary:IImmutableDictionary<'TKey, 'TValue> * key:'TKey -> 'TValue + 1 overload
  static member ToImmutableDictionary<'TKey, 'TValue> : source:IEnumerable<KeyValuePair<'TKey, 'TValue>> -> ImmutableDictionary<'TKey, 'TValue> + 7 overloads
Multiple items
val int : value:'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int
Multiple items
val string : value:'T -> string

--------------------
type string = String
Multiple items
type ImmutableSortedDictionary<'TKey,'TValue> =
  member Add : key:'TKey * value:'TValue -> ImmutableSortedDictionary<'TKey, 'TValue>
  member AddRange : items:IEnumerable<KeyValuePair<'TKey, 'TValue>> -> ImmutableSortedDictionary<'TKey, 'TValue>
  member Clear : unit -> ImmutableSortedDictionary<'TKey, 'TValue>
  member Contains : pair:KeyValuePair<'TKey, 'TValue> -> bool
  member ContainsKey : key:'TKey -> bool
  member ContainsValue : value:'TValue -> bool
  member Count : int
  member GetEnumerator : unit -> Enumerator<'TKey, 'TValue>
  member IsEmpty : bool
  member Item : 'TKey -> 'TValue
  ...
  nested type Builder
  nested type Enumerator

--------------------
type ImmutableSortedDictionary =
  static member Create<'TKey, 'TValue> : unit -> ImmutableSortedDictionary<'TKey, 'TValue> + 2 overloads
  static member CreateBuilder<'TKey, 'TValue> : unit -> Builder<'TKey, 'TValue> + 2 overloads
  static member CreateRange<'TKey, 'TValue> : items:IEnumerable<KeyValuePair<'TKey, 'TValue>> -> ImmutableSortedDictionary<'TKey, 'TValue> + 2 overloads
  static member ToImmutableSortedDictionary<'TKey, 'TValue> : source:IEnumerable<KeyValuePair<'TKey, 'TValue>> -> ImmutableSortedDictionary<'TKey, 'TValue> + 5 overloads
val lookupInFSharpMapAndPersistentMap : n:int -> count:int -> unit
Multiple items
val list : (string * int) list

--------------------
type 'T list = List<'T>
Int32.ToString() : string
Int32.ToString(provider: IFormatProvider) : string
Int32.ToString(format: string) : string
Int32.ToString(format: string, provider: IFormatProvider) : string
val fsharpMap : Map<string,int>
val map : obj
val i : int32
val dict : obj
val d : obj ref
val key : string
val value : int
val dict' : obj
Fork me on GitHub