diff mbox series

[RFC] tree-optimization/113910 - improve bitmap_hash

Message ID 20240214151431.1391C3860002@sourceware.org
State New
Headers show
Series [RFC] tree-optimization/113910 - improve bitmap_hash | expand

Commit Message

Richard Biener Feb. 14, 2024, 3:14 p.m. UTC 
The following tries to improve the actual hash function for hashing
bitmaps.  We're still getting collision rates as high as 23 for the
testcase in the PR.  The following improves this by properly mixing
in the bitmap element starting bit number.  This brings down the
collision rate below 1.4, improving compile-time by 25% for the
testcase but at the expense of bringing bitmap_hash into the
profile at around 5% of the samples as collected by perf.

When you actually mix each set bit number collisions are virtually
non-existent but hashing is then taking 35% of the compile time.

Any better ideas?

	PR tree-optimization/113910
	* bitmap.cc (bitmap_hash): Improve hash function by
	mixing the bitmap element index rather than XORing it.
	XOR individual elements into the hash.
---
 gcc/bitmap.cc | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)
diff mbox series

Patch

diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc
index 459e32c1ad1..80e185d5146 100644
--- a/gcc/bitmap.cc
+++ b/gcc/bitmap.cc
@@ -2695,18 +2695,22 @@  hashval_t
 bitmap_hash (const_bitmap head)
 {
   const bitmap_element *ptr;
-  BITMAP_WORD hash = 0;
+  hashval_t hash = 0;
   int ix;
 
   gcc_checking_assert (!head->tree_form);
 
   for (ptr = head->first; ptr; ptr = ptr->next)
     {
-      hash ^= ptr->indx;
+      hash = iterative_hash_hashval_t (ptr->indx, hash);
+      BITMAP_WORD bits = 0;
       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
-	hash ^= ptr->bits[ix];
+	bits ^= ptr->bits[ix];
+      if (sizeof (bits) == 8 && sizeof (hashval_t) == 4)
+	bits ^= bits >> 32;
+      hash ^= (hashval_t)bits;
     }
-  return iterative_hash (&hash, sizeof (hash), 0);
+  return hash;
 }