[Haskell-cafe] Re: Laziness leaks
barsoap at web.de
Wed Jun 4 23:28:25 EDT 2008
"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,
(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
More information about the Haskell-Cafe