Associative Map Performance Tests

Hashmap.hs

-- compile with ghc -O3
{-# LANGUAGE ScopedTypeVariables #-}
-- hashtables in Haskell
import Text.Printf
import System.Time
-- import System.CPUTime  -- this module has some problems on OSX 10.6
import qualified Data.HashMap.Strict as H
import Data.Bits
import Data.Word

-- testing ordered insert operation
insertTest1 :: Int -> [Double] -> IO ([Double])
insertTest1 0 tl = return (tl)
insertTest1 n tl = do
    start <- getClockTime
--  strangely, this doesn't work!?!
--  start <- getCPUTime
    ht <- H.new (==) fromIntegral :: IO (H.HashTable Int Double)
    let loop 0 = return ()
        loop i = do
            H.insert ht i (fromIntegral $ i+n)
            loop (i-1)
    loop (10^7)
--  strangely, this doesn't work!?!
--  end <- getCPUTime
    end <- getClockTime
    let tdDiff = diffClockTimes end start
    -- picosecond resolution has problems on OSX 10.6!!
    let diff :: Double = (fromIntegral $ tdSec tdDiff) -- + (fromIntegral $ tdPicosec tdDiff) / (10^12)
    print n
    insertTest1 (n-1) (diff:tl)

lookupTest1 = do
    ht <- H.new (==) fromIntegral :: IO (H.HashTable Int Double)
    let loop 0 = return ()
        loop i = do
            H.insert ht i (fromIntegral $ i+3)
            loop (i-1)
    loop (10^7)
    start <- getClockTime
    let loop2 0 x lfsr = return x
        loop2 i x lfsr = do
            ans <- H.lookup ht (fromIntegral lfsr)
            let x1 = case ans of
                        Just dx -> x + dx
                        Nothing -> x
            loop2 (i-1) x1 ((lfsr `shiftR` 1) `xor` ((0 - (lfsr .&. 1)) .&. 0xd0000001::Word32))
    loop2 (10^7) 0.0 (0xd0000001 :: Word32)
    end <- getClockTime
    let tdDiff = diffClockTimes end start
    -- picosecond resolution has problems on OSX 10.6!!
    let diff :: Double = (fromIntegral $ tdSec tdDiff) -- + (fromIntegral $ tdPicosec tdDiff) / (10^12)
    return diff
    
-- testing pseudo random insert operation (GLFSR)
insertTest2 :: Int -> [Double] -> IO ([Double])
insertTest2 0 tl = return (tl)
insertTest2 n tl = do
    start <- getClockTime
    ht <- H.new (==) fromIntegral :: IO (H.HashTable Int Double)
    let loop 0 _ = return ()
        loop i lfsr = do
            H.insert ht (fromIntegral lfsr) (fromIntegral $ i+n)
            loop (i-1) ((lfsr `shiftR` 1) `xor` ((0 - (lfsr .&. 1)) .&. 0xd0000001::Word32))
    loop (10^7) (0xd0000001 :: Word32)
    end <- getClockTime
    let tdDiff = diffClockTimes end start
    -- picosecond resolution has problems on OSX 10.6!!
    let diff :: Double = (fromIntegral $ tdSec tdDiff) -- + (fromIntegral $ tdPicosec tdDiff) / (10^12)
    print n
    insertTest2 (n-1) (diff:tl)

lookupTest2 = do
    ht <- H.new (==) fromIntegral :: IO (H.HashTable Int Double)
    let loop 0 _ = return ()
        loop i lfsr = do
            H.insert ht (fromIntegral lfsr) (fromIntegral $ i+3)
            loop (i-1) ((lfsr `shiftR` 1) `xor` ((0 - (lfsr .&. 1)) .&. 0xd0000001::Word32))
    loop (10^7) (0xd0000001 :: Word32)
    start <- getClockTime
    let loop2 0 x lfsr = return x
        loop2 i x lfsr = do
            ans <- H.lookup ht (fromIntegral lfsr)
            let x1 = case ans of
                        Just dx -> x + dx
                        Nothing -> x
            loop2 (i-1) x1 ((lfsr `shiftR` 1) `xor` ((0 - (lfsr .&. 1)) .&. 0xd0000001::Word32))
    loop2 (10^7) 0.0 (0xd0000001 :: Word32)
    end <- getClockTime
    let tdDiff = diffClockTimes end start
    -- picosecond resolution has problems on OSX 10.6!!
    let diff :: Double = (fromIntegral $ tdSec tdDiff) -- + (fromIntegral $ tdPicosec tdDiff) / (10^12)
    return diff

stats :: [Double] -> (Double, Double)
stats [] = (0.0, 0.0)
stats xs = (mean, stdv)
            where
                size = length xs
                mean = (sum xs) / (fromIntegral size)
                stdv = sqrt $ (foldl (\v x -> v + (x-mean)**2) 0.0 xs) / (fromIntegral size)

main :: IO ()
main = do
    measurement2 <- insertTest1 20 []
    let (m2, s2) = stats measurement2
    printf "Insert timing (unordered) in sec.: mean %.2f, stdv %.2f\n" m2 s2
    timing2 <- lookupTest2
    printf "Lookup timing (no misses) in sec.: %.2f\n" timing2
    measurement1 <- insertTest1 20 []
    let (m1, s1) = stats measurement1
    printf "Insert timing (ordered) in sec.: mean %.2f, stdv %.2f\n" m1 s1
    timing1 <- lookupTest1
    printf "Lookup timing (mostly misses) in sec.: %.2f\n" timing1

Hashtable.fs

(* 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)

Hashtable.hs

-- compile with ghc -O3
{-# LANGUAGE ScopedTypeVariables #-}
-- hashtables in Haskell
import Text.Printf
import System.Time
-- import System.CPUTime  -- this module has some problems on OSX 10.6
import qualified Data.HashTable as H
import Data.Bits
import Data.Word

-- testing ordered insert operation
insertTest1 :: Int -> [Double] -> IO ([Double])
insertTest1 0 tl = return (tl)
insertTest1 n tl = do
    start <- getClockTime
--  strangely, this doesn't work!?!
--  start <- getCPUTime
    ht <- H.new (==) fromIntegral :: IO (H.HashTable Int Double)
    let loop 0 = return ()
        loop i = do
            H.insert ht i (fromIntegral $ i+n)
            loop (i-1)
    loop (10^7)
--  strangely, this doesn't work!?!
--  end <- getCPUTime
    end <- getClockTime
    let tdDiff = diffClockTimes end start
    -- picosecond resolution has problems on OSX 10.6!!
    let diff :: Double = (fromIntegral $ tdSec tdDiff) -- + (fromIntegral $ tdPicosec tdDiff) / (10^12)
    print n
    insertTest1 (n-1) (diff:tl)

lookupTest1 = do
    ht <- H.new (==) fromIntegral :: IO (H.HashTable Int Double)
    let loop 0 = return ()
        loop i = do
            H.insert ht i (fromIntegral $ i+3)
            loop (i-1)
    loop (10^7)
    start <- getClockTime
    let loop2 0 x lfsr = return x
        loop2 i x lfsr = do
            ans <- H.lookup ht (fromIntegral lfsr)
            let x1 = case ans of
                        Just dx -> x + dx
                        Nothing -> x
            loop2 (i-1) x1 ((lfsr `shiftR` 1) `xor` ((0 - (lfsr .&. 1)) .&. 0xd0000001::Word32))
    loop2 (10^7) 0.0 (0xd0000001 :: Word32)
    end <- getClockTime
    let tdDiff = diffClockTimes end start
    -- picosecond resolution has problems on OSX 10.6!!
    let diff :: Double = (fromIntegral $ tdSec tdDiff) -- + (fromIntegral $ tdPicosec tdDiff) / (10^12)
    return diff
    
-- testing pseudo random insert operation (GLFSR)
insertTest2 :: Int -> [Double] -> IO ([Double])
insertTest2 0 tl = return (tl)
insertTest2 n tl = do
    start <- getClockTime
    ht <- H.new (==) fromIntegral :: IO (H.HashTable Int Double)
    let loop 0 _ = return ()
        loop i lfsr = do
            H.insert ht (fromIntegral lfsr) (fromIntegral $ i+n)
            loop (i-1) ((lfsr `shiftR` 1) `xor` ((0 - (lfsr .&. 1)) .&. 0xd0000001::Word32))
    loop (10^7) (0xd0000001 :: Word32)
    end <- getClockTime
    let tdDiff = diffClockTimes end start
    -- picosecond resolution has problems on OSX 10.6!!
    let diff :: Double = (fromIntegral $ tdSec tdDiff) -- + (fromIntegral $ tdPicosec tdDiff) / (10^12)
    print n
    insertTest2 (n-1) (diff:tl)

lookupTest2 = do
    ht <- H.new (==) fromIntegral :: IO (H.HashTable Int Double)
    let loop 0 _ = return ()
        loop i lfsr = do
            H.insert ht (fromIntegral lfsr) (fromIntegral $ i+3)
            loop (i-1) ((lfsr `shiftR` 1) `xor` ((0 - (lfsr .&. 1)) .&. 0xd0000001::Word32))
    loop (10^7) (0xd0000001 :: Word32)
    start <- getClockTime
    let loop2 0 x lfsr = return x
        loop2 i x lfsr = do
            ans <- H.lookup ht (fromIntegral lfsr)
            let x1 = case ans of
                        Just dx -> x + dx
                        Nothing -> x
            loop2 (i-1) x1 ((lfsr `shiftR` 1) `xor` ((0 - (lfsr .&. 1)) .&. 0xd0000001::Word32))
    loop2 (10^7) 0.0 (0xd0000001 :: Word32)
    end <- getClockTime
    let tdDiff = diffClockTimes end start
    -- picosecond resolution has problems on OSX 10.6!!
    let diff :: Double = (fromIntegral $ tdSec tdDiff) -- + (fromIntegral $ tdPicosec tdDiff) / (10^12)
    return diff

stats :: [Double] -> (Double, Double)
stats [] = (0.0, 0.0)
stats xs = (mean, stdv)
            where
                size = length xs
                mean = (sum xs) / (fromIntegral size)
                stdv = sqrt $ (foldl (\v x -> v + (x-mean)**2) 0.0 xs) / (fromIntegral size)

main :: IO ()
main = do
    measurement2 <- insertTest1 20 []
    let (m2, s2) = stats measurement2
    printf "Insert timing (unordered) in sec.: mean %.2f, stdv %.2f\n" m2 s2
    timing2 <- lookupTest2
    printf "Lookup timing (no misses) in sec.: %.2f\n" timing2
    measurement1 <- insertTest1 20 []
    let (m1, s1) = stats measurement1
    printf "Insert timing (ordered) in sec.: mean %.2f, stdv %.2f\n" m1 s1
    timing1 <- lookupTest1
    printf "Lookup timing (mostly misses) in sec.: %.2f\n" timing1

HashTable.java

// provide plenty of heap memory java -Xmx1500m ...
import java.util.*;

public class HashTable {

    public static void main(String[] args) {
        long insertDurationSum = 0;
        long[] insertDurationMeas = new long[10];
        final Hashtable<Integer,Double> ht = new Hashtable<Integer,Double>();

        // ordered insert
        for(int n=10; n>0; n--) {
            long startTime = System.nanoTime();
            ht.clear();

            for(int i=10000000; i>0; i--)
                ht.put(new Integer(i), new Double((double)(i+n)));

            long duration = System.nanoTime() - startTime;
            insertDurationSum += duration;
            insertDurationMeas[n-1] = duration;
            System.out.println(n);
        }

        // find adjustment
        long startTime = System.nanoTime();
        Double tmp;
        for(int i=10000000; i>0; i--)
            tmp = new Double((double)(i+3));
        long adjustment1 = System.nanoTime() - startTime;

        // lookup test
        startTime = System.nanoTime();
        long lfsr = 1; // Java doesn't have unsigned types
        double x = 0.0;
        for(int i=10000000; i>0; i--) {

            lfsr = (lfsr >> 1) ^ (0 - (lfsr & 1L) & 0xd0000001L);
            Double val = ht.get(lfsr);
            if (val != null)
              x += val.doubleValue();
        }
        long lookupDuration = System.nanoTime() - startTime;

        // find adjustment
        startTime = System.nanoTime();
        lfsr = 1;
        for(int i=10000000; i>0; i--)
            lfsr = (lfsr >> 1) ^ (0 - (lfsr & 1L) & 0xd0000001L);
        long adjustment = System.nanoTime() - startTime;

        // report on timing
        long durationMean = insertDurationSum/10;
        long durationVar = 0;
        for(long dv : insertDurationMeas) {
          durationVar += (dv - durationMean)*(dv - durationMean);
        }
        double mean = new Double(durationMean)/(1e9);
        double adj1 = new Double(adjustment1)/(1e9);
        double stdv = Math.sqrt(new Double(durationVar/10))/(1e9);
        System.out.format("insert timing (ordered) in seconds: ");
        System.out.format("mean %.3f, adj-mean %.3f, stdv %.3f\n",mean,mean-adj1,stdv);
        double lookup = new Double(lookupDuration)/(1e9);
        double lookupadj = new Double(lookupDuration-adjustment)/(1e9);
        System.out.format("lookup timing (mostly misses) in seconds: %.3f, adj %.3f\n", lookup, lookupadj);

        // unordered insert
        insertDurationSum = 0;
        for(int n=10; n>0; n--) {
            startTime = System.nanoTime();
            ht.clear();
            lfsr = 1; // Java doesn't have unsigned types

            for(int i=10000000; i>0; i--) {
                lfsr = (lfsr >> 1) ^ (0 - (lfsr & 1L) & 0xd0000001L);
                ht.put(new Integer((int)lfsr), new Double((double)(i+n)));
            }
            long duration = System.nanoTime() - startTime;
            insertDurationSum += duration;
            insertDurationMeas[n-1] = duration;
            System.out.println(n);
        }
        
        // find adjustment
        startTime = System.nanoTime();
        lfsr = 1;
        for(int i=10000000; i>0; i--) {
            lfsr = (lfsr >> 1) ^ (0 - (lfsr & 1L) & 0xd0000001L);
            tmp = new Double((double)(i+3));
        }
        adjustment1 = System.nanoTime() - startTime;
        
        // lookup test
        startTime = System.nanoTime();
        lfsr = 1; // Java doesn't have unsigned types
        x = 0.0;
        for(int i=10000000; i>0; i--) {

            lfsr = (lfsr >> 1) ^ (0 - (lfsr & 1L) & 0xd0000001L);
            Double val = ht.get(lfsr);
            if (val != null)
              x += val.doubleValue();
        }
        lookupDuration = System.nanoTime() - startTime;

        // report on timing
        durationMean = insertDurationSum/10;
        durationVar = 0;
        for(long dv : insertDurationMeas) {
          durationVar += (dv - durationMean)*(dv - durationMean);
        }
        mean = new Double(durationMean)/(1e9);
        adj1 = new Double(adjustment1)/(1e9);
        stdv = Math.sqrt(new Double(durationVar/10))/(1e9);
        System.out.format("insert timing (unordered) in seconds: ");
        System.out.format("mean %.3f, adj-mean %.3f, stdv %.3f\n",mean,mean-adj1,stdv);
        lookup = new Double(lookupDuration)/(1e9);
        lookupadj = new Double(lookupDuration-adjustment)/(1e9);
        System.out.format("lookup timing (no misses) in seconds: %.3f, adj %.3f\n", lookup, lookupadj);
    }
}

Hashtable.pl

use Time::HiRes qw( time );

# ordered insert
$insertDurationSum = 0.0;
@insertDurationMeas = ();
for ($n = 10; $n > 0; $n--) {
    $start = time();
    my %ht = ();
    for ($i = 10000000; $i > 0; $i--) {
        $ht{$i} = $i + $n + 0.0;
    }
    $end = time();
    $duration = $end - $start;
    $insertDurationSum += $duration;
    push(@insertDurationMeas, $duration);
    print "$n\n";
}
# find adjustment
$start = time();
$x = 0.0;
for ($i = 10000000; $i > 0; $i--) {
    $x = $i + 3.0;
}
$end = time();
$adjustment = $end - $start;
# report on timing
$mean = $insertDurationSum/10.0;
$durationVar = 0.0;
foreach $v (@insertDurationMeas) {
    $durationVar += ($v-$mean)*($v-$mean);
}
$stdv = sqrt($durationVar/10.0);
printf("insert timing (ordered) in seconds: mean %.2f, adj-mean %.2f, stdv %.2f\n", $mean, $mean - $adjustment, $stdv);
# lookup test
$start = time();
$lfsr = 1;
$x = 0.0;
for ($i = 10000000; $i > 0; $i--) {
    $lfsr = ($lfsr >> 1) ^ (0 - ($lfsr & 1) & 0xd0000001);
    $x += $ht{$lfsr}
}
$end = time();
$lookupDuration = $end - $start;
# find adjustment
$start = time();
$lfsr = 1;
$x = 0.0;
for ($i = 10000000; $i > 0; $i--) {
    $lfsr = ($lfsr >> 1) ^ (0 - ($lfsr & 1) & 0xd0000001);
    $x += $i
}
$end = time();
$adjustment = $end - $start;
printf("lookup timing (mostly misses) in seconds: %.2f, adj %.2f\n", $lookupDuration, $lookupDuration-$adjustment);

# unordered insert
$insertDurationSum = 0.0;
@insertDurationMeas = ();
for ($n = 10; $n > 0; $n--) {
    $start = time();
    my %ht = ();
    $lfsr = 1;
    for ($i = 10000000; $i > 0; $i--) {
        $lfsr = ($lfsr >> 1) ^ (0 - ($lfsr & 1) & 0xd0000001);
        $ht{$lfsr} = $i + $n + 0.0;
    }
    $end = time();
    $duration = $end - $start;
    $insertDurationSum += $duration;
    push(@insertDurationMeas, $duration);
    print "$n\n";
}
# find adjustment
$start = time();
$lfsr = 1;
$x = 0.0;
for ($i = 10000000; $i > 0; $i--) {
    $lfsr = ($lfsr >> 1) ^ (0 - ($lfsr & 1) & 0xd0000001);
    $x = $i + 3.0
}
$end = time();
$adjustment = $end - $start;
# report on timing
$mean = $insertDurationSum/10.0;
$durationVar = 0.0;
foreach $v (@insertDurationMeas) {
    $durationVar += ($v-$mean)*($v-$mean);
}
$stdv = sqrt($durationVar/10.0);
printf("insert timing (unordered) in seconds: mean %.2f, adj-mean %.2f, stdv %.2f\n", $mean, $mean - $adjustment, $stdv);
# lookup test
$start = time();
$lfsr = 1;
$x = 0.0;
for ($i = 10000000; $i > 0; $i--) {
    $lfsr = ($lfsr >> 1) ^ (0 - ($lfsr & 1) & 0xd0000001);
    $x += $ht{$lfsr}
}
$end = time();
$lookupDuration = $end - $start;
# find adjustment
$start = time();
$lfsr = 1;
$x = 0.0;
for ($i = 10000000; $i > 0; $i--) {
    $lfsr = ($lfsr >> 1) ^ (0 - ($lfsr & 1) & 0xd0000001);
    $x += $i;
}
$end = time();
$adjustment = $end - $start;
printf("lookup timing (no misses) in seconds: %.2f, adj %.2f\n", $lookupDuration, $lookupDuration-$adjustment);

Hashtable.py

# hashtables in Python
from functools import reduce # needed for python 3
from math import sqrt
from time import time

durationSum = 0.0
durationMeas = []
for n in range(10,0,-1):
    startTime = time()
    ht = {}
    # use xrange as the generator (2.6), python 3 range is default
    [ht.setdefault(i,float(n+i)) for i in xrange(10000000,0,-1)]
    duration = time() - startTime
    durationSum = durationSum + duration
    durationMeas.append(duration)
    print n
# find adjustment
startTime = time()
[float(3+i) for i in xrange(10000000,0,-1)]
adjustment = time() - startTime
# report on timing
meanT = durationSum / 10.0
stdv = sqrt(reduce(lambda x, y: x + (y-meanT)*(y-meanT), durationMeas, 0.0) / 10.0)
print("insert timing (ordered) in seconds: mean %.3f, adj-mean %.3f, stdv %.3f" % (meanT,meanT-adjustment,stdv))
# lookup timing
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), ht.get(lfsr,0)+x), xrange(0,10000000), (lfsr1,0.0))
lookupDuration = time() - startTime
# find adjustment
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), x), xrange(0,10000000), (lfsr1,0.0))
adjustment = time() - startTime
# report on timing
print("lookup timing (mostly misses) in seconds: %.3f, adj %.3f\n" % (lookupDuration, lookupDuration-adjustment))

# unordered insert
durationSum = 0.0
durationMeas = []
for n in range(10,0,-1):
    startTime = time()
    ht = {}
    lfsr0 = 1
    lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
    reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001),ht.setdefault(lfsr,float(n+i))), xrange(10000000,0,-1), (lfsr1,0.0))
    duration = time() - startTime
    durationSum = durationSum + duration
    durationMeas.append(duration)
    print n
# find adjustment
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), x), xrange(0,10000000), (lfsr1,0.0))
adjustment = time() - startTime
# report on timing
meanT = durationSum / 10.0
stdv = sqrt(reduce(lambda x, y: x + (y-meanT)*(y-meanT), durationMeas, 0.0) / 10.0)
print("insert timing (unordered) in seconds: mean %.3f, adj-mean %.3f, stdv %.3f" % (meanT,meanT-adjustment,stdv))
# lookup timing
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), ht.get(lfsr,0)+x), xrange(0,10000000), (lfsr1,0.0))
lookupDuration = time() - startTime
# find adjustment
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), x), xrange(0,10000000), (lfsr1,0.0))
adjustment = time() - startTime
# report on timing
print("lookup timing (no misses) in seconds: %.3f, adj %.3f\n" % (lookupDuration, lookupDuration-adjustment))

Hashtable.rb

