[PATCH] Reuse the saved_scope structures allocated by push_to_top_level

[PATCH] Reuse the saved_scope structures allocated by push_to_top_level

[Patrick Palka]

push_to_top_level gets called fairly frequently in template-heavy code
that performs a lot of instantiations, and we currently "leak" a lot of
GC memory when compiling such code since [push|pop]_to_top_level() do
not bother reusing or even freeing each saved_scope structure it
allocates.

This patch makes push_to_top_level() reuse the saved_scope structures it
allocates.  This is similar to how begin_scope() reuses the
cp_binding_level structures it allocates.

This patch reduces the maximum memory usage of the compiler by 4.5%,
from 525MB to 500MB, when compiling the Boost::Fusion test file
libs/fusion/test/compile_time/transform.cpp from the Boost 1.60 testsuite.

Bootstrapped and tested on x86_64-pc-linux-gnu, OK for
trunk or for GCC 7?

gcc/cp/ChangeLog:

	* name-lookup.c (free_saved_scope): New free list of saved_scope
	structures.
	(push_to_top_level): Attempt to reuse a saved_scope struct
	from free_saved_scope instead of allocating a new one each time.
	(pop_from_top_level_1): Chain the now-unused saved_scope structure
	onto free_saved_scope.
---
 gcc/cp/name-lookup.c | 25 ++++++++++++++++++++++++-
 1 file changed, 24 insertions(+), 1 deletion(-)

diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
index 89d84d7..3478b6a 100644
--- a/gcc/cp/name-lookup.c
+++ b/gcc/cp/name-lookup.c
@@ -6134,6 +6134,10 @@ store_class_bindings (vec<cp_class_binding, va_gc> *names,
   timevar_cond_stop (TV_NAME_LOOKUP, subtime);
 }
 
+/* A chain of saved_scope structures awaiting reuse.  */
+
+static GTY((deletable)) struct saved_scope *free_saved_scope;
+
 void
 push_to_top_level (void)
 {
@@ -6144,7 +6148,21 @@ push_to_top_level (void)
   bool need_pop;
 
   bool subtime = timevar_cond_start (TV_NAME_LOOKUP);
-  s = ggc_cleared_alloc<saved_scope> ();
+
+  /* Reuse or create a new structure for this saved scope.  */
+  if (free_saved_scope != NULL)
+    {
+      s = free_saved_scope;
+      free_saved_scope = s->prev;
+
+      vec<cxx_saved_binding, va_gc> *old_bindings = s->old_bindings;
+      memset (s, 0, sizeof (*s));
+      /* Also reuse the structure's old_bindings vector.  */
+      vec_safe_truncate (old_bindings, 0);
+      s->old_bindings = old_bindings;
+    }
+  else
+    s = ggc_cleared_alloc<saved_scope> ();
 
   b = scope_chain ? current_binding_level : 0;
 
@@ -6237,6 +6255,11 @@ pop_from_top_level_1 (void)
   current_function_decl = s->function_decl;
   cp_unevaluated_operand = s->unevaluated_operand;
   c_inhibit_evaluation_warnings = s->inhibit_evaluation_warnings;
+
+  /* Make this saved_scope structure available for reuse by
+     push_to_top_level.  */
+  s->prev = free_saved_scope;
+  free_saved_scope = s;
 }
 
 /* Wrapper for pop_from_top_level_1.  */
-- 
2.8.0.rc0.11.g9bfbc33

Re: [PATCH] Reuse the saved_scope structures allocated by push_to_top_level

[Markus Trippelsdorf]

On 2016.03.03 at 09:16 -0500, Patrick Palka wrote:
> push_to_top_level gets called fairly frequently in template-heavy code
> that performs a lot of instantiations, and we currently "leak" a lot of
> GC memory when compiling such code since [push|pop]_to_top_level() do
> not bother reusing or even freeing each saved_scope structure it
> allocates.
> 
> This patch makes push_to_top_level() reuse the saved_scope structures it
> allocates.  This is similar to how begin_scope() reuses the
> cp_binding_level structures it allocates.
> 
> This patch reduces the maximum memory usage of the compiler by 4.5%,
> from 525MB to 500MB, when compiling the Boost::Fusion test file
> libs/fusion/test/compile_time/transform.cpp from the Boost 1.60 testsuite.
> 
> Bootstrapped and tested on x86_64-pc-linux-gnu, OK for
> trunk or for GCC 7?

Great. push_to_top_level also shows up very high in profiles when
building Chromium for example. 

There is an old bug for this issue:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64500

-- 
Markus

Re: [PATCH] Reuse the saved_scope structures allocated by push_to_top_level

[Patrick Palka]

On Thu, Mar 3, 2016 at 9:22 AM, Markus Trippelsdorf
<markus@trippelsdorf.de> wrote:
> On 2016.03.03 at 09:16 -0500, Patrick Palka wrote:
>> push_to_top_level gets called fairly frequently in template-heavy code
>> that performs a lot of instantiations, and we currently "leak" a lot of
>> GC memory when compiling such code since [push|pop]_to_top_level() do
>> not bother reusing or even freeing each saved_scope structure it
>> allocates.
>>
>> This patch makes push_to_top_level() reuse the saved_scope structures it
>> allocates.  This is similar to how begin_scope() reuses the
>> cp_binding_level structures it allocates.
>>
>> This patch reduces the maximum memory usage of the compiler by 4.5%,
>> from 525MB to 500MB, when compiling the Boost::Fusion test file
>> libs/fusion/test/compile_time/transform.cpp from the Boost 1.60 testsuite.
>>
>> Bootstrapped and tested on x86_64-pc-linux-gnu, OK for
>> trunk or for GCC 7?
>
> Great. push_to_top_level also shows up very high in profiles when
> building Chromium for example.
>
> There is an old bug for this issue:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64500
>
> --
> Markus

I forgot what exactly I was benchmarking but I also saw
push_to_top_level high on the list which is what made me interested in
this function in the first place.

I think the slowness of this function is mostly due to the pointer
chasing performed in the function store_bindings, where we iterate
over all the names in each non-global scope to figure out whether to
preserve them.  It would probably improve performance if
cp_binding_level::names were a vector of trees instead of a linked
list of trees.

Re: [PATCH] Reuse the saved_scope structures allocated by push_to_top_level

[Manuel López-Ibáñez]

On 03/03/16 14:49, Patrick Palka wrote:
> I think the slowness of this function is mostly due to the pointer
> chasing performed in the function store_bindings, where we iterate
> over all the names in each non-global scope to figure out whether to
> preserve them.  It would probably improve performance if
> cp_binding_level::names were a vector of trees instead of a linked
> list of trees.

It would be an overall improvement if it was neither a TREE_LIST, nor a 
TREE_VECTOR: https://gcc.gnu.org/wiki/Speedup_areas#Trees

Those kinds of cleanups are always welcome even if they do not improve 
performance noticeably at first glance. The speed-up will show up once 
TREE_LIST is removed completely.

Cheers,

	Manuel.

Re: [PATCH] Reuse the saved_scope structures allocated by push_to_top_level

[Patrick Palka]

On Thu, Mar 3, 2016 at 10:22 AM, Manuel López-Ibáñez
<lopezibanez@gmail.com> wrote:
> On 03/03/16 14:49, Patrick Palka wrote:
>>
>> I think the slowness of this function is mostly due to the pointer
>> chasing performed in the function store_bindings, where we iterate
>> over all the names in each non-global scope to figure out whether to
>> preserve them.  It would probably improve performance if
>> cp_binding_level::names were a vector of trees instead of a linked
>> list of trees.
>
>
> It would be an overall improvement if it was neither a TREE_LIST, nor a
> TREE_VECTOR: https://gcc.gnu.org/wiki/Speedup_areas#Trees
>
> Those kinds of cleanups are always welcome even if they do not improve
> performance noticeably at first glance. The speed-up will show up once
> TREE_LIST is removed completely.

Ah yeah, I meant if cp_binding_level::names were a vec<tree, va_gc>
since it would have to be resizable.

>
> Cheers,
>
>         Manuel.
>
>

Re: [PATCH] Reuse the saved_scope structures allocated by push_to_top_level

[Manuel López-Ibáñez]

On 3 March 2016 at 15:39, Patrick Palka <patrick@parcs.ath.cx> wrote:
> On Thu, Mar 3, 2016 at 10:22 AM, Manuel López-Ibáñez
> <lopezibanez@gmail.com> wrote:
>> It would be an overall improvement if it was neither a TREE_LIST, nor a
>> TREE_VECTOR: https://gcc.gnu.org/wiki/Speedup_areas#Trees
>>
>> Those kinds of cleanups are always welcome even if they do not improve
>> performance noticeably at first glance. The speed-up will show up once
>> TREE_LIST is removed completely.
>
> Ah yeah, I meant if cp_binding_level::names were a vec<tree, va_gc>
> since it would have to be resizable.

Sure, what I meant is that such a change is an improvement even if you
cannot measure any speed-up at all right now. Go for it!

Cheers,

Manuel.

Re: [PATCH] Reuse the saved_scope structures allocated by push_to_top_level

[Patrick Palka]

On Thu, Mar 3, 2016 at 9:16 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> push_to_top_level gets called fairly frequently in template-heavy code
> that performs a lot of instantiations, and we currently "leak" a lot of
> GC memory when compiling such code since [push|pop]_to_top_level() do
> not bother reusing or even freeing each saved_scope structure it
> allocates.
>
> This patch makes push_to_top_level() reuse the saved_scope structures it
> allocates.  This is similar to how begin_scope() reuses the
> cp_binding_level structures it allocates.
>
> This patch reduces the maximum memory usage of the compiler by 4.5%,
> from 525MB to 500MB, when compiling the Boost::Fusion test file
> libs/fusion/test/compile_time/transform.cpp from the Boost 1.60 testsuite.
>
> Bootstrapped and tested on x86_64-pc-linux-gnu, OK for
> trunk or for GCC 7?
>
> gcc/cp/ChangeLog:
>
>         * name-lookup.c (free_saved_scope): New free list of saved_scope
>         structures.
>         (push_to_top_level): Attempt to reuse a saved_scope struct
>         from free_saved_scope instead of allocating a new one each time.
>         (pop_from_top_level_1): Chain the now-unused saved_scope structure
>         onto free_saved_scope.
> ---
>  gcc/cp/name-lookup.c | 25 ++++++++++++++++++++++++-
>  1 file changed, 24 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
> index 89d84d7..3478b6a 100644
> --- a/gcc/cp/name-lookup.c
> +++ b/gcc/cp/name-lookup.c
> @@ -6134,6 +6134,10 @@ store_class_bindings (vec<cp_class_binding, va_gc> *names,
>    timevar_cond_stop (TV_NAME_LOOKUP, subtime);
>  }
>
> +/* A chain of saved_scope structures awaiting reuse.  */
> +
> +static GTY((deletable)) struct saved_scope *free_saved_scope;
> +
>  void
>  push_to_top_level (void)
>  {
> @@ -6144,7 +6148,21 @@ push_to_top_level (void)
>    bool need_pop;
>
>    bool subtime = timevar_cond_start (TV_NAME_LOOKUP);
> -  s = ggc_cleared_alloc<saved_scope> ();
> +
> +  /* Reuse or create a new structure for this saved scope.  */
> +  if (free_saved_scope != NULL)
> +    {
> +      s = free_saved_scope;
> +      free_saved_scope = s->prev;
> +
> +      vec<cxx_saved_binding, va_gc> *old_bindings = s->old_bindings;
> +      memset (s, 0, sizeof (*s));
> +      /* Also reuse the structure's old_bindings vector.  */
> +      vec_safe_truncate (old_bindings, 0);
> +      s->old_bindings = old_bindings;
> +    }
> +  else
> +    s = ggc_cleared_alloc<saved_scope> ();
>
>    b = scope_chain ? current_binding_level : 0;
>
> @@ -6237,6 +6255,11 @@ pop_from_top_level_1 (void)
>    current_function_decl = s->function_decl;
>    cp_unevaluated_operand = s->unevaluated_operand;
>    c_inhibit_evaluation_warnings = s->inhibit_evaluation_warnings;
> +
> +  /* Make this saved_scope structure available for reuse by
> +     push_to_top_level.  */
> +  s->prev = free_saved_scope;
> +  free_saved_scope = s;
>  }
>
>  /* Wrapper for pop_from_top_level_1.  */
> --
> 2.8.0.rc0.11.g9bfbc33
>

Ping.

Re: [PATCH] Reuse the saved_scope structures allocated by push_to_top_level

[Jason Merrill]

OK.

Jason