Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3176

Re: Good explanation of Recursive Ascent Parsing wanted

Show all headers | View raw

>[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.

Concerning recursive ascent, my dim memory of the article I read about
it a long time ago says that on reduction a routine does often not
return to its parent caller, but to some ancestor.  Since the
introduction of the return stack predictor in microarchitectures in
the mid-1990s, implementing that directly causes at least one
misprediction (~20 cycles), and possibly there are followup
mispredictions from having the predictor stack go out-of-sync with the
real returns.  Looking at the Wikipedia page, it says that on
reduction a counter is returned, so you take the returns one at a time
and count down until you arrive at the desired level.  This costs some
cycles, too.

Overall the performance of recursive ascent relative to table-driven
is less advantageous than it may have been in the 1980s (before branch
prediction and I-caches).  Penello reports a speedup by a factor 5.5
for the recursive-ascent parser (which uses assembly language) over
"an interpretive LR parser written in Pascal and compiled by a good
optimizing Pascal compiler" on an 80286.  It would be interesting to
see a performance comparison between todays Bison skeletons compiled
with a present-day optimizing C compiler and a recursive ascent parser
on present-day hardware.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Good explanation of Recursive Ascent Parsing wanted Aaron Gray <aaronngray@gmail.com> - 2022-09-28 20:26 -0700
  Re: Good explanation of Recursive Ascent Parsing wanted Kaz Kylheku <864-117-4973@kylheku.com> - 2022-09-29 17:49 +0000
    Re: Good explanation of Recursive Ascent Parsing wanted Aaron Gray <aaronngray@gmail.com> - 2022-09-29 11:55 -0700
      Re: Good explanation of Recursive Ascent Parsing wanted Kaz Kylheku <864-117-4973@kylheku.com> - 2022-09-29 22:32 +0000
  Re: Good explanation of Recursive Ascent Parsing wanted anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-09-30 08:05 +0000
    Re: Good explanation of Recursive Ascent Parsing wanted antispam@math.uni.wroc.pl - 2022-10-06 15:30 +0000
      Re: Good explanation of Recursive Ascent Parsing wanted Kaz Kylheku <864-117-4973@kylheku.com> - 2022-10-07 18:57 +0000
  Re: Good explanation of Recursive Ascent Parsing wanted Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2022-09-30 10:45 +0000

csiph-web