This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH 3/9] Use murmurhash3 for pointer map hashing
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: Andi Kleen <andi at firstfloor dot org>
- Cc: gcc-patches at gcc dot gnu dot org, hubicka at ucw dot cz, Andi Kleen <ak at linux dot intel dot com>
- Date: Mon, 22 Apr 2013 13:46:58 +0200
- Subject: Re: [PATCH 3/9] Use murmurhash3 for pointer map hashing
- References: <1366407117-18462-1-git-send-email-andi at firstfloor dot org> <1366407117-18462-4-git-send-email-andi at firstfloor dot org>
On Fri, Apr 19, 2013 at 11:31 PM, Andi Kleen <andi@firstfloor.org> wrote:
> From: Andi Kleen <ak@linux.intel.com>
>
> For a large LTO test case The previous pointer hash change brought
> the collision rate for the WPA gimple type hash table from 90% to
> 70. This patch uses the well known murmur3 to improve it further
> to 64%.
But if they are pointers then pointer_hash should be good enough... ?
That said, I still have that large type merging reorg pending ... (just my
day only has 24h ...)
Richard.
> gcc/:
>
> 2013-04-18 Andi Kleen <ak@linux.intel.com>
>
> * Makefile.in (tree.o): Add murmurhash3.h dependency.
> * tree.c (tree_map_base_hash): Use murmurhash3.
> ---
> gcc/Makefile.in | 2 +-
> gcc/tree.c | 4 +++-
> 2 files changed, 4 insertions(+), 2 deletions(-)
>
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index 109f865..28815a2 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -2216,7 +2216,7 @@ tree.o: tree.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
> $(BASIC_BLOCK_H) $(TREE_FLOW_H) $(OBSTACK_H) pointer-set.h \
> $(TREE_PASS_H) $(LANGHOOKS_DEF_H) $(DIAGNOSTIC_H) $(CGRAPH_H) \
> $(EXCEPT_H) debug.h intl.h tree-diagnostic.h $(TREE_PRETTY_PRINT_H) \
> - $(COMMON_TARGET_H)
> + $(COMMON_TARGET_H) murmurhash.h
> tree-dump.o: tree-dump.c $(CONFIG_H) $(SYSTEM_H) $(TM_H) $(TREE_H) \
> langhooks.h $(TREE_DUMP_H) tree-iterator.h $(TREE_PRETTY_PRINT_H)
> tree-inline.o : tree-inline.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
> diff --git a/gcc/tree.c b/gcc/tree.c
> index d8f2424..2fb732f 100644
> --- a/gcc/tree.c
> +++ b/gcc/tree.c
> @@ -59,6 +59,7 @@ along with GCC; see the file COPYING3. If not see
> #include "except.h"
> #include "debug.h"
> #include "intl.h"
> +#include "murmurhash3.h"
>
> /* Tree code classes. */
>
> @@ -5935,7 +5936,8 @@ tree_map_base_eq (const void *va, const void *vb)
> unsigned int
> tree_map_base_hash (const void *item)
> {
> - return htab_hash_pointer (((const struct tree_map_base *)item)->from);
> + return murmurhash3_32 (&((const struct tree_map_base *)item)->from,
> + sizeof (void *), 0);
> }
>
> /* Return true if this tree map structure is marked for garbage collection
> --
> 1.8.1.4
>