From fd39c5874a3fe6e0009832e5b50999afeda671d2 Mon Sep 17 00:00:00 2001 From: drh Date: Sat, 21 Apr 2018 22:40:08 +0000 Subject: [PATCH] Performance improvements on the main loop of the LEMON-generated parser. FossilOrigin-Name: fec1ebadeb9d6b55b19a1c159c543fd7ae67b3307c4caee4d2541bd783630e23 --- manifest | 12 +++++----- manifest.uuid | 2 +- tool/lempar.c | 63 +++++++++++++++++++++++++++++---------------------- 3 files changed, 43 insertions(+), 34 deletions(-) diff --git a/manifest b/manifest index c39c2e57ca..fbd61bf9a3 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Enhance\sLEMON\sto\strack\swhich\ssymbols\sactually\scarry\ssemantic\scontent.\nOutput\sthe\slist\sof\ssymbols\sthat\sdo\snot\scarry\scontent\sat\sthe\send\sof\sthe\nreport,\sbut\sdo\snot\s(yet)\sdo\sanything\selse\swith\sthe\sinformation. -D 2018-04-21T20:24:19.958 +C Performance\simprovements\son\sthe\smain\sloop\sof\sthe\sLEMON-generated\sparser. +D 2018-04-21T22:40:08.247 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea F Makefile.in 5ce9343cba9c189046f1afe6d2bcc1f68079439febc05267b98aec6ecc752439 @@ -1645,7 +1645,7 @@ F tool/genfkey.test 4196a8928b78f51d54ef58e99e99401ab2f0a7e5 F tool/getlock.c f4c39b651370156cae979501a7b156bdba50e7ce F tool/kvtest-speed.sh 4761a9c4b3530907562314d7757995787f7aef8f F tool/lemon.c 33892e2a243865f73e6c6e7cecce3c6eb4bb95db4a3d9d86d146c8064feb92fd -F tool/lempar.c 8ce83cbec62cba95819760de2ebab98a1b0d00861af5876bd456a29e1158229d +F tool/lempar.c 01f28a4d245f0ea480fab1147c1244fe50434cea924ce258b3e8570a6340a0d3 F tool/libvers.c caafc3b689638a1d88d44bc5f526c2278760d9b9 F tool/loadfts.c c3c64e4d5e90e8ba41159232c2189dba4be7b862 F tool/logest.c 11346aa019e2e77a00902aa7d0cabd27bd2e8cca @@ -1725,7 +1725,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0 -P b78005b6d41640203c163ffde4faf9336f11f47f42e8b7fe10b95415bbaed028 -R bdad1972dfc51eb7c1aa0a96e8529d8a +P dcf2bafc159179859b91ffea3a4ebd70b5ca6de9e1d515eaf9afde8cfff26c6c +R 30c687ea8cbf9562ea971a83f0b60716 U drh -Z c5d80323466004edd7fb02f443feea52 +Z 5f81242a2fad2cc1a6991b9a8c5f4a01 diff --git a/manifest.uuid b/manifest.uuid index 1fc92158dc..febf97a27e 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -dcf2bafc159179859b91ffea3a4ebd70b5ca6de9e1d515eaf9afde8cfff26c6c \ No newline at end of file +fec1ebadeb9d6b55b19a1c159c543fd7ae67b3307c4caee4d2541bd783630e23 \ No newline at end of file diff --git a/tool/lempar.c b/tool/lempar.c index fcc47f9bed..d2b700a8cf 100644 --- a/tool/lempar.c +++ b/tool/lempar.c @@ -505,13 +505,12 @@ int ParseCoverage(FILE *out){ ** Find the appropriate action for a parser given the terminal ** look-ahead token iLookAhead. */ -static unsigned int yy_find_shift_action( - yyParser *pParser, /* The parser */ - YYCODETYPE iLookAhead /* The look-ahead token */ +static YYACTIONTYPE yy_find_shift_action( + YYCODETYPE iLookAhead, /* The look-ahead token */ + YYACTIONTYPE stateno /* Current state number */ ){ int i; - int stateno = pParser->yytos->stateno; - + if( stateno>YY_MAX_SHIFT ) return stateno; assert( stateno <= YY_SHIFT_COUNT ); #if defined(YYCOVERAGE) @@ -575,7 +574,7 @@ static unsigned int yy_find_shift_action( ** look-ahead token iLookAhead. */ static int yy_find_reduce_action( - int stateno, /* Current state number */ + YYACTIONTYPE stateno, /* Current state number */ YYCODETYPE iLookAhead /* The look-ahead token */ ){ int i; @@ -647,8 +646,8 @@ static void yyTraceShift(yyParser *yypParser, int yyNewState, const char *zTag){ */ static void yy_shift( yyParser *yypParser, /* The parser to be shifted */ - int yyNewState, /* The new state to shift in */ - int yyMajor, /* The major token to shift in */ + YYACTIONTYPE yyNewState, /* The new state to shift in */ + YYCODETYPE yyMajor, /* The major token to shift in */ ParseTOKENTYPE yyMinor /* The minor token to shift in */ ){ yyStackEntry *yytos; @@ -678,8 +677,8 @@ static void yy_shift( yyNewState += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; } yytos = yypParser->yytos; - yytos->stateno = (YYACTIONTYPE)yyNewState; - yytos->major = (YYCODETYPE)yyMajor; + yytos->stateno = yyNewState; + yytos->major = yyMajor; yytos->minor.yy0 = yyMinor; yyTraceShift(yypParser, yyNewState, "Shift"); } @@ -706,7 +705,7 @@ static void yy_accept(yyParser*); /* Forward Declaration */ ** only called from one place, optimizing compilers will in-line it, which ** means that the extra parameters have no performance impact. */ -static void yy_reduce( +static YYACTIONTYPE yy_reduce( yyParser *yypParser, /* The parser */ unsigned int yyruleno, /* Number of the rule by which to reduce */ int yyLookahead, /* Lookahead token, or YYNOCODE if none */ @@ -748,13 +747,13 @@ static void yy_reduce( #if YYSTACKDEPTH>0 if( yypParser->yytos>=yypParser->yystackEnd ){ yyStackOverflow(yypParser); - return; + return YY_ACCEPT_ACTION; } #else if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz-1] ){ if( yyGrowStack(yypParser) ){ yyStackOverflow(yypParser); - return; + return YY_ACCEPT_ACTION; } yymsp = yypParser->yytos; } @@ -791,6 +790,7 @@ static void yy_reduce( yymsp->stateno = (YYACTIONTYPE)yyact; yymsp->major = (YYCODETYPE)yygoto; yyTraceShift(yypParser, yyact, "... then shift"); + return yyact; } /* @@ -888,7 +888,7 @@ void Parse( ParseARG_PDECL /* Optional %extra_argument parameter */ ){ YYMINORTYPE yyminorunion; - unsigned int yyact; /* The parser action. */ + YYACTIONTYPE yyact; /* The parser action. */ #if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY) int yyendofinput; /* True if we are at the end of input */ #endif @@ -904,32 +904,40 @@ void Parse( yyendofinput = (yymajor==0); #endif + yyact = yypParser->yytos->stateno; #ifndef NDEBUG if( yyTraceFILE ){ - int stateno = yypParser->yytos->stateno; - if( stateno < YY_MIN_REDUCE ){ + if( yyact < YY_MIN_REDUCE ){ fprintf(yyTraceFILE,"%sInput '%s' in state %d\n", - yyTracePrompt,yyTokenName[yymajor],stateno); + yyTracePrompt,yyTokenName[yymajor],yyact); }else{ fprintf(yyTraceFILE,"%sInput '%s' with pending reduce %d\n", - yyTracePrompt,yyTokenName[yymajor],stateno-YY_MIN_REDUCE); + yyTracePrompt,yyTokenName[yymajor],yyact-YY_MIN_REDUCE); } } #endif do{ - yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); + assert( yyact==yypParser->yytos->stateno ); + yyact = yy_find_shift_action(yymajor,yyact); if( yyact >= YY_MIN_REDUCE ){ - yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor,yyminor ParseCTX_PARAM); + yyact = yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor, + yyminor ParseCTX_PARAM); }else if( yyact <= YY_MAX_SHIFTREDUCE ){ yy_shift(yypParser,yyact,yymajor,yyminor); #ifndef YYNOERRORRECOVERY yypParser->yyerrcnt--; #endif - yymajor = YYNOCODE; + break; }else if( yyact==YY_ACCEPT_ACTION ){ - yypParser->yytos--; - yy_accept(yypParser); + /* YY_ACCEPT_ACTION also happens on a stack overflow. We distingush + ** the two cases by observing that on a true accept, there should be + ** a single token left on the stack, whereas on a stack overflow, + ** the stack has been popped (by yyStackOverflow()) to be empty */ + if( yypParser->yytos > yypParser->yystack ){ + yypParser->yytos--; + yy_accept(yypParser); + } return; }else{ assert( yyact == YY_ERROR_ACTION ); @@ -997,6 +1005,8 @@ void Parse( } yypParser->yyerrcnt = 3; yyerrorhit = 1; + if( yymajor==YYNOCODE ) break; + yyact = yypParser->yytos->stateno; #elif defined(YYNOERRORRECOVERY) /* If the YYNOERRORRECOVERY macro is defined, then do not attempt to ** do any kind of error recovery. Instead, simply invoke the syntax @@ -1007,8 +1017,7 @@ void Parse( */ yy_syntax_error(yypParser,yymajor, yyminor); yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); - yymajor = YYNOCODE; - + break; #else /* YYERRORSYMBOL is not defined */ /* This is what we do if the grammar does not define ERROR: ** @@ -1030,10 +1039,10 @@ void Parse( yypParser->yyerrcnt = -1; #endif } - yymajor = YYNOCODE; + break; #endif } - }while( yymajor!=YYNOCODE && yypParser->yytos>yypParser->yystack ); + }while( yypParser->yytos>yypParser->yystack ); #ifndef NDEBUG if( yyTraceFILE ){ yyStackEntry *i; -- 2.47.2