# hashtables in Ruby
require "benchmark"

maxiter = 10000000

ht = Hash.new
durationMeas = []
durationSum = 0.0
10.step(1,-1) do |n|
    duration = Benchmark.realtime do
      ht.clear
      maxiter.step(1,-1) {|i| ht[i] = Float(i+n)}
    end
    durationSum = durationSum + duration
    durationMeas.push duration
    puts n
end
adjustment = Benchmark.realtime do
    maxiter.step(1,-1) {|i| Float(i+3)}
end

mean = durationSum/10.0
stdv = Math.sqrt(durationMeas.inject(0.0) {|var, m| var + (m-mean)**2}/10.0)
printf("insert time (ordered) in seconds: mean %.3f, adj-mean %.3f, stdv %.3f\n", mean, mean-adjustment,stdv)

Accum = Struct.new(:lfsr, :x)

duration = Benchmark.realtime do
    (1..maxiter).inject(Accum.new(1,0.0)) { |a,i| nlfsr = (a.lfsr >> 1) ^ (0 - (a.lfsr & 1) & 0xd0000001); val = ht[nlfsr]; nx = a.x + (val.nil? ? 0 : val); a.lfsr = nlfsr; a.x = nx; a }
end
adjustment = Benchmark.realtime do
    (1..maxiter).inject(Accum.new(1,0.0)) { |a,i| nlfsr = (a.lfsr >> 1) ^ (0 - (a.lfsr & 1) & 0xd0000001); val = 0; nx = a.x + (val.nil? ? 0 : val); a.lfsr = nlfsr; a.x = nx; a }
end
printf("lookup timing (mostly misses) in seconds: %.3f, adj %.3f\n", duration, duration-adjustment)

durationMeas = []
durationSum = 0.0
10.step(1,-1) do |n|
    duration = Benchmark.realtime do
      ht.clear
      (1..maxiter).inject(1) { |lfsr,i| nlfsr = (lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001); ht[nlfsr] = Float(i+n); nlfsr; }
    end
    durationSum = durationSum + duration
    durationMeas.push duration
    puts n
end
adjustment = Benchmark.realtime do
    (1..maxiter).inject(1) { |lfsr,i| nlfsr = (lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001); Float(i+3); nlfsr; }
end

mean = durationSum/10.0
stdv = Math.sqrt(durationMeas.inject(0.0) {|var, m| var + (m-mean)**2}/10.0)
printf("insert time (unordered) in seconds: mean %.3f, adj-mean %.3f, stdv %.3f\n", mean, mean-adjustment, stdv)

duration = Benchmark.realtime do
    (1..maxiter).inject(Accum.new(1,0.0)) { |a,i| nlfsr = (a.lfsr >> 1) ^ (0 - (a.lfsr & 1) & 0xd0000001); val = ht[nlfsr]; nx = a.x + (val.nil? ? 0 : val); a.lfsr = nlfsr; a.x = nx; a }
