[Mesa-dev] [PATCH 2/8] util: Change table size to be power of two

[Thomas Helland]

This gives better performance as we can do bitmasking
instead of modulo operations.

This reduces oprofile hits on a shader-db run accordingly:
hash_table_insert       4.28 ---> 2.57
hash_table_search       4.59 ---> 2.67
runtime	                175  ---> 170

Since the last patch hits assertion failures this is
the result for these two patches combined.
---
 src/util/hash_table.c | 75 ++++++++++++++++++++++++++-------------------------
 1 file changed, 38 insertions(+), 37 deletions(-)

diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 542f583..49a1fea 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -51,44 +51,45 @@
 static const uint32_t deleted_key_value;
 
 /**
- * From Knuth -- a good choice for hash values is p, where is prime.
+ * We chose table sizes that's a power of two.
+ * This is computationally less expensive than primes.
+ * FNV-1a has good avalanche properties, so collision is not an issue.
  * These tables are sized to have an extra 10% free to avoid
  * exponential performance degradation as the hash table fills
  */
 static const struct {
    uint32_t max_entries, size;
 } hash_sizes[] = {
-   { 2,			5		},
-   { 4,			7		},
-   { 8,			13		},
-   { 16,		19		},
-   { 32,		43		},
-   { 64,		73		},
-   { 128,		151		},
-   { 256,		283		},
-   { 512,		571		},
-   { 1024,		1153		},
-   { 2048,		2269		},
-   { 4096,		4519		},
-   { 8192,		9013		},
-   { 16384,		18043		},
-   { 32768,		36109		},
-   { 65536,		72091		},
-   { 131072,		144409		},
-   { 262144,		288361		},
-   { 524288,		576883		},
-   { 1048576,		1153459	},
-   { 2097152,		2307163	},
-   { 4194304,		4613893	},
-   { 8388608,		9227641	},
-   { 16777216,		18455029	},
-   { 33554432,		36911011	},
-   { 67108864,		73819861	},
-   { 134217728,		147639589	},
-   { 268435456,		295279081	},
-   { 536870912,		590559793	},
-   { 1073741824,	1181116273	},
-   { 2147483648ul,	2362232233ul}
+      { 3,            4            },
+      { 7,            8            },
+      { 14,           16           },
+      { 28,           32           },
+      { 57,           64           },
+      { 115,          128          },
+      { 230,          256          },
+      { 460,          512          },
+      { 921,          1024         },
+      { 1843,         2048         },
+      { 3686,         4096         },
+      { 7372,         8192         },
+      { 14745,        16384        },
+      { 29491,        32768        },
+      { 58982,        65536        },
+      { 117964,       131072       },
+      { 235929,       262144       },
+      { 471859,       524288       },
+      { 943718,       1048576      },
+      { 1887436,      2097152      },
+      { 3774873,      4194304      },
+      { 7549747,      8388608      },
+      { 15099494,     16777216     },
+      { 30198988,     33554432     },
+      { 60397977,     67108864     },
+      { 120795955,    134217728    },
+      { 241591910,    268435456    },
+      { 483183820,    536870912    },
+      { 966367641,    1073741824   },
+      { 1932735283ul, 2147483648ul }
 };
 
 static int
@@ -181,7 +182,7 @@ _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key)
 static struct hash_entry *
 hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
 {
-   uint32_t start_hash_address = hash % ht->size;
+   uint32_t start_hash_address = hash & (ht->size -1);
    uint32_t hash_address = start_hash_address;
    uint32_t quad_hash = 1;
 
@@ -196,7 +197,7 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
          }
       }
 
-      hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
+      hash_address = (hash_address + quad_hash*quad_hash) & (ht->size -1);
       quad_hash++;
    } while (hash_address != start_hash_address);
 
@@ -272,7 +273,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
       _mesa_hash_table_rehash(ht, ht->size_index);
    }
 
-   start_hash_address = hash % ht->size;
+   start_hash_address = hash & (ht->size -1);
    hash_address = start_hash_address;
 
    do {
@@ -304,7 +305,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
          return entry;
       }
 
-      hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
+      hash_address = (hash_address + quad_hash*quad_hash) & (ht->size -1);
       quad_hash++;
    } while (hash_address != start_hash_address);
 
@@ -400,7 +401,7 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
                               bool (*predicate)(struct hash_entry *entry))
 {
    struct hash_entry *entry;
-   uint32_t i = rand() % ht->size;
+   uint32_t i = rand() & (ht->size -1);
 
    if (ht->entries == 0)
       return NULL;
-- 
2.2.1