Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Associative Map Performance Tests
-- 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 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)
-- 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
// 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);
}
}
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);
# 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))
# 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);
#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;
}
#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;
}
#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;
}
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment