Обсуждение: Bison state table
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 <bruce@momjian.us> 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 +
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
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 <bruce@momjian.us> 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 +
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
On Sat, Jan 26, 2019 at 5:39 AM Bruce Momjian <bruce@momjian.us> 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@lrde.epita.fr -- John Naylor https://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Вложения
On Tue, Aug 13, 2019 at 05:09:30PM +0700, John Naylor wrote: > On Sat, Jan 26, 2019 at 5:39 AM Bruce Momjian <bruce@momjian.us> 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 <bruce@momjian.us> 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 +