[Haskell-cafe] Help understanding sharing

[Ryan Ingram]

To add to this; sharing is not always what you want; sometimes it's a
time/space trade-off and sometimes it's actually strictly worse than
not sharing.

For example:

> f :: Integer -> [Integer]
> f x = take 10000000 [x..]

> sum :: [Integer] -> Integer
> sum = foldl' (+) 0

> expensiveZero :: Integer
> expensiveZero = let (a,b) = (f 0, f 0) in sum a + sum (map negate b)

If the applications of f are unshared, "expensive" runs in small
constant memory.  But, if the applications of f are shared, it will
likely exhaust memory (if it doesn't, add another few zeroes to the
"take" in f).

Here's why.  Assume that (+) evaluates its left argument first.  Then
"sum a" is going to consume the entire list stored in "a".  If the
applications of f are unshared, the garbage collector will reclaim the
beginning of the list "a" while sum is evaluating!  But if they are
shared, it can't; b is the same list and is still live until the rhs
of the (+) gets evaluated.  So the entire list will end up in memory!

Not only that, the program will likely take longer to run than the
unshared version, because the garbage collector has so much more work
to do maintaining the live data set.

This is why most compilers use aliasing of names for sharing; it gives
the programmer control of whether a computation will be shared or not.

  -- ryan

On Mon, Apr 14, 2008 at 8:24 PM, Albert Y. C. Lai <trebla at vex.net> wrote:
> Patrick Surry wrote:
>
> > I've seen other discussions that suggest that lists are always shared
> while in scope (so the fibs trick works).  But is that just a feature of the
> standard compilers, or is it somewhere mandated in the Hakell spec (I don't
> see anything obvious in the Haskell Report tho haven't read it cover to
> cover)?
> >
>
>  It is just a feature of most compilers. The Haskell Report does not specify
> sharing.
>
>  For most compilers, a sufficient condition for sharing is aliasing, e.g.,
>
>  let y = f x in (y,y,y,y,y)
>
>  you can be sure that most compilers share one copy of "f x" for those five
> mentions of "y".
>
>  As another example,
>
>  let x = 0:x in x
>
>  you can be sure that most compilers create a tight cyclic graph for that.
>
>  In contrast, most compilers may create redundantly new expressions for the
> following:
>
>  (f x, f x, f x, f x, f x)
>
>  -- given the definition: recurse f = f (recurse f)
>  recurse (\x -> 0:x)
>
>  _______________________________________________
>  Haskell-Cafe mailing list
>  Haskell-Cafe at haskell.org
>  http://www.haskell.org/mailman/listinfo/haskell-cafe
>