fsprojects/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: 
121: 
122: 
open FSharpx.Collections.PersistentHashMap

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

open FSharpx.Collections.TimeMeasurement

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 empty
        for (key,value) in list do
            m := add key value !m
        !m

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

    averageTime trials "  PersistentHashMap.ofSeq" 
        (fun () -> 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 = 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
Multiple items
namespace System.Collections

--------------------
namespace Microsoft.FSharp.Collections
val trials : int

Full name: PersistentHashMapPerformance.trials
val r : Random

Full name: PersistentHashMapPerformance.r
Multiple items
type Random =
  new : unit -> Random + 1 overload
  member Next : unit -> int + 2 overloads
  member NextBytes : buffer:byte[] -> unit
  member NextDouble : unit -> float

Full name: System.Random

--------------------
Random() : unit
Random(Seed: int) : unit
val initFSharpMapAndPersistentMapFromList : n:int -> 'a

Full name: PersistentHashMapPerformance.initFSharpMapAndPersistentMapFromList
val n : int
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
Multiple items
val list : (int * string) list

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  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
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val sortBy : projection:('T -> 'Key) -> list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sortBy
val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd
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 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
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
val ofSeq : elements:seq<'Key * 'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.ofSeq
val initPersistentHashMap : (seq<'b * 'c> -> 'd)
Multiple items
val list : seq<'b * 'c>

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val m : 'd ref
Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>
val key : 'b
val value : 'c
val initImmutableDictionary : (seq<'b * 'c> -> 'd)
val d : 'd ref
namespace System.Collections
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

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

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string
val lookupInFSharpMapAndPersistentMap : n:int -> count:int -> 'a

Full name: PersistentHashMapPerformance.lookupInFSharpMapAndPersistentMap
val count : int
Multiple items
val list : (string * int) list

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
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 dict : obj
val d : obj ref
val key : string
val value : int
val dict' : obj
Fork me on GitHub