[Haskell-cafe] asymmetric runtimes for symmetric trees

[Daniel Seidel]

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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe