Re: Good explanation of Recursive Ascent Parsing wanted

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> >[Maybe it'll even be slower since
> >there is a lot more code so it's less likely to fit in a CPU cache.
> >-John]
>
> My experience is: Don't worry about I-cache misses until you have
> them. I have seen cases where a lot of code was produced, but it had
> enough temporal and spatial locality that I-cache misses were no
> problem, as well as a case where we applied a technique that reduced
> the code size (with the intent of reducing I-cache misses), but as a
> result we saw a slowdown from increased I-cache misses, because the
> resulting code had worse spatial locality.
>
> Looking at the numbers in 'Thomas J Penello (1986). "Very fast LR
> parsing"', one need not worry much about the I-cache: He describes an
> experiment with a grammar with 126 productions, resulting in 192
> states, 305 terminal transitions and 226 nonterminal transitions in
> the LALR(1) parser; the resulting parse tables for the table-driven
> parser has 2022 bytes, while the recursive-ascent parser has 5602
> bytes (including 397 bytes in common with the table-driven parser).
> I-cache sizes these days are typically 32KB, so this parser would be
> completely within the I-cache (even if we assume a factor of two from
> going from 80286 code to AMD64 code), so one does not even need to
> think about locality. Penello also reports that a 158-production
> grammar for standard Pascal with a few minor extensions yielded a
> 5326-line assembly program (which MASM 3.0 failed to assemble); this
> should also easily fit into 32KB.


Karlsruhe team (Grosch and collaborators) had somewhat different
conclusions. When they added extra features needed for production
compiler they noted slowdowns on bigger grammars when translating
to code. OTOH they reported quite good results from table-driven
parsers. Reports were available online, but I do not have links
handy (quite possible that old links are broken now).


Of couse, modern machines tend to have larger caches than the
old ones. But also modern machines are troughput oriented
and my suffer more from latency.


--
                                                            Waldek Hebisch

Return to the comp.compilers page.
Search the comp.compilers archives again.