Hi, I've got the answer - its the sumLeafs function that behaves different for leftPath / rightPath. If one exchanges it in the leftPath case by
sumLeafs (Fork l r) = sumLeafs r + sumLeafs l sumLeafs (Leaf i) = i the difference in runtime is gone. Cheers, Daniel. Am Dienstag, den 21.09.2010, 19:14 +0200 schrieb Daniel Seidel: > Hi, > > I'm having a tree data type > > data Tree a = Leaf a | Fork (Tree a) (Tree a) > > , a generator for the left-most path of the tree, taking the depth > > leftPath :: Int -> Tree Int > leftPath d > | d > 1 = Fork (leftPath (d-1)) (Leaf 1) > | d == 1 = (Leaf 1) > | otherwise = error "Can't make tree of depth <= 0." > > and the similar thing for a right-most path > > rightPath :: Int -> Tree Int > rightPath d > | d > 1 = Fork (Leaf 1) (rightPath (d-1)) > | d == 1 = (Leaf 1) > | otherwise = error "Can't make tree of depth <= 0." > > Now I measured how long it takes to build a huge tree via > > print $ sumLeafs $ leftPath 1000000 > > and > > print $ sumLeafs $ rightPath 1000000 > > as main functions where > > sumLeafs (Fork l r) = sumLeafs l + sumLeafs r > sumLeafs (Leaf i) = i > > > Compiling without optimisation and running with no extra runtime > options, besides -K50M to make available enough stack, yields on my > machine (measured via time) that for leftPath the runtime is 3.8s, for > rightPath 2.9s. > If I optimize with -O2 runtimes decrease to approx. 1s / 0.8s, meaning > the difference is still there. > > Using the -sstderr runtime option shows that (also with the runtime > option -H2.5G) garbage collection for the leftPath case takes always > slightly longer than for the rightPath case. > > Can anyone explain why there is that difference? > > Cheers, > > Daniel. > > PS: Here the programs as one block: > > ---LeftPath.hs > > module Main where > > data Tree a = Leaf a | Fork (Tree a) (Tree a) > > leftPath :: Int -> Tree Int > leftPath d > | d > 1 = Fork (leftPath (d-1)) (Leaf 1) > | d == 1 = (Leaf 1) > | otherwise = error "Can't make tree of depth <= 0." > > sumLeafs (Fork l r) = sumLeafs l + sumLeafs r > sumLeafs (Leaf i) = i > > main = print $ sumLeafs $ leftPath 1000000 > > ---RightPath.hs > > module Main where > > data Tree a = Leaf a | Fork (Tree a) (Tree a) > > rightPath :: Int -> Tree Int > rightPath d > | d > 1 = Fork (Leaf 1) (rightPath (d-1)) > | d == 1 = (Leaf 1) > | otherwise = error "Can't make tree of depth <= 0." > > sumLeafs (Fork l r) = sumLeafs l + sumLeafs r > sumLeafs (Leaf i) = i > > main = print $ sumLeafs $ rightPath 1000000 > > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
