[Haskell-cafe] Space usage and CSE in Haskell

[ok]

On 25 Jul 2007, at 6:50 pm, Melissa O'Neill wrote:
[section 23.4.2 of Simon's 1987 book].

The really scary thing about this example is that so much depends
on the order in which the subsets are returned, which in many cases
does not matter.  Here's code that I tried with GHC on a 500MHz SPARC.

With today's memory we might be willing to put up with the O(2**N)
space cost (as long as N isn't too big), because that saves us more
than a factor of 3 in time.  But changing the order of the results
gives us a nice bounded space solution which is nearly 9 times faster
than the naive sharing code.

In a non-trivial program, we wouldn't have a hope of spotting issues
like this without memory use profiling.  Unless someone has some ideas
about how to design code so that it's not a problem?

main = print (length (power_list [1..20]))

power_list :: [Int] -> [[Int]]

power_list [] = [[]]
{- Classic 23.4.2 first definition of power_list
    with space sharing and therefore "O(2**N) transient residency".

    power_list (x:xs) = pxs ++ map (x :) pxs where pxs = power_list xs

-- 3.540 user + 0.220 system = 3.760 total seconds.
-}

{- Classic 23.4.2 second definition,
    with recomputing, "constant residency", but poor run-time.

    power_list (x:xs) = power_list xs ++ map (x :) (power_list xs)

-- 12.130 user + 0.110 system = 12.240 total seconds.
-}

{- A fairly obvious variant of the first definition.
    The order is changed to eliminate wasted appends,
    but the space behaviour doesn't change that much.

    power_list (x:xs) = map (x :) pxs ++ pxs where pxs = power_list xs

-- 2.020 user + 0.240 system = 2.260 total seconds.
-}

{- Another change to the order to give us MORE sharing takes
    less time AND less space.  The surprise is how much less time.
-}
power_list (x:xs) = foo (power_list xs) x
   where foo [] _ = []
         foo (y:ys) x = (x:y) : y : foo ys x

-- 0.370 user + 0.060 system = 0.430 total seconds.