Created
December 12, 2012 00:13
-
-
Save fkuehnel/4263654 to your computer and use it in GitHub Desktop.
Associative Map Performance Tests
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(* 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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