Re: Parser Cruft in gram.y

On 2012-12-20 15:58:12 +0000, Greg Stark wrote:
> On Thu, Dec 20, 2012 at 3:18 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> > Greg Stark <stark(at)mit(dot)edu> writes:
> >> But I'm not entirely convinced any of this is actually useful. Just
> >> becuase the transition table is large doesn't mean it's inefficient.
> >
> > That's a fair point. However, I've often noticed base_yyparse() showing
> > up rather high on profiles --- higher than seemed plausible at the time,
> > given that its state-machine implementation is pretty tight. Now I'm
> > wondering whether that isn't coming from cache stalls from trying to
> > touch all the requisite parts of the transition table.
>
> For what it's worth the bloat isn't in the parser transition table at all:
> 516280 yy_transition
> 147208 yytable
> 147208 yycheck
> 146975 base_yyparse
> 17468 yypact
> 9571 core_yylex
> 8734 yystos
> 8734 yydefact
>
> Unless I'm confused yy_transition is in fact the *lexer* transition
> table. I'm not sure how to reconcile that with the profiling results
> showing the cache misses in base_yyparse() though.

The scanner is compiled together with the parser, so its not unlikely
that the compiler bunches them together making only base_yyparse visible
in the profile.
I quickly checked though, and the top three offenders for L1 caches are
in bison not in the lexer... Its not implausible that the state
transitions in the lexer are better cached and/or predicted...

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services