[Haskell-cafe] Space usage and CSE in Haskell
Dan Weston
westondan at imageworks.com
Wed Jul 25 20:15:29 EDT 2007
Maybe it behooves writers of GHC libraries who create list generating
functions f where the complexity of length . f is strictly less than the
complexity of f itself to provide an fLength function and a rewrite rule
for it:
{-# RULES
"listLength" length . f = fLength
#-}
Then people like me could mindlessly write
> main = print (length (power_list [1..20]))
and get
> main = print (power_list_length [1..20])
without worrying about efficiency.
Dan
ok wrote:
> 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.
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
More information about the Haskell-Cafe
mailing list