Skip to content

Instantly share code, notes, and snippets.

@AdamStelmaszczyk

AdamStelmaszczyk/slow.hs

Last active June 13, 2017 20:23
Show Gist options
  • Save AdamStelmaszczyk/f9a5d156a752fbe6c71652866fed9770 to your computer and use it in GitHub Desktop.
Save AdamStelmaszczyk/f9a5d156a752fbe6c71652866fed9770 to your computer and use it in GitHub Desktop.
Download ZIP
hashtables
Raw
slow.hs
import Data.List
import qualified Data.HashTable.IO as H
import Data.Maybe (fromJust)
type HashTable k v = H.BasicHashTable k v
(!) :: IO (HashTable Int Int) -> Int -> IO Int
(!) m k = do
h <- m
x <- H.lookup h k
return (fromJust x)
problem :: Int -> IO (Int)
problem n = sieve (H.fromListWithSizeHint (2 * r) [(i, i * (i + 1) `div` 2 - 1) | i <- vs]) n 2 r vs
where vs = [n `div` i | i <- [1..r]] ++ [n', n' - 1 .. 1]
r = floor (sqrt (fromIntegral n))
n' = n `div` r - 1
sieve :: IO (HashTable Int Int) -> Int -> Int -> Int -> [Int] -> IO (Int)
sieve m n p r vs | p > r = do
result <- m ! n
return result
| otherwise = do
a <- m ! p
b <- m ! (p - 1)
result <- sieve (if a > b then update m vs p else m) n (p + 1) r vs
return result
update :: IO (HashTable Int Int) -> [Int] -> Int -> IO (HashTable Int Int)
update m vs p = do
h <- foldl' (decrease p) m (takeWhile (>= p * p) vs)
return h
decrease :: Int -> IO (HashTable Int Int) -> Int -> IO (HashTable Int Int)
decrease p m k = do
old <- m ! k
s <- sumOfSieved m k p
h <- m
H.insert h k (old - s)
return h
sumOfSieved :: IO (HashTable Int Int) -> Int -> Int -> IO Int
sumOfSieved m v p = do
a <- m ! (v `div` p)
b <- m ! (p - 1)
return (p * (a - b))
main = do
result <- problem $ 30
print result
Raw
slow.prof
Tue Jun 13 22:12 2017 Time and Allocation Profiling Report (Final)
slow +RTS -p -RTS
total time = 44.36 secs (44364 ticks @ 1000 us, 1 processor)
total alloc = 24,326,842,088 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
sumOfSieved Main 17.3 21.5
delete' Data.HashTable.ST.Basic 13.7 16.8
decrease Main 8.7 11.6
checkOverflow Data.HashTable.ST.Basic 8.1 2.6
! Main 8.0 10.4
delete'.go Data.HashTable.ST.Basic 7.4 5.3
writeLoad Data.HashTable.ST.Basic 7.3 3.3
writeArray Data.HashTable.Internal.Array 5.1 5.4
readLoad Data.HashTable.ST.Basic 2.7 1.3
readArray Data.HashTable.Internal.IntArray 2.6 1.4
lookup/go Data.HashTable.ST.Basic 2.5 0.3
delete'.he Data.HashTable.ST.Basic 2.2 1.3
fI Data.HashTable.Internal.CacheLine 2.2 4.3
readDelLoad Data.HashTable.ST.Basic 1.9 1.3
newSizedReal Data.HashTable.ST.Basic 1.7 0.4
nextBestPrime.idx Data.HashTable.Internal.Utils 1.2 0.4
readArray Data.HashTable.Internal.Array 1.2 1.1
newArray Data.HashTable.Internal.Array 1.2 3.9
newArray Data.HashTable.Internal.IntArray 0.6 1.6
mappend Data.HashTable.ST.Basic 0.5 1.9
writeArray Data.HashTable.Internal.IntArray 0.5 2.6
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 133 0 0.0 0.0 100.0 100.0
CAF Main 265 0 0.0 0.0 100.0 100.0
main Main 266 1 0.0 0.0 100.0 100.0
problem Main 267 1 0.0 0.0 100.0 100.0
problem.n' Main 327 1 0.0 0.0 0.0 0.0
problem.vs Main 291 1 0.0 0.0 0.0 0.0
problem.r Main 269 1 0.0 0.0 0.0 0.0
sieve Main 268 5 0.0 0.0 100.0 100.0
update Main 337 3 0.0 0.0 0.0 0.0
decrease Main 339 10 0.0 0.0 0.0 0.0
! Main 341 10 0.0 0.0 0.0 0.0
! Main 270 1403567 8.0 10.4 100.0 100.0
update Main 338 0 0.0 0.0 76.2 76.0
decrease Main 340 0 8.7 11.6 76.2 76.0
checkOverflow Data.HashTable.ST.Basic 405 5438803 2.3 0.7 5.6 2.3
rehashAll Data.HashTable.ST.Basic 423 32 0.0 0.0 0.0 0.0
rehashAll.newValues Data.HashTable.ST.Basic 440 32 0.0 0.0 0.0 0.0
rehashAll.newKeys Data.HashTable.ST.Basic 439 32 0.0 0.0 0.0 0.0
rehashAll.newHashes Data.HashTable.ST.Basic 438 32 0.0 0.0 0.0 0.0
rehashAll.rehash Data.HashTable.ST.Basic 433 32 0.0 0.0 0.0 0.0
rehashAll.rehash.go Data.HashTable.ST.Basic 434 640 0.0 0.0 0.0 0.0
growTable/rehash Data.HashTable.ST.Basic 435 608 0.0 0.0 0.0 0.0
writeArray Data.HashTable.Internal.IntArray 451 288 0.0 0.0 0.0 0.0
toPtr Data.HashTable.Internal.IntArray 442 288 0.0 0.0 0.0 0.0
insertRecord/probe Data.HashTable.ST.Basic 441 288 0.0 0.0 0.0 0.0
writeArray Data.HashTable.Internal.Array 453 0 0.0 0.0 0.0 0.0
fI Data.HashTable.Internal.CacheLine 443 0 0.0 0.0 0.0 0.0
readArray Data.HashTable.Internal.Array 437 0 0.0 0.0 0.0 0.0
readArray Data.HashTable.Internal.IntArray 436 608 0.0 0.0 0.0 0.0
rehashAll.(...) Data.HashTable.ST.Basic 432 32 0.0 0.0 0.0 0.0
rehashAll.loadRef' Data.HashTable.ST.Basic 431 32 0.0 0.0 0.0 0.0
writeLoad Data.HashTable.ST.Basic 430 0 0.0 0.0 0.0 0.0
readLoad Data.HashTable.ST.Basic 429 0 0.0 0.0 0.0 0.0
newSizedReal Data.HashTable.ST.Basic 424 32 0.0 0.0 0.0 0.0
newSizeRefs Data.HashTable.ST.Basic 428 0 0.0 0.0 0.0 0.0
newArray Data.HashTable.Internal.Array 427 0 0.0 0.0 0.0 0.0
newArray Data.HashTable.Internal.IntArray 426 32 0.0 0.0 0.0 0.0
newSizedReal.m' Data.HashTable.ST.Basic 425 32 0.0 0.0 0.0 0.0
readDelLoad Data.HashTable.ST.Basic 408 0 0.5 0.4 0.5 0.4
writeLoad Data.HashTable.ST.Basic 407 0 2.0 0.9 2.0 0.9
readLoad Data.HashTable.ST.Basic 406 0 0.7 0.4 0.7 0.4
_values Data.HashTable.ST.Basic 404 5438803 0.0 0.0 0.0 0.0
_keys Data.HashTable.ST.Basic 403 5438803 0.0 0.0 0.0 0.0
writeArray Data.HashTable.Internal.Array 402 0 1.3 1.4 1.3 1.4
writeArray Data.HashTable.Internal.IntArray 401 5438803 0.1 0.7 0.1 0.7
delete' Data.HashTable.ST.Basic 390 5438803 4.0 4.7 11.2 9.4
delete'.bump Data.HashTable.ST.Basic 420 701779 0.2 0.0 0.6 0.2
writeLoad Data.HashTable.ST.Basic 422 0 0.3 0.1 0.3 0.1
readLoad Data.HashTable.ST.Basic 421 0 0.1 0.0 0.1 0.0
_wasDeleted Data.HashTable.ST.Basic 400 5438803 0.0 0.0 0.0 0.0
_slot Data.HashTable.ST.Basic 397 5438803 0.0 0.0 0.0 0.0
toPtr Data.HashTable.Internal.IntArray 393 5438803 0.0 0.0 0.0 0.0
delete'.he Data.HashTable.ST.Basic 392 5438803 0.7 0.4 0.7 0.4
delete'.go Data.HashTable.ST.Basic 391 5438803 3.4 1.6 6.0 4.2
mappend Data.HashTable.ST.Basic 419 701779 0.0 0.1 0.0 0.1
writeArray Data.HashTable.Internal.Array 418 0 0.2 0.2 0.2 0.2
writeArray Data.HashTable.Internal.IntArray 417 701779 0.0 0.0 0.0 0.0
delete'.bumpDel Data.HashTable.ST.Basic 413 701779 0.3 0.0 0.8 0.2
writeDelLoad Data.HashTable.ST.Basic 416 0 0.4 0.1 0.4 0.1
readDelLoad Data.HashTable.ST.Basic 414 0 0.1 0.0 0.1 0.0
delete'.go.samePlace Data.HashTable.ST.Basic 411 701779 0.1 0.0 0.1 0.0
_slot Data.HashTable.ST.Basic 412 701779 0.0 0.0 0.0 0.0
readArray Data.HashTable.Internal.Array 410 0 0.2 0.2 0.2 0.2
delete'.haveWrapped Data.HashTable.ST.Basic 409 701779 0.0 0.0 0.0 0.0
delete'.go.pl Data.HashTable.ST.Basic 398 4737024 0.1 0.0 0.2 0.5
mappend Data.HashTable.ST.Basic 399 4737024 0.1 0.5 0.1 0.5
readArray Data.HashTable.Internal.IntArray 396 5438803 0.6 0.4 0.6 0.4
toPtr Data.HashTable.Internal.IntArray 395 0 0.0 0.0 0.0 0.0
fI Data.HashTable.Internal.CacheLine 394 0 0.5 1.1 0.5 1.1
_hashes Data.HashTable.ST.Basic 389 5438803 0.0 0.0 0.0 0.0
insert Data.HashTable.ST.Basic 388 5438803 0.1 0.0 0.1 0.0
nextBestPrime Data.HashTable.Internal.Utils 381 526336 0.1 0.1 0.4 0.2
nextBestPrime.yi Data.HashTable.Internal.Utils 384 526336 0.0 0.0 0.0 0.0
nextBestPrime.xi Data.HashTable.Internal.Utils 383 526336 0.1 0.0 0.1 0.0
nextBestPrime.idx Data.HashTable.Internal.Utils 382 526336 0.3 0.1 0.3 0.1
newSizedReal Data.HashTable.ST.Basic 379 526336 0.5 0.1 1.1 1.6
newSizeRefs Data.HashTable.ST.Basic 387 0 0.2 0.2 0.2 0.2
newArray Data.HashTable.Internal.Array 386 0 0.3 1.0 0.3 1.0
newArray Data.HashTable.Internal.IntArray 385 526336 0.1 0.4 0.1 0.4
newSizedReal.m' Data.HashTable.ST.Basic 380 526336 0.0 0.0 0.0 0.0
sumOfSieved Main 342 701779 17.3 21.5 47.6 48.7
lookup/go Data.HashTable.ST.Basic 374 1403558 1.6 0.2 2.7 1.2
readArray Data.HashTable.Internal.Array 378 0 0.6 0.6 0.6 0.6
readArray Data.HashTable.Internal.IntArray 377 1403558 0.2 0.1 0.2 0.1
fI Data.HashTable.Internal.CacheLine 376 0 0.3 0.3 0.3 0.3
toPtr Data.HashTable.Internal.IntArray 375 1403558 0.0 0.0 0.0 0.0
lookup Data.HashTable.ST.Basic 373 1403558 0.0 0.0 0.0 0.0
checkOverflow Data.HashTable.ST.Basic 369 9474048 3.8 1.2 9.3 4.1
readDelLoad Data.HashTable.ST.Basic 372 0 0.9 0.6 0.9 0.6
writeLoad Data.HashTable.ST.Basic 371 0 3.4 1.6 3.4 1.6
readLoad Data.HashTable.ST.Basic 370 0 1.3 0.6 1.3 0.6
_values Data.HashTable.ST.Basic 368 9474048 0.0 0.0 0.0 0.0
_keys Data.HashTable.ST.Basic 367 9474048 0.0 0.0 0.0 0.0
writeArray Data.HashTable.Internal.Array 366 0 2.4 2.5 2.4 2.5
writeArray Data.HashTable.Internal.IntArray 365 9474048 0.2 1.2 0.2 1.2
delete' Data.HashTable.ST.Basic 354 9474048 6.4 8.1 12.5 14.6
_wasDeleted Data.HashTable.ST.Basic 364 9474048 0.0 0.0 0.0 0.0
_slot Data.HashTable.ST.Basic 361 9474048 0.0 0.0 0.0 0.0
toPtr Data.HashTable.Internal.IntArray 357 9474048 0.0 0.0 0.0 0.0
delete'.he Data.HashTable.ST.Basic 356 9474048 1.1 0.6 1.1 0.6
delete'.go Data.HashTable.ST.Basic 355 9474048 2.6 2.5 5.0 5.9
delete'.go.pl Data.HashTable.ST.Basic 362 9474048 0.1 0.0 0.4 0.9
mappend Data.HashTable.ST.Basic 363 9474048 0.3 0.9 0.3 0.9
readArray Data.HashTable.Internal.IntArray 360 9474048 1.3 0.6 1.3 0.6
toPtr Data.HashTable.Internal.IntArray 359 0 0.0 0.0 0.0 0.0
fI Data.HashTable.Internal.CacheLine 358 0 0.7 1.9 0.7 1.9
_hashes Data.HashTable.ST.Basic 353 9474048 0.0 0.0 0.0 0.0
insert Data.HashTable.ST.Basic 352 9474048 0.1 0.0 0.1 0.0
nextBestPrime Data.HashTable.Internal.Utils 345 1052672 0.1 0.1 0.9 0.4
nextBestPrime.yi Data.HashTable.Internal.Utils 348 1052672 0.1 0.0 0.1 0.0
nextBestPrime.xi Data.HashTable.Internal.Utils 347 1052672 0.1 0.1 0.1 0.1
nextBestPrime.idx Data.HashTable.Internal.Utils 346 1052672 0.6 0.2 0.6 0.2
newSizedReal Data.HashTable.ST.Basic 343 1052672 0.8 0.2 2.0 3.3
newSizeRefs Data.HashTable.ST.Basic 351 0 0.3 0.3 0.3 0.3
newArray Data.HashTable.Internal.Array 350 0 0.6 1.9 0.6 1.9
newArray Data.HashTable.Internal.IntArray 349 1052672 0.3 0.8 0.3 0.8
newSizedReal.m' Data.HashTable.ST.Basic 344 1052672 0.1 0.0 0.1 0.0
lookup/go Data.HashTable.ST.Basic 329 701788 0.9 0.1 1.5 0.6
readArray Data.HashTable.Internal.Array 336 0 0.3 0.3 0.3 0.3
readArray Data.HashTable.Internal.IntArray 334 701788 0.1 0.0 0.1 0.0
fI Data.HashTable.Internal.CacheLine 331 0 0.2 0.1 0.2 0.1
toPtr Data.HashTable.Internal.IntArray 330 701788 0.0 0.0 0.0 0.0
lookup Data.HashTable.ST.Basic 328 701788 0.0 0.0 0.0 0.0
checkOverflow Data.HashTable.ST.Basic 320 4737042 2.0 0.6 4.7 2.0
readDelLoad Data.HashTable.ST.Basic 326 0 0.4 0.3 0.4 0.3
writeLoad Data.HashTable.ST.Basic 324 0 1.6 0.8 1.6 0.8
readLoad Data.HashTable.ST.Basic 322 0 0.6 0.3 0.6 0.3
_values Data.HashTable.ST.Basic 319 4737042 0.0 0.0 0.0 0.0
_keys Data.HashTable.ST.Basic 318 4737042 0.0 0.0 0.0 0.0
writeArray Data.HashTable.Internal.Array 317 0 1.1 1.2 1.1 1.2
writeArray Data.HashTable.Internal.IntArray 315 4737042 0.1 0.6 0.1 0.6
delete' Data.HashTable.ST.Basic 297 4737042 3.3 4.1 6.5 7.3
_wasDeleted Data.HashTable.ST.Basic 314 4737042 0.0 0.0 0.0 0.0
_slot Data.HashTable.ST.Basic 311 4737042 0.0 0.0 0.0 0.0
toPtr Data.HashTable.Internal.IntArray 303 4737042 0.0 0.0 0.0 0.0
delete'.he Data.HashTable.ST.Basic 300 4737042 0.5 0.3 0.5 0.3
delete'.go Data.HashTable.ST.Basic 299 4737042 1.4 1.2 2.7 3.0
delete'.go.pl Data.HashTable.ST.Basic 312 4737042 0.1 0.0 0.2 0.5
mappend Data.HashTable.ST.Basic 313 4737042 0.1 0.5 0.1 0.5
readArray Data.HashTable.Internal.IntArray 310 4737042 0.5 0.3 0.5 0.3
toPtr Data.HashTable.Internal.IntArray 309 0 0.0 0.0 0.0 0.0
fI Data.HashTable.Internal.CacheLine 305 0 0.5 0.9 0.5 0.9
_hashes Data.HashTable.ST.Basic 296 4737042 0.0 0.0 0.0 0.0
insert Data.HashTable.ST.Basic 292 4737042 0.1 0.0 0.1 0.0
nextBestPrime Data.HashTable.Internal.Utils 274 526338 0.1 0.1 0.6 0.2
nextBestPrime.yi Data.HashTable.Internal.Utils 279 526338 0.0 0.0 0.0 0.0
nextBestPrime.xi Data.HashTable.Internal.Utils 277 526338 0.1 0.0 0.1 0.0
nextBestPrime.idx Data.HashTable.Internal.Utils 275 526338 0.4 0.1 0.4 0.1
newSizedReal Data.HashTable.ST.Basic 272 526338 0.5 0.1 1.2 1.6
newSizeRefs Data.HashTable.ST.Basic 288 0 0.2 0.2 0.2 0.2
newArray Data.HashTable.Internal.Array 286 0 0.3 1.0 0.3 1.0
newArray Data.HashTable.Internal.IntArray 282 526338 0.2 0.4 0.2 0.4
newSizedReal.m' Data.HashTable.ST.Basic 273 526338 0.0 0.0 0.0 0.0
CAF Data.HashTable.ST.Basic 263 0 0.0 0.0 0.0 0.0
rehashAll Data.HashTable.ST.Basic 444 0 0.0 0.0 0.0 0.0
rehashAll.rehash Data.HashTable.ST.Basic 445 0 0.0 0.0 0.0 0.0
rehashAll.rehash.go Data.HashTable.ST.Basic 446 0 0.0 0.0 0.0 0.0
growTable/rehash Data.HashTable.ST.Basic 447 0 0.0 0.0 0.0 0.0
insertRecord/probe Data.HashTable.ST.Basic 448 0 0.0 0.0 0.0 0.0
fI Data.HashTable.Internal.CacheLine 449 0 0.0 0.0 0.0 0.0
writeDelLoad Data.HashTable.ST.Basic 415 1 0.0 0.0 0.0 0.0
lookup/go Data.HashTable.ST.Basic 332 0 0.0 0.0 0.0 0.0
fI Data.HashTable.Internal.CacheLine 333 0 0.0 0.0 0.0 0.0
readDelLoad Data.HashTable.ST.Basic 325 1 0.0 0.0 0.0 0.0
writeLoad Data.HashTable.ST.Basic 323 1 0.0 0.0 0.0 0.0
readLoad Data.HashTable.ST.Basic 321 1 0.0 0.0 0.0 0.0
delete' Data.HashTable.ST.Basic 306 0 0.0 0.0 0.0 0.0
delete'.go Data.HashTable.ST.Basic 307 0 0.0 0.0 0.0 0.0
fI Data.HashTable.Internal.CacheLine 308 0 0.0 0.0 0.0 0.0
deletedMarker Data.HashTable.ST.Basic 302 1 0.0 0.0 0.0 0.0
emptyMarker Data.HashTable.ST.Basic 301 1 0.0 0.0 0.0 0.0
mempty Data.HashTable.ST.Basic 298 1 0.0 0.0 0.0 0.0
intSz Data.HashTable.ST.Basic 290 1 0.0 0.0 0.0 0.0
newSizeRefs Data.HashTable.ST.Basic 287 1 0.0 0.0 0.0 0.0
newSizeRefs.asz Data.HashTable.ST.Basic 289 1 0.0 0.0 0.0 0.0
maxLoad Data.HashTable.ST.Basic 278 1 0.0 0.0 0.0 0.0
newSized Data.HashTable.ST.Basic 271 1 0.0 0.0 0.0 0.0
CAF Data.HashTable.Internal.Array 260 0 0.0 0.0 0.0 0.0
readArray Data.HashTable.Internal.Array 335 1 0.0 0.0 0.0 0.0
writeArray Data.HashTable.Internal.Array 316 1 0.0 0.0 0.0 0.0
newArray Data.HashTable.Internal.Array 285 1 0.0 0.0 0.0 0.0
CAF Data.HashTable.Internal.IntArray 259 0 0.0 0.0 0.0 0.0
primWordToElem Data.HashTable.Internal.IntArray 295 1 0.0 0.0 0.0 0.0
elemMask Data.HashTable.Internal.IntArray 293 1 0.0 0.0 0.0 0.0
cacheLineSize Data.HashTable.Internal.IntArray 284 1 0.0 0.0 0.0 0.0
wordSizeInBytes Data.HashTable.Internal.IntArray 283 1 0.0 0.0 0.0 0.0
CAF Data.HashTable.Internal.CacheLine 258 0 0.0 0.0 0.0 0.0
fI Data.HashTable.Internal.CacheLine 304 2 0.0 0.0 0.0 0.0
CAF Data.HashTable.Internal.Utils 255 0 0.0 0.0 0.0 0.0
wordSize Data.HashTable.Internal.Utils 294 1 0.0 0.0 0.0 0.0
cacheLineSize Data.HashTable.Internal.Utils 281 1 0.0 0.0 0.0 0.0
numElemsInCacheLine Data.HashTable.Internal.Utils 280 1 0.0 0.0 0.0 0.0
primeSizes Data.HashTable.Internal.Utils 276 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.FD 182 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding 173 0 0.0 0.0 0.0 0.0
CAF GHC.Conc.Signal 159 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv 157 0 0.0 0.0 0.0 0.0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment