To: vim_dev@googlegroups.com Subject: Patch 8.0.0504 Fcc: outbox From: Bram Moolenaar Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ------------ Patch 8.0.0504 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) Files: src/Makefile, src/create_cmdidxs.pl, src/ex_docmd.c, Filelist *** ../vim-8.0.0503/src/Makefile 2017-03-21 17:08:46.678923883 +0100 --- src/Makefile 2017-03-25 14:11:14.611853538 +0100 *************** *** 1884,1889 **** --- 1883,1898 ---- -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: *** ../vim-8.0.0503/src/create_cmdidxs.pl 2017-03-25 14:49:46.422380577 +0100 --- src/create_cmdidxs.pl 2017-03-25 14:44:17.276864694 +0100 *************** *** 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"; + *** ../vim-8.0.0503/src/ex_docmd.c 2017-03-16 17:23:26.819815897 +0100 --- src/ex_docmd.c 2017-03-25 14:44:23.248819614 +0100 *************** *** 495,534 **** #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 }; static char_u dollar_command[2] = {'$', 0}; --- 495,575 ---- #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 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,620 **** } #endif - /* * do_exmode(): Repeatedly get commands for the "Ex" mode, until the ":vi" * command is given. --- 655,660 ---- *************** *** 3208,3217 **** } } ! if (ASCII_ISLOWER(*eap->cmd)) ! eap->cmdidx = cmdidxs[CharOrdLow(*eap->cmd)]; else ! eap->cmdidx = cmdidxs[26]; for ( ; (int)eap->cmdidx < (int)CMD_SIZE; eap->cmdidx = (cmdidx_T)((int)eap->cmdidx + 1)) --- 3248,3271 ---- } } ! 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 = CMD_bang; for ( ; (int)eap->cmdidx < (int)CMD_SIZE; eap->cmdidx = (cmdidx_T)((int)eap->cmdidx + 1)) *** ../vim-8.0.0503/Filelist 2017-03-12 17:10:14.417925081 +0100 --- Filelist 2017-03-25 14:49:07.770672237 +0100 *************** *** 215,220 **** --- 215,221 ---- 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 \ *** ../vim-8.0.0503/src/version.c 2017-03-23 21:53:31.045117492 +0100 --- src/version.c 2017-03-25 13:55:04.375213595 +0100 *************** *** 766,767 **** --- 766,769 ---- { /* Add new patch number below this line */ + /**/ + 504, /**/ -- $ echo pizza > /dev/oven /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\ /// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\ \\\ an exciting new programming language -- http://www.Zimbu.org /// \\\ help me help AIDS victims -- http://ICCF-Holland.org ///