Should decrease collisions and therefore improve performance.
---
src/util/hash_table.c | 60 +++++++++++++++++++++++++--------------------------
src/util/set.c | 60 +++++++++++++++++++++++++--------------------------
2 files changed, 60 insertions(+), 60 deletions(-)
diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 92ffc10..733df46 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -54,42 +54,42 @@ static const uint32_t deleted_key_value;
* 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
+ * These tables are sized to have an extra 23% free to avoid
* exponential performance degradation as the hash table fills
*/
static const struct {
uint32_t max_entries, size;
} hash_sizes[] = {
{ 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 }
+ { 6, 8 },
+ { 12, 16 },
+ { 24, 32 },
+ { 49, 64 },
+ { 98, 128 },
+ { 197, 256 },
+ { 394, 512 },
+ { 788, 1024 },
+ { 1576, 2048 },
+ { 3153, 4096 },
+ { 6307, 8192 },
+ { 12615, 16384 },
+ { 25231, 32768 },
+ { 50462, 65536 },
+ { 100925, 131072 },
+ { 201850, 262144 },
+ { 403701, 524288 },
+ { 807403, 1048576 },
+ { 1614807, 2097152 },
+ { 3229614, 4194304 },
+ { 6459228, 8388608 },
+ { 12918456, 16777216 },
+ { 25836912, 33554432 },
+ { 51673825, 67108864 },
+ { 103347650, 134217728 },
+ { 206695301, 268435456 },
+ { 413390602, 536870912 },
+ { 826781204, 1073741824 },
+ { 1653562408ul, 2147483648ul }
};
static int
diff --git a/src/util/set.c b/src/util/set.c
index 8f0ad0d..356387e 100644
--- a/src/util/set.c
+++ b/src/util/set.c
@@ -52,42 +52,42 @@ const void *deleted_key = &deleted_key_value;
* 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
+ * These tables are sized to have an extra 23% free to avoid
* exponential performance degradation as the hash table fills
*/
static const struct {
uint32_t max_entries, size;
} hash_sizes[] = {
{ 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 }
+ { 6, 8 },
+ { 12, 16 },
+ { 24, 32 },
+ { 49, 64 },
+ { 98, 128 },
+ { 197, 256 },
+ { 394, 512 },
+ { 788, 1024 },
+ { 1576, 2048 },
+ { 3153, 4096 },
+ { 6307, 8192 },
+ { 12615, 16384 },
+ { 25231, 32768 },
+ { 50462, 65536 },
+ { 100925, 131072 },
+ { 201850, 262144 },
+ { 403701, 524288 },
+ { 807403, 1048576 },
+ { 1614807, 2097152 },
+ { 3229614, 4194304 },
+ { 6459228, 8388608 },
+ { 12918456, 16777216 },
+ { 25836912, 33554432 },
+ { 51673825, 67108864 },
+ { 103347650, 134217728 },
+ { 206695301, 268435456 },
+ { 413390602, 536870912 },
+ { 826781204, 1073741824 },
+ { 1653562408ul, 2147483648ul }
};
static int
--
2.2.1
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
