FSharpx.Collections


PersistentVector - Performance tests

Bulk operations on PersistentVector use an internal TransientVector 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: 
open FSharpx.Collections

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

let initArrayAndVectorFromList n =
    sprintf "Init with n = %d" n |> printInFsiTags
    let list = [for i in 1..n -> r.Next()]

    let initvector list = 
        let v = ref PersistentVector.empty
        for x in list do
            v := PersistentVector.conj x !v
        !v

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

    averageTime trials "  Multiple PersistentVector.conj" 
        (fun () -> initvector list)

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

let lookupInArrayAndVector n count =
    sprintf "%d Lookups in size n = %d" count n |> printInFsiTags
    let list = [for i in 1..n -> r.Next()]
    let array = Array.ofSeq list
    let vector = PersistentVector.ofSeq list

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

    averageTime trials "  PersistentVector" 
        (fun () -> for i in 1..count do PersistentVector.nth (r.Next n) vector)


let replaceInArrayAndVector n count =
    sprintf "%d writes in size n = %d" count n |> printInFsiTags
    let list = [for i in 1..n -> r.Next()]
    let array = Array.ofSeq list
    let vector = PersistentVector.ofSeq list

    averageTime trials "  Array" 
        (fun () -> for i in 1..count do array.[r.Next n] <- r.Next())

    averageTime trials "  PersistentVector" 
        (fun () -> for i in 1..count do PersistentVector.update (r.Next n) (r.Next()) vector)

initArrayAndVectorFromList 10000
initArrayAndVectorFromList 100000
initArrayAndVectorFromList 1000000

lookupInArrayAndVector 10000 10000
lookupInArrayAndVector 100000 10000
lookupInArrayAndVector 1000000 10000
lookupInArrayAndVector 10000000 10000

replaceInArrayAndVector 10000 10000
replaceInArrayAndVector 100000 10000
replaceInArrayAndVector 1000000 10000
replaceInArrayAndVector 10000000 10000

Init with n = 10000
  Array.ofSeq 0.0ms
  Multiple PersistentVector.conj 4.2ms
  PersistentVector.ofSeq 2.0ms
Init with n = 100000
  Array.ofSeq 0.4ms
  Multiple PersistentVector.conj 43.0ms
  PersistentVector.ofSeq 18.4ms
Init with n = 1000000
  Array.ofSeq 5.2ms
  Multiple PersistentVector.conj 429.6ms
  PersistentVector.ofSeq 251.2ms
10000 Lookups in size n = 10000
  Array 0.2ms
  PersistentVector 0.6ms
10000 Lookups in size n = 100000
  Array 0.0ms
  PersistentVector 0.6ms
10000 Lookups in size n = 1000000
  Array 0.0ms
  PersistentVector 1.8ms
10000 Lookups in size n = 10000000
  Array 0.0ms
  PersistentVector 3.2ms
10000 writes in size n = 10000
  Array 0.2ms
  PersistentVector 6.4ms
10000 writes in size n = 100000
  Array 0.2ms
  PersistentVector 8.2ms
10000 writes in size n = 1000000
  Array 0.4ms
  PersistentVector 11.4ms
10000 writes in size n = 10000000
  Array 1.0ms
  PersistentVector 24.2ms
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 initArrayAndVectorFromList : n:int -> unit
val n : int
Multiple items
val list : int list

--------------------
type 'T list = List<'T>
val i : int
Random.Next() : int
Random.Next(maxValue: int) : int
Random.Next(minValue: int, maxValue: int) : int
val initvector : (seq<'a> -> 'b)
Multiple items
val list : seq<'a>

--------------------
type 'T list = List<'T>
val v : 'b ref
Multiple items
val ref : value:'T -> 'T ref

--------------------
type 'T ref = Ref<'T>
val x : 'a
type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...
val ofSeq : source:seq<'T> -> 'T []
val lookupInArrayAndVector : n:int -> count:int -> unit
Multiple items
val array : int []

--------------------
type 'T array = 'T []
val vector : obj
val i : int32
val replaceInArrayAndVector : n:int -> count:int -> unit
Fork me on GitHub