fsprojects/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: 
100: 
101: 
open FSharpx.Collections.PersistentVector

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

open FSharpx.Collections.TimeMeasurement

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 empty
        for x in list do
            v := 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 () -> 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 = 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 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 = 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 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
Multiple items
namespace System.Collections

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

Full name: PersistentVectorPerformance.trials
val r : Random

Full name: PersistentVectorPerformance.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 initArrayAndVectorFromList : n:int -> 'a

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

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
Multiple items
val list : int list

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

Full name: Microsoft.FSharp.Collections.list<_>
val i : int
Random.Next() : int
Random.Next(maxValue: int) : int
Random.Next(minValue: int, maxValue: int) : int
val initvector : (seq<'b> -> 'c)
Multiple items
val list : seq<'b>

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

Full name: Microsoft.FSharp.Collections.list<_>
val v : 'c 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 x : 'b
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
  ...

Full name: System.Array
val ofSeq : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Array.ofSeq
val lookupInArrayAndVector : n:int -> count:int -> 'a

Full name: PersistentVectorPerformance.lookupInArrayAndVector
val count : int
Multiple items
val array : int []

--------------------
type 'T array = 'T []

Full name: Microsoft.FSharp.Core.array<_>
val vector : obj
val replaceInArrayAndVector : n:int -> count:int -> 'a

Full name: PersistentVectorPerformance.replaceInArrayAndVector
Fork me on GitHub