Re: Parser Cruft in gram.y

Tom Lane wrote:

> the parser tables are basically number-of-tokens wide by
> number-of-states high. (In HEAD there are 433 tokens known to the
> grammar, all but 30 of which are keywords, and 4367 states.)
>
> Splitting the grammar into multiple grammars is unlikely to do
> much to improve this --- in fact, it could easily make matters
> worse due to duplication.

I agree that without knowing what percentage would be used by each
parser in a split, it could go either way.  Consider a hypothetical
situation where one parser has 80% and the other 50% of the current
combined parser -- 30% overlap on both tokens and grammer
constructs. (Picking numbers out of the air, for purposes of
demonstration.)

Combined = 433 * 4,367 = 1,890,911

80% = 346 * 3,493 = 1,208,578
50% = 216 * 2,183 =   471,528

Total for split =   1,680,106

Of course if they were both at 80% it would be a higher total than
combined, but unless you have a handle on the percentages, it
doesn't seem like a foregone conclusion. Do you have any feel for
what the split would be?

-Kevin

"Kevin Grittner" <kgrittn(at)mail(dot)com> writes:
> Tom Lane wrote:
>> the parser tables are basically number-of-tokens wide by
>> number-of-states high. (In HEAD there are 433 tokens known to the
>> grammar, all but 30 of which are keywords, and 4367 states.)
>>
>> Splitting the grammar into multiple grammars is unlikely to do
>> much to improve this --- in fact, it could easily make matters
>> worse due to duplication.

> Of course if they were both at 80% it would be a higher total than
> combined, but unless you have a handle on the percentages, it
> doesn't seem like a foregone conclusion. Do you have any feel for
> what the split would be?

I don't really, but I will note that the scalar-expression subgrammar is
a pretty sizable part of the whole, and it's difficult to see how you'd
make a useful split that didn't duplicate it. I guess you could push
CREATE TABLE, ALTER TABLE, CREATE DOMAIN, ALTER DOMAIN, COPY, and
anything else that included expression arguments over into the "main"
grammar. But that path leads to more and more stuff getting moved to
the "main" grammar over time, making the whole thing more and more
questionable. The whole concept seems ugly and unmaintainable in any
case.

regards, tom lane

On Sat, Dec 15, 2012 at 11:52 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> "Kevin Grittner" <kgrittn(at)mail(dot)com> writes:
>> Tom Lane wrote:
>>> the parser tables are basically number-of-tokens wide by
>>> number-of-states high. (In HEAD there are 433 tokens known to the
>>> grammar, all but 30 of which are keywords, and 4367 states.)
>>>
>>> Splitting the grammar into multiple grammars is unlikely to do
>>> much to improve this --- in fact, it could easily make matters
>>> worse due to duplication.
>
>> Of course if they were both at 80% it would be a higher total than
>> combined, but unless you have a handle on the percentages, it
>> doesn't seem like a foregone conclusion. Do you have any feel for
>> what the split would be?
>
> I don't really, but I will note that the scalar-expression subgrammar is
> a pretty sizable part of the whole, and it's difficult to see how you'd
> make a useful split that didn't duplicate it. I guess you could push
> CREATE TABLE, ALTER TABLE, CREATE DOMAIN, ALTER DOMAIN, COPY, and
> anything else that included expression arguments over into the "main"
> grammar. But that path leads to more and more stuff getting moved to
> the "main" grammar over time, making the whole thing more and more
> questionable. The whole concept seems ugly and unmaintainable in any
> case.

I thought a little bit about the sort of thing that Dimitri is
proposing in the past, and it seemed to me that one could put DML in
one grammar and everything else in another grammar and then decide,
based on the first word of the input, which grammar to use. But there
are a couple of problems with this. First, the DML grammar has to
include an awful lot of stuff, because the grammar for expressions is
really complicated and involves a lot of things like special-case
syntax for XML that are probably not really carrying their weight but
which cannot easily be factored out. Second, the DDL grammar would
have to duplicate a lot of stuff that also shows up in the DML
grammar, because things like expressions can also show up in DEFAULT
or USING clauses which show up in things like CREATE TABLE and ALTER
TABLE and CREATE SCHEMA .. CREATE TABLE.

Now either one of these problems by itself might not be sufficient to
kill the idea: if the DML grammar were a small subset of the full
grammar, one might not mind duplicating some stuff, on the grounds
that in most cases that full grammar would not be used, and using only
the smaller tables most of the time would be easier on the L1 cache.
And on the other hand, if you could get a clean split between the two
grammars, then regardless of exactly what the split was, it might seem
a win. But it seemed to me when I looked at this that you'd have to
duplicate a lot of stuff and the small parser still wouldn't end up
being very small, which I found hard to get excited about.

I'm frankly kind of shocked at the revelation that the parser is
already 14% of the backend. I knew it was big; I didn't realize it
was THAT big.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> I'm frankly kind of shocked at the revelation that the parser is
> already 14% of the backend. I knew it was big; I didn't realize it
> was THAT big.

Yeah, likewise. It makes me wonder whether we aren't past the size
of grammar that bison is a good choice for: considering that gram.y
is only circa 1% of the source text, it's surprising to find that
it compiles to >10% of the object code.

I'm not sure what other tool might be better though. I looked through
http://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages
but it seems our options are a bit limited if we want something
that produces C. It's not clear to me that any of the likely options
are as mature as bison, let alone likely to substantially outperform it.
(For instance, Hyacc sounded pretty promising until I got to the part
about it doesn't yet support %union or %type.) Still, I didn't spend
much time on this --- maybe somebody else would like to do a bit more
research.

regards, tom lane

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> And on the other hand, if you could get a clean split between the two
> grammars, then regardless of exactly what the split was, it might seem
> a win. But it seemed to me when I looked at this that you'd have to
> duplicate a lot of stuff and the small parser still wouldn't end up
> being very small, which I found hard to get excited about.

I think the goal is not so much about getting a much smaller parser, but
more about have a separate parser that you don't care about the "bloat"
of, so that you can improve DDL without fearing about main parser
performance regressions.

If we come out with no regression and no gain on the main query parser,
I say it still worth the separation effort. And anyway we only add
things to the main parser (queries) when the standard saith we have to.

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
> I'm not sure what other tool might be better though. I looked through
> http://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages
> but it seems our options are a bit limited if we want something
> that produces C. It's not clear to me that any of the likely options
> are as mature as bison, let alone likely to substantially outperform it.
> (For instance, Hyacc sounded pretty promising until I got to the part
> about it doesn't yet support %union or %type.) Still, I didn't spend
> much time on this --- maybe somebody else would like to do a bit more
> research.

I did spend a very little time on it too, with a different search angle,
and did find that "experimental" thing that might be worth looking at,
or maybe not.

http://en.wikipedia.org/wiki/Parsing_expression_grammar
http://piumarta.com/software/peg/

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

On Tue, Dec 18, 2012 at 4:33 AM, Dimitri Fontaine
<dimitri(at)2ndquadrant(dot)fr> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> And on the other hand, if you could get a clean split between the two
>> grammars, then regardless of exactly what the split was, it might seem
>> a win. But it seemed to me when I looked at this that you'd have to
>> duplicate a lot of stuff and the small parser still wouldn't end up
>> being very small, which I found hard to get excited about.
>
> I think the goal is not so much about getting a much smaller parser, but
> more about have a separate parser that you don't care about the "bloat"
> of, so that you can improve DDL without fearing about main parser
> performance regressions.

Well that would be nice, but the problem is that I see no way to
implement it. If, with a unified parser, the parser is 14% of our
source code, then splitting it in two will probably crank that number
up well over 20%, because there will be duplication between the two.
That seems double-plus un-good.

I can't help but suspect that the way we handle keywords today is
monumentally inefficient. The unreserved_keyword products, et al,
just seem somehow badly wrong-headed. We take the trouble to
distinguish all of those cases so that we an turn around and not
distinguish them. I feel like there ought to be some way to use lexer
states to handle this - if we're in a context where an unreserved
keyword will be treated as an IDENT, then have the lexer return IDENT
when it sees an unreserved keyword. I might be wrong, but it seems
like that would eliminate a whole lot of parser state transitions.
However, even if I'm right, I have no idea how to implement it. It
just seems very wasteful that we have so many parser states that have
no purpose other than (effectively) to convert an unreserved_keyword
into an IDENT when the lexer could do the same thing much more cheaply
given a bit more context.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 12/18/12 5:10 PM, Robert Haas wrote:
> I can't help but suspect that the way we handle keywords today is
> monumentally inefficient. The unreserved_keyword products, et al,
> just seem somehow badly wrong-headed. We take the trouble to
> distinguish all of those cases so that we an turn around and not
> distinguish them. I feel like there ought to be some way to use lexer
> states to handle this - if we're in a context where an unreserved
> keyword will be treated as an IDENT, then have the lexer return IDENT
> when it sees an unreserved keyword.

The problem would be the lookahead. You need to know the next token
before you can decide what context the current one is in.

On Tue, Dec 18, 2012 at 5:24 PM, Peter Eisentraut <peter_e(at)gmx(dot)net> wrote:
> On 12/18/12 5:10 PM, Robert Haas wrote:
>> I can't help but suspect that the way we handle keywords today is
>> monumentally inefficient. The unreserved_keyword products, et al,
>> just seem somehow badly wrong-headed. We take the trouble to
>> distinguish all of those cases so that we an turn around and not
>> distinguish them. I feel like there ought to be some way to use lexer
>> states to handle this - if we're in a context where an unreserved
>> keyword will be treated as an IDENT, then have the lexer return IDENT
>> when it sees an unreserved keyword.
>
> The problem would be the lookahead. You need to know the next token
> before you can decide what context the current one is in.

Yeah, that's why I don't know how to make it work. It feels like this
is partly artifact of the tool, though. I mean, suppose we haven't
read anything yet. Then, the next token can't be an IDENT, so if we
see an unreserved keyword, we know we're not going to convert it to an
IDENT. OTOH, if we've seen CREATE TABLE, the next token cannot be an
unreserved keyword that is intended as a keyword; it has to be
something that will reduce to ColId.

I guess the problem situation is where we can shift the keyword and
then use the following token to decide whether to reduce it to
ColId/type_function_name/ColLabel or use some other rule instead; the
CREATE INDEX CONCURRENTLY productions might be such a case.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Dec 18, 2012 at 10:33:12AM +0100, Dimitri Fontaine wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> > And on the other hand, if you could get a clean split between the two
> > grammars, then regardless of exactly what the split was, it might seem
> > a win. But it seemed to me when I looked at this that you'd have to
> > duplicate a lot of stuff and the small parser still wouldn't end up
> > being very small, which I found hard to get excited about.
>
> I think the goal is not so much about getting a much smaller parser, but
> more about have a separate parser that you don't care about the "bloat"
> of, so that you can improve DDL without fearing about main parser
> performance regressions.

In addition to this, there could well be uses for a more modular
parser. For example, if it turns out to be possible to do our parser
in a way that is exportable and (can be converted to a type that)
looks forward, client code could do a lot of interesting (and provably
correct) things.

> If we come out with no regression and no gain on the main query parser,
> I say it still worth the separation effort. And anyway we only add
> things to the main parser (queries) when the standard saith we have to.
>
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
> > I'm not sure what other tool might be better though. I looked through
> > http://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages
> > but it seems our options are a bit limited if we want something
> > that produces C. It's not clear to me that any of the likely options
> > are as mature as bison, let alone likely to substantially outperform it.
> > (For instance, Hyacc sounded pretty promising until I got to the part
> > about it doesn't yet support %union or %type.) Still, I didn't spend
> > much time on this --- maybe somebody else would like to do a bit more
> > research.
>
> I did spend a very little time on it too, with a different search angle,
> and did find that "experimental" thing that might be worth looking at,
> or maybe not.
>
> http://en.wikipedia.org/wiki/Parsing_expression_grammar
> http://piumarta.com/software/peg/

More angles:

http://wwwiti.cs.uni-magdeburg.de/~rosenmue/publications/SKS+08.pdf

Might anyone here wish to investigate this, given some kind of
resources for the initial study?

Cheers,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david(dot)fetter(at)gmail(dot)com
iCal: webcal://www.tripit.com/feed/ical/people/david74/tripit.ics

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

On Tue, Dec 18, 2012 at 10:44 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> Yeah, that's why I don't know how to make it work. It feels like this
> is partly artifact of the tool, though. I mean, suppose we haven't
> read anything yet. Then, the next token can't be an IDENT, so if we
> see an unreserved keyword, we know we're not going to convert it to an
> IDENT. OTOH, if we've seen CREATE TABLE, the next token cannot be an
> unreserved keyword that is intended as a keyword; it has to be
> something that will reduce to ColId.
>
> I guess the problem situation is where we can shift the keyword and
> then use the following token to decide whether to reduce it to
> ColId/type_function_name/ColLabel or use some other rule instead; the
> CREATE INDEX CONCURRENTLY productions might be such a case.

It seems to me the avenue for simplifying the transition table would
be keywords that can never be used in the same place. That is, if we
replaced all the elements of such a set with a single token then the
grammar would be unambigous and we could insert a check that the right
actual token was present in each place it's used. I'm thinking of the
various "noise words" that the SQL standard introduces which are all
going to be reduced to IDENT except for a few places each of which
will only admit one such noise word anyways.

I think doing this manually would be unmaintainable since every time
we modified the grammar it would introduce random unpredictable
conflicts which would be hard to debug. But I wonder if we could
preparse the transitions table, find any such large sets and rewrite
either the transition table or regenerate the grammar and rerun bison
on it.

Alternately we could just replace the transition table with a
representation that is less wasteful such as a list of perfect hash
tables just large enough to hold the valid transition. Or even a
single very large perfect hash table where the key is <state,token>.

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.
Most of these bytes are being wasted on transitions which can never
occur or which can never occur in syntactically valid SQL. The
transitions which can occur will still be present in any condensed
representation we come up with. The L2 cache might still be large
enough to hold these hot transitions which might not be a very large
subset at all.

valgrind comes with a tool called cachegrind which can emulate the
cache algorithm on some variants of various cpus and produce reports.
Can it be made to produce a report for a specific block of memory?

--
greg

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.

> valgrind comes with a tool called cachegrind which can emulate the
> cache algorithm on some variants of various cpus and produce reports.
> Can it be made to produce a report for a specific block of memory?

I believe that oprofile can be persuaded to produce statistics about
where in one's code are the most cache misses, not just the most
wall-clock ticks; which would shed a lot of light on this question.
However, my oprofile-fu doesn't quite extend to actually persuading it.

regards, tom lane

On Wed, Dec 19, 2012 at 10:18 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> valgrind comes with a tool called cachegrind which can emulate the
>> cache algorithm on some variants of various cpus and produce reports.
>> Can it be made to produce a report for a specific block of memory?
>
> I believe that oprofile can be persuaded to produce statistics about
> where in one's code are the most cache misses, not just the most
> wall-clock ticks; which would shed a lot of light on this question.
> However, my oprofile-fu doesn't quite extend to actually persuading it.

perf can certainly do this.

$ perf record -a -e cache-misses pgbench -n -S -T 30
...output elided...
$ perf report -d postgres | grep -v '^#' | head
8.88% postgres base_yyparse
7.05% swapper 0x807c
4.67% postgres SearchCatCache
3.77% pgbench 0x172dd58
3.47% postgres hash_search_with_hash_value
3.23% postgres AllocSetAlloc
2.58% postgres core_yylex
1.87% postgres LWLockAcquire
1.83% postgres fmgr_info_cxt_security
1.75% postgres 0x4d1054

For comparison:

$ perf record -a -e cycles -d postgres pgbench -n -S -T 30
$ perf report -d postgres | grep -v '^#' | head
6.54% postgres AllocSetAlloc
4.08% swapper 0x4ce754
3.60% postgres hash_search_with_hash_value
2.74% postgres base_yyparse
2.71% postgres MemoryContextAllocZeroAligned
2.57% postgres MemoryContextAlloc
2.36% postgres SearchCatCache
2.10% postgres _bt_compare
1.70% postgres LWLockAcquire
1.54% postgres FunctionCall2Coll

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 12/18/12 5:10 PM, Robert Haas wrote:
> I can't help but suspect that the way we handle keywords today is
> monumentally inefficient. The unreserved_keyword products, et al,
> just seem somehow badly wrong-headed. We take the trouble to
> distinguish all of those cases so that we an turn around and not
> distinguish them. I feel like there ought to be some way to use lexer
> states to handle this - if we're in a context where an unreserved
> keyword will be treated as an IDENT, then have the lexer return IDENT
> when it sees an unreserved keyword. I might be wrong, but it seems
> like that would eliminate a whole lot of parser state transitions.
> However, even if I'm right, I have no idea how to implement it. It
> just seems very wasteful that we have so many parser states that have
> no purpose other than (effectively) to convert an unreserved_keyword
> into an IDENT when the lexer could do the same thing much more cheaply
> given a bit more context.

Another way of attack along these lines might be to use the %glr-parser
and then try to cut back on all those redundant rules that were put in
to avoid conflicts. The number of key words categories and such could
perhaps also be reduced that way.

Of course, this is mostly speculation.

On 18 December 2012 22:10, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> Well that would be nice, but the problem is that I see no way to
> implement it. If, with a unified parser, the parser is 14% of our
> source code, then splitting it in two will probably crank that number
> up well over 20%, because there will be duplication between the two.
> That seems double-plus un-good.

I don't think the size of the parser binary is that relevant. What is
relevant is how much of that is regularly accessed.

Increasing parser cache misses for DDL and increasing size of binary
overall are acceptable costs if we are able to swap out the unneeded
areas and significantly reduce the cache misses on the well travelled
portions of the parser.

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

On Thu, Dec 20, 2012 at 8:55 AM, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
> On 18 December 2012 22:10, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> Well that would be nice, but the problem is that I see no way to
>> implement it. If, with a unified parser, the parser is 14% of our
>> source code, then splitting it in two will probably crank that number
>> up well over 20%, because there will be duplication between the two.
>> That seems double-plus un-good.
>
> I don't think the size of the parser binary is that relevant. What is
> relevant is how much of that is regularly accessed.
>
> Increasing parser cache misses for DDL and increasing size of binary
> overall are acceptable costs if we are able to swap out the unneeded
> areas and significantly reduce the cache misses on the well travelled
> portions of the parser.

I generally agree. We don't want to bloat the size of the parser with
wild abandon, but yeah if we can reduce the cache misses on the
well-travelled portions that seems like it ought to help. My previous
hacky attempt to quantify the potential benefit in this area was:

http://archives.postgresql.org/pgsql-hackers/2011-05/msg01008.php

On my machine there seemed to be a small but consistent win; on a very
old box Jeff Janes tried, it didn't seem like there was any benefit at
all. Somehow, I have a feeling we're missing a trick here.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 2012-12-20 09:11:46 -0500, Robert Haas wrote:
> On Thu, Dec 20, 2012 at 8:55 AM, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
> > On 18 December 2012 22:10, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> >> Well that would be nice, but the problem is that I see no way to
> >> implement it. If, with a unified parser, the parser is 14% of our
> >> source code, then splitting it in two will probably crank that number
> >> up well over 20%, because there will be duplication between the two.
> >> That seems double-plus un-good.
> >
> > I don't think the size of the parser binary is that relevant. What is
> > relevant is how much of that is regularly accessed.
> >
> > Increasing parser cache misses for DDL and increasing size of binary
> > overall are acceptable costs if we are able to swap out the unneeded
> > areas and significantly reduce the cache misses on the well travelled
> > portions of the parser.
>
> I generally agree. We don't want to bloat the size of the parser with
> wild abandon, but yeah if we can reduce the cache misses on the
> well-travelled portions that seems like it ought to help. My previous
> hacky attempt to quantify the potential benefit in this area was:
>
> http://archives.postgresql.org/pgsql-hackers/2011-05/msg01008.php
>
> On my machine there seemed to be a small but consistent win; on a very
> old box Jeff Janes tried, it didn't seem like there was any benefit at
> all. Somehow, I have a feeling we're missing a trick here.

I don't think you will see too many cache misses on such a low number of
extremly simply statements, so its not too surprising not to see a that
big difference with that.

Are we sure its really cache-misses and not just the actions performed
in the grammar that make bison code show up in profiles? I remember the
latter being the case...

Greetings,

Andres Freund

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

On 2012-12-20 15:45:47 +0100, Andres Freund wrote:
> On 2012-12-20 09:11:46 -0500, Robert Haas wrote:
> > On Thu, Dec 20, 2012 at 8:55 AM, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
> > > On 18 December 2012 22:10, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> > >> Well that would be nice, but the problem is that I see no way to
> > >> implement it. If, with a unified parser, the parser is 14% of our
> > >> source code, then splitting it in two will probably crank that number
> > >> up well over 20%, because there will be duplication between the two.
> > >> That seems double-plus un-good.
> > >
> > > I don't think the size of the parser binary is that relevant. What is
> > > relevant is how much of that is regularly accessed.
> > >
> > > Increasing parser cache misses for DDL and increasing size of binary
> > > overall are acceptable costs if we are able to swap out the unneeded
> > > areas and significantly reduce the cache misses on the well travelled
> > > portions of the parser.
> >
> > I generally agree. We don't want to bloat the size of the parser with
> > wild abandon, but yeah if we can reduce the cache misses on the
> > well-travelled portions that seems like it ought to help. My previous
> > hacky attempt to quantify the potential benefit in this area was:
> >
> > http://archives.postgresql.org/pgsql-hackers/2011-05/msg01008.php
> >
> > On my machine there seemed to be a small but consistent win; on a very
> > old box Jeff Janes tried, it didn't seem like there was any benefit at
> > all. Somehow, I have a feeling we're missing a trick here.
>
> I don't think you will see too many cache misses on such a low number of
> extremly simply statements, so its not too surprising not to see a that
> big difference with that.
>
> Are we sure its really cache-misses and not just the actions performed
> in the grammar that make bison code show up in profiles? I remember the
> latter being the case...

Hm. A very, very quick perf stat -dvvv of pgbench -S -c 20 -j 20 -T 20 later:

218350.885559 task-clock # 10.095 CPUs utilized
1,676,479 context-switches # 0.008 M/sec
2,396 cpu-migrations # 0.011 K/sec
796,038 page-faults # 0.004 M/sec
506,312,525,518 cycles # 2.319 GHz [20.00%]
405,944,435,754 stalled-cycles-frontend # 80.18% frontend cycles idle [30.32%]
236,712,872,641 stalled-cycles-backend # 46.75% backend cycles idle [40.51%]
193,459,120,458 instructions # 0.38 insns per cycle
# 2.10 stalled cycles per insn [50.70%]
36,433,144,472 branches # 166.856 M/sec [51.12%]
3,623,778,087 branch-misses # 9.95% of all branches [50.87%]
50,344,123,581 L1-dcache-loads # 230.565 M/sec [50.33%]
5,548,192,686 L1-dcache-load-misses # 11.02% of all L1-dcache hits [49.69%]
2,666,461,361 LLC-loads # 12.212 M/sec [35.63%]
112,407,198 LLC-load-misses # 4.22% of all LL-cache hits [ 9.67%]

21.629396701 seconds time elapsed

So there definitely a noticeable rate of cache misses...

Greetings,

Andres Freund

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

On 2012-12-20 15:51:37 +0100, Andres Freund wrote:
> On 2012-12-20 15:45:47 +0100, Andres Freund wrote:
> > On 2012-12-20 09:11:46 -0500, Robert Haas wrote:
> > > On Thu, Dec 20, 2012 at 8:55 AM, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
> > > > On 18 December 2012 22:10, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> > > >> Well that would be nice, but the problem is that I see no way to
> > > >> implement it. If, with a unified parser, the parser is 14% of our
> > > >> source code, then splitting it in two will probably crank that number
> > > >> up well over 20%, because there will be duplication between the two.
> > > >> That seems double-plus un-good.
> > > >
> > > > I don't think the size of the parser binary is that relevant. What is
> > > > relevant is how much of that is regularly accessed.
> > > >
> > > > Increasing parser cache misses for DDL and increasing size of binary
> > > > overall are acceptable costs if we are able to swap out the unneeded
> > > > areas and significantly reduce the cache misses on the well travelled
> > > > portions of the parser.
> > >
> > > I generally agree. We don't want to bloat the size of the parser with
> > > wild abandon, but yeah if we can reduce the cache misses on the
> > > well-travelled portions that seems like it ought to help. My previous
> > > hacky attempt to quantify the potential benefit in this area was:
> > >
> > > http://archives.postgresql.org/pgsql-hackers/2011-05/msg01008.php
> > >
> > > On my machine there seemed to be a small but consistent win; on a very
> > > old box Jeff Janes tried, it didn't seem like there was any benefit at
> > > all. Somehow, I have a feeling we're missing a trick here.
> >
> > I don't think you will see too many cache misses on such a low number of
> > extremly simply statements, so its not too surprising not to see a that
> > big difference with that.
> >
> > Are we sure its really cache-misses and not just the actions performed
> > in the grammar that make bison code show up in profiles? I remember the
> > latter being the case...
>
> Hm. A very, very quick perf stat -dvvv of pgbench -S -c 20 -j 20 -T 20 later:
>
> 218350.885559 task-clock # 10.095 CPUs utilized
> 1,676,479 context-switches # 0.008 M/sec
> 2,396 cpu-migrations # 0.011 K/sec
> 796,038 page-faults # 0.004 M/sec
> 506,312,525,518 cycles # 2.319 GHz [20.00%]
> 405,944,435,754 stalled-cycles-frontend # 80.18% frontend cycles idle [30.32%]
> 236,712,872,641 stalled-cycles-backend # 46.75% backend cycles idle [40.51%]
> 193,459,120,458 instructions # 0.38 insns per cycle
> # 2.10 stalled cycles per insn [50.70%]
> 36,433,144,472 branches # 166.856 M/sec [51.12%]
> 3,623,778,087 branch-misses # 9.95% of all branches [50.87%]
> 50,344,123,581 L1-dcache-loads # 230.565 M/sec [50.33%]
> 5,548,192,686 L1-dcache-load-misses # 11.02% of all L1-dcache hits [49.69%]
> 2,666,461,361 LLC-loads # 12.212 M/sec [35.63%]
> 112,407,198 LLC-load-misses # 4.22% of all LL-cache hits [ 9.67%]
>
> 21.629396701 seconds time elapsed
>
> So there definitely a noticeable rate of cache misses...

L1 misses:
# Samples: 997K of event 'L1-dcache-load-misses'
# Overhead Command Shared Object Symbol
# ........ ........ ...............................................................
6.49% postgres postgres [.] SearchCatCache
3.65% postgres postgres [.] base_yyparse
3.48% postgres postgres [.] hash_search_with_hash_value
3.41% postgres postgres [.] AllocSetAlloc
1.84% postgres postgres [.] LWLockAcquire
1.40% postgres postgres [.] fmgr_info_cxt_security
1.36% postgres postgres [.] nocachegetattr
1.23% postgres libc-2.13.so [.] _int_malloc
1.20% postgres postgres [.] core_yylex
1.15% postgres postgres [.] MemoryContextAllocZeroAligned
0.94% postgres postgres [.] PostgresMain
0.94% postgres postgres [.] MemoryContextAlloc
0.91% postgres libc-2.13.so [.] __memcpy_ssse3_back
0.89% postgres postgres [.] CatalogCacheComputeHashValue
0.86% postgres postgres [.] PinBuffer
0.86% postgres [kernel.kallsyms] [k] __audit_syscall_entry
0.80% postgres libc-2.13.so [.] __strcmp_sse42
0.80% postgres postgres [.] _bt_compare
0.78% postgres postgres [.] FunctionCall2Coll
0.77% postgres libc-2.13.so [.] malloc
0.73% postgres libc-2.13.so [.] __memset_sse2
0.72% postgres postgres [.] GetSnapshotData
0.69% postgres [kernel.kallsyms] [k] fget_light
0.69% postgres postgres [.] DirectFunctionCall1Coll
0.67% postgres postgres [.] hash_search
0.67% postgres libc-2.13.so [.] 0x000000000011a3a5
0.66% postgres postgres [.] pgstat_initstats
0.66% postgres postgres [.] AllocSetFree
0.65% postgres libc-2.13.so [.] __strlen_sse42
0.60% postgres libc-2.13.so [.] _int_free
0.60% postgres [kernel.kallsyms] [k] cpuacct_charge
0.59% postgres postgres [.] heap_getsysattr
0.59% postgres postgres [.] MemoryContextAllocZero
0.58% postgres postgres [.] PopActiveSnapshot
0.53% postgres libc-2.13.so [.] __memcmp_sse4_1
0.51% postgres postgres [.] ReadBuffer_common
0.49% postgres postgres [.] ScanKeywordLookup
0.49% postgres postgres [.] LockAcquireExtended
0.47% postgres [kernel.kallsyms] [k] update_cfs_shares
0.45% postgres postgres [.] SearchCatCacheList
0.45% postgres postgres [.] new_list
0.44% postgres postgres [.] get_relation_info

LLC misses:
# Samples: 1M of event 'LLC-load-misses'
# Event count (approx.): 143379713
# Overhead Command Shared Object Symbol
# ........ ........ ...............................................................
25.08% postgres postgres [.] _bt_compare
12.84% postgres postgres [.] PinBuffer
9.18% postgres postgres [.] LWLockAcquire
6.31% postgres postgres [.] GetSnapshotData
6.08% postgres postgres [.] heap_hot_search_buffer
5.13% postgres postgres [.] hash_search_with_hash_value
4.85% postgres postgres [.] _bt_checkpage
3.95% postgres postgres [.] _bt_moveright
3.09% postgres postgres [.] heap_page_prune_opt
2.12% postgres postgres [.] slot_deform_tuple
1.98% postgres postgres [.] LWLockRelease
1.82% postgres libc-2.13.so [.] __memcmp_sse4_1
1.16% postgres postgres [.] ExecProject
1.16% postgres postgres [.] FunctionCall2Coll
0.94% postgres [kernel.kallsyms] [k] copy_user_generic_string
0.94% postgres [kernel.kallsyms] [k] tg_load_down
0.78% postgres [kernel.kallsyms] [k] find_get_page
0.73% postgres postgres [.] ProcArrayEndTransaction
0.73% postgres postgres [.] pfree
0.71% postgres postgres [.] pgstat_report_xact_timestamp
0.69% postgres postgres [.] index_fetch_heap
0.66% postgres postgres [.] LockAcquireExtended
0.56% postgres postgres [.] LockBuffer
0.45% postgres postgres [.] slot_getsomeattrs
0.40% postgres postgres [.] _bt_readpage

So it seems L1 misses are the interesting thing wrt to parsing.

When doing a source/assembly annotation in SearchCatCache about half of
the misses are attributed to the memcpy() directly at the beginning.
In base_yyparse the three biggest offenders (15%, 10.5%, 5.58%) really
seem to be various kinds of table lookups.

So it seems to confirm the various suspicious that the table size might
be rather relevant.

Greetings,

Andres Freund

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

On 2012-12-20 16:04:49 +0100, Andres Freund wrote:
> On 2012-12-20 15:51:37 +0100, Andres Freund wrote:
> When doing a source/assembly annotation in SearchCatCache about half of
> the misses are attributed to the memcpy() directly at the beginning.

Using a separate array for storing the arguments instead of copying &
modifying cache->cc_skey yields a 2% speedup in pgbench -S for me...

The attached patch is clearly not ready and I don't really have time &
energy to pursue it right now, but it seems interesting enough to
post. The approach seems solid and sensible although the implementation
is not (too much c&p, no comments).

Greetings,

Andres Freund

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

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.

--
greg

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

>
> Another way of attack along these lines might be to use the %glr-parser
> and then try to cut back on all those redundant rules that were put in
> to avoid conflicts. The number of key words categories and such could
> perhaps also be reduced that way.
>
> Of course, this is mostly speculation.
>
>

The GLR output from Bison is licensed under the GPL (unlike the LALR output).
So using Bison's GLR mode isn't an option.

On 2012-12-20 23:12:55 +0000, McDevitt, Charles wrote:
> >
> > Another way of attack along these lines might be to use the %glr-parser
> > and then try to cut back on all those redundant rules that were put in
> > to avoid conflicts. The number of key words categories and such could
> > perhaps also be reduced that way.
> >
> > Of course, this is mostly speculation.
> >
> >
>
> The GLR output from Bison is licensed under the GPL (unlike the LALR output).
> So using Bison's GLR mode isn't an option.

Thats not the case anymore:
http://www.gnu.org/software/bison/manual/html_node/Conditions.html

Greetings,

Andres Freund

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

> >
> > The GLR output from Bison is licensed under the GPL (unlike the LALR output).
> > So using Bison's GLR mode isn't an option.
>
> Thats not the case anymore:
> http://www.gnu.org/software/bison/manual/html_node/Conditions.html

Sorry! My mistake... I didn't realize they changed the rules.
I'll be more careful to check these things in the future.

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> On 2012-12-20 23:12:55 +0000, McDevitt, Charles wrote:
>>> Another way of attack along these lines might be to use the %glr-parser
>>> and then try to cut back on all those redundant rules that were put in
>>> to avoid conflicts. The number of key words categories and such could
>>> perhaps also be reduced that way.

>> The GLR output from Bison is licensed under the GPL (unlike the LALR output).
>> So using Bison's GLR mode isn't an option.

> Thats not the case anymore:
> http://www.gnu.org/software/bison/manual/html_node/Conditions.html

This does mean that we'd have to specify a minimum bison version of 2.2
in order to be squeaky-clean license wise, if we went over to using the
GLR mode. However, that would likely be a good idea anyway from a
technical standpoint --- the GLR mode may exist in ancient bison
versions, but who knows how bug-free it is.

Anyway, this is all merest speculation until somebody actually tries it
and sees if a performance gain is possible. Having just re-read
the description of GLR mode, I wouldn't be surprised if any savings in
table size is squandered by its handling of ambiguous cases (ie, the
need to track and merge multiple parser states).

regards, tom lane