Patchwork [6/9] Add --param tunables for the initial size of the type merging hash tables

login
register
mail settings
Submitter Andi Kleen
Date April 19, 2013, 9:31 p.m.
Message ID <1366407117-18462-7-git-send-email-andi@firstfloor.org>
Download mbox | patch
Permalink /patch/238119/
State New
Headers show

Comments

Andi Kleen - April 19, 2013, 9:31 p.m.
From: Andi Kleen <ak@linux.intel.com>

WPA can spend a lot of time just resizing the type merging hash tables.
This adds experimental --params to size them large initially. On my large
LTO build I get a 1.1% improvement in build time from presizing the hash
tables to a large enough value.

Later on I think it's better to either always use large hash tables
(virtual memory is cheap) or to dynamically size them based on a
estimate of the available types. But as a first step having
these --params is useful to play around with it.

gcc/:

2013-04-19  Andi Kleen  <ak@linux.intel.com>

	* gimple.c (gimple_canonical_type_hash): Use param to size hash table.
	(gimple_register_canonical_type): dito.
	* lto/lto.c (read_cgraph_and_symbols): dito.
	* params.def (PARAM_TYPE_CACHE_HASH_SIZE, PARAM_CANONICAL_TYPE_HASH_SIZE,
 	PARAM_CANONICAL_TYPE_CACHE_HASH_SIZE, PARAM_GIMPLE_TYPE_HASH_SIZE): Add.
---
 gcc/gimple.c   |  9 ++++++---
 gcc/lto/lto.c  |  7 +++++--
 gcc/params.def | 20 ++++++++++++++++++++
 3 files changed, 31 insertions(+), 5 deletions(-)
Richard Guenther - April 22, 2013, 11:49 a.m.
On Fri, Apr 19, 2013 at 11:31 PM, Andi Kleen <andi@firstfloor.org> wrote:
> From: Andi Kleen <ak@linux.intel.com>
>
> WPA can spend a lot of time just resizing the type merging hash tables.
> This adds experimental --params to size them large initially. On my large
> LTO build I get a 1.1% improvement in build time from presizing the hash
> tables to a large enough value.

With what values?  Certainly we will have at least as many hashes
as types, so increasing the hash cache sizes to the size of the types
(thus use the same --param) would be obvious.  Likewise there will
be less canonical types than regular types.

Richard.

> Later on I think it's better to either always use large hash tables
> (virtual memory is cheap) or to dynamically size them based on a
> estimate of the available types. But as a first step having
> these --params is useful to play around with it.
>
> gcc/:
>
> 2013-04-19  Andi Kleen  <ak@linux.intel.com>
>
>         * gimple.c (gimple_canonical_type_hash): Use param to size hash table.
>         (gimple_register_canonical_type): dito.
>         * lto/lto.c (read_cgraph_and_symbols): dito.
>         * params.def (PARAM_TYPE_CACHE_HASH_SIZE, PARAM_CANONICAL_TYPE_HASH_SIZE,
>         PARAM_CANONICAL_TYPE_CACHE_HASH_SIZE, PARAM_GIMPLE_TYPE_HASH_SIZE): Add.
> ---
>  gcc/gimple.c   |  9 ++++++---
>  gcc/lto/lto.c  |  7 +++++--
>  gcc/params.def | 20 ++++++++++++++++++++
>  3 files changed, 31 insertions(+), 5 deletions(-)
>
> diff --git a/gcc/gimple.c b/gcc/gimple.c
> index 64f7b1a..2777816 100644
> --- a/gcc/gimple.c
> +++ b/gcc/gimple.c
> @@ -36,6 +36,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "alias.h"
>  #include "demangle.h"
>  #include "langhooks.h"
> +#include "params.h"
>
>  /* Global canonical type table.  */
>  static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node)))
> @@ -3173,8 +3174,9 @@ static hashval_t
>  gimple_canonical_type_hash (const void *p)
>  {
>    if (canonical_type_hash_cache == NULL)
> -    canonical_type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
> -                                                tree_int_map_eq, NULL);
> +      canonical_type_hash_cache = htab_create_ggc (PARAM_VALUE (PARAM_CANONICAL_TYPE_CACHE_HASH_SIZE),
> +                                                  tree_int_map_hash,
> +                                                  tree_int_map_eq, NULL);
>
>    return iterative_hash_canonical_type (CONST_CAST_TREE ((const_tree) p), 0);
>  }
> @@ -3429,7 +3431,8 @@ gimple_register_canonical_type (tree t)
>      return TYPE_CANONICAL (t);
>
>    if (gimple_canonical_types == NULL)
> -    gimple_canonical_types = htab_create_ggc (16381, gimple_canonical_type_hash,
> +    gimple_canonical_types = htab_create_ggc (PARAM_VALUE (PARAM_CANONICAL_TYPE_HASH_SIZE),
> +                                             gimple_canonical_type_hash,
>                                               gimple_canonical_type_eq, 0);
>
>    slot = htab_find_slot (gimple_canonical_types, t, INSERT);
> diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c
> index d757be0..4aaf2dc 100644
> --- a/gcc/lto/lto.c
> +++ b/gcc/lto/lto.c
> @@ -38,6 +38,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "ipa-prop.h"
>  #include "common.h"
>  #include "debug.h"
> +#include "params.h"
>  #include "gimple.h"
>  #include "lto.h"
>  #include "lto-tree.h"
> @@ -2947,12 +2948,14 @@ read_cgraph_and_symbols (unsigned nfiles, const char **fnames)
>
>    tree_with_vars = htab_create_ggc (101, htab_hash_pointer, htab_eq_pointer,
>                                     NULL);
> -  type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
> +  type_hash_cache = htab_create_ggc (PARAM_VALUE (PARAM_TYPE_CACHE_HASH_SIZE),
> +                                    tree_int_map_hash,
>                                      tree_int_map_eq, NULL);
>    type_pair_cache = XCNEWVEC (struct type_pair_d, GIMPLE_TYPE_PAIR_SIZE);
>    gimple_type_leader = ggc_alloc_cleared_vec_gimple_type_leader_entry_s
>                         (GIMPLE_TYPE_LEADER_SIZE);
> -  gimple_types = htab_create_ggc (16381, gimple_type_hash, gimple_type_eq, 0);
> +  gimple_types = htab_create_ggc (PARAM_VALUE (PARAM_GIMPLE_TYPE_HASH_SIZE),
> +                                 gimple_type_hash, gimple_type_eq, 0);
>
>    if (!quiet_flag)
>      fprintf (stderr, "Reading object files:");
> diff --git a/gcc/params.def b/gcc/params.def
> index 3c52651..46843df 100644
> --- a/gcc/params.def
> +++ b/gcc/params.def
> @@ -1020,6 +1020,26 @@ DEFPARAM (PARAM_MAX_SLSR_CANDIDATE_SCAN,
>           "strength reduction",
>           50, 1, 999999)
>
> +DEFPARAM (PARAM_TYPE_CACHE_HASH_SIZE,
> +       "type-cache-hash-size",
> +       "Initial size of the gimple type cache hash table",
> +       512, 512, 0)
> +
> +DEFPARAM (PARAM_CANONICAL_TYPE_HASH_SIZE,
> +       "canonical-type-hash-size",
> +       "Initial size of the gimple canonical type hash table",
> +       16381, 16381, 0)
> +
> +DEFPARAM (PARAM_CANONICAL_TYPE_CACHE_HASH_SIZE,
> +       "canonical-type-cache-hash-size",
> +       "Initial size of the gimple canonical type cache hash table",
> +       512, 512, 0)
> +
> +DEFPARAM (PARAM_GIMPLE_TYPE_HASH_SIZE,
> +       "type-hash-size",
> +       "Initial size of the gimple type hash table",
> +       16381, 16381, 0)
> +
>  /*
>  Local variables:
>  mode:c
> --
> 1.8.1.4
>
Andi Kleen - April 22, 2013, 3:44 p.m.
On Mon, Apr 22, 2013 at 01:49:39PM +0200, Richard Biener wrote:
> On Fri, Apr 19, 2013 at 11:31 PM, Andi Kleen <andi@firstfloor.org> wrote:
> > From: Andi Kleen <ak@linux.intel.com>
> >
> > WPA can spend a lot of time just resizing the type merging hash tables.
> > This adds experimental --params to size them large initially. On my large
> > LTO build I get a 1.1% improvement in build time from presizing the hash
> > tables to a large enough value.
> 
> With what values?  Certainly we will have at least as many hashes

For the test I used just the final values from -flto-report from a previous
run.  I know it's cheating. But it's reasonable to just always use a 
large table, unless someone comes up with a nice way to pre estimate.

> as types, so increasing the hash cache sizes to the size of the types
> (thus use the same --param) would be obvious.  Likewise there will

iirc the caches were usually smaller than the types from lto-report. Perhaps
they have less collisions.

-Andi
Geert Bosch - April 22, 2013, 4:24 p.m.
On Apr 19, 2013, at 17:31, Andi Kleen <andi@firstfloor.org> wrote:
> Later on I think it's better to either always use large hash tables
> (virtual memory is cheap) or to dynamically size them based on a
> estimate of the available types. 

That logic doesn't really work for hash tables. Assuming the hash keys
as close to random (as they should be), there is no locality of reference,
so most/all of the hash table will be part of the working set: hash tables
don't just use virtual memory, they use real memory.

A very sparsely populated hash table may end up wasting most of each VM page
to just store a few hashed values. Bad for locality, and bad for performance.

  -Geert

Patch

diff --git a/gcc/gimple.c b/gcc/gimple.c
index 64f7b1a..2777816 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -36,6 +36,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "alias.h"
 #include "demangle.h"
 #include "langhooks.h"
+#include "params.h"
 
 /* Global canonical type table.  */
 static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node)))
@@ -3173,8 +3174,9 @@  static hashval_t
 gimple_canonical_type_hash (const void *p)
 {
   if (canonical_type_hash_cache == NULL)
-    canonical_type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
-						 tree_int_map_eq, NULL);
+      canonical_type_hash_cache = htab_create_ggc (PARAM_VALUE (PARAM_CANONICAL_TYPE_CACHE_HASH_SIZE),
+						   tree_int_map_hash,
+						   tree_int_map_eq, NULL);
 
   return iterative_hash_canonical_type (CONST_CAST_TREE ((const_tree) p), 0);
 }
@@ -3429,7 +3431,8 @@  gimple_register_canonical_type (tree t)
     return TYPE_CANONICAL (t);
 
   if (gimple_canonical_types == NULL)
-    gimple_canonical_types = htab_create_ggc (16381, gimple_canonical_type_hash,
+    gimple_canonical_types = htab_create_ggc (PARAM_VALUE (PARAM_CANONICAL_TYPE_HASH_SIZE),
+					      gimple_canonical_type_hash,
 					      gimple_canonical_type_eq, 0);
 
   slot = htab_find_slot (gimple_canonical_types, t, INSERT);
diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c
index d757be0..4aaf2dc 100644
--- a/gcc/lto/lto.c
+++ b/gcc/lto/lto.c
@@ -38,6 +38,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "ipa-prop.h"
 #include "common.h"
 #include "debug.h"
+#include "params.h"
 #include "gimple.h"
 #include "lto.h"
 #include "lto-tree.h"
@@ -2947,12 +2948,14 @@  read_cgraph_and_symbols (unsigned nfiles, const char **fnames)
 
   tree_with_vars = htab_create_ggc (101, htab_hash_pointer, htab_eq_pointer,
 				    NULL);
-  type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
+  type_hash_cache = htab_create_ggc (PARAM_VALUE (PARAM_TYPE_CACHE_HASH_SIZE),
+				     tree_int_map_hash,
 				     tree_int_map_eq, NULL);
   type_pair_cache = XCNEWVEC (struct type_pair_d, GIMPLE_TYPE_PAIR_SIZE);
   gimple_type_leader = ggc_alloc_cleared_vec_gimple_type_leader_entry_s
 		        (GIMPLE_TYPE_LEADER_SIZE);
-  gimple_types = htab_create_ggc (16381, gimple_type_hash, gimple_type_eq, 0);
+  gimple_types = htab_create_ggc (PARAM_VALUE (PARAM_GIMPLE_TYPE_HASH_SIZE),
+				  gimple_type_hash, gimple_type_eq, 0);
 
   if (!quiet_flag)
     fprintf (stderr, "Reading object files:");
diff --git a/gcc/params.def b/gcc/params.def
index 3c52651..46843df 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -1020,6 +1020,26 @@  DEFPARAM (PARAM_MAX_SLSR_CANDIDATE_SCAN,
 	  "strength reduction",
 	  50, 1, 999999)
 
+DEFPARAM (PARAM_TYPE_CACHE_HASH_SIZE,
+	"type-cache-hash-size",
+	"Initial size of the gimple type cache hash table",
+	512, 512, 0)
+
+DEFPARAM (PARAM_CANONICAL_TYPE_HASH_SIZE,
+	"canonical-type-hash-size",
+	"Initial size of the gimple canonical type hash table",
+	16381, 16381, 0)
+
+DEFPARAM (PARAM_CANONICAL_TYPE_CACHE_HASH_SIZE,
+	"canonical-type-cache-hash-size",
+	"Initial size of the gimple canonical type cache hash table",
+	512, 512, 0)
+
+DEFPARAM (PARAM_GIMPLE_TYPE_HASH_SIZE,
+	"type-hash-size",
+	"Initial size of the gimple type hash table",
+	16381, 16381, 0)
+
 /*
 Local variables:
 mode:c