Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site decwrl.UUCP
Path: utzoo!linus!decvax!decwrl!baskett
From: baskett@decwrl.UUCP (Forest Baskett)
Newsgroups: net.lang
Subject: Why displays are always faster than static links
Message-ID: <3731@decwrl.UUCP>
Date: Sat, 22-Oct-83 11:41:58 EDT
Article-I.D.: decwrl.3731
Posted: Sat Oct 22 11:41:58 1983
Date-Received: Sun, 23-Oct-83 07:36:59 EDT
Organization: DEC Western Research Lab, Los Altos, CA
Lines: 46

Displays are always faster than static links (except in pathological
cases) provided the compiler exercises a little bit of intelligence
when generating code for procedure entry and exit.  The previous
discussions make clear that displays are faster for referencing
non-locals/non-globals but some of them suggest that procedure
calling suffers more from displays than from static links.  In fact,
the reverse is usually true.  Here's why.  Most procedures do not do
non-local/non-golbal referencing so if we could find a way to call
and return from those procedures without any action related to
lexical scoping, we would, 99% of the time, be on the same footing
as languages without lexical scoping (e.g., C).  The display enables
us to do that if the compiler cooperates.  If I'm a procedure and I
have local variables that some other proceudre is going to access
(notice that this other procedure must be defined inside me), then
when I am entered, I must save the display pointer to my lexical level
that existed at entry and replace it with a pointer to my locals.  When
I exit, I need to restore the old display pointer.  Now here's the flip
side.  If I'm a procedure and NO OTHER procedure references my locals
(the usual case), then I can blithly DO NOTHING about the display pointer
to my lexical level.  I can leave it along, not touch it, not execute
any instructions associated with it.  When I exit, everything will be fine,
no matter who I've called in the meantime.  (This is an inductive argument.)
Can the compiler easily tell if no other procedures reference my locals?
Well, some compilers actually can and most compilers can be fixed so
that they can.  Remember that the only procedures that can reference my
locals are those that are defined INSIDE me.  Thus when the compiler gets
to the point of generating code for my body, it will have seen all the
procedures that have any chance of referencing my locals.  If it watches
for non-local/non-global references as it processes those procedures and
marks the current procedure being compiled at a lexical level that does
experience a non-local/non-global reference, then when it gets to my body
there will be a flag that tells it whether to bother with the display or
not on my entry and exit sequences.  A less demanding but almost as
effective strategy is to just key off the presence or absence of 
enclosed procedures.  If there are no procedures defined inside me
(a very common case), then I don't need to do display maintenance.

I've used this trick on several compilers now and it works and is very
effective.  I can't imagine ever using static links.  I don't know
where this trick comes from but I'm pretty sure it's pretty old.
I have a very foggy recollection of Edsgar Dijkstra telling Burroughs
Corporation how to do it for their Algol 60 compiler.  It's too bad
it doesn't ever seem to be mentioned in compiler books.

Forest Baskett
...!decwrl!baskett