end
adjustment = Benchmark.realtime do
    (1..maxiter).inject(Accum.new(1,0.0)) { |a,i| nlfsr = (a.lfsr >> 1) ^ (0 - (a.lfsr & 1) & 0xd0000001); val = 0; nx = a.x + (val.nil? ? 0 : val); a.lfsr = nlfsr; a.x = nx; a }
end
printf("lookup timing (no misses) in seconds: %.3f, adj %.3f\n", duration, duration-adjustment);

HashtableV1.cc

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <map>

#define RANDOM 1

int main()
{
    std::map<unsigned, double> ht;
    double insertDurationMeas[10];
    double insertDurationSum = 0.0;
    time_t begin, end; 

    for(int n=10000000; n>0; n--) {

        time(&begin);
        ht.clear();
        unsigned lfsr = 1;
        for(int i=10; i>0; i--) {

            lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u); 
#ifdef RANDOM
            ht[lfsr] = (double)(i+n);
#else
            ht[i] = (double)(i+n);
#endif
        }
        time(&end);
        double duration = difftime(end, begin);
        insertDurationSum += duration;
        insertDurationMeas[n-1] = duration;
        printf("%.1f\n", ht[42]);
    }

    // random lookups
    time(&begin);
    unsigned lfsr = 1;
    double x = 0.0;
    for(int i=10000000; i>0; i--) {

        lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u);
        x += ht[lfsr];
    }
    time(&end);
    double lookupDuration = difftime(end, begin);

    // report on timing
    double mean = insertDurationSum/10.0;
    double durationVar = 0.0;
    for(int i=0; i<10; i++)
        durationVar += (insertDurationMeas[i]-mean)*(insertDurationMeas[i]-mean);

    double stdv = sqrt(durationVar/10.0);
    printf("insert timing in seconds: mean %.3f, stdv %.3f\n",mean,stdv);
    printf("lookup timing in seconds: %.3f\n",lookupDuration);
    return 0;
}

