dictionary_types.fs

type KeyStruct(_1':int, _2':int, _3':int) = struct
    member this._1 = _1'
    member this._2 = _2'
    member this._3 = _3'
end

type KeyGenericStruct<'a>(_1':'a, _2':'a, _3':'a) = struct
    member this._1 = _1'
    member this._2 = _2'
    member this._3 = _3'
end

type KeyRecord = { _1 : int; _2 : int; _3 : int }

type KeyGenericRecord<'a> = { _1 : 'a; _2 : 'a; _3 : 'a }

let inline RunTest<'a when 'a : equality> iterationCount createAssociativeMap (createKey:System.Func<_,_,_,'a>) =
    System.GC.Collect ()
    System.GC.WaitForFullGCComplete () |> ignore

    let data = [|
        for a in 0..99 do
            for b in 0..99 do
                for c in 0..99 do
                    yield a,b,c |]
    // shuffle
    let r = System.Random (0)
    for i = 0 to data.Length-1 do
        let j = r.Next (i, data.Length)
        let t = data.[i]
        data.[i] <- data.[j]
        data.[j] <- t

    let keyValues =
        data
        |> Array.mapi (fun i k -> k, 0.5-(float i)/(float data.Length))
        |> Array.toSeq

    let sw = System.Diagnostics.Stopwatch.StartNew ()
    let mapper = createAssociativeMap createKey keyValues
    let creationTime = sw.ElapsedMilliseconds

    let sw = System.Diagnostics.Stopwatch.StartNew ()
    let mutable checksum = 0.
    for i = 0 to iterationCount do
        let a, b, c = r.Next 100, r.Next 100, r.Next 100
        let key = createKey.Invoke(a, b, c)
        checksum <- checksum + (mapper key)
    let accessTime= sw.ElapsedMilliseconds

    printfn "checksum %f elapsed %d/%d (%s)" checksum creationTime accessTime (typeof<'a>.Name)

let RunNTrials<'a when 'a : equality> = RunTest<'a> 1000000

let createDictionary (create:System.Func<_,_,_,_>) keyValues = 
    let d = System.Collections.Generic.Dictionary<_,_> ()
    keyValues
    |> Seq.map (fun ((_1,_2,_3),value) -> create.Invoke( _1, _2, _3), value)
    |> Seq.iter (fun (key,value) -> d.[key] <- value)
    (fun key -> d.[key])

let createDictionaryStructural (create:System.Func<_,_,_,_>) keyValues = 
    let d = System.Collections.Generic.Dictionary<_,_> HashIdentity.Structural
    keyValues
    |> Seq.map (fun ((_1,_2,_3),value) -> create.Invoke( _1, _2, _3), value)
    |> Seq.iter (fun (key,value) -> d.[key] <- value)
    (fun key -> d.[key])

let createDict (create:System.Func<_,_,_,_>) keyValues =
    let d = 
        keyValues
        |> Seq.map (fun ((_1,_2,_3),value) -> create.Invoke(_1, _2, _3), value)
        |> dict
    (fun key -> d.[key])

let createSortedDictionary (create:System.Func<_,_,_,_>) keyValues = 
    let d = System.Collections.Generic.SortedDictionary<_,_> ()
    keyValues
    |> Seq.map (fun ((_1,_2,_3),value) -> create.Invoke( _1, _2, _3), value)
    |> Seq.iter (fun (key,value) -> d.[key] <- value)
    (fun key -> d.[key])

let createSortedDictionaryStructural (create:System.Func<_,_,_,_>) keyValues = 
    let d = System.Collections.Generic.SortedDictionary<_,_> ComparisonIdentity.Structural
    keyValues
    |> Seq.map (fun ((_1,_2,_3),value) -> create.Invoke( _1, _2, _3), value)
    |> Seq.iter (fun (key,value) -> d.[key] <- value)
    (fun key -> d.[key])

let createMap (create:System.Func<_,_,_,_>) keyValues =
    let d = 
        keyValues
        |> Seq.map (fun ((_1,_2,_3),value) -> create.Invoke( _1, _2, _3), value)
        |> Map.ofSeq
    (fun key -> d.[key])

let createCustomArray create keyValues =
    let maxA = 1 + (keyValues |> Seq.map (fun ((a,_,_),_) -> a) |> Seq.max)
    let maxB = 1 + (keyValues |> Seq.map (fun ((_,b,_),_) -> b) |> Seq.max)
    let maxC = 1 + (keyValues |> Seq.map (fun ((_,_,c),_) -> c) |> Seq.max)

    let createIndex a b c = a * maxB * maxC + b * maxC + c

    let values : array<float> = Array.create (maxA * maxB * maxC) 0.
    keyValues
    |> Seq.iter (fun ((a,b,c),d) -> values.[createIndex a b c] <- d)

    (fun (a,b,c) -> values.[a * maxB * maxC + b * maxC + c])

let RunDictionary<'a when 'a : equality> = RunNTrials<'a> createDictionary 
let RunDictionaryStructural<'a when 'a : equality> = RunNTrials<'a> createDictionaryStructural
let RunDict<'a when 'a : equality> = RunNTrials<'a> createDict
let RunSortedDictionary<'a when 'a : equality> = RunNTrials<'a> createSortedDictionary 
let RunSortedDictionaryStructural<'a when 'a : comparison> = RunNTrials<'a> createSortedDictionaryStructural
let RunMap<'a when 'a : comparison> = RunNTrials<'a> createMap
let RunCustomArray = RunNTrials<_> createCustomArray

[<EntryPoint>]
let main _ =
    printfn "%s\n" Id.Name

    printfn "Using .net's System.Collections.Generic.Dictionary"
    RunDictionary (System.Func<_,_,_,_>(fun a b c -> { KeyRecord._1=a; _2=b; _3=c }) )
    RunDictionary (System.Func<_,_,_,_>(fun a b c -> { KeyGenericRecord._1=a; _2=b; _3=c }))
    RunDictionary (System.Func<_,_,_,_>(fun a b c -> KeyStruct(a, b, c)))
    RunDictionary (System.Func<_,_,_,_>(fun a b c -> KeyGenericStruct(a, b, c)))
    RunDictionary (System.Func<_,_,_,_>(fun a b c -> (a, b, c)))

    printfn "Using .net's System.Collections.Generic.Dictionary (Structural Identity)"
    RunDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> { KeyRecord._1=a; _2=b; _3=c }) )
    RunDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> { KeyGenericRecord._1=a; _2=b; _3=c }))
    RunDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> KeyStruct(a, b, c)))
    RunDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> KeyGenericStruct(a, b, c)))
    RunDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> (a, b, c)))

    printfn "Using f# 'dict'"
    RunDict (System.Func<_,_,_,_>(fun a b c -> { KeyRecord._1=a; _2=b; _3=c })) 
    RunDict (System.Func<_,_,_,_>(fun a b c -> { KeyGenericRecord._1=a; _2=b; _3=c }))
    RunDict (System.Func<_,_,_,_>(fun a b c -> KeyStruct(a, b, c)))
    RunDict (System.Func<_,_,_,_>(fun a b c -> KeyGenericStruct(a, b, c)))
    RunDict (System.Func<_,_,_,_>(fun a b c -> (a, b, c)))

    printfn "Using .net's System.Collections.Generic.SortedDictionary"
    RunSortedDictionary (System.Func<_,_,_,_>(fun a b c -> { KeyRecord._1=a; _2=b; _3=c }) )
    RunSortedDictionary (System.Func<_,_,_,_>(fun a b c -> { KeyGenericRecord._1=a; _2=b; _3=c }))
    RunSortedDictionary (System.Func<_,_,_,_>(fun a b c -> KeyStruct(a, b, c)))
    RunSortedDictionary (System.Func<_,_,_,_>(fun a b c -> KeyGenericStruct(a, b, c)))
    RunSortedDictionary (System.Func<_,_,_,_>(fun a b c -> (a, b, c)))

    printfn "Using .net's System.Collections.Generic.SortedDictionary (Structural Identity)"
    RunSortedDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> { KeyRecord._1=a; _2=b; _3=c }) )
    RunSortedDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> { KeyGenericRecord._1=a; _2=b; _3=c }))
    RunSortedDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> KeyStruct(a, b, c)))
    RunSortedDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> KeyGenericStruct(a, b, c)))
    RunSortedDictionaryStructural (System.Func<_,_,_,_>(fun a b c -> (a, b, c)))

    printfn "Using f# 'Map'"
    RunMap (System.Func<_,_,_,_>(fun a b c -> { KeyRecord._1=a; _2=b; _3=c }) )
    RunMap (System.Func<_,_,_,_>(fun a b c -> { KeyGenericRecord._1=a; _2=b; _3=c }))
    RunMap (System.Func<_,_,_,_>(fun a b c -> KeyStruct(a, b, c)))
    RunMap (System.Func<_,_,_,_>(fun a b c -> KeyGenericStruct(a, b, c)))
    RunMap (System.Func<_,_,_,_>(fun a b c -> (a, b, c)))

    printfn "Using custom array"
    RunCustomArray (System.Func<_,_,_,_>(fun a b c -> (a, b, c)))

    0