patch 8.0.0504: looking up an Ex command is a bit slow

Problem:    Looking up an Ex command is a bit slow.
Solution:   Instead of just using the first letter, also use the second letter
            to skip ahead in the list of commands. Generate the table with a
            Perl script. (Dominique Pelle, closes #1589)

4 files changed, 175 insertions, 35 deletions

diff --git a/src/Makefile b/src/Makefile
index 1309a636d..e8314ea6e 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -1884,6 +1884,16 @@ autoconf:
 	-rm -rf autom4te.cache
 	-rm -f auto/config.status auto/config.cache
 
+# Run Perl to generate the Ex command lookup table.  This only needs to be run
+# when a command name has been added or changed.
+# NOTE: Only works when perl and vim executables are available
+cmdidxs: ex_cmds.h
+	if test X`perl -e "print 123"` = "X123"; then \
+	   vim ex_docmd.c -c '/Beginning.*create_cmdidxs/,/End.*create_cmdidxs/! perl create_cmdidxs.pl' -c wq; \
+	else \
+	   echo Cannot run Perl; \
+	fi
+
 # Re-execute this Makefile to include the new auto/config.mk produced by
 # configure Only used when typing "make" with a fresh auto/config.mk.
 myself:
diff --git a/src/create_cmdidxs.pl b/src/create_cmdidxs.pl
new file mode 100644
index 000000000..ff8dcc3f4
--- /dev/null
+++ b/src/create_cmdidxs.pl
@@ -0,0 +1,74 @@
+#!/usr/bin/perl -w
+#
+# This script generates the tables cmdidxs1[] and cmdidxs2[][] which,
+# given a Ex command, determine the first value to probe to find
+# a matching command in cmdnames[] based on the first character
+# and the first 2 characters of the command.
+# This is used to speed up lookup in cmdnames[].
+#
+# Script should be run every time new Ex commands are added in Vim,
+# from the src/vim directory, since it reads commands from "ex_cmds.h".
+
+# Find the list of Vim commands from cmdnames[] table in ex_cmds.h
+my @cmds;
+my @skipped;
+open(IN, "< ex_cmds.h") or die "can't open ex_cmds.h: $!\n";
+while (<IN>) {
+  if (/^EX\(CMD_\S*,\s*"([a-z][^"]*)"/) {
+    push (@cmds, $1);
+  } elsif (/^EX\(CMD_/) {
+    push (@skipped, $1);
+  }
+}
+
+my %cmdidxs1;
+my %cmdidxs2;
+
+for (my $i = $#cmds; $i >= 0; --$i) {
+  my $cmd = $cmds[$i];
+  my $c1 = substr($cmd, 0, 1); # First character of command.
+
+  $cmdidxs1{$c1} = $i;
+
+  if (length($cmd) > 1) {
+    my $c2 = substr($cmd, 1, 1); # Second character of command.
+    $cmdidxs2{$c1}{$c2} = $i if (('a' lt $c2) and ($c2 lt 'z'));
+  }
+}
+
+print "/* Beginning of automatically generated code by create_cmdidxs.pl\n",
+      " *\n",
+      " * Table giving the index of the first command in cmdnames[] to lookup\n",
+      " * based on the first letter of a command.\n",
+      " */\n",
+      "static const unsigned short cmdidxs1[26] =\n{\n",
+      join(",\n", map("  /* $_ */ $cmdidxs1{$_}", ('a' .. 'z'))),
+      "\n};\n",
+      "\n",
+      "/*\n",
+      " * Table giving the index of the first command in cmdnames[] to lookup\n",
+      " * based on the first 2 letters of a command.\n",
+      " * Values in cmdidxs2[c1][c2] are relative to cmdidxs1[c1] so that they\n",
+      " * fit in a byte.\n",
+      " */\n",
+      "static const unsigned char cmdidxs2[26][26] =\n",
+      "{ /*         a   b   c   d   e   f   g   h   i   j   k   l   m   n   o   p   q   r   s   t   u   v   w   x   y   z */\n";
+for my $c1 ('a' .. 'z') {
+  print "  /* $c1 */ {";
+  for my $c2 ('a' .. 'z') {
+    if (exists $cmdidxs2{$c1}{$c2}) {
+      printf "%3d,", $cmdidxs2{$c1}{$c2} - $cmdidxs1{$c1};
+    } else {
+      printf "  0,";
+    }
+  }
+  print " }";
+  print "," unless ($c1 eq 'z');
+  print "\n";
+}
+print "};\n",
+      "\n",
+      "static int command_count = ", $#cmds + $#skipped + 2 , ";\n",
+      "\n",
+      "/* End of automatically generated code by create_cmdidxs.pl */\n";
+
diff --git a/src/ex_docmd.c b/src/ex_docmd.c
index 96e2b3f5f..17fec33ec 100644
--- a/src/ex_docmd.c
+++ b/src/ex_docmd.c
@@ -495,40 +495,81 @@ static void	ex_folddo(exarg_T *eap);
 #define DO_DECLARE_EXCMD
 #include "ex_cmds.h"
 
+/* Beginning of automatically generated code by create_cmdidxs.pl
+ *
+ * Table giving the index of the first command in cmdnames[] to lookup
+ * based on the first letter of a command.
+ */
+static const unsigned short cmdidxs1[26] =
+{
+  /* a */ 0,
+  /* b */ 19,
+  /* c */ 42,
+  /* d */ 103,
+  /* e */ 125,
+  /* f */ 145,
+  /* g */ 161,
+  /* h */ 167,
+  /* i */ 176,
+  /* j */ 194,
+  /* k */ 196,
+  /* l */ 201,
+  /* m */ 259,
+  /* n */ 277,
+  /* o */ 297,
+  /* p */ 309,
+  /* q */ 348,
+  /* r */ 351,
+  /* s */ 370,
+  /* t */ 437,
+  /* u */ 472,
+  /* v */ 483,
+  /* w */ 501,
+  /* x */ 516,
+  /* y */ 525,
+  /* z */ 526
+};
+
 /*
- * Table used to quickly search for a command, based on its first character.
- */
-static cmdidx_T cmdidxs[27] =
-{
-	CMD_append,
-	CMD_buffer,
-	CMD_change,
-	CMD_delete,
-	CMD_edit,
-	CMD_file,
-	CMD_global,
-	CMD_help,
-	CMD_insert,
-	CMD_join,
-	CMD_k,
-	CMD_list,
-	CMD_move,
-	CMD_next,
-	CMD_open,
-	CMD_print,
-	CMD_quit,
-	CMD_read,
-	CMD_substitute,
-	CMD_t,
-	CMD_undo,
-	CMD_vglobal,
-	CMD_write,
-	CMD_xit,
-	CMD_yank,
-	CMD_z,
-	CMD_bang
+ * Table giving the index of the first command in cmdnames[] to lookup
+ * based on the first 2 letters of a command.
+ * Values in cmdidxs2[c1][c2] are relative to cmdidxs1[c1] so that they
+ * fit in a byte.
+ */
+static const unsigned char cmdidxs2[26][26] =
+{ /*         a   b   c   d   e   f   g   h   i   j   k   l   m   n   o   p   q   r   s   t   u   v   w   x   y   z */
+  /* a */ {  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  4,  5,  6,  0,  0,  0,  7, 15,  0, 16,  0,  0,  0,  0,  0, },
+  /* b */ {  0,  0,  0,  4,  5,  7,  0,  0,  0,  0,  0,  8,  9, 10, 11, 12,  0, 13,  0,  0,  0,  0, 22,  0,  0,  0, },
+  /* c */ {  0, 10, 12, 14, 16, 18, 21,  0,  0,  0,  0, 29, 33, 36, 42, 51, 53, 54, 55,  0, 57,  0, 60,  0,  0,  0, },
+  /* d */ {  0,  0,  0,  0,  0,  0,  0,  0,  6, 15,  0, 16,  0,  0, 17,  0,  0, 19, 20,  0,  0,  0,  0,  0,  0,  0, },
+  /* e */ {  0,  0,  2,  0,  0,  0,  0,  0,  0,  0,  0,  7,  9, 10,  0,  0,  0,  0,  0,  0,  0,  0,  0, 16,  0,  0, },
+  /* f */ {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  9,  0,  0,  0,  0,  0, 15,  0,  0,  0,  0,  0, },
+  /* g */ {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  2,  0,  0,  4,  5,  0,  0,  0,  0, },
+  /* h */ {  0,  0,  0,  0,  0,  0,  0,  0,  6,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, },
+  /* i */ {  0,  0,  0,  0,  0,  3,  0,  0,  0,  4,  0,  5,  6,  0,  0,  0,  0,  0, 13,  0, 15,  0,  0,  0,  0,  0, },
+  /* j */ {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0, },
+  /* k */ {  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, },
+  /* l */ {  0,  9, 11, 15, 16, 20, 23, 28,  0,  0,  0, 30, 33, 36, 40, 46,  0, 48, 57, 49, 50, 54, 56,  0,  0,  0, },
+  /* m */ {  0,  0,  0,  0,  7,  0,  0,  0,  0,  0, 10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, },
+  /* n */ {  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  5,  8, 10,  0,  0,  0,  0,  0, 17,  0,  0,  0,  0,  0, },
+  /* o */ {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  2,  5,  0,  0,  0,  0,  0,  0,  9,  0, 11,  0,  0,  0, },
+  /* p */ {  0,  0,  3,  0,  4,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7,  9,  0,  0, 16, 17, 26,  0, 27,  0, 28,  0, },
+  /* q */ {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, },
+  /* r */ {  0,  0,  0,  0,  0,  0,  0,  0, 11,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 13, 18,  0,  0,  0,  0, },
+  /* s */ {  0,  6, 15,  0, 18, 22,  0, 24, 25,  0,  0, 28, 30, 34, 38, 40,  0, 48,  0, 49,  0, 61, 62,  0, 63,  0, },
+  /* t */ {  0,  0, 19,  0, 22, 23,  0, 24,  0, 25,  0, 26, 27, 28, 29, 30,  0, 31, 33,  0, 34,  0,  0,  0,  0,  0, },
+  /* u */ {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, },
+  /* v */ {  0,  0,  0,  0,  1,  0,  0,  0,  4,  0,  0,  0,  9, 12,  0,  0,  0,  0, 15,  0, 16,  0,  0,  0,  0,  0, },
+  /* w */ {  0,  0,  0,  0,  0,  0,  0,  3,  4,  0,  0,  0,  0,  8,  0,  9, 10,  0, 12,  0, 13, 14,  0,  0,  0,  0, },
+  /* x */ {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  2,  5,  0,  0,  0,  0,  0,  0,  7,  0,  0,  0,  0,  0, },
+  /* y */ {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, },
+  /* z */ {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, }
 };
 
+static int command_count = 539;
+
+/* End of automatically generated code by create_cmdidxs.pl */
+
 static char_u dollar_command[2] = {'$', 0};
 
 
@@ -614,7 +655,6 @@ restore_dbg_stuff(struct dbg_stuff *dsp)
 }
 #endif
 
-
 /*
  * do_exmode(): Repeatedly get commands for the "Ex" mode, until the ":vi"
  * command is given.
@@ -3208,10 +3248,24 @@ find_command(exarg_T *eap, int *full UNUSED)
 	    }
 	}
 
-	if (ASCII_ISLOWER(*eap->cmd))
-	    eap->cmdidx = cmdidxs[CharOrdLow(*eap->cmd)];
+	if (ASCII_ISLOWER(eap->cmd[0]))
+	{
+	    if (command_count != (int)CMD_SIZE)
+	    {
+		iemsg((char_u *)_("E943: Command table needs to be updated, run 'make cmdidxs'"));
+		getout(1);
+	    }
+
+	    /* Use a precomputed index for fast look-up in cmdnames[]
+	     * taking into account the first 2 letters of eap->cmd. */
+	    int c1 = eap->cmd[0];
+	    int c2 = eap->cmd[1];
+	    eap->cmdidx = cmdidxs1[CharOrdLow(c1)];
+	    if (ASCII_ISLOWER(c2))
+		eap->cmdidx += cmdidxs2[CharOrdLow(c1)][CharOrdLow(c2)];
+	}
 	else
-	    eap->cmdidx = cmdidxs[26];
+	    eap->cmdidx = CMD_bang;
 
 	for ( ; (int)eap->cmdidx < (int)CMD_SIZE;
 			       eap->cmdidx = (cmdidx_T)((int)eap->cmdidx + 1))
diff --git a/src/version.c b/src/version.c
index b6cc7d65a..6719bf100 100644
--- a/src/version.c
+++ b/src/version.c
@@ -765,6 +765,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    504,
+/**/
     503,
 /**/
     502,