Replace the data structure used for keyword lookup.

Previously, ScanKeywordLookup was passed an array of string pointers.
This had some performance deficiencies: the strings themselves might
be scattered all over the place depending on the compiler (and some
quick checking shows that at least with gcc-on-Linux, they indeed
weren't reliably close together).  That led to very cache-unfriendly
behavior as the binary search touched strings in many different pages.
Also, depending on the platform, the string pointers might need to
be adjusted at program start, so that they couldn't be simple constant
data.  And the ScanKeyword struct had been designed with an eye to
32-bit machines originally; on 64-bit it requires 16 bytes per
keyword, making it even more cache-unfriendly.

Redesign so that the keyword strings themselves are allocated
consecutively (as part of one big char-string constant), thereby
eliminating the touch-lots-of-unrelated-pages syndrome.  And get
rid of the ScanKeyword array in favor of three separate arrays:
uint16 offsets into the keyword array, uint16 token codes, and
uint8 keyword categories.  That reduces the overhead per keyword
to 5 bytes instead of 16 (even less in programs that only need
one of the token codes and categories); moreover, the binary search
only touches the offsets array, further reducing its cache footprint.
This also lets us put the token codes somewhere else than the
keyword strings are, which avoids some unpleasant build dependencies.

While we're at it, wrap the data used by ScanKeywordLookup into
a struct that can be treated as an opaque type by most callers.
That doesn't change things much right now, but it will make it
less painful to switch to a hash-based lookup method, as is being
discussed in the mailing list thread.

Most of the change here is associated with adding a generator
script that can build the new data structure from the same
list-of-PG_KEYWORD header representation we used before.
The PG_KEYWORD lists that plpgsql and ecpg used to embed in
their scanner .c files have to be moved into headers, and the
Makefiles have to be taught to invoke the generator script.
This work is also necessary if we're to consider hash-based lookup,
since the generator script is what would be responsible for
constructing a hash table.

Aside from saving a few kilobytes in each program that includes
the keyword table, this seems to speed up raw parsing (flex+bison)
by a few percent.  So it's worth doing even as it stands, though
we think we can gain even more with a follow-on patch to switch
to hash-based lookup.

John Naylor, with further hacking by me

Discussion: https://postgr.es/m/CAJVSVGXdFVU2sgym89XPL=Lv1zOS5=EHHQ8XWNzFL=mTXkKMLw@mail.gmail.com

4 files changed, 198 insertions, 1 deletions

diff --git a/src/tools/gen_keywordlist.pl b/src/tools/gen_keywordlist.pl
new file mode 100644
index 00000000000..d764affaa66
--- /dev/null
+++ b/src/tools/gen_keywordlist.pl
@@ -0,0 +1,156 @@
+#----------------------------------------------------------------------
+#
+# gen_keywordlist.pl
+#	Perl script that transforms a list of keywords into a ScanKeywordList
+#	data structure that can be passed to ScanKeywordLookup().
+#
+# The input is a C header file containing a series of macro calls
+#	PG_KEYWORD("keyword", ...)
+# Lines not starting with PG_KEYWORD are ignored.  The keywords are
+# implicitly numbered 0..N-1 in order of appearance in the header file.
+# Currently, the keywords are required to appear in ASCII order.
+#
+# The output is a C header file that defines a "const ScanKeywordList"
+# variable named according to the -v switch ("ScanKeywords" by default).
+# The variable is marked "static" unless the -e switch is given.
+#
+#
+# Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
+# Portions Copyright (c) 1994, Regents of the University of California
+#
+# src/tools/gen_keywordlist.pl
+#
+#----------------------------------------------------------------------
+
+use strict;
+use warnings;
+use Getopt::Long;
+
+my $output_path = '';
+my $extern = 0;
+my $varname = 'ScanKeywords';
+
+GetOptions(
+	'output:s' => \$output_path,
+	'extern'   => \$extern,
+	'varname:s' => \$varname) || usage();
+
+my $kw_input_file = shift @ARGV || die "No input file.\n";
+
+# Make sure output_path ends in a slash if needed.
+if ($output_path ne '' && substr($output_path, -1) ne '/')
+{
+	$output_path .= '/';
+}
+
+$kw_input_file =~ /(\w+)\.h$/ || die "Input file must be named something.h.\n";
+my $base_filename = $1 . '_d';
+my $kw_def_file = $output_path . $base_filename . '.h';
+
+open(my $kif, '<', $kw_input_file) || die "$kw_input_file: $!\n";
+open(my $kwdef, '>', $kw_def_file) || die "$kw_def_file: $!\n";
+
+# Opening boilerplate for keyword definition header.
+printf $kwdef <<EOM, $base_filename, uc $base_filename, uc $base_filename;
+/*-------------------------------------------------------------------------
+ *
+ * %s.h
+ *    List of keywords represented as a ScanKeywordList.
+ *
+ * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * NOTES
+ *  ******************************
+ *  *** DO NOT EDIT THIS FILE! ***
+ *  ******************************
+ *
+ *  It has been GENERATED by src/tools/gen_keywordlist.pl
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#ifndef %s_H
+#define %s_H
+
+#include "common/kwlookup.h"
+
+EOM
+
+# Parse input file for keyword names.
+my @keywords;
+while (<$kif>)
+{
+	if (/^PG_KEYWORD\("(\w+)"/)
+	{
+		push @keywords, $1;
+	}
+}
+
+# Error out if the keyword names are not in ASCII order.
+for my $i (0..$#keywords - 1)
+{
+	die qq|The keyword "$keywords[$i + 1]" is out of order in $kw_input_file\n|
+	  if ($keywords[$i] cmp $keywords[$i + 1]) >= 0;
+}
+
+# Emit the string containing all the keywords.
+
+printf $kwdef qq|static const char %s_kw_string[] =\n\t"|, $varname;
+print $kwdef join qq|\\0"\n\t"|, @keywords;
+print $kwdef qq|";\n\n|;
+
+# Emit an array of numerical offsets which will be used to index into the
+# keyword string.  Also determine max keyword length.
+
+printf $kwdef "static const uint16 %s_kw_offsets[] = {\n", $varname;
+
+my $offset = 0;
+my $max_len = 0;
+foreach my $name (@keywords)
+{
+	my $this_length = length($name);
+
+	print $kwdef "\t$offset,\n";
+
+	# Calculate the cumulative offset of the next keyword,
+	# taking into account the null terminator.
+	$offset += $this_length + 1;
+
+	# Update max keyword length.
+	$max_len = $this_length if $max_len < $this_length;
+}
+
+print $kwdef "};\n\n";
+
+# Emit a macro defining the number of keywords.
+# (In some places it's useful to have access to that as a constant.)
+
+printf $kwdef "#define %s_NUM_KEYWORDS %d\n\n", uc $varname, scalar @keywords;
+
+# Emit the struct that wraps all this lookup info into one variable.
+
+print $kwdef "static " if !$extern;
+printf $kwdef "const ScanKeywordList %s = {\n", $varname;
+printf $kwdef qq|\t%s_kw_string,\n|, $varname;
+printf $kwdef qq|\t%s_kw_offsets,\n|, $varname;
+printf $kwdef qq|\t%s_NUM_KEYWORDS,\n|, uc $varname;
+printf $kwdef qq|\t%d\n|, $max_len;
+print $kwdef "};\n\n";
+
+printf $kwdef "#endif\t\t\t\t\t\t\t/* %s_H */\n", uc $base_filename;
+
+
+sub usage
+{
+	die <<EOM;
+Usage: gen_keywordlist.pl [--output/-o <path>] [--varname/-v <varname>] [--extern/-e] input_file
+    --output   Output directory (default '.')
+    --varname  Name for ScanKeywordList variable (default 'ScanKeywords')
+    --extern   Allow the ScanKeywordList variable to be globally visible
+
+gen_keywordlist.pl transforms a list of keywords into a ScanKeywordList.
+The output filename is derived from the input file by inserting _d,
+for example kwlist_d.h is produced from kwlist.h.
+EOM
+}
diff --git a/src/tools/msvc/Mkvcbuild.pm b/src/tools/msvc/Mkvcbuild.pm
index 2921d193a16..56192f1b20c 100644
--- a/src/tools/msvc/Mkvcbuild.pm
+++ b/src/tools/msvc/Mkvcbuild.pm
@@ -118,7 +118,7 @@ sub mkvcbuild
 
 	our @pgcommonallfiles = qw(
 	  base64.c config_info.c controldata_utils.c exec.c file_perm.c ip.c
-	  keywords.c link-canary.c md5.c
+	  keywords.c kwlookup.c link-canary.c md5.c
 	  pg_lzcompress.c pgfnames.c psprintf.c relpath.c rmtree.c
 	  saslprep.c scram-common.c string.c unicode_norm.c username.c
 	  wait_error.c);
diff --git a/src/tools/msvc/Solution.pm b/src/tools/msvc/Solution.pm
index eb2346b8d3e..937bf184e27 100644
--- a/src/tools/msvc/Solution.pm
+++ b/src/tools/msvc/Solution.pm
@@ -410,6 +410,42 @@ sub GenerateFiles
 	}
 
 	if (IsNewer(
+			'src/common/kwlist_d.h',
+			'src/include/parser/kwlist.h'))
+	{
+		print "Generating kwlist_d.h...\n";
+		system('perl src/tools/gen_keywordlist.pl --extern -o src/common src/include/parser/kwlist.h');
+	}
+
+	if (IsNewer(
+			'src/pl/plpgsql/src/pl_reserved_kwlist_d.h',
+			'src/pl/plpgsql/src/pl_reserved_kwlist.h')
+		|| IsNewer(
+			'src/pl/plpgsql/src/pl_unreserved_kwlist_d.h',
+			'src/pl/plpgsql/src/pl_unreserved_kwlist.h'))
+	{
+		print "Generating pl_reserved_kwlist_d.h and pl_unreserved_kwlist_d.h...\n";
+		chdir('src/pl/plpgsql/src');
+		system('perl ../../../tools/gen_keywordlist.pl --varname ReservedPLKeywords pl_reserved_kwlist.h');
+		system('perl ../../../tools/gen_keywordlist.pl --varname UnreservedPLKeywords pl_unreserved_kwlist.h');
+		chdir('../../../..');
+	}
+
+	if (IsNewer(
+			'src/interfaces/ecpg/preproc/c_kwlist_d.h',
+			'src/interfaces/ecpg/preproc/c_kwlist.h')
+		|| IsNewer(
+			'src/interfaces/ecpg/preproc/ecpg_kwlist_d.h',
+			'src/interfaces/ecpg/preproc/ecpg_kwlist.h'))
+	{
+		print "Generating c_kwlist_d.h and ecpg_kwlist_d.h...\n";
+		chdir('src/interfaces/ecpg/preproc');
+		system('perl ../../../tools/gen_keywordlist.pl --varname ScanCKeywords c_kwlist.h');
+		system('perl ../../../tools/gen_keywordlist.pl --varname ScanECPGKeywords ecpg_kwlist.h');
+		chdir('../../../..');
+	}
+
+	if (IsNewer(
 			'src/interfaces/ecpg/preproc/preproc.y',
 			'src/backend/parser/gram.y'))
 	{
diff --git a/src/tools/msvc/clean.bat b/src/tools/msvc/clean.bat
index 7a23a2b55f7..069d6eb569d 100755
--- a/src/tools/msvc/clean.bat
+++ b/src/tools/msvc/clean.bat
@@ -64,6 +64,11 @@ if %DIST%==1 if exist src\pl\tcl\pltclerrcodes.h del /q src\pl\tcl\pltclerrcodes
 if %DIST%==1 if exist src\backend\utils\sort\qsort_tuple.c del /q src\backend\utils\sort\qsort_tuple.c
 if %DIST%==1 if exist src\bin\psql\sql_help.c del /q src\bin\psql\sql_help.c
 if %DIST%==1 if exist src\bin\psql\sql_help.h del /q src\bin\psql\sql_help.h
+if %DIST%==1 if exist src\common\kwlist_d.h del /q src\common\kwlist_d.h
+if %DIST%==1 if exist src\pl\plpgsql\src\pl_reserved_kwlist_d.h del /q src\pl\plpgsql\src\pl_reserved_kwlist_d.h
+if %DIST%==1 if exist src\pl\plpgsql\src\pl_unreserved_kwlist_d.h del /q src\pl\plpgsql\src\pl_unreserved_kwlist_d.h
+if %DIST%==1 if exist src\interfaces\ecpg\preproc\c_kwlist_d.h del /q src\interfaces\ecpg\preproc\c_kwlist_d.h
+if %DIST%==1 if exist src\interfaces\ecpg\preproc\ecpg_kwlist_d.h del /q src\interfaces\ecpg\preproc\ecpg_kwlist_d.h
 if %DIST%==1 if exist src\interfaces\ecpg\preproc\preproc.y del /q src\interfaces\ecpg\preproc\preproc.y
 if %DIST%==1 if exist src\backend\catalog\postgres.bki del /q src\backend\catalog\postgres.bki
 if %DIST%==1 if exist src\backend\catalog\postgres.description del /q src\backend\catalog\postgres.description