Hi all, We encountered a case where elimination of intermediate data structure seeems to have a bad impact on the overall performance and we were wondering why. Relationally, our program would be as simple as: f . g where g :: Seed -> Tree1 and f :: Tree1 -> Tree2. Basically g generate some kind of tree via an unfold and f map a Tree1 to some (usually 3 or 4) Tree2. In reality we have to implement relations as set (or list) valued functions, so it becomes concat . map f. g where g looks like g seed = [ z | (s1, s2) <- split seed, x <- g s1, y <- g s2, z <- join x y ] The relation f was almost as simple as a replacing each constructor in Tree1 with one or more coresponding constructors in Tree2. They two can be fused together and becomes fg seed = [ z | (s1, s2) <- split seed, x <- fg s1, y <- fg s2, z <- join' x y ] The intermediate datatype Tree1 was thus eliminated. The problem was: the fused program ran slower than the original one! At least if you measure the total running time (either via the UNIX time command or use the CPUTime module). The time reported in the GHC time profile indeed showed that the fused program is faster, though, if GC time is excluded. We were quite curious why and my guess was: since f maps a Tree1 to more than one Tree2, in the two list comprehensions, the list produced by (fg s2) is much longer than (g s2). The fused program thus has to keep a longer list in memory. Worse heap residency results in more GCs. (Luckily GHC did not attempt to automatically perform the fusion for us! :) ) An obvious thing to try was to increase the heap size. Again we were surprised. Indeed the GC time decreased but the running time in the profile (excluding the GC time) increased a bit. Our guess was that it might have something to do with the way GHC allocates new memory cells such that larger heap results in longer allocation time. It was quite tricky to find the best heap size at which the program runs at maximal speed. Are the above guesses are plausible? Is it a known phenomena? Thank you very much. sincerely, Shin-Cheng Mu
Shin-Cheng Mu wrote:
g seed = [ z | (s1, s2) <- split seed, x <- g s1, y <- g s2, z <- join x y ]
The relation f was almost as simple as a replacing each constructor in Tree1 with one or more coresponding constructors in Tree2. They two can be fused together and becomes
fg seed = [ z | (s1, s2) <- split seed, x <- fg s1, y <- fg s2, z <- join' x y ]
The intermediate datatype Tree1 was thus eliminated.
The problem was: the fused program ran slower than the original one! At least if you measure the total running time (either via the UNIX time command or use the CPUTime module). The time reported in the GHC time profile indeed showed that the fused program is faster, though, if GC time is excluded.
We were quite curious why and my guess was: since f maps a Tree1 to more than one Tree2, in the two list comprehensions, the list produced by (fg s2) is much longer than (g s2). The fused program thus has to keep a longer list in memory. Worse heap residency results in more GCs. (Luckily GHC did not attempt to automatically perform the fusion for us! :) )
Note that you have done more than just deforestation. You have moved f through join, obtaining join'. Because as you say (fg s2) is much longer than (g s2), join' is applied more often than join was applied before. I don't know how expensive your join and join' are. Furthermore, deforestation itself does not reduce runtime very much. More important is the secondary effect that deforstation moves formerly separated expressions close to each other, so that further optimisations can take place. Maybe in your example there are not many further optimisations? In real life it is seldomly clear which transformations are optimisations... (maybe a different machine will yield different results again?). Ciao, Olaf -- OLAF CHITIL, Dept. of Computer Science, The University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767
Dear Simon and Olaf, Thank you very much for your replies. Monday, May 6, 2002, 02:37 PM, Olaf Chitil wrote:
Shin-Cheng Mu wrote:
The intermediate datatype Tree1 was thus eliminated. The problem was: the fused program ran slower than the original one! Note that you have done more than just deforestation. You have moved f through join, obtaining join'. Because as you say (fg s2) is much longer than (g s2), join' is applied more often than join was applied before. I don't know how expensive your join and join' are.
I will be a bit more precise. Let f and g have type: g :: Seed -> [Tree] f :: Tree -> [Expr] where Tree1 is a tip-valued binary tree, and Tree2 is also a binary tree but the forks are arithmetic operators: data Tree = Tip Int | Bin Tree1 Tree1 data Expr = Val Int | Add Tree2 Tree2 | Sub Tree2 Tree2 | Mul .... The function g is defined like: g seed = [ z | (s1, s2) <- split seed, x <- g s1, y <- g s2, z <- Bin x y ] The function f converts a Tree to many Exprs by replacing Bin with one of Add, Sub, Mul or Div: f (Tip i) = [Val i] f (Bin x y) = [op x' y' | x' <- f x, y' <- f y, op <- join x y] The program before fusion looks like: concat . map f . g while the fused program simply: fg seed = [ z | (s1, s2) <- split seed, x <- fg s1, y <- fg s2, z <- join x y ] join x y = [op x y | op <- [Add, Sub, ... ]] And the surprise was the fused program ran slower than the naive one before fusion. The time profiling showed that, in one run, the naive program itself took 2.00 sec to finish, with 9% extra GC time. The fused program itself, on the other hand, took only 1.84 sec but spent an extra 67% of time on GC (the heap size is the default 64M). Considering their heap profiles, both of them look like several steep, slanted triangles standing next to each other. The highest peak in the heap profile of the naive program reaches only 50K of memory, while that for the fused program reaches as much as 1500K. In the former case, the heap is mostly occupied by chunks created by g. In the latter case, the heap is mostly occupied by join.
Furthermore, deforestation itself does not reduce runtime very much.
Indeed. Looks like it helps to speed up the mutator a bit but end up spending more time on GC, due to increased heap demand.
More important is the secondary effect that deforstation moves formerly separated expressions close to each other, so that further optimisations can take place. Maybe in your example there are not many further optimisations?
I think so. As you can see there are not much optimisations to be done, other than the ones done by hand. :) Monday, May 6, 2002, 12:02 PM, Simon Marlow wrote：
It is entirely plausible that as you increase the heap size the mutator time increases: this is because you get fewer cache hits with a larger heap. GHC starts off with a small heap size so as to try to make the most of the cache. However, on most examples we've seen the benefits of reducing garbage collections by increasing the heap size tend to outweigh the benefits from staying in the cache. Did you try heap profiling to discover what structure was filling up the heap?
Thanks for the explanation. :) More info. about the heap was given above. By the way, could there be situations where increasing the heap size also increases the GC time? sincerely, Shin
participants (2)
-
Olaf Chitil -
Shin-Cheng Mu