Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Use a pointer to the top of the stack rather than an index into the stack in the Lemon-generated parser template, for about 6.6% parser performance gain. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
3c2a770549d5bb65fcd6cc684e0a0ae6 |
User & Date: | drh 2016-05-23 21:56:24.427 |
Context
2016-05-24
| ||
00:40 | Improvements to the initialization of the push-down automoton for the Lemon-generated parser. Smaller and faster. (check-in: 3b28b68e23 user: drh tags: trunk) | |
2016-05-23
| ||
21:56 | Use a pointer to the top of the stack rather than an index into the stack in the Lemon-generated parser template, for about 6.6% parser performance gain. (check-in: 3c2a770549 user: drh tags: trunk) | |
19:02 | Avoid a minor error message when running RTREE without an sqlite_stat1 table. (check-in: 276e92f5b4 user: drh tags: trunk) | |
Changes
Changes to tool/lempar.c.
︙ | ︙ | |||
199 200 201 202 203 204 205 | ** is the value of the token */ }; typedef struct yyStackEntry yyStackEntry; /* The state of the parser is completely contained in an instance of ** the following structure */ struct yyParser { | | | | 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 | ** is the value of the token */ }; typedef struct yyStackEntry yyStackEntry; /* The state of the parser is completely contained in an instance of ** the following structure */ struct yyParser { yyStackEntry *yytos; /* Pointer to top element of the stack */ #ifdef YYTRACKMAXSTACKDEPTH int yyhwm; /* High-water mark of the stack */ #endif #ifndef YYNOERRORRECOVERY int yyerrcnt; /* Shifts left before out of the error */ #endif ParseARG_SDECL /* A place to hold %extra_argument */ #if YYSTACKDEPTH<=0 int yystksz; /* Current side of the stack */ |
︙ | ︙ | |||
313 314 315 316 317 318 319 | ** A pointer to a parser. This pointer is used in subsequent calls ** to Parse and ParseFree. */ void *ParseAlloc(void *(*mallocProc)(YYMALLOCARGTYPE)){ yyParser *pParser; pParser = (yyParser*)(*mallocProc)( (YYMALLOCARGTYPE)sizeof(yyParser) ); if( pParser ){ | | | | 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 | ** A pointer to a parser. This pointer is used in subsequent calls ** to Parse and ParseFree. */ void *ParseAlloc(void *(*mallocProc)(YYMALLOCARGTYPE)){ yyParser *pParser; pParser = (yyParser*)(*mallocProc)( (YYMALLOCARGTYPE)sizeof(yyParser) ); if( pParser ){ pParser->yytos = 0; #ifdef YYTRACKMAXSTACKDEPTH pParser->yyhwm = 0; #endif #if YYSTACKDEPTH<=0 pParser->yystack = NULL; pParser->yystksz = 0; yyGrowStack(pParser); #endif } |
︙ | ︙ | |||
365 366 367 368 369 370 371 | ** Pop the parser's stack once. ** ** If there is a destructor routine associated with the token which ** is popped from the stack, then call it. */ static void yy_pop_parser_stack(yyParser *pParser){ yyStackEntry *yytos; | | | | 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 | ** Pop the parser's stack once. ** ** If there is a destructor routine associated with the token which ** is popped from the stack, then call it. */ static void yy_pop_parser_stack(yyParser *pParser){ yyStackEntry *yytos; assert( pParser->yytos!=0 ); yytos = pParser->yytos--; #ifndef NDEBUG if( yyTraceFILE ){ fprintf(yyTraceFILE,"%sPopping %s\n", yyTracePrompt, yyTokenName[yytos->major]); } #endif |
︙ | ︙ | |||
393 394 395 396 397 398 399 | void *p, /* The parser to be deleted */ void (*freeProc)(void*) /* Function used to reclaim memory */ ){ yyParser *pParser = (yyParser*)p; #ifndef YYPARSEFREENEVERNULL if( pParser==0 ) return; #endif | | | | | 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 | void *p, /* The parser to be deleted */ void (*freeProc)(void*) /* Function used to reclaim memory */ ){ yyParser *pParser = (yyParser*)p; #ifndef YYPARSEFREENEVERNULL if( pParser==0 ) return; #endif while( pParser->yytos>=pParser->yystack ) yy_pop_parser_stack(pParser); #if YYSTACKDEPTH<=0 free(pParser->yystack); #endif (*freeProc)((void*)pParser); } /* ** Return the peak depth of the stack for a parser. */ #ifdef YYTRACKMAXSTACKDEPTH int ParseStackPeak(void *p){ yyParser *pParser = (yyParser*)p; return pParser->yyhwm; } #endif /* ** 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 */ ){ int i; int stateno = pParser->yytos->stateno; if( stateno>=YY_MIN_REDUCE ) return stateno; assert( stateno <= YY_SHIFT_COUNT ); do{ i = yy_shift_ofst[stateno]; if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno]; assert( iLookAhead!=YYNOCODE ); |
︙ | ︙ | |||
512 513 514 515 516 517 518 | } /* ** The following routine is called if the stack overflows. */ static void yyStackOverflow(yyParser *yypParser){ ParseARG_FETCH; | | | | | | | | > | | | | | 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 | } /* ** The following routine is called if the stack overflows. */ static void yyStackOverflow(yyParser *yypParser){ ParseARG_FETCH; yypParser->yytos--; #ifndef NDEBUG if( yyTraceFILE ){ fprintf(yyTraceFILE,"%sStack Overflow!\n",yyTracePrompt); } #endif while( yypParser->yytos>=yypParser->yystack ) yy_pop_parser_stack(yypParser); /* Here code is inserted which will execute if the parser ** stack every overflows */ /******** Begin %stack_overflow code ******************************************/ %% /******** End %stack_overflow code ********************************************/ ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ } /* ** Print tracing information for a SHIFT action */ #ifndef NDEBUG static void yyTraceShift(yyParser *yypParser, int yyNewState){ if( yyTraceFILE ){ if( yyNewState<YYNSTATE ){ fprintf(yyTraceFILE,"%sShift '%s', go to state %d\n", yyTracePrompt,yyTokenName[yypParser->yytos->major], yyNewState); }else{ fprintf(yyTraceFILE,"%sShift '%s'\n", yyTracePrompt,yyTokenName[yypParser->yytos->major]); } } } #else # define yyTraceShift(X,Y) #endif /* ** Perform a shift action. */ 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 */ ParseTOKENTYPE yyMinor /* The minor token to shift in */ ){ yyStackEntry *yytos; yypParser->yytos++; #ifdef YYTRACKMAXSTACKDEPTH if( (int)(yypParser->yytos - yypParser->yystack)>yypParser->yyhwm ){ yypParser->yyhwm++; assert( yypParser->yyhwm == (int)(yypParser->yytos - yypParser->yystack) ); } #endif #if YYSTACKDEPTH>0 if( yypParser->yytos>=&yypParser->yystack[YYSTACKDEPTH] ){ yyStackOverflow(yypParser); return; } #else if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz] ){ yyGrowStack(yypParser); if( yypParser->yytos>=&yypParser->yystach[yypParser->yystksz] ){ yyStackOverflow(yypParser); return; } } #endif yytos = yypParser->yytos; yytos->stateno = (YYACTIONTYPE)yyNewState; yytos->major = (YYCODETYPE)yyMajor; yytos->minor.yy0 = yyMinor; yyTraceShift(yypParser, yyNewState); } /* The following table contains information about every rule that |
︙ | ︙ | |||
609 610 611 612 613 614 615 | unsigned int yyruleno /* Number of the rule by which to reduce */ ){ int yygoto; /* The next state */ int yyact; /* The next action */ yyStackEntry *yymsp; /* The top of the parser's stack */ int yysize; /* Amount to pop the stack */ ParseARG_FETCH; | | | | > | | | | 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 | unsigned int yyruleno /* Number of the rule by which to reduce */ ){ int yygoto; /* The next state */ int yyact; /* The next action */ yyStackEntry *yymsp; /* The top of the parser's stack */ int yysize; /* Amount to pop the stack */ ParseARG_FETCH; yymsp = yypParser->yytos; #ifndef NDEBUG if( yyTraceFILE && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){ yysize = yyRuleInfo[yyruleno].nrhs; fprintf(yyTraceFILE, "%sReduce [%s], go to state %d.\n", yyTracePrompt, yyRuleName[yyruleno], yymsp[-yysize].stateno); } #endif /* NDEBUG */ /* Check that the stack is large enough to grow by a single entry ** if the RHS of the rule is empty. This ensures that there is room ** enough on the stack to push the LHS value */ if( yyRuleInfo[yyruleno].nrhs==0 ){ #ifdef YYTRACKMAXSTACKDEPTH if( (int)(yypParser->yytos - yypParser->yystack)>yypParser->yyhwm ){ yypParser->yyhwm++; assert( yypParser->yyhwm == (int)(yypParser->yytos - yypParser->yystack)); } #endif #if YYSTACKDEPTH>0 if( yypParser->yytos>=&yypParser->yystack[YYSTACKDEPTH-1] ){ yyStackOverflow(yypParser); return; } #else if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz-1] ){ yyGrowStack(yypParser); if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz-1] ){ yyStackOverflow(yypParser); return; } } #endif } |
︙ | ︙ | |||
661 662 663 664 665 666 667 | /********** End reduce actions ************************************************/ }; assert( yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) ); yygoto = yyRuleInfo[yyruleno].lhs; yysize = yyRuleInfo[yyruleno].nrhs; yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); if( yyact <= YY_MAX_SHIFTREDUCE ){ | | | > > | | > | 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 | /********** End reduce actions ************************************************/ }; assert( yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) ); yygoto = yyRuleInfo[yyruleno].lhs; yysize = yyRuleInfo[yyruleno].nrhs; yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); if( yyact <= YY_MAX_SHIFTREDUCE ){ if( yyact>YY_MAX_SHIFT ){ yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; } yymsp -= yysize-1; yypParser->yytos = yymsp; yymsp->stateno = (YYACTIONTYPE)yyact; yymsp->major = (YYCODETYPE)yygoto; yyTraceShift(yypParser, yyact); }else{ assert( yyact == YY_ACCEPT_ACTION ); yypParser->yytos -= yysize; yy_accept(yypParser); } } /* ** The following code executes when the parse fails */ #ifndef YYNOERRORRECOVERY static void yy_parse_failed( yyParser *yypParser /* The parser */ ){ ParseARG_FETCH; #ifndef NDEBUG if( yyTraceFILE ){ fprintf(yyTraceFILE,"%sFail!\n",yyTracePrompt); } #endif while( yypParser->yytos>=yypParser->yystack ) yy_pop_parser_stack(yypParser); yypParser->yytos = 0; /* Here code is inserted which will be executed whenever the ** parser fails */ /************ Begin %parse_failure code ***************************************/ %% /************ End %parse_failure code *****************************************/ ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ } |
︙ | ︙ | |||
725 726 727 728 729 730 731 | ){ ParseARG_FETCH; #ifndef NDEBUG if( yyTraceFILE ){ fprintf(yyTraceFILE,"%sAccept!\n",yyTracePrompt); } #endif | | > | 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 | ){ ParseARG_FETCH; #ifndef NDEBUG if( yyTraceFILE ){ fprintf(yyTraceFILE,"%sAccept!\n",yyTracePrompt); } #endif while( yypParser->yytos>=yypParser->yystack ) yy_pop_parser_stack(yypParser); yypParser->yytos = 0; /* Here code is inserted which will be executed whenever the ** parser accepts */ /*********** Begin %parse_accept code *****************************************/ %% /*********** End %parse_accept code *******************************************/ ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ } |
︙ | ︙ | |||
771 772 773 774 775 776 777 | #ifdef YYERRORSYMBOL int yyerrorhit = 0; /* True if yymajor has invoked an error */ #endif yyParser *yypParser; /* The parser */ /* (re)initialize the parser, if necessary */ yypParser = (yyParser*)yyp; | | | | 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 | #ifdef YYERRORSYMBOL int yyerrorhit = 0; /* True if yymajor has invoked an error */ #endif yyParser *yypParser; /* The parser */ /* (re)initialize the parser, if necessary */ yypParser = (yyParser*)yyp; if( yypParser->yytos==0 ){ #if YYSTACKDEPTH<=0 if( yypParser->yystksz <=0 ){ yyStackOverflow(yypParser); return; } #endif yypParser->yytos = yypParser->yystack; #ifndef YYNOERRORRECOVERY yypParser->yyerrcnt = -1; #endif yypParser->yystack[0].stateno = 0; yypParser->yystack[0].major = 0; #ifndef NDEBUG if( yyTraceFILE ){ |
︙ | ︙ | |||
805 806 807 808 809 810 811 | fprintf(yyTraceFILE,"%sInput '%s'\n",yyTracePrompt,yyTokenName[yymajor]); } #endif do{ yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); if( yyact <= YY_MAX_SHIFTREDUCE ){ | | > > | 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 | fprintf(yyTraceFILE,"%sInput '%s'\n",yyTracePrompt,yyTokenName[yymajor]); } #endif do{ yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); if( yyact <= YY_MAX_SHIFTREDUCE ){ if( yyact > YY_MAX_SHIFT ){ yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; } yy_shift(yypParser,yyact,yymajor,yyminor); #ifndef YYNOERRORRECOVERY yypParser->yyerrcnt--; #endif yymajor = YYNOCODE; }else if( yyact <= YY_MAX_REDUCE ){ yy_reduce(yypParser,yyact-YY_MIN_REDUCE); |
︙ | ︙ | |||
847 848 849 850 851 852 853 | ** processing will occur until three tokens have been ** shifted successfully. ** */ if( yypParser->yyerrcnt<0 ){ yy_syntax_error(yypParser,yymajor,yyminor); } | | < | | | | | | 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 | ** processing will occur until three tokens have been ** shifted successfully. ** */ if( yypParser->yyerrcnt<0 ){ yy_syntax_error(yypParser,yymajor,yyminor); } yymx = yypParser->yytos->major; if( yymx==YYERRORSYMBOL || yyerrorhit ){ #ifndef NDEBUG if( yyTraceFILE ){ fprintf(yyTraceFILE,"%sDiscard input token %s\n", yyTracePrompt,yyTokenName[yymajor]); } #endif yy_destructor(yypParser, (YYCODETYPE)yymajor, &yyminorunion); yymajor = YYNOCODE; }else{ while( yypParser->yytos >= &yypParser->yystack && yymx != YYERRORSYMBOL && (yyact = yy_find_reduce_action( yypParser->yytos->stateno, YYERRORSYMBOL)) >= YY_MIN_REDUCE ){ yy_pop_parser_stack(yypParser); } if( yypParser->yytos < yypParser->yystack || yymajor==0 ){ yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); yy_parse_failed(yypParser); yymajor = YYNOCODE; }else if( yymx!=YYERRORSYMBOL ){ yy_shift(yypParser,yyact,YYERRORSYMBOL,yyminor); } } |
︙ | ︙ | |||
910 911 912 913 914 915 916 | yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); if( yyendofinput ){ yy_parse_failed(yypParser); } yymajor = YYNOCODE; #endif } | | | > | | < > > | 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 | yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); if( yyendofinput ){ yy_parse_failed(yypParser); } yymajor = YYNOCODE; #endif } }while( yymajor!=YYNOCODE && yypParser->yytos>=yypParser->yystack ); #ifndef NDEBUG if( yyTraceFILE ){ yyStackEntry *i; char cDiv = '['; fprintf(yyTraceFILE,"%sReturn. Stack=",yyTracePrompt); for(i=&yypParser->yystack[1]; i<=yypParser->yytos; i++){ fprintf(yyTraceFILE,"%c%s", cDiv, yyTokenName[i->major]); cDiv = ' '; } fprintf(yyTraceFILE,"]\n"); } #endif return; } |