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