nevin1@ihlpf.ATT.COM (00704a-Liber) (03/10/88)
In article <2791@enea.se> sommar@enea.UUCP(Erland Sommarskog) writes: >Nevin J Liber (nevin1@ihlpf.UUCP) writes: >>How many novice Pascal programmers use many global vars because it saves >>memory? On a paging system, though, you may need more pages in real memory >>because of the way the chaining of variables is done in Pascal. > > Nevin would have loved them. They used a lot of global variables. >A typical procedure could have some local variables, but mostly they >used the used the global ones, even for typical local purposes. To >make it even more fun, all variables had one-letter prefixes like >cnumber, cix etc. And on top of all, the modules were *huge*. 6000 >lines or so. > >So moral: You may save some execution time by having your variables >global, but you since you are obscuring your code so fatally, >you will lose the notion of what you are doing and introduce >bugs and inefficiencies instead. I would NOT have loved it!! I hope that I didn't give the impression that I like lots of global variables; that is not what I meant to do. I happen to think that the scoping rules are a plus for Pascal/Modula-2; but there are other implementations that can be done when efficiency is necessary. Globals, unless implemented with the optimization I'm going to state later, are much less efficient than using locals! If I didn't make that point clear in my last posting, please excuse me. For every level deep that a variable is used after it is declared, one climb up the static chain of activation records (I think this is the right term; it's been a long time since I took an implementation of PLs class) is required to access the variable (this is due to the possibility of recursion). For example: procedure p1(); var a1,b1:integer; procedure p2(); var a2,b2:integer; procedure p3(); var a3,b3:integer; begin ... end begin ... end begin ... end I am defining proc p1() to be on level 1 and p2() on level 2 (making p3() a level 3 declaration). In order for p3() to access var a1, 2 climbs on the static chain are required. This is in contrast to p3() accessing a3, which require no climbing of the static chain. If some vars are declared 'globally' (at the topmost level), it is very inefficient to access those variables in a procedure declared more than 1 or 2 levels deep. There is a way to implement scoping that alleviates this inefficiency, however. In addition to the standard var declarations, one should be allowed to declare a variable 'static' (to steal from C). The scoping would be the same as for standard vars (ex: if var a2 in the above example were declared as static, then only proc p2() and proc p3() could access it), but it would always take up the same physical location in memory (it would not be part of the activation record). The only difference between a static var and a standard var is that when used recursively, the same static var is always manipulated (it would be like implicitly passing it as a 'var' type). Note: This optimization can already be done on variables that can be determined not to be used recursively and are referenced at a level deeper then they are declared. However, by adding explicit static declarations, the programmer has much more flexibility. Comments?? -- _ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194 ' ) ) "The secret compartment of my ring I fill / / _ , __o ____ with an Underdog super-energy pill." / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah
crowl@cs.rochester.edu (Lawrence Crowl) (03/11/88)
In article <3949@ihlpf.ATT.COM> nevin1@ihlpf.UUCP (00704a-Liber,N.J.) writes: [access to variables outside the current scope] >For every level deep that a variable is used after it is declared, one climb >up the static chain of activation records is required to access the variable >(this is due to the possibility of recursion). An alternative technique for accessing these variables is "display registers". Essentially, you have a register pointing to the current activation record for each level of nesting. No pointer chasing is required. For more details, see a compilers text. In most modern architectures, access to local variables is no more expensive than access to global variables. For local variables, access is via a small offset off the frame pointer (or one of the display registers). For global variables, access is via an absolute address. Since absolute addresses require more storage to encode, they often take more time to execute. Even when global variables are more efficient, the gain in efficiency is often not worth the loss in program clarity. -- Lawrence Crowl 716-275-9499 University of Rochester crowl@cs.rochester.edu Computer Science Department ...!{allegra,decvax,rutgers}!rochester!crowl Rochester, New York, 14627
michael@boulder.Colorado.EDU (Michael Schmidt) (03/11/88)
Posting-Front-End: Gnews 1.1 In article <3949@ihlpf.ATT.COM>, nevin1@ihlpf (00704a-Liber) writes: > If some vars are declared 'globally' (at the topmost level), it is very > inefficient to access those variables in a procedure declared more than 1 > or 2 levels deep. There is a way to implement scoping that alleviates this > inefficiency, however. I think the most UN*X compilers do it rather efficient. The global variables are allocated in the bss (or data) segment. So the access to global *and* local variables doesn't require to follow the static chain. Michael Schmidt
ok@quintus.UUCP (Richard A. O'Keefe) (03/11/88)
In article <3949@ihlpf.ATT.COM>, nevin1@ihlpf (00704a-Liber) writes: > If some vars are declared 'globally' (at the topmost level), it is very > inefficient to access those variables in a procedure declared more than 1 > or 2 levels deep. There is a way to implement scoping that alleviates this > inefficiency, however. Can you say "display"? I knew you could. You don't even need a full display. Just retain a pointer to each level of the display you actually need. E.g. program main(..); var x; procedure one(...); var y; procedure two(...); var z; procedure three(...); begin {use x and y but not z} end; --> procedure three(...); var one_ptr: ^frame of one; begin one_ptr := self^.parent^.parent; {use global^.x and one_ptr^.y} end; Any Pascal compiler which searches the static chain on every non-local variable reference is a toy.
sommar@enea.se (Erland Sommarskog) (03/12/88)
00704a-Liber,N.J. (nevin1@ihlpf.UUCP) writes: >Globals, unless implemented with the optimization I'm going to state later, >are much less efficient than using locals! If I didn't make that point >clear in my last posting, please excuse me. > >For every level deep that a variable is used after it is declared, one >climb up the static chain of activation records (I think this is the right Nevin continues with an example, which I have deleted. Yes, that kind of globals are slower, for sure. I was thinking of variables declared on module/program level. They are allocated to a fix adress, and there very quick to access. In the case I quoted, I think they were global on process level. I don't know the details of the implementation, but it seems likely that time to access a process variable and local variable are about the same. >In addition to the standard var declarations, one should be allowed to >declare a variable 'static' (to steal from C). The scoping would be the >... >Note: This optimization can already be done on variables that can be >determined not to be used recursively and are referenced at a level deeper >then they are declared. However, by adding explicit static declarations, >the programmer has much more flexibility. Comments?? It seems to me that compiler should have the headache to decide which variables should be static, not the programmer. -- Erland Sommarskog ENEA Data, Stockholm sommar@enea.UUCP "Si tu crois l'amour tabou... Regarde bien, les yeux d'un fou!!!" -- Ange
robison@uiucdcsb.cs.uiuc.edu (03/12/88)
For languages without "upward funargs" (e.g. Pascal), a global display
is sufficient, and furthermore requires only one extra push/pop per
procedure call.
Let D[0..n] be the display registers. Then the code for entering a procedure
with lexical level n is:
push D[n];
D[n] := local_frame_pointer;
And the code for procedure exit is:
pop D[n];
return
One need not copy the entire display for each procedure call.
This was the Burroughs 6700's way of handling the display. I also notice
that it was rediscovered in SIPLAN notices last year. I suppose the
``expensive display'' myth is related to the ``expensive procedure call''
myth.
I've heard that the "static link" approach is not inefficient with a
global optimizer. The "chase" becomes a common subexpression and is
computed just once.
Arch D. Robison
University of Illinois at Urbana-Champaign
CSNET: robison@UIUC.CSNET
UUCP: {ihnp4,pur-ee,convex}!uiucdcs!robison
ARPA: robison@B.CS.UIUC.EDU (robison@UIUC.ARPA)djs@actnyc.UUCP (Dave Seward) (03/13/88)
In article <3949@ihlpf.ATT.COM> nevin1@ihlpf.UUCP (00704a-Liber,N.J.) writes: >Globals, unless implemented with the optimization I'm going to state later, >are much less efficient than using locals! If I didn't make that point >clear in my last posting, please excuse me. > >For every level deep that a variable is used after it is declared, one >climb up the static chain of activation records (I think this is the right >term; it's been a long time since I took an implementation of PLs class) is >required to access the variable >... >level 3 declaration). In order for p3() to access var a1, 2 climbs on the >static chain are required. This is in contrast to p3() accessing a3, which >require no climbing of the static chain. > >If some vars are declared 'globally' (at the topmost level), it is very >inefficient to access those variables in a procedure declared more than 1 >or 2 levels deep. There is a way to implement scoping that alleviates this >inefficiency, however. > This is true in principle, but it doesn't have to be implemented this way. First of all, a static link is a frame pointer for an enclosing activation record and so is a constant for a given invocation of a nested routine. The routine may therefore obtain the value once (through a static link chain walkback, or however) and then reuse it any number of times, even across calls. Some implementations create an array of static links, subscripted by the lexical level, and pass it into a routine, so that only a single dereference is required to access an outer level variable, regardless of the number of intervening levels. Finally, I believe that most compilers treat variables at the outermost level (usu. 1) as static anyway, so their addresses are constants during the program's execution. An optimizer can determine that a routine is not directly recursively called, and can either place its variables in the enclosing scope, or can at least access the enclosing scope variables directly via its own frame pointer, rather than using the static link. Dave Seward uucp.actnyc.djs
gvcormack@watdragon.waterloo.edu (Gordon V. Cormack) (03/14/88)
In article <170500016@uiucdcsb>, robison@uiucdcsb.cs.uiuc.edu writes: > > For languages without "upward funargs" (e.g. Pascal), a global display > is sufficient, and furthermore requires only one extra push/pop per > procedure call. Not true. Procedure and Function parameters can access an environment totally disjoint from the calling environment. Hence, each such parameter requires its own display (or static link). -- Gordon V. Cormack CS Dept, University of Waterloo, Canada N2L 3G1 gvcormack@waterloo { .CSNET or .CDN or .EDU } gvcormack@water { UUCP or BITNET }
michael@boulder.Colorado.EDU (Michael Schmidt) (03/14/88)
Posting-Front-End: Gnews 1.1 In article <170500016@uiucdcsb>, robison@uiucdcsb writes: > >For languages without "upward funargs" (e.g. Pascal), ... What do you mean with "upward funargs"? And (e.g. Pascal)?? Michael Schmidt
michael@boulder.Colorado.EDU (Michael Schmidt) (03/14/88)
Posting-Front-End: Gnews 1.1 In article <170500016@uiucdcsb>, robison@uiucdcsb writes: >For languages without "upward funargs" (e.g. Pascal), a global display >is sufficient, and furthermore requires only one extra push/pop per >procedure call. No! Cosider the following program: { LAST EDIT: Sat Mar 12 12:27:35 MST 1988 by Michael Schmidt (michael) } PROGRAM funparm (input, output); VAR FirstTime : Boolean; PROCEDURE f(procedure x); VAR j: integer; BEGIN x END; {f} PROCEDURE g(); VAR i: integer; PROCEDURE h(); BEGIN if FirstTime then begin FirstTime := false; f(h) end else writeln(i) END; {h} BEGIN h END; {g} BEGIN END. {funparm} At execution of 'h', you will have the frame of 'f' in the display for level 1 instead of the frame of 'g'! And you will get the value of 'j' instead of the value of 'i'! Right? Michael
firth@sei.cmu.edu (Robert Firth) (03/14/88)
In article <170500016@uiucdcsb> robison@uiucdcsb.cs.uiuc.edu writes: > >For languages without "upward funargs" (e.g. Pascal), a global display >is sufficient, and furthermore requires only one extra push/pop per >procedure call. Sigh! The erroneous display implementations seem to be repeatedly rediscovered. One more time: this fails in a language with any one of parametric procedures procedure variables parametric labels label variables jumps out of procedures It therefore fails in ISO Pascal, under the fifth case.
nevin1@ihlpf.ATT.COM (00704a-Liber) (03/19/88)
In article <2832@enea.se> sommar@enea.UUCP(Erland Sommarskog) writes: .00704a-Liber,N.J. (nevin1@ihlpf.UUCP) writes: . ..In addition to the standard var declarations, one should be allowed to ..declare a variable 'static' (to steal from C). The scoping would be the ..... ..Note: This optimization can already be done on variables that can be ..determined not to be used recursively and are referenced at a level deeper ..then they are declared. However, by adding explicit static declarations, ..the programmer has much more flexibility. Comments?? . .It seems to me that compiler should have the headache to decide which .variables should be static, not the programmer. I did not propose to eliminate that 'headache' from the compiler (see the word 'addition' in my first sentence) but to allow the user to specify variables he wishes to use on more than one level but allows recursive calls to use the same variable. With a type 'static', he can declare global-type (quick-access) variables AND restrict their scope. This would be in *addition* to the standard types of variable declarations. -- _ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194 ' ) ) "The secret compartment of my ring I fill / / _ , __o ____ with an Underdog super-energy pill." / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah