Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.misty.com!news.iecc.com!.POSTED!nerds-end From: George Neuner Newsgroups: comp.compilers Subject: Re: Is multi-level function return possible? Date: Wed, 26 Mar 2014 04:00:19 -0400 Organization: A noiseless patient Spider Lines: 55 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <14-03-060@comp.compilers> References: <14-03-020@comp.compilers> <14-03-022@comp.compilers> <14-03-025@comp.compilers> <14-03-030@comp.compilers> <14-03-044@comp.compilers> <14-03-046@comp.compilers> <14-03-047@comp.compilers> <14-03-048@comp.compilers> <14-03-053@comp.compilers> <14-03-057@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: miucha.iecc.com 1395851644 32271 2001:470:1f07:1126:0:676f:7373:6970 (26 Mar 2014 16:34:04 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Wed, 26 Mar 2014 16:34:04 +0000 (UTC) Keywords: code, history Posted-Date: 26 Mar 2014 12:34:04 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1182 On Mon, 24 Mar 2014 17:06:07 GMT, anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote: >So this [Atlas] compiler maintained a display in the registers. >The costs here are: > > : > >2) Maintaining the display. AFAIK it turned out that maintaining the >display is more costly in typical uses than the access cost it saves, >so displays fell out of favour. This means that the run-time cost of >non-local variables is typically even more costly on this implementation >than one an implementation using static link chains. I think it was more the expanded use of techniques like closure conversion and lambda lifting that allowed rewriting nested code so as to eliminate non-local accesses or to make them, at most, single indirections through local pointers. In any event, static links are more performant only when there is relatively little use of deep non-locals - if you are often chasing more than 2 links, you're better off using a display. Unfortunately, although a compiler can determine the number of non-locals and the number of lexical levels involved, it can't determine frequencies of access so as to make an intelligent decision regarding implementation. The instruction cost is slightly greater to maintain a display than to maintain a static chain, but if the display is in suitably fast memory - in registers or locked into cache - the actual difference in *time* spent on maintenance may be insignificant. Moreover, the maximum depth of display for any call chain can be statically determined and a display does not have to be large to be very effective: I recall usage studies of non-locals in programs written in various languages - Algol, Pascal, Lisp, etc. - showing that 4 levels was sufficient for ~80% of the code and 8 levels was sufficient to handle very nearly all of it. IIRC, less than 0.1% of all the code studied needed 16 or more levels. I suspect that if similar studies were done today using modern nested languages they would find very little difference: most programmers just don't write very deeply *scoped* nested code - they tend to create relatively shallow closures instead. And then the compiler flattens the closures so all the variables within are a single indirection regardless of lexical level. I.e. no more need for any non-local mechanism. You can (maybe) argue that a display in registers is wasteful and that the registers could be put to better use. OTOH, the machine in question may have had memory mapped pseudo-registers or a similar fast RAM area for holding frequently used variables. Even if the registers were real, they may have been dedicated to addressing/indexing anyway. YMMV, George