Re: Is multi-level function return possible?

On Mon, 24 Mar 2014 17:06:07 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:


>So this [Atlas] compiler maintained a display in the registers.
>The costs here are:
>
> :
>
>2) Maintaining the display. AFAIK it turned out that maintaining the
>display is more costly in typical uses than the access cost it saves,
>so displays fell out of favour. This means that the run-time cost of
>non-local variables is typically even more costly on this implementation
>than one an implementation using static link chains.


I think it was more the expanded use of techniques like closure
conversion and lambda lifting that allowed rewriting nested code so as
to eliminate non-local accesses or to make them, at most, single
indirections through local pointers.


In any event, static links are more performant only when there is
relatively little use of deep non-locals - if you are often chasing
more than 2 links, you're better off using a display. Unfortunately,
although a compiler can determine the number of non-locals and the
number of lexical levels involved, it can't determine frequencies of
access so as to make an intelligent decision regarding implementation.


The instruction cost is slightly greater to maintain a display than to
maintain a static chain, but if the display is in suitably fast memory
- in registers or locked into cache - the actual difference in *time*
spent on maintenance may be insignificant.


Moreover, the maximum depth of display for any call chain can be
statically determined and a display does not have to be large to be
very effective: I recall usage studies of non-locals in programs
written in various languages - Algol, Pascal, Lisp, etc. - showing
that 4 levels was sufficient for ~80% of the code and 8 levels was
sufficient to handle very nearly all of it. IIRC, less than 0.1% of
all the code studied needed 16 or more levels.


I suspect that if similar studies were done today using modern nested
languages they would find very little difference: most programmers
just don't write very deeply *scoped* nested code - they tend to
create relatively shallow closures instead. And then the compiler
flattens the closures so all the variables within are a single
indirection regardless of lexical level. I.e. no more need for any
non-local mechanism.


You can (maybe) argue that a display in registers is wasteful and that
the registers could be put to better use. OTOH, the machine in
question may have had memory mapped pseudo-registers or a similar fast
RAM area for holding frequently used variables. Even if the registers
were real, they may have been dedicated to addressing/indexing anyway.


YMMV,
George

Return to the comp.compilers page.
Search the comp.compilers archives again.