From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,affd14e05b8fb09a X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2004-04-29 09:36:32 PST Path: archiver1.google.com!news1.google.com!news.glorb.com!border1.nntp.ash.giganews.com!nntp.giganews.com!local1.nntp.ash.giganews.com!nntp.comcast.com!news.comcast.com.POSTED!not-for-mail NNTP-Posting-Date: Thu, 29 Apr 2004 11:36:31 -0500 Date: Thu, 29 Apr 2004 12:36:30 -0400 From: "Robert I. Eachus" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Hierarchical States Machines References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Message-ID: NNTP-Posting-Host: 24.147.90.114 X-Trace: sv3-xTcHOeA/rw9MdpeKLk4okScwjjTc2JTHt/GyD5aqAxNHe2lXL7wBM0CkNvjyJ/jIYJ/QwCBJoP86Awh!BJSdNoUYb8pr/tKE3Yms7UzWjNVDa9FLtQmuw5s5iUu8owAl12DLG/jXMIrtng== X-Complaints-To: abuse@comcast.net X-DMCA-Complaints-To: dmca@comcast.net X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.1 Xref: archiver1.google.com comp.lang.ada:7569 Date: 2004-04-29T12:36:30-04:00 List-Id: tmoran@acm.org wrote: >>and ran 40% slower. (Register pressure from those state variables push > > Do you mean the parser state transitions ran 40% slower, or the whole > compiler, including IO, lexer, symbol tables, code generation, etc > was slowed by 40%? Sorry, the first pass of the compiler, which included the scanner (lexer) and created the symbol table and AST. The second pass did the semantic analysis and 'decorated' the parse tree, and did all the code-generator independent optimizations. As I remember it, the running times were roughly 1-3-3. So it would have been 1.4-3-3, for a 5 to 6% overall slowdown. Even so it was pretty huge, and it shocked me. By the point this occurred we had done a lot of optimization of the LALR1 engine and structure so that (mostly for error correcting reasons) successive reduce operations on the parse stack were deferred, then all called at once after two successful succeeding shifts, or a successful shift and (pending) reduce. That sounds complicated, and it was. But it made for wonderful syntax error correction without increasing the parse table size. (Well we had about a half dozen added states to allow "panic mode" if none of the single or double token fixes worked.) We were initially worried about the changes for the error correction support slowing down performance, but since it grouped the actions that resulted in subroutine calls, it actually sped things up significantly by eliminating register spills. When we looked at the generated code to try and explain that 40% number, adding the two flags for the non-goto solution increased the number of active variables from 6 to 8 in the key loops--and we had six available registers once you eliminated the stack pointer and program counter. Worse the access pattern basically rotated through the variables. We thought about fixing that for both the Ada and Multics PL/1 compilers, but a little bit of monitoring indicated that this code was about the only thing around that hit this 'misfeature'. The wonderful thing about being in a compiler group, and using Multics, was that we could slip in performance counters like this on the production machine, and see whether or not we should actually fix anything. Technically our group supported the DPS-6 line not DPS-8M, but we were in Billerica, MA, Multics development was at CISL in Cambridge, MA, and GCOS-3/8 support was in Phoenix, AZ. So I could submit a performance counter proposal like that to CISL, and we and they would put it into the "development" version of the compiler within a few days. My favorite story about doing that was that we had a debate about using static links or a display to manage up-level references in the Ada/SIL compiler. We had a ferocious call-graph analyzer that merged stack frames whenever possible, and of course, all variables in library packages (and in the main program if it was not called recursively) were handled directly. So we put in a trigger that added the static pointers if necessary, and sent e-mail to a list of compiler people. Almost two years later, I finally got one of those messages--for an ACVC test. We decided we would take that code out and use a dynamic stack walk if it was really necessary. I don't think that change ever happened--it was of course, very low priority. -- Robert I. Eachus "The terrorist enemy holds no territory, defends no population, is unconstrained by rules of warfare, and respects no law of morality. Such an enemy cannot be deterred, contained, appeased or negotiated with. It can only be destroyed--and that, ladies and gentlemen, is the business at hand." -- Dick Cheney