# HG changeset patch # User Christian Brabandt # Date 1490450405 -3600 # Node ID 62c96fee518e715295728c4ced46ab2990a7f740 # Parent 9b7de4c4fd04adeca883817a3987bce646ea7c44 patch 8.0.0504: looking up an Ex command is a bit slow commit https://github.com/vim/vim/commit/e5e0fbcd4244d032a0635ad7defe2831f251c639 Author: Bram Moolenaar Date: Sat Mar 25 14:51:01 2017 +0100 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) diff --git a/Filelist b/Filelist --- a/Filelist +++ b/Filelist @@ -215,6 +215,7 @@ SRC_UNIX = \ src/config.mk.in \ src/configure \ src/configure.ac \ + src/create_cmdidxs.pl \ src/gui_at_fs.c \ src/gui_at_sb.c \ src/gui_at_sb.h \ diff --git a/src/Makefile b/src/Makefile --- 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 --- /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 () { + 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 --- 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" -/* - * 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 +/* 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 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 UNU } } - 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 --- 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,