[PATCH][C++] Save memory and reallocations in name-lookup

[PATCH][C++] Save memory and reallocations in name-lookup

[Richard Guenther]

This reduces the number of re-allocations and the amount of memory
wasted by store_binding.  Previously, on a cut-down testcase from
PR54146 we can see (--enable-gather-detailed-mem-stats -fmem-report
output):

cp/name-lookup.c:5874 (store_binding)              12033504: 1.6%    
8564032: 2.4%          0: 0.0%    2398752:12.9%      30134

that's the GC VEC (re-)allocation which wastes 2MB and re-allocates
30134 times.  After the patch we have

cp/name-lookup.c:5911 (store_bindings)              1243648: 0.2%     
352240: 0.1%          0: 0.0%     154064: 0.9%       9407
cp/name-lookup.c:5945 (store_class_bindings)        9643632: 1.3%     
120160: 0.0%          0: 0.0%     209376: 1.3%      10109

which means only 19516 reallocations and 350kb wasted memory.  The
compile-time effects are neutral (name-lookup is 1.0+-0.05s on
the reduced testcase) - a slightly different version which omitted
the temporary vector but walked things twice was consistently slower
(about 1.2s).  It seems we can end up with duplicates in the
names chain of store_bindings (not sure if that is intended).

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Ok if that passes?

Thanks,
Richard.

2012-08-17  Richard Guenther  <rguenther@suse.de>

	cp/
	* name-lookup.c (store_binding_p): New predicate, split out from ...
	(store_binding): ... here.  Always store binding and require
	target vector with enough space.
	(store_bindings): Collect to store bindings and reserve space
	for them, then store them.
	(store_class_bindings): Likewise.

Index: gcc/cp/name-lookup.c
===================================================================
*** gcc/cp/name-lookup.c	(revision 190471)
--- gcc/cp/name-lookup.c	(working copy)
*************** pushtag (tree name, tree type, tag_scope
*** 5855,5877 ****
     scope isn't enough, because more binding levels may be pushed.  */
  struct saved_scope *scope_chain;
  
! /* If ID has not already been marked, add an appropriate binding to
!    *OLD_BINDINGS.  */
  
  static void
  store_binding (tree id, VEC(cxx_saved_binding,gc) **old_bindings)
  {
    cxx_saved_binding *saved;
  
!   if (!id || !IDENTIFIER_BINDING (id))
!     return;
! 
!   if (IDENTIFIER_MARKED (id))
!     return;
  
    IDENTIFIER_MARKED (id) = 1;
  
!   saved = VEC_safe_push (cxx_saved_binding, gc, *old_bindings, NULL);
    saved->identifier = id;
    saved->binding = IDENTIFIER_BINDING (id);
    saved->real_type_value = REAL_IDENTIFIER_TYPE_VALUE (id);
--- 5855,5887 ----
     scope isn't enough, because more binding levels may be pushed.  */
  struct saved_scope *scope_chain;
  
! /* Return true if ID has not already been marked.  */
! 
! static inline bool
! store_binding_p (tree id)
! {
!   if (!id || !IDENTIFIER_BINDING (id))
!     return false;
! 
!   if (IDENTIFIER_MARKED (id))
!     return false;
! 
!   return true;
! }
! 
! /* Add an appropriate binding to *OLD_BINDINGS which needs to already
!    have enough space reserved.  */
  
  static void
  store_binding (tree id, VEC(cxx_saved_binding,gc) **old_bindings)
  {
    cxx_saved_binding *saved;
  
!   gcc_checking_assert (store_binding_p (id));
  
    IDENTIFIER_MARKED (id) = 1;
  
!   saved = VEC_quick_push (cxx_saved_binding, *old_bindings, NULL);
    saved->identifier = id;
    saved->binding = IDENTIFIER_BINDING (id);
    saved->real_type_value = REAL_IDENTIFIER_TYPE_VALUE (id);
*************** store_binding (tree id, VEC(cxx_saved_bi
*** 5881,5899 ****
  static void
  store_bindings (tree names, VEC(cxx_saved_binding,gc) **old_bindings)
  {
!   tree t;
  
    bool subtime = timevar_cond_start (TV_NAME_LOOKUP);
    for (t = names; t; t = TREE_CHAIN (t))
      {
-       tree id;
- 
        if (TREE_CODE (t) == TREE_LIST)
  	id = TREE_PURPOSE (t);
        else
  	id = DECL_NAME (t);
  
!       store_binding (id, old_bindings);
      }
    timevar_cond_stop (TV_NAME_LOOKUP, subtime);
  }
--- 5891,5922 ----
  static void
  store_bindings (tree names, VEC(cxx_saved_binding,gc) **old_bindings)
  {
!   static VEC(tree,heap) *bindings_need_stored = NULL;
!   tree t, id;
!   size_t i;
  
    bool subtime = timevar_cond_start (TV_NAME_LOOKUP);
    for (t = names; t; t = TREE_CHAIN (t))
      {
        if (TREE_CODE (t) == TREE_LIST)
  	id = TREE_PURPOSE (t);
        else
  	id = DECL_NAME (t);
  
!       if (store_binding_p (id))
! 	VEC_safe_push(tree, heap, bindings_need_stored, id);
!     }
!   if (!VEC_empty (tree, bindings_need_stored))
!     {
!       VEC_reserve_exact (cxx_saved_binding, gc, *old_bindings,
! 			 VEC_length (tree, bindings_need_stored));
!       for (i = 0; VEC_iterate(tree, bindings_need_stored, i, id); ++i)
! 	{
! 	  /* We can appearantly have duplicates in NAMES.  */
! 	  if (store_binding_p (id))
! 	    store_binding (id, old_bindings);
! 	}
!       VEC_truncate (tree, bindings_need_stored, 0);
      }
    timevar_cond_stop (TV_NAME_LOOKUP, subtime);
  }
*************** static void
*** 5905,5916 ****
  store_class_bindings (VEC(cp_class_binding,gc) *names,
  		      VEC(cxx_saved_binding,gc) **old_bindings)
  {
    size_t i;
    cp_class_binding *cb;
  
    bool subtime = timevar_cond_start (TV_NAME_LOOKUP);
    for (i = 0; VEC_iterate(cp_class_binding, names, i, cb); ++i)
!     store_binding (cb->identifier, old_bindings);
    timevar_cond_stop (TV_NAME_LOOKUP, subtime);
  }
  
--- 5928,5950 ----
  store_class_bindings (VEC(cp_class_binding,gc) *names,
  		      VEC(cxx_saved_binding,gc) **old_bindings)
  {
+   static VEC(tree,heap) *bindings_need_stored = NULL;
    size_t i;
    cp_class_binding *cb;
  
    bool subtime = timevar_cond_start (TV_NAME_LOOKUP);
    for (i = 0; VEC_iterate(cp_class_binding, names, i, cb); ++i)
!     if (store_binding_p (cb->identifier))
!       VEC_safe_push (tree, heap, bindings_need_stored, cb->identifier);
!   if (!VEC_empty (tree, bindings_need_stored))
!     {
!       tree id;
!       VEC_reserve_exact (cxx_saved_binding, gc, *old_bindings,
! 			 VEC_length (tree, bindings_need_stored));
!       for (i = 0; VEC_iterate(tree, bindings_need_stored, i, id); ++i)
! 	store_binding (id, old_bindings);
!       VEC_truncate (tree, bindings_need_stored, 0);
!     }
    timevar_cond_stop (TV_NAME_LOOKUP, subtime);
  }
  

Re: [PATCH][C++] Save memory and reallocations in name-lookup

[Gabriel Dos Reis]

On Fri, Aug 17, 2012 at 6:17 AM, Richard Guenther <rguenther@suse.de> wrote:
>
> This reduces the number of re-allocations and the amount of memory
> wasted by store_binding.  Previously, on a cut-down testcase from
> PR54146 we can see (--enable-gather-detailed-mem-stats -fmem-report
> output):
>
> cp/name-lookup.c:5874 (store_binding)              12033504: 1.6%
> 8564032: 2.4%          0: 0.0%    2398752:12.9%      30134
>
> that's the GC VEC (re-)allocation which wastes 2MB and re-allocates
> 30134 times.  After the patch we have
>
> cp/name-lookup.c:5911 (store_bindings)              1243648: 0.2%
> 352240: 0.1%          0: 0.0%     154064: 0.9%       9407
> cp/name-lookup.c:5945 (store_class_bindings)        9643632: 1.3%
> 120160: 0.0%          0: 0.0%     209376: 1.3%      10109

Nice saving.  As original author of the name lookup refactoring and improvement,
I am delighted to see we can do much better.

I am however concerned with:

>   static void
>   store_bindings (tree names, VEC(cxx_saved_binding,gc) **old_bindings)
>   {
> !   static VEC(tree,heap) *bindings_need_stored = NULL;

I would be more comfortable to see the cache be on per-scope
(e.g. namespace scope) basis as opposed
a blanket global cache stored in a global variable.

-- Gaby

Re: [PATCH][C++] Save memory and reallocations in name-lookup

[Gabriel Dos Reis]

On Fri, Aug 17, 2012 at 6:17 AM, Richard Guenther <rguenther@suse.de> wrote:

> which means only 19516 reallocations and 350kb wasted memory.  The
> compile-time effects are neutral (name-lookup is 1.0+-0.05s on
> the reduced testcase) - a slightly different version which omitted
> the temporary vector but walked things twice was consistently slower
> (about 1.2s).

Funny; I found something similar 10 years ago :-/

> It seems we can end up with duplicates in the
> names chain of store_bindings (not sure if that is intended).
>

the chain is supposed to implement a stack, not a set.

-- Gaby

Re: [PATCH][C++] Save memory and reallocations in name-lookup

[Richard Guenther]

On Fri, 17 Aug 2012, Gabriel Dos Reis wrote:

> On Fri, Aug 17, 2012 at 6:17 AM, Richard Guenther <rguenther@suse.de> wrote:
> >
> > This reduces the number of re-allocations and the amount of memory
> > wasted by store_binding.  Previously, on a cut-down testcase from
> > PR54146 we can see (--enable-gather-detailed-mem-stats -fmem-report
> > output):
> >
> > cp/name-lookup.c:5874 (store_binding)              12033504: 1.6%
> > 8564032: 2.4%          0: 0.0%    2398752:12.9%      30134
> >
> > that's the GC VEC (re-)allocation which wastes 2MB and re-allocates
> > 30134 times.  After the patch we have
> >
> > cp/name-lookup.c:5911 (store_bindings)              1243648: 0.2%
> > 352240: 0.1%          0: 0.0%     154064: 0.9%       9407
> > cp/name-lookup.c:5945 (store_class_bindings)        9643632: 1.3%
> > 120160: 0.0%          0: 0.0%     209376: 1.3%      10109
> 
> Nice saving.  As original author of the name lookup refactoring and improvement,
> I am delighted to see we can do much better.
> 
> I am however concerned with:
> 
> >   static void
> >   store_bindings (tree names, VEC(cxx_saved_binding,gc) **old_bindings)
> >   {
> > !   static VEC(tree,heap) *bindings_need_stored = NULL;
> 
> I would be more comfortable to see the cache be on per-scope
> (e.g. namespace scope) basis as opposed
> a blanket global cache stored in a global variable.

It's a "cache" only to not need a malloc/free for each store_bindings,
store_class_bindings invocation.  I've made it function local for
code cleaniness.  We're using this kind of trick elsewhere in the
compiler.

> > It seems we can end up with duplicates in the
> > names chain of store_bindings (not sure if that is intended).
>
> the chain is supposed to implement a stack, not a set.

Ah, I see.  That explains it.

Richard.

Re: [PATCH][C++] Save memory and reallocations in name-lookup

[Jakub Jelinek]

On Fri, Aug 17, 2012 at 06:41:37AM -0500, Gabriel Dos Reis wrote:
> I am however concerned with:
> 
> >   static void
> >   store_bindings (tree names, VEC(cxx_saved_binding,gc) **old_bindings)
> >   {
> > !   static VEC(tree,heap) *bindings_need_stored = NULL;
> 
> I would be more comfortable to see the cache be on per-scope
> (e.g. namespace scope) basis as opposed
> a blanket global cache stored in a global variable.

It is not any kind of cache.  It could be in theory an automatic variable
vector pointer, it is only used during that function.  The reason why it is
static variable instead is just to avoid constant allocation/deallocation
of the vector, this way after the first call it will be already allocated
(but, upon entry to store_bindings will always be empty).

	Jakub

Re: [PATCH][C++] Save memory and reallocations in name-lookup

[Gabriel Dos Reis]

On Fri, Aug 17, 2012 at 6:55 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Fri, Aug 17, 2012 at 06:41:37AM -0500, Gabriel Dos Reis wrote:
>> I am however concerned with:
>>
>> >   static void
>> >   store_bindings (tree names, VEC(cxx_saved_binding,gc) **old_bindings)
>> >   {
>> > !   static VEC(tree,heap) *bindings_need_stored = NULL;
>>
>> I would be more comfortable to see the cache be on per-scope
>> (e.g. namespace scope) basis as opposed
>> a blanket global cache stored in a global variable.
>
> It is not any kind of cache.  It could be in theory an automatic variable
> vector pointer, it is only used during that function.  The reason why it is
> static variable instead is just to avoid constant allocation/deallocation
> of the vector, this way after the first call it will be already allocated
> (but, upon entry to store_bindings will always be empty).

Ah, OK.  The patch is OK then.
Thanks,

-- Gaby

Re: [PATCH][C++] Save memory and reallocations in name-lookup

[Dimitrios Apostolou]

Hi,

On Fri, 17 Aug 2012, Jakub Jelinek wrote:
> On Fri, Aug 17, 2012 at 06:41:37AM -0500, Gabriel Dos Reis wrote:
>> I am however concerned with:
>>
>>>   static void
>>>   store_bindings (tree names, VEC(cxx_saved_binding,gc) **old_bindings)
>>>   {
>>> !   static VEC(tree,heap) *bindings_need_stored = NULL;
>>
>> I would be more comfortable to see the cache be on per-scope
>> (e.g. namespace scope) basis as opposed
>> a blanket global cache stored in a global variable.
>
> It is not any kind of cache.  It could be in theory an automatic variable
> vector pointer, it is only used during that function.  The reason why it is
> static variable instead is just to avoid constant allocation/deallocation
> of the vector, this way after the first call it will be already allocated
> (but, upon entry to store_bindings will always be empty).

Why not use stack vector of sufficient size for most cases then? I usually 
do something like:

       VEC (tree, stack) *bindings_need_stored = VEC_alloc (tree, stack, 32);
       ...
       VEC_free (tree, stack, bindings_need_stored);

if I've measured that 32 (or whatever) is enough for most cases. I 
don't have a clue about this case though.


Dimitris

Re: [PATCH][C++] Save memory and reallocations in name-lookup

[Richard Guenther]

On Sat, 18 Aug 2012, Dimitrios Apostolou wrote:

> Hi,
> 
> On Fri, 17 Aug 2012, Jakub Jelinek wrote:
> > On Fri, Aug 17, 2012 at 06:41:37AM -0500, Gabriel Dos Reis wrote:
> > > I am however concerned with:
> > > 
> > > >   static void
> > > >   store_bindings (tree names, VEC(cxx_saved_binding,gc) **old_bindings)
> > > >   {
> > > > !   static VEC(tree,heap) *bindings_need_stored = NULL;
> > > 
> > > I would be more comfortable to see the cache be on per-scope
> > > (e.g. namespace scope) basis as opposed
> > > a blanket global cache stored in a global variable.
> > 
> > It is not any kind of cache.  It could be in theory an automatic variable
> > vector pointer, it is only used during that function.  The reason why it is
> > static variable instead is just to avoid constant allocation/deallocation
> > of the vector, this way after the first call it will be already allocated
> > (but, upon entry to store_bindings will always be empty).
> 
> Why not use stack vector of sufficient size for most cases then? I usually do
> something like:
> 
>       VEC (tree, stack) *bindings_need_stored = VEC_alloc (tree, stack, 32);
>       ...
>       VEC_free (tree, stack, bindings_need_stored);
> 
> if I've measured that 32 (or whatever) is enough for most cases. I don't have
> a clue about this case though.

I considered that, but I'm not sure it would be an improvement.  We'd
have a re-allocation and free in some cases then.

Richard.