This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[3.3] C++ PATCH: Reduce size of saved bindings.
- From: Gabriel Dos Reis <gdr at integrable-solutions dot net>
- To: gcc-patches at gcc dot gnu dot org
- Date: 04 Mar 2003 22:20:12 +0100
- Subject: [3.3] C++ PATCH: Reduce size of saved bindings.
- Organization: Integrable Solutions
Here is a preliminary small patch on name lookup performance issue
I'm working on. It is check on gcc-3_3-branch and will be checked
also on mainline.
It comes out as a separate patch because I wanted to make patches that
deal with one thing at a time.
When instantiating templates (either implicitly or explicitly), we
need to go forth and back between the sets of bindings we consider.
To do that, we build a stack which we push or pop depending on the
needs. See cp/decl.c:store_binding and cp/decl.c:maybe_push_to_top_level.
To remember a C++ binding, we need to manage four (4) pieces of
information:
1) The identifier for which we're remembering the binding.
2) A pointer to the binding.
3) The value value of the binding.
4) The real identifier type value.
All those are implemented as "tree"s. If we count the "link" we need
to chain the saved binding for an identifier into a stack, we get 5
pointers. On a 32bit machines, that means 20 bytes.
However, we "make_tree_vec(4)" to store the four pointers. That
means we're using 32 bytes (on a 32-bit machines) where 20 bytes
would be sufficient, so we waste 12 bytes per saved binding. That
wouldn't be a big deal if it weren't that we can allocate hundreds of
thousands of such TREE_VEC.
This patch makes us be less wasteful. It uses a straight datatype to
remember the bindings, reducing memory consuming. Some days, when we
have better adequate data structures to capture name lookup machinery,
we may not even need to allocate so much memory. Or we may now take
advantage of this "typeful" datatype and manage a dedicated
cxx_saved_binding allocator possibly with a free-list. To be explored
latter.
I ran the compiler on Qt-3.1.1. There were many cases where we make
hundreds of thousands of calls to "make_tree_vec(4)" for storing
bindings. To keep the list to a manageable size, I listed only those
files for which we make more than 300000 allocations -- these often
are the cases where name lookup is also showing high as time consumer.
propertyeditor.cpp 631228
command.cpp 576267
mainwindow.cpp 524105
mainwindowactions.cpp 448793
widgetfactory.cpp 426165
hierarchyview.cpp 416371
formwindow.cpp 393596
newformimpl.cpp 382449
resource.cpp 374049
actiondnd.cpp 369108
connectionitems.cpp 360047
designerappiface.cpp 339184
metadatabase.cpp 332631
workspace.cpp 323318
formfile.cpp 313450
layout.cpp 312155
project.cpp 308566
tableeditorimpl.cpp 307490
connectiondialog.cpp 304040
The patch below is against gcc-3_3-branch. Bootstrapped and tested
with no regression.
The next logical patch (to be sent latter) will:
1) do stack allocation where possible, so as to minimize
head-allocation;
2) catch a bug as a side effect of using a more "typeful" datatype
to reprent bindings.
-- Gaby
2003-03-04 Gabriel Dos Reis <gdr at integrable-solutions dot net>
* cp-tree.h (cxx_saved_binding): Declare.
(struct saved_scope): Adjust type of field 'old_binding'.
* decl.c (cxx_saved_binding_make): New macro.
(struct cxx_saved_binding): Define.
(store_bindings): Adjust prototype. Use cxx_saved_binding to save
C++ bindings.
(maybe_push_to_top_level): Adjust local variable type.
(pop_from_top_level): Likewise.
Index: cp-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/cp-tree.h,v
retrieving revision 1.776.2.7
diff -p -r1.776.2.7 cp-tree.h
*** cp-tree.h 3 Mar 2003 21:58:23 -0000 1.776.2.7
--- cp-tree.h 4 Mar 2003 21:04:52 -0000
*************** struct diagnostic_context;
*** 221,226 ****
--- 221,230 ----
(flag_abi_version == 0 || flag_abi_version >= (N))
+ /* Datatype used to temporarily save C++ bindings (for implicit
+ instantiations purposes and like). Implemented in decl.c. */
+ typedef struct cxx_saved_binding cxx_saved_binding;
+
/* Language-dependent contents of an identifier. */
struct lang_identifier GTY(())
*************** extern GTY(()) tree cp_global_trees[CPTI
*** 752,758 ****
struct saved_scope GTY(())
{
! tree old_bindings;
tree old_namespace;
tree decl_ns_list;
tree class_name;
--- 756,762 ----
struct saved_scope GTY(())
{
! cxx_saved_binding *old_bindings;
tree old_namespace;
tree decl_ns_list;
tree class_name;
Index: decl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/decl.c,v
retrieving revision 1.965.2.22
diff -p -r1.965.2.22 decl.c
*** decl.c 4 Mar 2003 01:12:55 -0000 1.965.2.22
--- decl.c 4 Mar 2003 21:04:52 -0000
*************** static void storedecls PARAMS ((tree));
*** 66,72 ****
static void require_complete_types_for_parms PARAMS ((tree));
static int ambi_op_p PARAMS ((enum tree_code));
static int unary_op_p PARAMS ((enum tree_code));
! static tree store_bindings PARAMS ((tree, tree));
static tree lookup_tag_reverse PARAMS ((tree, tree));
static tree lookup_name_real PARAMS ((tree, int, int, int));
static void push_local_name PARAMS ((tree));
--- 66,72 ----
static void require_complete_types_for_parms PARAMS ((tree));
static int ambi_op_p PARAMS ((enum tree_code));
static int unary_op_p PARAMS ((enum tree_code));
! static cxx_saved_binding *store_bindings (tree, cxx_saved_binding *);
static tree lookup_tag_reverse PARAMS ((tree, tree));
static tree lookup_name_real PARAMS ((tree, int, int, int));
static void push_local_name PARAMS ((tree));
*************** pop_nested_namespace (ns)
*** 2337,2342 ****
--- 2337,2358 ----
}
+ /* Allocate storage for saving a C++ binding. */
+ #define cxx_saved_binding_make() \
+ (ggc_alloc (sizeof (cxx_saved_binding)))
+
+ struct cxx_saved_binding GTY(())
+ {
+ /* Link that chains saved C++ bindings for a given name into a stack. */
+ cxx_saved_binding *previous;
+ /* The name of the current binding. */
+ tree identifier;
+ /* The binding we're saving. */
+ tree binding;
+ tree class_value;
+ tree real_type_value;
+ };
+
/* Subroutines for reverting temporarily to top-level for instantiation
of templates and such. We actually need to clear out the class- and
local-value slots of all identifiers, so that only the global values
*************** pop_nested_namespace (ns)
*** 2344,2360 ****
scope isn't enough, because more binding levels may be pushed. */
struct saved_scope *scope_chain;
! static tree
! store_bindings (names, old_bindings)
! tree names, old_bindings;
{
tree t;
! tree search_bindings = old_bindings;
timevar_push (TV_NAME_LOOKUP);
for (t = names; t; t = TREE_CHAIN (t))
{
! tree binding, t1, id;
if (TREE_CODE (t) == TREE_LIST)
id = TREE_PURPOSE (t);
--- 2360,2377 ----
scope isn't enough, because more binding levels may be pushed. */
struct saved_scope *scope_chain;
! static cxx_saved_binding *
! store_bindings (tree names, cxx_saved_binding *old_bindings)
{
tree t;
! cxx_saved_binding *search_bindings = old_bindings;
timevar_push (TV_NAME_LOOKUP);
for (t = names; t; t = TREE_CHAIN (t))
{
! tree id;
! cxx_saved_binding *saved;
! cxx_saved_binding *t1;
if (TREE_CODE (t) == TREE_LIST)
id = TREE_PURPOSE (t);
*************** store_bindings (names, old_bindings)
*** 2368,2387 ****
|| !(IDENTIFIER_BINDING (id) || IDENTIFIER_CLASS_VALUE (id)))
continue;
! for (t1 = search_bindings; t1; t1 = TREE_CHAIN (t1))
! if (TREE_VEC_ELT (t1, 0) == id)
goto skip_it;
my_friendly_assert (TREE_CODE (id) == IDENTIFIER_NODE, 135);
! binding = make_tree_vec (4);
! TREE_VEC_ELT (binding, 0) = id;
! TREE_VEC_ELT (binding, 1) = REAL_IDENTIFIER_TYPE_VALUE (id);
! TREE_VEC_ELT (binding, 2) = IDENTIFIER_BINDING (id);
! TREE_VEC_ELT (binding, 3) = IDENTIFIER_CLASS_VALUE (id);
IDENTIFIER_BINDING (id) = NULL_TREE;
IDENTIFIER_CLASS_VALUE (id) = NULL_TREE;
! TREE_CHAIN (binding) = old_bindings;
! old_bindings = binding;
skip_it:
;
}
--- 2385,2404 ----
|| !(IDENTIFIER_BINDING (id) || IDENTIFIER_CLASS_VALUE (id)))
continue;
! for (t1 = search_bindings; t1; t1 = t1->previous)
! if (t1->identifier == id)
goto skip_it;
my_friendly_assert (TREE_CODE (id) == IDENTIFIER_NODE, 135);
! saved = cxx_saved_binding_make ();
! saved->previous = old_bindings;
! saved->identifier = id;
! saved->binding = IDENTIFIER_BINDING (id);
! saved->class_value = IDENTIFIER_CLASS_VALUE (id);;
! saved->real_type_value = REAL_IDENTIFIER_TYPE_VALUE (id);
IDENTIFIER_BINDING (id) = NULL_TREE;
IDENTIFIER_CLASS_VALUE (id) = NULL_TREE;
! old_bindings = saved;
skip_it:
;
}
*************** maybe_push_to_top_level (pseudo)
*** 2394,2400 ****
{
struct saved_scope *s;
struct cp_binding_level *b;
! tree old_bindings;
int need_pop;
timevar_push (TV_NAME_LOOKUP);
--- 2411,2417 ----
{
struct saved_scope *s;
struct cp_binding_level *b;
! cxx_saved_binding *old_bindings;
int need_pop;
timevar_push (TV_NAME_LOOKUP);
*************** maybe_push_to_top_level (pseudo)
*** 2412,2418 ****
else
need_pop = 0;
! old_bindings = NULL_TREE;
if (scope_chain && previous_class_type)
old_bindings = store_bindings (previous_class_values, old_bindings);
--- 2429,2435 ----
else
need_pop = 0;
! old_bindings = NULL;
if (scope_chain && previous_class_type)
old_bindings = store_bindings (previous_class_values, old_bindings);
*************** void
*** 2464,2470 ****
pop_from_top_level ()
{
struct saved_scope *s = scope_chain;
! tree t;
timevar_push (TV_NAME_LOOKUP);
--- 2481,2487 ----
pop_from_top_level ()
{
struct saved_scope *s = scope_chain;
! cxx_saved_binding *saved;
timevar_push (TV_NAME_LOOKUP);
*************** pop_from_top_level ()
*** 2475,2487 ****
current_lang_base = 0;
scope_chain = s->prev;
! for (t = s->old_bindings; t; t = TREE_CHAIN (t))
{
! tree id = TREE_VEC_ELT (t, 0);
! SET_IDENTIFIER_TYPE_VALUE (id, TREE_VEC_ELT (t, 1));
! IDENTIFIER_BINDING (id) = TREE_VEC_ELT (t, 2);
! IDENTIFIER_CLASS_VALUE (id) = TREE_VEC_ELT (t, 3);
}
/* If we were in the middle of compiling a function, restore our
--- 2492,2504 ----
current_lang_base = 0;
scope_chain = s->prev;
! for (saved = s->old_bindings; saved; saved = saved->previous)
{
! tree id = saved->identifier;
! IDENTIFIER_BINDING (id) = saved->binding;
! IDENTIFIER_CLASS_VALUE (id) = saved->class_value;
! SET_IDENTIFIER_TYPE_VALUE (id, saved->real_type_value);
}
/* If we were in the middle of compiling a function, restore our