[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]


> > Under what circumstances should a language implementor *not* use
> > copy-on-mutate?  Where's the cost?
> Any lazy evaluation has a wierd impact on performance... the net
> performance is always as good or better than eager evaluation but it
> happens at different times.

I don't believe the net performance is always as good or better.  For
example, consider the sequence of expressions
(1) let x = 1 + 2
(2) x
(3) x
(where (2) and (3) occur in contexts where the value is referenced, and some
other expressions may intervene in order to make things interesting).  In a
strict language, the interpretation of (1) involves an addition and a store,
and evaluations of (2) and (3) involve a load.  In contrast, in a lazy
language (1) involves an allocation (generally heap) for the thunk (or
closure) that adds 1 and 2, several stores to initialize it, and finally a
store to bind x to the thunk.  (2) requires a test to determine whether x is
a bound to a value or a future, followed by a call to the code that actually
performs the add, followed by a store (to replace the binding of x); and (3)
requires that same test followed by a load.

The lazy evaluation requires the execution of more primitive operations, and
takes more memory.

As someone said earlier, the win for lazy evaluation is when evaluation is
infinitely deferred.  It doesn't win when all the values end up being used.
(And this matches the self-help tip that it saves time to do things right
away, instead of put them on a to-do list.)

Lazy evaluation can win in space even when all the values are used, if they
aren't needed at once, though.  For example, Haskell's
  foldl1 (+) [1..2^40]
takes less memory than Python's
  reduce(operator.add, range(2L**40))
(Which matches the self-help tip that you can reduce clutter by going
through your to-do stack and doing everything, in the order you get to it,
that isn't waiting on an external resource.)  The lazy evaluation is still
slower, unless properties of your VM/OS come into play: for example, the
Python expression might page more than the Haskell expression, and therefore
be much slower even though fewer instructions are executed outside of the
OS.  (Pretend Python is compiled for this comparison; otherwise, Python is
even slower, for reasons that aren't related to laziness.)

Similarly with copy-on-demand.  If you know ahead of time that all the pages
of the copy will be modified, it's more efficient to go ahead and copy it,
so that references to the elements of the copy don't have to go through a
layer of indirection, which ends up eventually executing all the code to
make the copy anyway.

It's interesting to look at the different approaches languages take to
mixing strict and lazy evaluation.  Haskell is lazy, but has a strictness
operator that you can (painfully) apply to force immediate evaluation.  ML,
I believe, is strict by default but lets you write lazy functions.  (I've
never programmed in ML; someone please correct me if this is wrong.)  Scheme
doesn't give you lazy evaluation as a language primitive, but it's
relatively easy to implement laziness with some syntactic overhead by using.
(I believe SICP walks you through active or generalized variables, which do
this.)  C++ makes laziness a tiny bit easier than assembly does.

By the way, generators are a replacement for laziness.  The Haskell
equivalent to (warning: untested code follows):
  def everyOther(seq):
    skip = 0
    for i in seq:
      if not skip:
        yield i
      skip = not skip
  everyOther (a:b:rest) = a : everyOther rest
  everyOther [a] = [a]
  everyOther [] = []
so everyOther [1..10] == [1,3,5,7,9], but so does
  take 5 (everyOther [1..10^9])
and without ever producing 11.  It's as if the Python program could be
  def everyOther(seq):
    res = []
    skip = 0
    for i in seq:
      if not skip:
      skip = not skip
    return res
but everyOther(range(10**9))[:5] only computed the first five elements ---
that is, generators distinct from sequence-producing functions are
unnecessary if sequences are lazy, which has the advantage that there's only
one way (at the interface level) to code the production of a sequence of

Until you get to monads, of course :-)