Skip to content

Instantly share code, notes, and snippets.

@manofstick
Created August 17, 2015 10:12
Show Gist options
  • Save manofstick/45559f273acc34b15661 to your computer and use it in GitHub Desktop.
Save manofstick/45559f273acc34b15661 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment