[libc.search] [PATCH 1/6] add wyhash as a header library

[SchrodingerZhu]

Summary

According to SMhasher, wyhash is one of fastest 64-bit hash functions that
does not have primary quality issues. This hash function is added
inorder to support string hashing used in hsearch related functions.
The code is derived from the original wyhash code released under
the public domain.

[tschuett]

Phabricator supports stacks. At the top right, you will find Edit Related Revisions ... .

[SchrodingerZhu]

To whom this may concern,

I am still hoping to work with you all to hear your opinions and to see if we can finally get these changes landed or not.
In the following week, I might be occupied by some work at my school department, which means I could be slow in response.
Please do leave comments if you ever get some time to review some piece of the code --- I will be back to this ASAP.

Best,
Yifan

[sivachandra]

In D136487#3910549, @SchrodingerZhu wrote:

To whom this may concern,

I am still hoping to work with you all to hear your opinions and to see if we can finally get these changes landed or not.
In the following week, I might be occupied by some work at my school department, which means I could be slow in response.
Please do leave comments if you ever get some time to review some piece of the code --- I will be back to this ASAP.

Best,
Yifan

Sorry for the delay. I have not forgotten about this and will definitely get back to you at the end of next week. Same with your post about the tsearch related work.

[SchrodingerZhu]

WYHASH V4 addressed PerlinNoise and BadSeed problem: https://github.com/wangyi-fudan/wyhash/blame/ea3b25e1aef55d90f707c3a292eeb9162e2615d8/wyhash.h#L45

[sivachandra]

I have started reviewing this patch set. It will take time but I will get back with feedback as soon as I can. Keep in mind that we are heading into the US holiday season.

[michaelrj]

I've done a general style review

libc/src/__support/wyhash.h

16

nit: "released"

24

the cpp namespace is for the CPP subdirectory. This should be internal instead.

26–27

add a comment explaining how you calculated these constants.

46–47

this should be a loop with shifts instead of memcpy, which should also allow you to avoid the endianness call below.

[SchrodingerZhu]

@michaelrj well received. Will work on it ASAP.

[SchrodingerZhu]

This commit updates the wyhash header library.
Notice that subsequent changes in other stacked patches are yet to be uploaded.

Changes:

• address code review
  • Use looped read with shift to avoid memcpy and endian conversion
  • Address the source of secret parameters
  • Move wyhash to internal namespace (TODO: Similar change need to be applied to other patches)
• Sync wyhash Implementation with version 4.1
  • hash function behavor changes at the initializing and finalizing stage
  • generate new sanity test hash values with ea3b25e1aef55d90f707c3a292eeb9162e2615d8

c++
        for (size_t i = 0; i < 7; ++i) {
            std::cout << std::hex << "0x" << wyhash(data[i], strlen(data[i]), i, _wyp) << std::endl;
        }

[michaelrj]

The patch overall looks good to me, but I'd like to see some more comprehensive tests. Specifically it would be good to demonstrate the avalanche effect by having test inputs that differ by one bit but have outputs that differ by much more. Once that is done I will approve.

[SchrodingerZhu]

• address problems mentioned reviews:
  • add tests to examine hash function has low bias in byte range
  • add tests to examine hash function has enough avalanche effect

[michaelrj]

Looks good to me.

[sivachandra]

Hi,
Before you land this, can you explain what the long term plan would be to keep this libc version in sync with the original wyhash implementation?
Thanks,
Siva Chandra

[SchrodingerZhu]

Hi,
I would like to share some ideas about the maintenance:

• Since the property of this Wyhash implementation is proved by both SMHasher and the provided tests, we can keep the it unchanged, unless:
• "security issue" is confirmed for this implementation such as one can prove that particular sequence of hashing leads to heavy collisions
• or, new hash implementation is highly promising in performance and robustness

Although wyhash is also stable across micro-architectures as it does not use platform-specific instructions and it take care of the endianness, currently this hash function is only intended to be used in in-memory hashmap that only relies on the stability of hash value (given a fixed seed) at runtime.

If runtime stability is all we required, I think there should be no bit concern for updating the hash implementation or even changing the algorithm if ever needed in the future.

Best,
Yifan

[SchrodingerZhu]

Rebase

[sivachandra]

I am referring to updates of the kind you have done to this patch itself, "Sync wyhash Implementation with version 4.1". What would be the strategy to take updates on a continuous basis?

[chandlerc]

Not active really here, but wanted to point out --

wyhash is not under the public domain AFAIK. The repository is here:
https://github.com/wangyi-fudan/wyhash

The license is the so-called "unlicense" which you can read about here:
https://softwareengineering.stackexchange.com/questions/147111/what-is-wrong-with-the-unlicense

In general, contributions to LLVM projects need to follow the basic rules in the developer policy, including that it is licensed under the LLVM license:
https://llvm.org/docs/DeveloperPolicy.html#copyright-license-and-patents:~:text=When%20you%20contribute%20code%20to%20the%20LLVM%20project%2C%20you%20license%20it%20under%20these%20terms.

That policy includes specific instructions for suggesting the inclusion of code under other licenses:
https://llvm.org/docs/DeveloperPolicy.html#copyright-license-and-patents:~:text=In%20certain%20circumstances,requesting%20a%20review.

Snippet for ease:

In certain circumstances, code licensed under other licenses can be added to the codebase. However, this may only be done with approval of the LLVM Foundation Board of Directors, and contributors should plan for the approval process to take at least 4-6 weeks. If you would like to contribute code under a different license, please create a Phabricator review with the code you want to contribute and email [e-mail] requesting a review.

[SchrodingerZhu]

Hi, @chandlerc,

I am so sorry I did not notice that Unlicense is actually complicating the situation. I regard it as public domain because projects like Go includes it as a derived work without mentioning the original license. That is being said, I totally agree that one should be careful about the Unlicense after reading through the stackoverflow discussion.

I will try to reach out the board. Meanwhile, I saw previous issue discussion at WyHash repo that the author intended to set their code completely free -- assuming they are still holding this intention, I will also try to reach out them to see if they are willingly to do multi licensing.

I ping you here just because I saw that the hash function in LLVM was maintained by you. If the worst case ever happens, is it possible to port the code in llvm library into libc library and use that instead?

@sivachandra, @michaelrj, I apologize again if I have added any complication to your work. Thanks for the reviews.

Yifan

libc/src/__support/CMakeLists.txt

 add_header_library(
   uint128
   HDRS
     UInt128.h
   DEPENDS
     .uint
 )
 
+add_header_library(
+  wyhash
+  HDRS
+  wyhash.h
+  DEPENDS
+    .common
+    .uint128
+)
+
 add_subdirectory(FPUtil)
 add_subdirectory(OSUtil)
 add_subdirectory(StringUtil)
 
 # Thread support is used by other "File". So, we add the "threads"
 # before "File".
 add_subdirectory(threads)
 
 add_subdirectory(File)

libc/src/__support/wyhash.h

+//===-- A 64-bit Hash Function ----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/__support/UInt128.h"
+#include "src/__support/common.h"
+
+// WyHash comes from https://github.com/wangyi-fudan/wyhash/ (which has been
+// released into public domain). It is also the default hash function
+// of Go, Nim and Zig.
+//
+// According to SMHasher's results, it is one of the fastest hash functions
+// without primary quality issues. This hash function can be used with
+// swisstable as it has the Avalanche effect to encode the data into full
+// 64-bits; thus the table can effectively utilize two level hash technique
+// to effectively locate candidate entries without too many false positives.
+namespace __llvm_libc::internal::wyhash {
+// default secret parameters from WyHash
+// commit hash: ea3b25e1aef55d90f707c3a292eeb9162e2615d8
+static constexpr inline uint64_t DEFAULT_SECRET[4] = {
+    0xa0761d6478bd642full, 0xe7037ed1a0b428dbull, 0x8ebc6af09c88c6e3ull,
+    0x589965cc75374cc3ull};
+template <bool EntropyProtection> class WyHash {
+  static void multiply(uint64_t &a, uint64_t &b) {
+    UInt128 data{a};
+    data *= b;
+    if constexpr (EntropyProtection) {
+      a ^= static_cast<uint64_t>(data);
+      b ^= static_cast<uint64_t>(data >> 64);
+    } else {
+      a = static_cast<uint64_t>(data);
+      b = static_cast<uint64_t>(data >> 64);
+    }
+  }
+  static uint64_t mix(uint64_t a, uint64_t b) {
+    multiply(a, b);
+    return a ^ b;
+  }
+  template <size_t N> static uint64_t read(const uint8_t *p) {
+    uint64_t value = 0;
+    for (size_t i = 0; i < N; ++i) {
+      value |= (static_cast<uint64_t>(p[i]) << (i * 8));
+    }
+    return value;
+  }
+
+  static uint64_t read3(const uint8_t *p, size_t k) {
+    auto a = static_cast<uint64_t>(p[0]) << 16;
+    auto b = static_cast<uint64_t>(p[k / 2]) << 8;
+    auto c = static_cast<uint64_t>(p[k - 1]);
+    return a | b | c;
+  }
+
+  static uint64_t wyhash(const void *key, size_t length, uint64_t seed,
+                         const uint64_t *secret) {
+    const uint8_t *p = static_cast<const uint8_t *>(key);
+    seed ^= mix(seed ^ secret[0], secret[1]);
+    uint64_t a = 0, b = 0;
+    if (likely(length <= 16)) {
+      if (likely(length >= 4)) {
+        a = (read<4>(p) << 32) | read<4>(p + ((length >> 3) << 2));
+        b = (read<4>(p + length - 4) << 32) |
+            read<4>(p + length - 4 - ((length >> 3) << 2));
+      } else if (likely(length > 0)) {
+        a = read3(p, length);
+        b = 0;
+      }
+    } else {
+      size_t i = length;
+      if (likely(i > 48)) {
+        uint64_t s1 = seed, s2 = seed;
+        do {
+          seed = mix(read<8>(p) ^ secret[1], read<8>(p + 8) ^ seed);
+          s1 = mix(read<8>(p + 16) ^ secret[2], read<8>(p + 24) ^ s1);
+          s2 = mix(read<8>(p + 32) ^ secret[3], read<8>(p + 40) ^ s2);
+          p += 48;
+          i -= 48;
+        } while (likely(i > 48));
+        seed ^= s1 ^ s2;
+      }
+      while (unlikely(i > 16)) {
+        seed = mix(read<8>(p) ^ secret[1], read<8>(p + 8) ^ seed);
+        i -= 16;
+        p += 16;
+      }
+      a = read<8>(p + i - 16);
+      b = read<8>(p + i - 8);
+    }
+    a ^= secret[1];
+    b ^= seed;
+    multiply(a, b);
+    return mix(a ^ secret[0] ^ length, b ^ secret[1]);
+  }
+
+public:
+  static uint64_t hash(const void *key, size_t length, uint64_t seed) {
+    return wyhash(key, length, seed, DEFAULT_SECRET);
+  }
+};
+
+// Follow the practice in Golang to disable low-entropy protection by default.
+using DefaultHash = WyHash<false>;
+
+} // namespace __llvm_libc::internal::wyhash

libc/test/src/__support/CMakeLists.txt

SUITE
     libc_support_unittests
   SRCS
     endian_test.cpp
   DEPENDS
     libc.src.__support.common
 )
 
 add_libc_unittest(
+  wyhash_test
+  SUITE
+    libc_support_unittests
+  SRCS
+    wyhash_test.cpp
+  DEPENDS
+    libc.src.__support.wyhash
+    libc.src.string.strlen
+    libc.src.string.memset
+    libc.src.stdlib.rand
+)
+
+add_libc_unittest(
   high_precision_decimal_test
   SUITE
     libc_support_unittests
   SRCS
   high_precision_decimal_test.cpp
   DEPENDS
     libc.src.__support.high_precision_decimal
     libc.src.__support.uint128

libc/test/src/__support/wyhash_test.cpp

+//===-- Unittests for wyhash ----------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/__support/wyhash.h"
+#include "src/stdlib/rand.h"
+#include "src/string/memset.h"
+#include "src/string/strlen.h"
+#include "utils/UnitTest/LibcTest.h"
+
+#if defined __has_builtin
+#if __has_builtin(__builtin_popcountll)
+#define LLVM_LIBC_WYHASH_TEST_HAS_BUILTIN_POPCOUNTLL
+#endif
+#endif
+
+static inline size_t random_string(char *buf) {
+  static constexpr size_t LOWER_LIMIT = 16;
+  static constexpr size_t UPPER_LIMIT = 64;
+  size_t length =
+      LOWER_LIMIT + __llvm_libc::rand() % (UPPER_LIMIT - LOWER_LIMIT);
+  // 1 << (8 + 16) ~ 1 << (8 + 64) should be of good randomness
+  for (size_t i = 0; i < length; ++i) {
+    buf[i] = __llvm_libc::rand();
+  }
+  return length;
+}
+
+static inline size_t hamming_distance(uint64_t x, uint64_t y) {
+#if defined LLVM_LIBC_WYHASH_TEST_HAS_BUILTIN_POPCOUNTLL
+  return __builtin_popcountll(x ^ y);
+#else
+  size_t sum = 0;
+  uint64_t current = x ^ y;
+  while (current != 0) {
+    sum += current & 0b1;
+    current >>= 1;
+  }
+  return sum;
+#endif
+}
+
+// We expect the hash value to be of low bias at each byte
+// so that we can select a section of hash value as a second-level hash
+TEST(LlvmLibcWyHashTest, LowBias) {
+  using namespace __llvm_libc::internal::wyhash;
+  static constexpr size_t SLOT_NUM = 1u << 8u;
+  static constexpr size_t SCALE = 1000;
+  static constexpr uint64_t SEED = 0x0123'4567'89AB'CDEFull;
+  // Iterate through each byte
+  for (size_t i = 0; i < sizeof(uint64_t) * 8; ++i) {
+    size_t counter[SLOT_NUM];
+    __llvm_libc::memset(counter, 0, sizeof(counter));
+    size_t total = SCALE * SLOT_NUM;
+    while (total--) {
+      char buf[64];
+      size_t length = random_string(buf);
+      uint64_t hash = DefaultHash::hash(buf, length, SEED);
+      // Get the section corresponds to the byte being examined
+      counter[(hash >> (i * 8)) & 0xFF]++;
+    }
+
+    // Sum up to get the variance
+    size_t sum = 0;
+    for (size_t i = 0; i < SLOT_NUM; ++i)
+      sum += static_cast<double>((counter[i] - SCALE) * (counter[i] - SCALE));
+
+    // We hope that averaged bias at each slot is less than 10%.
+    // Use square to avoid SQRT.
+    ASSERT_LE(sum / SLOT_NUM, (SCALE / 10) * (SCALE / 10));
+  }
+}
+
+// In real world, user may insert similar data into a hash set.
+// To make the hash function robust, we hope a single-bit change is
+// enough to change the hash value by a large extend.
+TEST(LlvmLibcWyHashTest, AvalancheRandomString) {
+  using namespace __llvm_libc::internal::wyhash;
+  static constexpr size_t TEST_GROUP_NUM = 10000;
+  static constexpr size_t TEST_GROUP_SIZE = 100;
+  static constexpr uint64_t SEED = 0x89AB'CDEF'0123'4567ull;
+  for (size_t i = 0; i < TEST_GROUP_NUM; ++i) {
+    char buf[64];
+    size_t length = random_string(buf);
+    size_t original_hash = DefaultHash::hash(buf, length, SEED);
+    for (size_t j = 0; j < TEST_GROUP_SIZE; ++j) {
+      // Randomly select a byte
+      size_t byte = __llvm_libc::rand() % length;
+      // Randomly select a bit
+      size_t bit = __llvm_libc::rand() % 8;
+      // Alter the bit
+      char backup = buf[byte];
+      buf[byte] ^= (1u << bit);
+      size_t new_hash = DefaultHash::hash(buf, length, SEED);
+      // The hamming distance of the hash is larger than 20% of the hash volume.
+      ASSERT_GE(hamming_distance(original_hash, new_hash),
+                (8 * sizeof(uint64_t)) * 2 / 10);
+      // Recover the string
+      buf[byte] = backup;
+    }
+  }
+}
+
+TEST(LlvmLibcWyHashTest, AvalancheSmallValue) {
+  using namespace __llvm_libc::internal::wyhash;
+  static constexpr uint64_t SEED = 0xCDEF'89AB'4567'0123ull;
+  for (size_t i = 0; i < 4096; ++i) {
+    for (size_t j = i + 1; j < 4096; ++j) {
+      size_t hash_i = DefaultHash::hash(&i, sizeof(i), SEED);
+      size_t hash_j = DefaultHash::hash(&j, sizeof(j), SEED);
+      // The hamming distance of the hash is larger than 20% of the hash volume.
+      ASSERT_GE(hamming_distance(hash_i, hash_j),
+                (8 * sizeof(uint64_t)) * 2 / 10);
+    }
+  }
+}
+
+// Sanity check
+TEST(LlvmLibcWyHashTest, DefaultValues) {
+  using namespace __llvm_libc::internal::wyhash;
+  // clang-format off
+  const char *data[] = {
+    "",
+    "a",
+    "abc",
+    "message digest",
+    "abcdefghijklmnopqrstuvwxyz",
+    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
+    "12345678901234567890123456789012345678901234567890123456789012345678901234567890" 
+  };
+  // generated with original WyHash implementation (ea3b25e1aef55d90f707c3a292eeb9162e2615d8)
+  uint64_t hash[] = {
+    0x0409638ee2bde459,
+    0xa8412d091b5fe0a9,
+    0x32dd92e4b2915153,
+    0x8619124089a3a16b,
+    0x7a43afb61d7f5f40,
+    0xff42329b90e50d58,
+    0xc39cab13b115aad3,
+
+  };
+  // clang-format on
+  for (size_t i = 0; i < 7; ++i) {
+    ASSERT_EQ(DefaultHash::hash(data[i], __llvm_libc::strlen(data[i]), i),
+              hash[i]);
+  }
+}