[Haskell-cafe] Re: Laziness leaks

[Achim Schneider]

"Ryan Ingram" <ryani.spam at gmail.com> wrote:

> On 6/4/08, apfelmus <apfelmus at quantentunnel.de> wrote:
> > Note that lazy evaluation never wastes time; evaluating a term with
> > lazy evaluation will always take less reduction steps than doing so
> > eagerly or partly eagerly.
> 
> True, but you can still have a "time leak"; this is particularily
> relevant in soft-real-time apps (like almost every app you use on a
> regular basis, from your editor to games); a time leak is when a
> computation that would take X time if evaluated every "time step" is
> left for many timesteps without being evaluated, leading to a hitch in
> responsiveness when it eventually is demanded N frames later taking
> N*X time.
> 
> Eager applications almost never have this sort of "time leak", but
> it's easy for it to happen with lazy evaluation.
> 
> A simple example: consider a variable that holds the number of
> timesteps since the app launched, for example.  Every time step it
> gets incremented by 1.  If the result is evaluated every time step, it
> takes a constant amount of time per timestep.  But if you go a long
> time without evaluating it, you end up with both a space leak (as the
> +1 thunks build up) but a time leak as well--when you eventually
> evaluate it, it takes O(n) time, where n is the number of frames since
> the variable was last evaluated.
> 
There won't ever be a space leak without a time leak nor a time leak
without a space leak. I'd just call it a leak.

You don't come across space-leaks in strict programs often because
data is usually allocated statically even if execution is non-strict.

Piping /dev/zero into a program that just sleeps does leak space,
though.

-- 
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited.