| Message ID | 1366407117-18462-7-git-send-email-andi@firstfloor.org |
|---|---|
| State | New |
| Headers | show |
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 >
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
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
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
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(-)