deps: cherry-pick c736883 from upstream V8

Original commit message:

    Optionally use halfsiphash for integer hashing.

    Change-Id: Ibd14f7b3fe78635675c76ae864112e3a3a7bc701
    Reviewed-on: https://chromium-review.googlesource.com/c/1382463
    Commit-Queue: Yang Guo <yangguo@chromium.org>
    Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#58674}

Refs: https://github.com/v8/v8/commit/c736883ed4e3ff92d1fd5a60497cec5311df9a25

1 files changed, 69 insertions, 0 deletions

diff --git a/deps/v8/test/cctest/test-hashcode.cc b/deps/v8/test/cctest/test-hashcode.cc
index 2059d53885..7c07ff6fdc 100644
--- a/deps/v8/test/cctest/test-hashcode.cc
+++ b/deps/v8/test/cctest/test-hashcode.cc
@@ -8,6 +8,8 @@
 
 #include "src/objects-inl.h"
 #include "src/objects.h"
+#include "src/third_party/siphash/halfsiphash.h"
+#include "src/utils.h"
 #include "src/v8.h"
 
 #include "test/cctest/cctest.h"
@@ -227,5 +229,72 @@ TEST(TransitionSlowToFastWithPropertyArray) {
   CheckFastObject(obj, hash);
 }
 
+namespace {
+
+typedef uint32_t (*HashFunction)(uint32_t key, uint64_t seed);
+
+void TestIntegerHashQuality(const int samples_log2, int num_buckets_log2,
+                            uint64_t seed, double max_var,
+                            HashFunction hash_function) {
+  int samples = 1 << samples_log2;
+  int num_buckets = 1 << num_buckets_log2;
+  int mean = samples / num_buckets;
+  int* buckets = new int[num_buckets];
+
+  for (int i = 0; i < num_buckets; i++) buckets[i] = 0;
+
+  for (int i = 0; i < samples; i++) {
+    uint32_t hash = hash_function(i, seed);
+    buckets[hash % num_buckets]++;
+  }
+
+  int sum_deviation = 0;
+  for (int i = 0; i < num_buckets; i++) {
+    int deviation = abs(buckets[i] - mean);
+    sum_deviation += deviation * deviation;
+  }
+  delete[] buckets;
+
+  double variation_coefficient = sqrt(sum_deviation * 1.0 / num_buckets) / mean;
+
+  printf("samples: 1 << %2d, buckets: 1 << %2d, var_coeff: %0.3f\n",
+         samples_log2, num_buckets_log2, variation_coefficient);
+  CHECK_LT(variation_coefficient, max_var);
+}
+uint32_t HalfSipHash(uint32_t key, uint64_t seed) {
+  return halfsiphash(key, seed);
+}
+
+uint32_t JenkinsHash(uint32_t key, uint64_t seed) {
+  return ComputeLongHash(static_cast<uint64_t>(key) ^ seed);
+}
+
+uint32_t DefaultHash(uint32_t key, uint64_t seed) {
+  return ComputeSeededHash(key, seed);
+}
+}  // anonymous namespace
+
+void TestIntegerHashQuality(HashFunction hash_function) {
+  TestIntegerHashQuality(17, 13, 0x123456789ABCDEFU, 0.4, hash_function);
+  TestIntegerHashQuality(16, 12, 0x123456789ABCDEFU, 0.4, hash_function);
+  TestIntegerHashQuality(15, 11, 0xFEDCBA987654321U, 0.4, hash_function);
+  TestIntegerHashQuality(14, 10, 0xFEDCBA987654321U, 0.4, hash_function);
+  TestIntegerHashQuality(13, 9, 1, 0.4, hash_function);
+  TestIntegerHashQuality(12, 8, 1, 0.4, hash_function);
+
+  TestIntegerHashQuality(17, 10, 0x123456789ABCDEFU, 0.2, hash_function);
+  TestIntegerHashQuality(16, 9, 0x123456789ABCDEFU, 0.2, hash_function);
+  TestIntegerHashQuality(15, 8, 0xFEDCBA987654321U, 0.2, hash_function);
+  TestIntegerHashQuality(14, 7, 0xFEDCBA987654321U, 0.2, hash_function);
+  TestIntegerHashQuality(13, 6, 1, 0.2, hash_function);
+  TestIntegerHashQuality(12, 5, 1, 0.2, hash_function);
+}
+
+TEST(HalfSipHashQuality) { TestIntegerHashQuality(HalfSipHash); }
+
+TEST(JenkinsHashQuality) { TestIntegerHashQuality(JenkinsHash); }
+
+TEST(DefaultHashQuality) { TestIntegerHashQuality(DefaultHash); }
+
 }  // namespace internal
 }  // namespace v8