[Mesa-dev] [PATCH 4/4] util: Change size of table to have 23% free

[Thomas Helland]

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