diff options
Diffstat (limited to 'vespalib')
6 files changed, 74 insertions, 18 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/datastore/array_store.h b/vespalib/src/vespa/vespalib/datastore/array_store.h index 4549b81283e..51a1f9fe950 100644 --- a/vespalib/src/vespa/vespalib/datastore/array_store.h +++ b/vespalib/src/vespa/vespalib/datastore/array_store.h @@ -94,7 +94,7 @@ private: EntryRef allocate_dynamic_array(size_t array_size, uint32_t type_id); EntryRef addLargeArray(ConstArrayRef array); EntryRef allocate_large_array(size_t array_size); - ConstArrayRef getSmallArray(RefT ref, size_t arraySize) const { + ConstArrayRef getSmallArray(RefT ref, size_t arraySize) const noexcept { const ElemT *buf = _store.template getEntryArray<ElemT>(ref, arraySize); return ConstArrayRef(buf, arraySize); } @@ -104,7 +104,7 @@ private: auto size = BufferType::get_dynamic_array_size(entry); return ConstArrayRef(entry, size); } - ConstArrayRef getLargeArray(RefT ref) const { + ConstArrayRef getLargeArray(RefT ref) const noexcept { const LargeArray *buf = _store.template getEntry<LargeArray>(ref); return ConstArrayRef(&(*buf)[0], buf->size()); } @@ -114,7 +114,7 @@ public: ArrayStore(const ArrayStoreConfig &cfg, std::shared_ptr<alloc::MemoryAllocator> memory_allocator, TypeMapper&& mapper); ~ArrayStore() override; EntryRef add(ConstArrayRef array); - ConstArrayRef get(EntryRef ref) const { + ConstArrayRef get(EntryRef ref) const noexcept { if (!ref.valid()) [[unlikely]] { return ConstArrayRef(); } diff --git a/vespalib/src/vespa/vespalib/datastore/datastore.h b/vespalib/src/vespa/vespalib/datastore/datastore.h index fa231e9cf94..0226c780cf1 100644 --- a/vespalib/src/vespa/vespalib/datastore/datastore.h +++ b/vespalib/src/vespa/vespalib/datastore/datastore.h @@ -96,7 +96,7 @@ public: EntryRef addEntry(const EntryType &e); - const EntryType &getEntry(EntryRef ref) const { + const EntryType &getEntry(EntryRef ref) const noexcept { return *this->template getEntry<EntryType>(RefType(ref)); } }; diff --git a/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp b/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp index 0e9393b7be4..5f63925bfef 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 = 4; + 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; } |