gvcormack@watdragon.waterloo.edu (Gordon V. Cormack) (03/13/88)
In article <4426@june.cs.washington.edu>, pardo@june.cs.washington.edu (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. This is just not true. For ordinary procedure calls, a global display involves trivial entry and exit overhead. The only time displays get expensive is if you do lots of "functional" style programming - passing procedures as parameters and/or using procedure variables. Even this is quite bearable - it uses time and space proportional to n to build a local copy of the display in order to pass a procedure (or procedures) as a parameter. Here is a comparison of the time to do static links vs. displays. (in terms of "n", the level of nesting). STRATEGY: static links global disply ENTRY CODE: O(1) O(1) EXIT CODE: 0 O(1) NONLOCAL REF: O(n) O(1) FUNC PARM: O(1) O(n)* --- * This cost applies only to procedures containing all of: a local variable x a nested procedure y that references x a procedure call passing y as a parameter -- 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 <5673@watdragon.waterloo.edu> you write: >This is just not true. For ordinary procedure calls, a global >display involves trivial entry and exit overhead. The only time >displays get expensive is if you do lots of "functional" style >programming - passing procedures as parameters and/or using >procedure variables. Carefull. If you have full procedure variables, you even cannot use the usual stack of activation records, because the extent of a procedure doesn't end necessarily, when you leave it. >Even this is quite bearable - it uses time >and space proportional to n to build a local copy of the display >in order to pass a procedure (or procedures) as a parameter. And you have to pass variable length, big objects around. >Here is a comparison of the time to do static links vs. displays. >(in terms of "n", the level of nesting). > > STRATEGY: static links global disply > > ENTRY CODE: O(1) O(1) > EXIT CODE: 0 O(1) > NONLOCAL REF: O(n) O(1) > FUNC PARM: O(1) O(n)* Yes, and now? If you realize, that NONLOCAL REF account for less than ONE PERCENT of all references (if we consider LOCAL-1 to be nearly LOCAL, cf. <4808@sigi.Colorado.EDU>), why should one use displays?? Michael Schmidt