peterr@utcsrgv.UUCP (Peter Rowley) (10/21/83)
Thanks to all those that responded to my query about the relative merits of
static links and displays. The comparison is not as simple as one would
expect.
First, I'll assume that one has "good" implementations of both mechanisms.
This means that both allow fast access to both local and global variables,
via a register pointing to the local activation record (needed anyway) and
either a register pointing to the level 0 activation record or addresses
of global variables directly in the code.
Given this, average variable access times for the two mechanisms will be
very close, as virtually all variable accesses are to local or global
variables. A notable exception to this pattern is the code for a recursive
descent compiler that uses one procedure per syntactic construct (e.g. the
compiler in Wirth's Algorithms+Data Structures = Bugs). Exceptions favour
the display. Reports of other exceptions are welcome.
The performance of a few other operations is affected by the choice of
mechanism: procedure call and exit and context switch. Procedure exit
takes longer with a display, as one display entry must be restored. The effect
of using a display on context switching depends on where the display is
stored. If it's in a set of registers, those registers have to be saved
and restored with the display for a new process on every context switch.
If the display is in memory, and thus slower to access, this is not a
problem, as it can be considered to be part of the per-process data.
Since, in a "good" implementation, the display is not accessed except
for non-local/non-global variables, it may well pay to put the display
in memory.
This leaves procedure call. The relative performance of the two
mechanisms depends on the distribution of procedure calls. If they
follow the almost-all-local-or-global pattern of variable access,
the static link mechanism will come out ahead, as it has less work
to do than the display mechanism (the latter has to save the display entry
it is about to update). If there are a lot of intermediate level calls,
such as in a recursive descent compiler, the display will probably win.
So, for most applications, the static link mechanism seems to come out
ahead, assuming a "good" implementation. This may be a moot point, as
many new languages have only two levels at run-time: local and global.
Do people think that languages that support many lexical levels are still
needed? Not many people still write procedure-based recursive descent
parsers, as far as I know.
peter rowley, University of Toronto Department of C.S., Ontario Canada M5S 1A4
{cornell,watmath,ihnp4,floyd,allegra,ubc-vision,uw-beaver}!utcsrgv!peterr
{cwruecmp,duke,linus,decvax,research}!utzoo!utcsrgv!peterr