[Bug c++/17596] New: expression parser is too slow, should be rewritten

[Bug c++/17596] New: expression parser is too slow, should be rewritten

[giovannibajo at libero dot it]

The expression parser is currently too slow due to its recursive nature. It 
could be speed up by rewriting it so that it manually tracks precedences.

Bug 14179 is an example of a machine-generated testcase which exposes our 
limits. I proposed a hack to help the testcase in that bug:
http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01839.html

but the patch was rejected. Mark said:
"""
I would like to hold off on this patch. Like Nathan says, this is the first 
good evidence I've seen that implementing operator-precedence parsing might be 
a measureable win on real code. If you, or Nathan, or I, or Zack, or somebody 
gets to implementing that, then that's probably the best way to go. If not, 
then we should consider your patch, as it really does make a big difference. 
Would you mind reminding me about this patch when we get ready to make the 
release branch, assuming we've not yet implemented the operator-precedence 
thing?
"""
http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01960.html


This bug was opened to track this.

-- 
           Summary: expression parser is too slow, should be rewritten
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P2
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: giovannibajo at libero dot it
                CC: gcc-bugs at gcc dot gnu dot org
OtherBugsDependingO 14179
             nThis:


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[giovannibajo at libero dot it]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|expression parser is too    |[3.4/4.0 Regression]
                   |slow, should be rewritten   |expression parser is too
                   |                            |slow, should be rewritten
   Target Milestone|---                         |4.0.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-09-22 00:46 -------
Confirmed

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-09-22 00:46:17
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-09-22 23:53 -------
[moving discussion from PR 14179 here, since this is the PR about the new 
expression parser].

Paolo, I did not read your email yet because I am not home. Your patch looks ok 
to me and Mark already approved it; the only quirk are those gotos that totally 
mess up the flow of the code. I wouldn't mind getting rid of them.

If you can do compile-time measures of your patch it would be ok, otherwise I 
will in the next few days.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bonzini at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[bonzini at gnu dot org]

------- Additional Comments From bonzini at gnu dot org  2004-09-23 07:49 -------
I have a patch which is in the PR14179.  While the concept was approved, it has
regressions. :-(

At a first glance, it seems that the stage1 compiler does not have them. 
Unfortunately I was low on disk space so for various reasons it is pretty well
possible that I horked something in my build directory.  Since the Java
testsuite was fine, I am restarting a C++-only bootstrap that should not have
any diskspace problems.

I hope to have this finished in a few hours and to have operator-precedence
committed.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[bonzini at gnu dot org]

------- Additional Comments From bonzini at gnu dot org  2004-09-23 08:04 -------
> the only quirk are those gotos that totally 
> mess up the flow of the code. I wouldn't mind
> getting rid of them.

Note that the final patch has fewer gotos than the one I had sent you -- only
those strictly necessary to simulate recursion, which is in turn a pretty well
formalized transformation.  I could have some very small duplication of code to
remove the gotos, but I am not really sure the flow of the code would be much
easier to understand, or rather on the contrary.

Paolo

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[bonzini at gnu dot org]

------- Additional Comments From bonzini at gnu dot org  2004-09-23 08:09 -------
Can anybody please assign this to me?

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-09-23 11:29 -------
Done. Notice that you have edit priviliges in Bugzilla if you use your 
bonzini@gcc.gnu.org login.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |bonzini at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2004-09-23 11:58 -------
Subject: Bug 17596

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	bonzini@gcc.gnu.org	2004-09-23 11:58:20

Modified files:
	gcc/cp         : parser.c ChangeLog 

Log message:
	2004-09-23  Paolo Bonzini  <bonzini@gnu.org>
	
	PR c++/17596
	
	* parser.c (cp_parser_token_tree_map_node,
	cp_parser_pm_expression, cp_parser_additive_expression,
	cp_parser_multiplicative_expression, cp_parser_shift_expression,
	cp_parser_relational_expression, cp_parser_equality_expression,
	cp_parser_and_expression, cp_parser_exclusive_or_expression,
	cp_parser_inclusive_or_expression,
	cp_parser_logical_and_expression,
	cp_parser_logical_or_expression): Removed.
	(enum cp_parser_prec, struct cp_parser_token_tree_map_node,
	binops, binops_by_token): New.
	(cp_parser_assignment_expression): Use cp_parser_binary_expression.
	(cp_parser_new): Initialize binops_by_token.
	(cp_parser_binary_expression): Rewritten.
	(N_CP_TTYPES): New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cp/parser.c.diff?cvsroot=gcc&r1=1.252&r2=1.253
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cp/ChangeLog.diff?cvsroot=gcc&r1=1.4379&r2=1.4380



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-09-23 12:20 -------
Many many thanks Paolo!

Let's keep this open until we get more numbers about the comparison of this 
with my quick hack to speed cp_parser_initializer which is on the 3.4 branch:

http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01839.html


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[paolo dot bonzini at polimi dot it]

------- Additional Comments From paolo dot bonzini at polimi dot it  2004-09-23 12:24 -------
Subject: Re:  [3.4/4.0 Regression] expression parser is too
 slow, should be rewritten

> Let's keep this open until we get more numbers about the comparison of this 
> with my quick hack to speed cp_parser_initializer which is on the 3.4 branch:

Yes, I think that a simplified version of the hack may still help.

Paolo



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596

[Bug c++/17596] [3.4/4.0 Regression] expression parser is too slow, should be rewritten

[bonzini at gcc dot gnu dot org]

------- Additional Comments From bonzini at gcc dot gnu dot org  2004-09-24 16:02 -------
Great news.  We now outperform 3.3.4 by 25% for a reduced PR14179 testcase (with
an array of 240000 elements).

I'm closing this bug and PR14179.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17596