Bison state table

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Bison state table

Bruce Momjian
With our scanner keywords list now more cache-aware, and with us
planning to use Bison for years to come, has anyone ever looked at
reordering the bison state machine array to be more cache aware, e.g.,
having common states next to each other rather than scattered around the
array?

--
  Bruce Momjian  <[hidden email]>        http://momjian.us
  EnterpriseDB                             http://enterprisedb.com

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +

Reply | Threaded
Open this post in threaded view
|

Re: Bison state table

David Fetter
On Fri, Jan 25, 2019 at 05:38:59PM -0500, Bruce Momjian wrote:
> With our scanner keywords list now more cache-aware, and with us
> planning to use Bison for years to come, has anyone ever looked at
> reordering the bison state machine array to be more cache aware, e.g.,
> having common states next to each other rather than scattered around the
> array?

Do we have a pretty good idea of what commonly grouped states are, or
at least a way to get some not-awful estimates of what they are?

Best,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778

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

Reply | Threaded
Open this post in threaded view
|

Re: Bison state table

Bruce Momjian
On Sat, Jan 26, 2019 at 12:49:50AM +0100, David Fetter wrote:
> On Fri, Jan 25, 2019 at 05:38:59PM -0500, Bruce Momjian wrote:
> > With our scanner keywords list now more cache-aware, and with us
> > planning to use Bison for years to come, has anyone ever looked at
> > reordering the bison state machine array to be more cache aware, e.g.,
> > having common states next to each other rather than scattered around the
> > array?
>
> Do we have a pretty good idea of what commonly grouped states are, or
> at least a way to get some not-awful estimates of what they are?

Uh, I am afraid we would need to profile the grammer with some sample
queries and then base the reordering on that, kind of how compilers use
sampling to do branch prediction.  Yeah, crazy idea, I know.  I figured
some smart person might have written a tool to do that.

--
  Bruce Momjian  <[hidden email]>        http://momjian.us
  EnterpriseDB                             http://enterprisedb.com

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +

Reply | Threaded
Open this post in threaded view
|

Re: Bison state table

David Fetter
On Fri, Jan 25, 2019 at 06:55:56PM -0500, Bruce Momjian wrote:

> On Sat, Jan 26, 2019 at 12:49:50AM +0100, David Fetter wrote:
> > On Fri, Jan 25, 2019 at 05:38:59PM -0500, Bruce Momjian wrote:
> > > With our scanner keywords list now more cache-aware, and with us
> > > planning to use Bison for years to come, has anyone ever looked at
> > > reordering the bison state machine array to be more cache aware, e.g.,
> > > having common states next to each other rather than scattered around the
> > > array?
> >
> > Do we have a pretty good idea of what commonly grouped states are, or
> > at least a way to get some not-awful estimates of what they are?
>
> Uh, I am afraid we would need to profile the grammer with some sample
> queries and then base the reordering on that, kind of how compilers use
> sampling to do branch prediction.  Yeah, crazy idea, I know.  I figured
> some smart person might have written a tool to do that.

Since you're framing it that way, maybe there's something clever to do
with the llvm toolchain, which just happens to have facilities like
that. Perhaps smart people have already done this...

Best,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778

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

Reply | Threaded
Open this post in threaded view
|

Re: Bison state table

John Naylor-2
In reply to this post by Bruce Momjian
On Sat, Jan 26, 2019 at 5:39 AM Bruce Momjian <[hidden email]> wrote:
>
> With our scanner keywords list now more cache-aware, and with us
> planning to use Bison for years to come, has anyone ever looked at
> reordering the bison state machine array to be more cache aware, e.g.,
> having common states next to each other rather than scattered around the
> array?

I recently spent some time investigating how the various arrays are
generated and accessed, and found this informative article:

https://www.cs.uic.edu/~spopuri/cparser.html

It's dated from 2006, but still seems to be correct on the whole,
judging by the gram.c output file. Anyway, the short answer is,
grouping common states would require changing Bison's algorithm for
compressing a sparse 2-D array into multiple less-sparse 1-D arrays,
if it's even possible to control the effect you have in mind.

That said, I had an idea. When Bison consults yytable, it has to also
consult yycheck with the same index to make sure the result is valid.
If the two arrays of int16 were merged into a single array of structs,
the state and the check would be on the same cache line. I tried this
by directly patching the gram.c output file (see attached for the
basic idea) and #include'-ing a separate file with the merged array.
It didn't improve raw parsing microbenchmarks using information schema
or short pgbench-like queries. So I'm guessing either a). the
microbenchmark already has better cache behavior than real queries so
won't show much difference here, and/or b). the bottleneck is
elsewhere than accessing yytable and yycheck.

In any case, I hope to follow Bison development and test any
performance improvements the maintainers come up with, as that was
reported to be on the roadmap:

https://www.postgresql.org/message-id/74DD0F55-F3CF-447E-ACF2-88C01E42AAC3@...

--
John Naylor                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

gram-combine.patch (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Bison state table

Bruce Momjian
On Tue, Aug 13, 2019 at 05:09:30PM +0700, John Naylor wrote:

> On Sat, Jan 26, 2019 at 5:39 AM Bruce Momjian <[hidden email]> wrote:
> >
> > With our scanner keywords list now more cache-aware, and with us
> > planning to use Bison for years to come, has anyone ever looked at
> > reordering the bison state machine array to be more cache aware, e.g.,
> > having common states next to each other rather than scattered around the
> > array?
>
> I recently spent some time investigating how the various arrays are
> generated and accessed, and found this informative article:
>
> https://www.cs.uic.edu/~spopuri/cparser.html
>
> It's dated from 2006, but still seems to be correct on the whole,
> judging by the gram.c output file. Anyway, the short answer is,
> grouping common states would require changing Bison's algorithm for
> compressing a sparse 2-D array into multiple less-sparse 1-D arrays,
> if it's even possible to control the effect you have in mind.
>
> That said, I had an idea. When Bison consults yytable, it has to also
> consult yycheck with the same index to make sure the result is valid.
> If the two arrays of int16 were merged into a single array of structs,
> the state and the check would be on the same cache line. I tried this
> by directly patching the gram.c output file (see attached for the
> basic idea) and #include'-ing a separate file with the merged array.
> It didn't improve raw parsing microbenchmarks using information schema
> or short pgbench-like queries. So I'm guessing either a). the
> microbenchmark already has better cache behavior than real queries so
> won't show much difference here, and/or b). the bottleneck is
> elsewhere than accessing yytable and yycheck.
>
> In any case, I hope to follow Bison development and test any
> performance improvements the maintainers come up with, as that was
> reported to be on the roadmap:

Very interesting.  Thanks for researching this.

--
  Bruce Momjian  <[hidden email]>        http://momjian.us
  EnterpriseDB                             http://enterprisedb.com

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +