Merge pull request #30943 from vespa-engine/balder/benchmark-binary-hamming-distance

Add micro benchmark for binary hamming distance.

4 files changed, 70 insertions, 14 deletions

diff --git a/vespalib/src/tests/util/hamming/CMakeLists.txt b/vespalib/src/tests/util/hamming/CMakeLists.txt
index 5c317627200..ab551eab583 100644
--- a/vespalib/src/tests/util/hamming/CMakeLists.txt
+++ b/vespalib/src/tests/util/hamming/CMakeLists.txt
@@ -7,3 +7,10 @@ vespa_add_executable(vespalib_hamming_test_app TEST
     GTest::GTest
 )
 vespa_add_test(NAME vespalib_hamming_test_app COMMAND vespalib_hamming_test_app)
+
+vespa_add_executable(vespalib_hamming_benchmark_app TEST
+    SOURCES
+    hamming_benchmark.cpp
+    DEPENDS
+    vespalib
+)
diff --git a/vespalib/src/tests/util/hamming/hamming_benchmark.cpp b/vespalib/src/tests/util/hamming/hamming_benchmark.cpp
new file mode 100644
index 00000000000..b6393dcd1b7
--- /dev/null
+++ b/vespalib/src/tests/util/hamming/hamming_benchmark.cpp
@@ -0,0 +1,40 @@
+// Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/util/binary_hamming_distance.h>
+#include <vector>
+#include <cstdlib>
+#include <cstdint>
+#include <cstdio>
+
+using namespace vespalib;
+
+int main(int argc, char* argv[]) {
+    size_t vector_length = 1024/8;
+    size_t num_vectors = 1;
+    size_t num_reps = 100000000;
+
+    if (argc > 2) {
+        vector_length = atol(argv[2])/8;
+    }
+    if (argc > 3) {
+        num_reps = atol(argv[3]);
+    }
+    if (argc > 4) {
+        num_vectors = atol(argv[4]);
+    }
+
+    std::vector<uint8_t> center(vector_length);
+    std::vector<uint8_t> vectors(num_vectors*vector_length);
+    srand(13);
+    for (uint8_t & v : center) { v = rand(); }
+    for (uint8_t & v : vectors) { v = rand(); }
+    uint64_t sum(0);
+    for (size_t i=0; i < num_reps; i++) {
+        for (size_t j(0); j < num_vectors; j++) {
+            sum += binary_hamming_distance(center.data(), vectors.data() + j*vector_length, vector_length);
+        }
+    }
+
+    printf("%lu vectors of %lu bits, repeated %lu times. Sum of distances = %lu\n", num_vectors, vector_length*8, num_reps, sum);
+    return 0;
+}
diff --git a/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp b/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp
index 0e9393b7be4..5f242059ccf 100644
--- a/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp
+++ b/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp
@@ -4,25 +4,34 @@
 
 namespace vespalib {
 
-size_t binary_hamming_distance(const void *lhs, const void *rhs, size_t sz) {
-    uintptr_t addr_a = (uintptr_t) lhs;
-    uintptr_t addr_b = (uintptr_t) rhs;
+namespace {
+    constexpr uint8_t WORD_SZ = sizeof (uint64_t);
+    constexpr uint8_t UNROLL_CNT = 2;
+    static_assert(sizeof(uint64_t) == 8);
+}
+size_t
+binary_hamming_distance(const void *lhs, const void *rhs, size_t sz) noexcept {
+    auto addr_a = (uintptr_t) lhs;
+    auto addr_b = (uintptr_t) rhs;
     size_t sum = 0;
     size_t i = 0;
-    static_assert(sizeof(uint64_t) == 8);
     bool aligned = ((addr_a & 0x7) == 0) && ((addr_b & 0x7) == 0);
     if (__builtin_expect(aligned, true)) {
-        const uint64_t *words_a = static_cast<const uint64_t *>(lhs);
-        const uint64_t *words_b = static_cast<const uint64_t *>(rhs);
-        for (; i * 8 + 7 < sz; ++i) {
-            uint64_t xor_bits = words_a[i] ^ words_b[i];
-            sum += __builtin_popcountl(xor_bits);
+        const auto *words_a = static_cast<const uint64_t *>(lhs);
+        const auto *words_b = static_cast<const uint64_t *>(rhs);
+        for (; (i+UNROLL_CNT) * WORD_SZ <= sz; i += UNROLL_CNT) {
+            for (uint8_t j=0; j < UNROLL_CNT; j++) {
+                sum += __builtin_popcountl(words_a[i+j] ^ words_b[i+j]);
+            }
+        }
+        for (; (i + 1) * WORD_SZ <= sz; ++i) {
+            sum += __builtin_popcountl(words_a[i] ^ words_b[i]);
         }
     }
-    if (__builtin_expect((i * 8 < sz), false)) {
-        const uint8_t *bytes_a = static_cast<const uint8_t *>(lhs);
-        const uint8_t *bytes_b = static_cast<const uint8_t *>(rhs);
-        for (i *= 8; i < sz; ++i) {
+    if (__builtin_expect((i * WORD_SZ < sz), false)) {
+        const auto *bytes_a = static_cast<const uint8_t *>(lhs);
+        const auto *bytes_b = static_cast<const uint8_t *>(rhs);
+        for (i *= WORD_SZ; i < sz; ++i) {
             uint64_t xor_bits = bytes_a[i] ^ bytes_b[i];
             sum += __builtin_popcountl(xor_bits);
         }
diff --git a/vespalib/src/vespa/vespalib/util/binary_hamming_distance.h b/vespalib/src/vespa/vespalib/util/binary_hamming_distance.h
index 84bbbe71788..f5280903db1 100644
--- a/vespalib/src/vespa/vespalib/util/binary_hamming_distance.h
+++ b/vespalib/src/vespa/vespalib/util/binary_hamming_distance.h
@@ -10,5 +10,5 @@ namespace vespalib {
  * @param sz number of bytes in each blob
  * @return number of bits that differ when comparing the two blobs
  **/
-size_t binary_hamming_distance(const void *lhs, const void *rhs, size_t sz);
+size_t binary_hamming_distance(const void *lhs, const void *rhs, size_t sz) noexcept;
 }