Re: push parser implemenation

[Bob Rossi]

On Fri, Apr 07, 2006 at 02:42:29PM +0200, Akim Demaille wrote:
> Bob,
> 
> I'm starting to toy with your implementation, and to try to bench it.
> It seems that there is about a 15% performance loss of push.c compared
> to yacc.c, both used in pull mode without compiler optimization on my
> Mac.

OK, I thought the 15% increase did not seem correct. The only major
difference besides an extra function call per token, is that yyparse has
to get 'pv->yychar' instead of 'yychar'. I personally believe that any
good compiler/CPU will store the address of pv->yychar and be able to
access that at the same speed as yychar. Here's how somone put it that
Emailed me privatly from the question I asked on gcc-help:

My question:

    I'm currently writing a patch to bison, and can not afford to effect
    it's efficiency.

    Theoretically, a function in bison uses a local variable named "lfoo" and 
    a global variable named "gfoo". I need to pack both of these into a struct,
    named "sfoo".

    If the function currently uses the variables directly like 'lfoo = 0;',
    will changing them to 'sfoo_obj->lfoo = 0;' effect the efficiency of the
    program in regards to speed?

Response:

    I am not exactly sure what size of a change in performance you would
    consider significant.  And it seems like for different types of
    processors, the impact would be different.  For a risc type chip
    (power-pc), there is a toc pointer which is always in a register.  To
    load the address of gfoo, it is an indexed look up from the toc.
    Usually one instruction and one memory fetch to get the address.  At
    that point, the code can get or set the value of gfoo.

    For lfoo, the value could be held in a register.  If not, then it is
    much ilke gfoo except instead of relative to the toc, it is relative
    to the stack pointer.

    If almost every variable is inside the struct, then the pointer to
    the struct will most likely be held in a register so the access to
    sfoo will be exactly like gfoo or lfoo in the case that lfoo is not
    in a register.  If, instead, you are going to have many structs, then
    you are likely going to have an extra instruction to get the address
    of the struct as well as an extra memory reference.  But, for a
    sequence of references that are close together to the same struct,
    the compiler will likely optimize out the extra fetches for the
    address of the struct.

    All this to say -- try it out.  Or maybe compile the code to assembly
    and look at the difference in the assembly.  My guess is that you
    will not be able to tell the difference but a lot of testing will
    show a small change.

> More experiments (and more eyes on this script) would help.
> 
> 
> I have a few comments.
> 
> 1. I think you should not change the semantics of yyparse in the push
>    parser.  In fact, I think the push parser should always provide
>    yyparse as the good old pull interface wrapping the yyparse_push
>    interface or whatever.
> 

OK, so you would like the push parser to have a yyparse () function that
internally calls yyparse_push? I can do that, even though I really don't
see the point. Why would a user want to use the push parser if they
didn't want to use it in push mode? There probably is some advantage to
this that I can't think of though.

Would you like me to name it yyparse_push? or yyparse_wrapper?

> 2. What is the way one is expected to pass yylval?  I cheated:
> 
>     #if YYPUSH
>     static int
>     yyparse_wrapper ()
>     {
>       struct yypvars *ctx = yypvarsinit ();
>       do {
>         yyparse (ctx);
>         set_yychar (ctx, yylex ());
>         ctx->yylval = yylval;
>       } while (get_yyresult (ctx) != 0);
>       free (ctx);
>     }
>     #define yyparse yyparse_wrapper
>     #endif

There are currently 4 user visible variables. They are
yychar, yylval, yynerrs, and yylloc.

I am proposing 4 set's of set/get functions that give the user access to
these variables. If that is acceptable, I'll add the functions into the
patch. We could also make the definition of the struct yypvars in a 
header file so user's could access the data directly. Alternativly, we
could make a yyuvars struct, which yypvars includes. Then put the
yyuvars struct in the header. However, this will yield 2 levels of
indirection in the yyparse function when attempting to access the user
visible areas. I prefer the set/get functions myself.

> 3. I don't think we should maintain the Cartesian product of all the
>    badly designed features, so I suggest that push => pure.  There are
>    a couple of place where the (m4) code could be simplified then.

Are you saying you don't want to see %push-parser option, but rather 
change %pure-parser to be the new "push parser"? If so, that would be 1
good reason for keeping yyparse () and adding a new function
yyparse_push. I would be happy to do this if you want.

> 4. Also, YYPARSE_PARAM is bad, does not scale well, etc.  Don't bother
>    with it except to maintain compatibility with the old mode.

OK, so just take those cases out?

> Attached is your diff, but this time with a "push.c" skeleton, leaving
> yacc.c as it was before.  That's easier to bench (alternatively I
> could have introduced a yacc.old.c, but that's clearer).

Thanks, I'll try this out.
Bob Rossi