[PRL] Bob Harper's new blog

[will at ccs.neu.edu]

David Herman wrote:
> I also still find the 90% figure incredibly high. Your point
> about loops is fair; it certainly does help inflate the number.
> But I would not be surprised if the number is highly variable
> depending on the community and application domain.

It does vary a lot.  It depends not only on the application
and the programming style, but upon tiny details of programming
language semantics and implementation.

Consider Scheme, for example.  You'd think that the R6RS semantics
would increase the percentage of calls to procedures whose code
can be determined statically, and that's usually the case, but the
R6RS also changed the semantics of internal definitions.  To do a
good job of optimizing the new R6RS semantics, compilers have to
implement a special-purpose flow analysis that, to my knowledge,
has been implemented only in Chez Scheme and in Ikarus.  Even with
that special-purpose flow analysis, it's easy to construct examples
that can be fully optimized only by generating two versions of the
code or by using a JIT compiler that compiles the code twice; JIT
compilers that compile the code only once can't fully optimize
these examples.

It turns out that the special-purpose R6RS flow analysis and/or
double compilation is more important than I had hoped.  The table
below shows the percentages of closed calls that were made to
procedures whose code was known to Larceny's compiler.  (These data
understate the percentage of known calls because they don't include
calls that were inlined by the compiler, and inlined calls often
account for a large fraction of the known calls.)

    	    	    R5RS    R6RS
    conform          30      23
    dynamic          37      69
    earley           90      91
    graphs           44      65
    lattice          21      32
    matrix           57      65
    maze             51      88
    mazefun           3      92
    mbrot            97     100
    nboyer           94       0
    nqueens          93      96
    nucleic          50      96
    paraffins       100     100
    peval            64      35
    primes           58     100
    ray              42      99
    scheme           22      23
    simplex          61      99
    slatex           55      63

Look at the line for nboyer.  With the special-purpose flow analysis,
well over 90% of the closed calls would have been to known procedures.
Without that flow analysis, virtually all closed calls are to unknown
code.  (This effect is also visible, but less dramatic, for the conform
and peval benchmarks.)  Some of the benchmarks, such as graphs and
lattice, make such extremely heavy use of higher-order procedures that
even the special-purpose R6RS flow analysis would be fairly ineffective.
In most cases, however, the R6RS percentages that are below 90% result
from Larceny's omission of that special-purpose flow analysis.

> I'm still confused about your overall point. Is it that the combination
> of the static techniques and dynamic techniques make FP the winner?

This line of discussion started when Matthias asked:

    How does the dynamic dispatch of inheritance differ from
    the 'random' jumps induced by calls to first-class
    functions in FPLs?

I said it's a matter of degree.  My point is (1) Matthias's "'random'
jumps" aren't as harmful to static analysis as he and the OO advocates
think, and (2) the dynamic dispatch of OO languages is (in practice) less
amenable to static analysis, and is therefore optimized by dynamic means
such as method caches and JIT compilers that can see the entire class
graph (and are prepared to recompile if that class graph changes at run
time).

Will