HashtableV2.cc

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <ext/hash_map>

//#define RANDOM 1

using namespace std;
using namespace __gnu_cxx;
struct eqint{
  bool operator()(const unsigned i1, const unsigned i2) const {
    return i1 == i2;
  }
};

int main()
{
    hash_map<unsigned, double, hash<unsigned>, eqint> ht;
    double insertDurationMeas[10];
    double insertDurationSum = 0.0;
    time_t begin, end; 

    for(int n=10; n>0; n--) {

        time(&begin);
        ht.clear();
        unsigned lfsr = 1;
        for(int i=10000000; i>0; i--) {

            lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u); 
#ifdef RANDOM
            ht[lfsr] = (double)(i+n);
#else
            ht[i] = (double)(i+n);
#endif
        }
        time(&end);
        double duration = difftime(end, begin);
        insertDurationSum += duration;
        insertDurationMeas[n-1] = duration;
        printf("%.1f\n", ht[42]);
    }

    // random lookups
    time(&begin);
    unsigned lfsr = 1;
    double x = 0.0;
    for(int i=10000000; i>0; i--) {

        lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u); 
        x += ht[lfsr];
    }
    time(&end);
    double lookupDuration = difftime(end, begin);

    // report on timing
    double mean = insertDurationSum/10.0;
    double durationVar = 0.0;
    for(int i=0; i<10; i++)
        durationVar += (insertDurationMeas[i]-mean)*(insertDurationMeas[i]-mean);

    double stdv = sqrt(durationVar/10.0);
    printf("insert timing in seconds: mean %.3f, stdv %.3f\n",mean,stdv);
    printf("lookup timing in seconds: %.3f\n",lookupDuration);
    return 0;
}

HashtableV3.cc

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <ext/hash_map>
#include <google/dense_hash_map>

//#define RANDOM 1

using google::dense_hash_map;  
using namespace std;
using namespace __gnu_cxx;

struct eqint{
  bool operator()(const unsigned i1, const unsigned i2) const {
    return i1 == i2;
  }
};

int main()
{
    dense_hash_map<unsigned, double, hash<unsigned>, eqint> ht;
    ht.set_empty_key(NULL);
    double insertDurationMeas[10];
    double insertDurationSum = 0.0;
    time_t begin, end; 

    // ordered/unordered integer keys
    for(int n=10; n>0; n--) {

        time(&begin);
        ht.clear();
        unsigned lfsr = 1;
        for(int i=10000000; i>0; i--) {

            lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u); 
#ifdef RANDOM
            ht[lfsr] = (double)(i+n);
#else
            ht[i] = (double)(i+n);
#endif
        }
        time(&end);
        double duration = difftime(end, begin);
        insertDurationSum += duration;
        insertDurationMeas[n-1] = duration;
        printf("%.3f\n", ht[42]); // thought as prograss indicator
    }

    // random lookups
    time(&begin);
    unsigned lfsr = 1;
    double x = 0.0;
    for(int i=10000000; i>0; i--) {

        lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u); 
        x += ht[lfsr];
    }
    time(&end);
    double lookupDuration = difftime(end, begin);

    // report on timing
    double mean = insertDurationSum/10.0;
    double durationVar = 0.0;
    for(int i=0; i<10; i++)
        durationVar += (insertDurationMeas[i]-mean)*(insertDurationMeas[i]-mean);

    double stdv = sqrt(durationVar/10.0);
    printf("insert timing in seconds: mean %.3f, stdv %.3f\n",mean,stdv);
    printf("lookup timing in seconds: %.3f\n",lookupDuration);
    return 0;
}

HashtableV4.cc

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <ext/hash_map>
#include <google/sparse_hash_map>

#define RANDOM 1

using google::sparse_hash_map;  
using namespace std;
using namespace __gnu_cxx;

struct eqint{
  bool operator()(const unsigned i1, const unsigned i2) const {
    return i1 == i2;
  }
};

int main()
{
    sparse_hash_map<unsigned, double, hash<unsigned>, eqint> ht;
    ht.set_deleted_key(NULL);
    
    double insertDurationMeas[10];
    double insertDurationSum = 0.0;
    time_t begin, end; 

    // ordered/unordered integer keys
    for(int n=10; n>0; n--) {

        time(&begin);
        ht.clear();
        unsigned lfsr = 1;
        for(int i=10000000; i>0; i--) {

            lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u); 
#ifdef RANDOM
            ht[lfsr] = (double)(i+n);
#else
            ht[i] = (double)(i+n);
#endif
        }
        time(&end);
        double duration = difftime(end, begin);
        insertDurationSum += duration;
        insertDurationMeas[n-1] = duration;
        printf("%.3f\n", ht[42]); // thought as prograss indicator
    }

    // random lookups
    time(&begin);
    unsigned lfsr = 1;
    double x = 0.0;
    for(int i=10000000; i>0; i--) {

        lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u); 
        x += ht[lfsr];
    }
    time(&end);
    double lookupDuration = difftime(end, begin);

    // report on timing
    double mean = insertDurationSum/10.0;
    double durationVar = 0.0;
    for(int i=0; i<10; i++)
        durationVar += (insertDurationMeas[i]-mean)*(insertDurationMeas[i]-mean);

    double stdv = sqrt(durationVar/10.0);
    printf("insert timing in seconds: mean %.3f, stdv %.3f\n",mean,stdv);
    printf("lookup timing in seconds: %.3f\n",lookupDuration);
    return 0;
}