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 --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; } -- 2.35.3