mind following haskell program:
-- (^) allocs memory define using native (**) pow :: int -> int -> int pow x y = floor $ fromintegral x ** fromintegral y -- tail recursive, div , mod native, believe, so, no alloc ispalindrome :: int -> bool ispalindrome x = go (pow 10 (floor $ logbase 10 $ fromintegral x)) x go m x = x <= 0 || div x m == mod x 10 && go (div m 100) (div (x - m * mod x 10) 10) -- go tail recursive too... no obvious allocation here wanderer :: int -> int wanderer n = go 0 (pow 10 n - 1) (pow 10 n - 1) go p x y | p > 0 && div p x >= pow 10 n = p go p x y | p > 0 && y < div p x || y < x = go p (x-1) (pow 10 n - 1) go p x y | ispalindrome (x*y) = go (x*y) x (y-1) go p x y = go p x (y-1) main = print . wanderer $ 8 profiling it, get:
fri may 8 03:36 2015 time , allocation profiling report (final) aff +rts -p -rts total time = 7.34 secs (7344 ticks @ 1000 us, 1 processor) total alloc = 6,487,919,472 bytes (excludes profiling overheads) cost centre module %time %alloc ispalindrome main 41.9 18.5 ispalindrome.go main 22.6 1.4 wanderer.go main 20.0 67.8 pow main 15.5 12.3 individual inherited cost centre module no. entries %time %alloc %time %alloc main main 47 0 0.0 0.0 100.0 100.0 main main 95 0 0.0 0.0 0.0 0.0 caf:main1 main 92 0 0.0 0.0 0.0 0.0 main main 94 1 0.0 0.0 0.0 0.0 caf:main2 main 91 0 0.0 0.0 100.0 100.0 main main 96 0 0.0 0.0 100.0 100.0 wanderer main 98 1 0.0 0.0 100.0 100.0 pow main 101 1 0.0 0.0 0.0 0.0 wanderer.go main 99 49995002 20.0 67.8 100.0 100.0 ispalindrome main 102 49985002 41.9 18.5 80.0 32.2 pow main 104 49985002 15.5 12.3 15.5 12.3 ispalindrome.go main 103 52207117 22.6 1.4 22.6 1.4 pow main 100 1 0.0 0.0 0.0 0.0 pow main 97 2 0.0 0.0 0.0 0.0 caf ghc.conc.signal 85 0 0.0 0.0 0.0 0.0 caf ghc.io.encoding 78 0 0.0 0.0 0.0 0.0 caf ghc.io.encoding.iconv 76 0 0.0 0.0 0.0 0.0 caf ghc.io.handle.fd 69 0 0.0 0.0 0.0 0.0 caf ghc.event.thread 55 0 0.0 0.0 0.0 0.0 as far i'm aware, seems functions tail recursive , prelude functions asm operations. yet simple program allocs 7gb of memory. allocation coming from?
the allocation coming go in ispalindrome:
go m x = x <= 0 || div x m == mod x 10 && go (div m 100) (div (x - m * mod x 10) 10) we have || on right hand side. short-circuit semantics of || realized through lazy evaluation. ghc sees m argument unused if x <= 0 evaluates true, doesn't unbox m, allowing remain uncomputed. of course, in case we're better off unboxing m too, let's that.
{-# language bangpatterns #-} go !m x = ... now ghc -o2 , +rts -s:
52,016 bytes allocated in heap 3,408 bytes copied during gc 44,312 bytes maximum residency (1 sample(s)) 17,128 bytes maximum slop 1 mb total memory in use (0 mb lost due fragmentation) 
Comments
Post a Comment