(* hashtable experiments in F# *)
open System.Collections.Generic

let cmp =
    { new System.Object()
        interface IEqualityComparer<int> with
            member this.Equals(x, y)  =  x=y
            member this.GetHashCode x =  int x }

let durationMeas = new List<int64>()
let ht = Dictionary(cmp)
(* ordered insert *)
for n=10 downto 1 do
    let timer = new System.Diagnostics.Stopwatch()
    timer.Start()
    ht.Clear()
    for i=10000000 downto 1 do
        ht.[i] <- float (i+n)
    let duration = timer.ElapsedMilliseconds
    timer.Stop()
    durationMeas.Add(duration)
    printfn "."
(* find adjustments *)
let findAdjustment1 = 
    let timer = new System.Diagnostics.Stopwatch()
    let mutable x = 0.0
    timer.Start()
    for i=10000000 downto 1 do
        x = float (i+3)
    let duration = timer.ElapsedMilliseconds
    timer.Stop()
    float duration

let findAdjustment2 = 
    let timer = new System.Diagnostics.Stopwatch()
    let mutable lfsr = 1u
    let mutable x = float 0
    timer.Start()
    for i=10000000 downto 1 do
        lfsr <- (lfsr >>> 1) ^^^ ((0u - (lfsr &&& 1u)) &&& 0xd0000001u)
        x = float (i+3)
    let duration = timer.ElapsedMilliseconds
    timer.Stop()
    float duration

(* lookup *)
let lookupDuration1 =
    let mutable lfsr = 1u
    let mutable x = float 0
    let mutable res = float 0;
    let timer = new System.Diagnostics.Stopwatch()
    timer.Start()
    for i=10000000 downto 1 do
        lfsr <- (lfsr >>> 1) ^^^ ((0u - (lfsr &&& 1u)) &&& 0xd0000001u)
        let foundIt = ht.TryGetValue(int lfsr, &res)
        if foundIt then x <- x + res
    let duration = timer.ElapsedMilliseconds
    timer.Stop()
    float duration

(* report on timing *)
let mean1 = float(durationMeas |> Seq.sum) / float(durationMeas.Count)
let durationVar1 = durationMeas |> Seq.map (fun x -> (fun y -> y*y)(float(x)-mean1)) |> Seq.sum
let stdv1 : float = sqrt(durationVar1/float(durationMeas.Count))

printfn "insert timing (ordered) in seconds: mean %A, adj-mean %A, stdv %A" (mean1/1000.0) ((mean1-findAdjustment1)/1000.0) (stdv1/1000.0)
printfn "lookup timing (mostly misses) in seconds: %A, adj %A" (lookupDuration1/1000.0) ((lookupDuration1 - findAdjustment2)/1000.0)

(* unordered insert *)
durationMeas.Clear()
for n=10 downto 1 do
    let timer = new System.Diagnostics.Stopwatch()
    timer.Start()
    ht.Clear()
    let mutable lfsr = 1u
    for i=10000000 downto 1 do
        lfsr <- (lfsr >>> 1) ^^^ ((0u - (lfsr &&& 1u)) &&& 0xd0000001u)
        ht.[int lfsr] <- float (i+n)
    let duration = timer.ElapsedMilliseconds
    timer.Stop()
    durationMeas.Add(duration)
    printfn "."

(* lookup *)
let lookupDuration2 =
    let mutable lfsr = 1u
    let mutable x = float 0
    let mutable res = float 0;
    let timer = new System.Diagnostics.Stopwatch()
    timer.Start()
    for i=10000000 downto 1 do
        lfsr <- (lfsr >>> 1) ^^^ ((0u - (lfsr &&& 1u)) &&& 0xd0000001u)
        let foundIt = ht.TryGetValue(int lfsr, &res)
        if foundIt then x <- x + res
    let duration = timer.ElapsedMilliseconds
    timer.Stop()
    float duration

(* report on timing *)
let mean2 = float(durationMeas |> Seq.sum) / float(durationMeas.Count)
let durationVar2 = durationMeas |> Seq.map (fun x -> (fun y -> y*y)(float(x)-mean2)) |> Seq.sum
let stdv2 : float = sqrt(durationVar2/float(durationMeas.Count))

printfn "insert timing (unordered) in seconds: mean %A, adj-mean %A, stdv %A" (mean2/1000.0) ((mean2-findAdjustment2)/1000.0) (stdv2/1000.0)
printfn "lookup timing (no misses) in seconds: %A, adj %A" (lookupDuration2/1000.0) ((lookupDuration2 - findAdjustment2)/1000.0)