This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[C++ PATCH] Remove quadratic behaviour from leave_scope
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 6 Dec 2004 08:52:52 -0700 (MST)
- Subject: [C++ PATCH] Remove quadratic behaviour from leave_scope
This is an example of my not seeing the problem due to the regression!
The bugzilla PR middle-end/12454 is a 4.0 regression due to compilation
of g++.dg/parse/stack1.C blowing up the stack on Darwin. The testcase
looks like:
void foo()
{
if (0) {}
else if (0) {}
else if (0) {}
...
}
whilst working on actually fixing the stack usage regression, I was
suprised/shocked at the compile-time statistics (also commented on
in the PR). The following numbers are on a 3GHz Xeon.
Execution times (seconds)
garbage collection : 0.01 ( 0%) usr 0.00 ( 0%) sys 0.01 ( 0%) wall
callgraph construction: 0.01 ( 0%) usr 0.00 ( 0%) sys 0.00 ( 0%) wall
CFG verifier : 0.00 ( 0%) usr 0.00 ( 0%) sys 0.01 ( 0%) wall
preprocessing : 0.05 ( 0%) usr 0.01 (12%) sys 0.06 ( 0%) wall
parser : 0.19 ( 1%) usr 0.04 (50%) sys 0.34 ( 2%) wall
name lookup : 18.44 (98%) usr 0.03 (37%) sys 18.37 (98%) wall
tree gimplify : 0.01 ( 0%) usr 0.00 ( 0%) sys 0.01 ( 0%) wall
TOTAL : 18.73 0.08 18.81
How does a subroutine without any identifiers manage to spend 98% of its
time in name lookup!?
It turns out that the problem is an O(n) loop in leave_scope, which
is called O(n) times, where everytime we leave a scope, we scan backwards
through the entire scope stack looking for the last "class" scope. The
simple realization is that the only time that we actually need to update
the class_binding_level variable (which holds the last class scope on
the stack), is only when we leave a "class" scope.
This simple tweak leads to a dramatic ~180x speed-up on this testcase,
but should provide at least some minor speed-up on any C++ code.
Execution times (seconds)
garbage collection : 0.01 (10%) usr 0.00 ( 0%) sys 0.01 ( 4%) wall
preprocessing : 0.00 ( 0%) usr 0.05 (38%) sys 0.04 (17%) wall
parser : 0.05 (50%) usr 0.07 (54%) sys 0.14 (61%) wall
name lookup : 0.02 (20%) usr 0.00 ( 0%) sys 0.01 ( 4%) wall
tree gimplify : 0.00 ( 0%) usr 0.01 ( 8%) sys 0.02 ( 9%) wall
dominator optimization: 0.01 (10%) usr 0.00 ( 0%) sys 0.00 ( 0%) wall
TOTAL : 0.10 0.13 0.23
The following patch has been tested on i686-pc-linux-gnu with a full
"make bootstrap", all default languages, and regression tested with a
top-level "make -k check" with no new failures. This doesn't resolve
PR 12454, but we should now blow-up the stack much faster!
Ok for mainline?
2004-12-06 Roger Sayle <roger@eyesopen.com>
* name-lookup.c (leave_scope): We only need to update
class_binding_level when leaving a class scope.
Index: name-lookup.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/name-lookup.c,v
retrieving revision 1.99
diff -c -3 -p -r1.99 name-lookup.c
*** name-lookup.c 1 Dec 2004 19:44:48 -0000 1.99
--- name-lookup.c 6 Dec 2004 06:30:04 -0000
*************** leave_scope (void)
*** 1329,1339 ****
/* Find the innermost enclosing class scope, and reset
CLASS_BINDING_LEVEL appropriately. */
! for (scope = current_binding_level;
! scope && scope->kind != sk_class;
! scope = scope->level_chain)
! ;
! class_binding_level = scope && scope->kind == sk_class ? scope : NULL;
return current_binding_level;
}
--- 1329,1344 ----
/* Find the innermost enclosing class scope, and reset
CLASS_BINDING_LEVEL appropriately. */
! if (scope->kind == sk_class)
! {
! class_binding_level = NULL;
! for (scope = current_binding_level; scope; scope = scope->level_chain)
! if (scope->kind == sk_class)
! {
! class_binding_level = scope;
! break;
! }
! }
return current_binding_level;
}
Roger
--
Roger Sayle, E-mail: roger@eyesopen.com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833