* marc.alff@stripped <marc.alff@stripped> [07/08/28 20:28]:
> ChangeSet@stripped, 2007-08-28 10:14:35-06:00, malff@weblab.(none) +3 -0
> Bug#30625 (Performance, reduce depth for expressions)
>
> This is a performance bug, affecting in particular the bison generated code
> for the parser.
>
> Prior to this fix, the grammar used a long chain of reduces to parse an
> expression, like:
> bit_expr -> bit_term
> bit_term -> bit_factor
> bit_factor -> value_expr
> value_expr -> term
> term -> factor
> etc
>
> This chain of reduces cause the internal state automaton in the generated
> parser to execute more state transitions and more reduces, so that the
> generated MySQLParse() function would spend a lot of time looping to execute
> all the grammar reductions.
>
> With this patch, the grammar has been reorganized so that rules are more
> "flat", limiting the depth of reduces needed to parse <expr>.
>
> Tests have been written to enforce that relative priorities and properties
> of operators have not changed while changing the grammar.
OK to push.
>
> For a test benchmark (1 Million INSERT of 100 values),
> the time spent inside MYSQLParse() according to gprof is:
>
> 5.0.48:
> 127.13 seconds
>
> 5.0.48 + fix for bug 30237:
> 97.10 seconds
>
> 5.0.48 + fix for bug 30237 + fix for this bug:
> 68.96 seconds
>
> yyparse() in 4.1.24:
> 48.48 seconds
Please replace the absolute numbers with a ratio.
> -factor:
> - factor '^' simple_expr { $$= new Item_func_bit_xor($1,$3); }
> - | simple_expr ;
> + bit_expr '|' bit_expr %prec '|'
> + { $$= new Item_func_bit_or($1,$3); }
> + | bit_expr '&' bit_expr %prec '&'
> + { $$= new Item_func_bit_and($1,$3); }
> + | bit_expr SHIFT_LEFT bit_expr %prec SHIFT_LEFT
> + { $$= new Item_func_shift_left($1,$3); }
> + | bit_expr SHIFT_RIGHT bit_expr %prec SHIFT_RIGHT
> + { $$= new Item_func_shift_right($1,$3); }
> + | bit_expr '+' bit_expr %prec '+'
> + { $$= new Item_func_plus($1,$3); }
> + | bit_expr '-' bit_expr %prec '-'
> + { $$= new Item_func_minus($1,$3); }
> + | bit_expr '+' interval_expr interval %prec '+'
> + { $$= new Item_date_add_interval($1,$3,$4,0); }
> + | bit_expr '-' interval_expr interval %prec '-'
> + { $$= new Item_date_add_interval($1,$3,$4,1); }
> + | bit_expr '*' bit_expr %prec '*'
> + { $$= new Item_func_mul($1,$3); }
> + | bit_expr '/' bit_expr %prec '/'
> + { $$= new Item_func_div($1,$3); }
> + | bit_expr '%' bit_expr %prec '%'
> + { $$= new Item_func_mod($1,$3); }
> + | bit_expr DIV_SYM bit_expr %prec DIV_SYM
> + { $$= new Item_func_int_div($1,$3); }
> + | bit_expr MOD_SYM bit_expr %prec MOD_SYM
> + { $$= new Item_func_mod($1,$3); }
> + | bit_expr '^' bit_expr
> + { $$= new Item_func_bit_xor($1,$3); }
> + | simple_expr
> + ;
>
Thank you for working on this.
--
-- Konstantin Osipov Software Developer, Moscow, Russia
-- MySQL AB, www.mysql.com The best DATABASE COMPANY in the GALAXY
