pardo@june.cs.washington.edu (David Keppel) (03/11/88)
In article <7562@sol.ARPA> crowl@cs.rochester.edu (Lawrence Crowl) writes: > >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. (Paraphrasing) from compilers class: "Displays are a really great idea, but are too expensive to implement to be useful for Algol-class languages." Where "too expensive" is measured in terms of the cost of maintaining one over each procedure call versus the performance penalty for scanning up the dynamic links. This cost measure is not true where there is hardware support for displays, but the implication is that your money would be better spent somewhere else. ;-D on ( Golly, Gee, and Whiz ) Pardo
crowl@cs.rochester.edu (Lawrence Crowl) (03/12/88)
In article <4426@june.cs.washington.edu> pardo@uw-june.UUCP (David Keppel) writes: )(Paraphrasing) from compilers class: ) ) "Displays are a really great idea, but are too expensive to ) implement to be useful for Algol-class languages." ) )Where "too expensive" is measured in terms of the cost of maintaining )one over each procedure call versus the performance penalty for scanning )up the dynamic links. Displays require one more load-to-register to implement than do static chains. (Assuming you have enough registers to implement the display. Most new processors do.) Given this incremental cost, an average of less than ONE non-local reference per procedure will pay for the cost of maintaining the display. To convince me that displays are not worth the cost, you must show me hard data indicating that non-local references are not much used. -- 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/13/88)
Posting-Front-End: Gnews 1.1 In article <7629@sol.ARPA>, crowl@cs (Lawrence Crowl) writes: >In article <4426@june.cs.washington.edu> pardo@uw-june.UUCP >(David Keppel) writes: >)(Paraphrasing) from compilers class: >) >) "Displays are a really great idea, but are too expensive to >) implement to be useful for Algol-class languages." >) >)Where "too expensive" is measured in terms of the cost of maintaining >)one over each procedure call versus the performance penalty for scanning >)up the dynamic links. > >Displays require one more load-to-register to implement than do static chains. That would be nice. But, it is wrong, unfortunately (as long as we have nested procedures and functional parameters, and I like this!). How would you implement the correct display, when a procedure of depth k calls a functional parameter of say k+n. At this moment you have no garanty that the static predecessor or the predecessor of the predecessor of the called procedure is in the display at all. So you have to reconstruct the display and restore it again at return time. How would you do this without static chain? >(Assuming you have enough registers to implement the display. Most new >processors do.) Well, I always thought, that the MC68020 is a fairly new processor. It has not more than 6 address register available for it (may be only 5). So if you have a nesting depth of six (not very common, but may happen), you have to be very carefull (and slow) with address computations. >To convince me that displays are not worth the cost, you must show >me hard data indicating that non-local references are not much used. Take a look in the PhD thesis of Lynn Carter, Univ. of Colorado, 1980. He analysed pascal programs and found out, that of all references to variables 56.47% are for global ones (under unix in bss or data memory, no chain involved), 36.66% to local ones (obviously no chain involved) and 5.97 to local-1 ones (one step in the chain). All others accounted for 0.9% and I think that is not so much. In article <758@cresswell.quintus.UUCP>, ok@quintus (Richard A. O'Keefe) writes: >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. See above. Non local variable don't really exist. But, that is nothing other than keeping a local display per activation record. But for that you have to maintain a static chain. I really see no possibility to implement pascal without static chain. Michael Schmidt -- Michael Schmidt, Universitaet-GH Paderborn, FB 17, Warburger Str.100, D-4790 Paderborn, West Germany z.Zt.: University of Colorado, Boulder Mail: michael@boulder.UUCP or michael@boulder.Colorado.EDU
firth@sei.cmu.edu (Robert Firth) (03/14/88)
In article <7629@sol.ARPA> crowl@cs.rochester.edu (Lawrence Crowl) writes: >Displays require one more load-to-register to implement than do static chains. >(Assuming you have enough registers to implement the display. Most new >processors do.) This statement is true ONLY for languages that do not have parametric procedures or procedure variables. Invoking a parametric procedure can require an arbitrary amount of a display to be reset, whereas the cost of maintaining the static chain is still very small. Moreover, the cost in other areas of reserving 5 or 6 registers for a display can be pretty high - you have that many fewer for locals, temporaries, parameters &c. By the way, what is the compiler supposed to do when a user nests procedures more deeply than you've allowed for in the display registers? Crash disgustingly?
news@santra.UUCP (news) (03/15/88)
In article <4808@sigi.Colorado.EDU> michael@boulder.Colorado.EDU (Michael Schmidt) writes: >In article <7629@sol.ARPA>, crowl@cs (Lawrence Crowl) writes: >>Displays require one more load-to-register to implement than do static chains. I think displays are much more efficient than static chains, for the following resons: - When calling a procedure of nesting depth N, you only have to do three things: 1) Push the value of display element N on the stack. This value is pointer to the activation record of the last called procedure of nesting depth N. 2) Save the address of the newly created activation record in display element N. 3) Upon return from the procedure, pop the saved value of the display element. Note also, that not even these steps are required if the variables of the called procedure are not accessed by procedures at nesting depth > N. Non-local variables are accessed from the called procedure by looking in the activation record pointed to by the appropriate display element. Using static chains the computer may have to do a lot more work at run time. First, calling a procedure at nesting level N from a procedure at nesting level M > N involves following M-N+1 access links to find out the activation record of the enclosing procedure. Second, accessing a variable at nesting level N from a procedure at nesting level M > N also means that you have to follow M-N access links to reach the activation record of the outer procedure. >That would be nice. But, it is wrong, unfortunately (as long as >we have nested procedures and functional parameters, and I like >this!). How would you implement the correct display, when a >procedure of depth k calls a functional parameter of say k+n. At >this moment you have no garanty that the static predecessor or >the predecessor of the predecessor of the called procedure is in >the display at all. So you have to reconstruct the display and >restore it again at return time. How would you do this without >static chain? You are right, this can't be done with a display. But as the subject line says "Wirth-type languages" I can't resist mentioning that this has been "fixed" :-) in Modula-2. Quoting from "Programming in Modula-2" (2.ed, p. 79): "... procedures that are assigned to variables or are passed as parameters, must not be declared local to any procedure." >>(Assuming you have enough registers to implement the display. Most new >>processors do.) > >Well, I always thought, that the MC68020 is a fairly new >processor. It has not more than 6 address register available for >it (may be only 5). So if you have a nesting depth of six (not >very common, but may happen), you have to be very carefull (and >slow) with address computations. I don't understand why it is necessary to implement the display using registers. A display element and an access links in the static chain are essentially the same thing: a pointer to an activation record on the stack. But the display has the advantage that its elements always point directly to the wanted activation record, and not to an activation record that contains a pointer to another activation record that may point to the activation record with the sought variable, or it may point to an activation record that contains a pointer to still another activation record that... Also, the display can be allocated in static memory, with fixed addresses. >>To convince me that displays are not worth the cost, you must show >>me hard data indicating that non-local references are not much used. > >[hard data omitted] But there is no cost, if you don't use non-local references. See above. > > Michael Schmidt >-- >Michael Schmidt, Universitaet-GH Paderborn, FB 17, Warburger Str.100, > D-4790 Paderborn, West Germany >z.Zt.: University of Colorado, Boulder >Mail: michael@boulder.UUCP or michael@boulder.Colorado.EDU Johan Myreen s30780a@puukko.hut.fi ...!mcvax!santra!puukko!s30780a
sommar@enea.se (Erland Sommarskog) (03/15/88)
What is quite evident from this debate is that the programmer
shouldn't really bother about this. His main task is to express
the solution of the problem as clearly as possible in the language
he is using. He should not bother too much about such things as globals
vs. locals. What may be fast one compiler may be slow on another
and vice versa, depending on the technique they use.
--
Erland Sommarskog
ENEA Data, Stockholm
sommar@enea.UUCP "Si tu crois l'amour tabou...
Regarde bien, les yeux d'un fou!!!" -- Angemichael@boulder.Colorado.EDU (Michael Schmidt) (03/17/88)
Posting-Front-End: Gnews 1.1 In article <11151@santra.UUCP>, news@santra (news) writes: >You are right, this can't be done with a display. But as the >subject line says "Wirth-type languages" I can't resist mentioning >that this has been "fixed" :-) in Modula-2. Quoting from "Programming in >Modula-2" (2.ed, p. 79): "... procedures that are assigned to variables >or are passed as parameters, must not be declared local to any >procedure." Yeah, Modula-2 is the way, of course. Unfortunately, there exists a language named 'pascal', which is considered to be "Wirth-type", too. -- Michael Schmidt, Universitaet-GH Paderborn, FB 17, Warburger Str.100, D-4790 Paderborn, West Germany z.Zt.: University of Colorado, Boulder Mail: michael@boulder.UUCP or michael@boulder.Colorado.EDU
nevin1@ihlpf.ATT.COM (00704a-Liber) (03/19/88)
In article <2850@enea.se> sommar@enea.UUCP(Erland Sommarskog) writes: > >What is quite evident from this debate is that the programmer >shouldn't really bother about this. His main task is to express >the solution of the problem as clearly as possible in the language >he is using. He should not bother too much about such things as globals >vs. locals. What may be fast one compiler may be slow on another >and vice versa, depending on the technique they use. I guess you never actually had to *sell* a program :-). While I would like never having to worry about how a language is implemented, I can't get my job done well if I don't. It would be nice if we could program assuming an infinite amount of memory and infinitely fast processors, but neither of those things exist (yet :-)). For example: two days ago I implemented a nice concise algorithm for parsing. When I tried to run it, I got a memory error. It turns out that it was due to the garbage collection scheme the language I was using implemented (something which I have no control over). I ended up having to reimplement the algorithm so that it accounted for garbage collection. Another example: when I was first learning Pascal, I was using an Apple II + with 64K of memory. I learned very quickly how large the stack space was because many of my consise (and usually recursive) routines would bomb with a fatal error. A programmer should always try to take into consideration how the language he is using is implemented. His/her task is not only to express the solution to a problem clearly and easily, but to express it so that his/her solution will work given real-world constraints. -- _ __ 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