NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/comp/lang/function/961

Text File | 1992-07-27 | 3.3 KB | 70 lines

Newsgroups: comp.lang.functional
Path: sparky!uunet!mcsun!sunic!kth.se!dentex.tds.kth.se!kff
From: [e-mail] (Karl-Filip Faxen)
Subject: Re: Gabriel benchmarks in a functional language?
Message-ID: <[e-mail]>
Sender: [e-mail] (Usenet)
Nntp-Posting-Host: dentex.tds.kth.se
Reply-To: [e-mail] (Karl-Filip Faxen)
Organization: Royal Institute of Technology, Stockholm, Sweden
References: <[e-mail]> <[e-mail]>
Date: Mon, 27 Jul 1992 15:32:05 GMT
Lines: 56

In article <[e-mail]>, [e-mail] (Vincent Delacour) writes:

|> Francis Dupont of INRIA has translated some of the Gabriel benchmarks
|> in a lazy variant of CAML. He found that, eg, the Boyer test program
|> was running faster in lazy mode than in eager mode, because most of
|> the lists it creates do not get used!
|>
|> Feel free to consider this a proof that lazyness is superior to
|> eagerness <8^]. IMO this is at best a proof that benchmarks are often
|> meaningless.

I haven't seen the code for the Gabriel benchmarks, but I can see three
reasons for this result:

(1) The benchmaks throws away their results, since they are just
    benchmarks. This is an old problem with optimizing compilers,
    that they eliminate 'unnecessary' code. It is interresting to
    note that in this sense, any lazy implementation will behave
    like a heavily optimizing implementation of an imperative
    language. This is often referred to as the 'self optimizing
    property' of lazy evaluation.

    The cure is, of course, to rewrite the benchmarks to do something
    with their result (eg write it to a file).

(2) The code is probably written so that datastructures are built
    and traversed. Now, these may sometimes not be traversed in their
    entirety, with the choice of what parts to traverse or not being
    data dependent. Also, these datastructures may be shared, ie
    traversed by several different functions. Then lazy evaluation
    guarantees that only the parts that actually are traversed will
    be constructed, and then they will only be constructed once.

    In a strict language, the datastructures in question will always
    be constructed in their entirety and only subsequently be
    traversed. The only way to get the behaviour of the lazy language
    is to merge the producer and consumers of the datastrucure. This
    may be hideously difficult and lead to very messy code, especially
    if there are multiple consumers (sharing), and one wishes to avoid
    recomputation by every consumer. In any case, even if there is only
    one consumer, modularity is greatly compromised.

    Thus laziness allows you to separate the problem of how to build
    the datastructure from the problem of determining how much of it
    will actually be needed.

(3) Sometimes, the evaluation order of a lazy evaluator is more
    efficient than that of a strict evaluator, since the lazy evaluator
    might build and traverse a datastructure incrementally using a
    constant amount of heap space and increasing the locality of the
    computation. This might have been such a case.


Karl-Filip
-----------------------------------------------------------------------
Make the frequent case fast, and the fast case frequent!