From 39670daf26c4fbbfe9148dec30c9f0e075eff404 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Sat, 8 Jun 2024 08:20:12 +0200 Subject: improve hash api and hash test --- test/app.cpp | 2 +- test/hash.cpp | 112 ++++++++++++++++++++++++++++++++++++++++++---------------- 2 files changed, 83 insertions(+), 31 deletions(-) (limited to 'test') diff --git a/test/app.cpp b/test/app.cpp index 35a65743..6ace3ca5 100644 --- a/test/app.cpp +++ b/test/app.cpp @@ -65,7 +65,6 @@ int App::exec() FM_TEST(test_bptr), FM_TEST(test_iptr), FM_TEST(test_entity), - FM_TEST(test_hash), // normal FM_TEST(test_bitmask), FM_TEST(test_json), @@ -75,6 +74,7 @@ int App::exec() FM_TEST(test_raycast), FM_TEST(test_wall_atlas), FM_TEST(test_wall_atlas2), + FM_TEST(test_hash), FM_TEST(test_region), // the rest are slow FM_TEST(test_rtree), diff --git a/test/hash.cpp b/test/hash.cpp index 16ae3173..a06d16a6 100644 --- a/test/hash.cpp +++ b/test/hash.cpp @@ -1,9 +1,12 @@ #include "app.hpp" #include "compat/int-hash.hpp" #include "compat/array-size.hpp" +#include "src/global-coords.hpp" +#include "src/world.hpp" #include #include #include +#include namespace floormat { @@ -16,49 +19,67 @@ void test_simple() size_t hashes[size] = {}; for (auto i = 0uz; i < size; i++) - hashes[i] = hash_64(list[i].data(), list[i].size()); + hashes[i] = hash_buf(list[i].data(), list[i].size()); for (auto i = 0uz; i < size; i++) for (auto j = i+1; j < size; j++) { if (hashes[i] == hashes[j]) - fm_abort("hash collision between '%s' and '%s': 0x%p", list[i].data(), list[j].data(), (void*)hashes[i]); + fm_abort("hash collision between '%s' and '%s': 0x%p", + list[i].data(), list[j].data(), (void*)hashes[i]); } } -void test_collisions() +template +[[nodiscard]] bool test_collisions(const char* name) { - constexpr int max = 8; - constexpr size_t size = (2*max+1)*(2*max+1)*4 * 10; - constexpr size_t max_collisions = size*2/100; - size_t iter = 0, num_collisions = 0; - auto bitset_ = std::make_unique>(false); + constexpr size_t Iters = (CoordMax*2 + 1)*(CoordMax*2 + 1)*(1+ZMax); + constexpr size_t BucketCount = Math::max(world::initial_capacity, size_t(Math::ceil(Iters / world::max_load_factor))); + uint32_t num_collisions = 0, iters = 0; + auto bitset_ = std::make_unique>(false); auto& bitset = *bitset_; - for (int j = -max; j <= max; j++) - { - for (int i = -max; i <= max; i++) - { - for (int k = -2; k <= 1; k++) + for (int16_t j = -CoordMax; j <= CoordMax; j++) + for (int16_t i = -CoordMax; i <= CoordMax; i++) + for (int8_t k = 0; k <= ZMax; k++) { - ++iter; - uint64_t value = 0; - value |= (uint64_t)(uint16_t)(int16_t)i << 0; - value |= (uint64_t)(uint16_t)(int16_t)j << 16; - value |= (uint64_t)(uint16_t)(int16_t)k << 32; - auto x = (size_t)hash_int(value); - //Debug {} << "bitset:" << i << j << k << "=" << x % size << "/" << x; - x %= size; -#if 1 - if (bitset.test(x) && ++num_collisions >= max_collisions) - fm_abort("test/bitset: %zu collisions at iter %zu id %zu (%d;%d:%d)", num_collisions, iter, x, i, j, k); + auto p = global_coords{i, j, k}; + auto h = hash_buf(&p, sizeof p); + h %= BucketCount; + auto ref = bitset[h]; + if (ref) [[unlikely]] + ++num_collisions; + else + ref = true; + (void)ref; + iters++; + } + + fm_assert_equal(Iters, iters); + +//#define FM_TEST_DEBUG_PRINT + + if (num_collisions > MaxCollisions) + { + DBG_nospace << Debug::color(Debug::Color::Magenta) + << "fail" << Debug::resetColor << ": test/hash(\"" << name << "\")" + << " collisions " << num_collisions << " > " << MaxCollisions + << " (iters:" << iters << " buckets:" << BucketCount << ")"; +#ifdef FM_TEST_DEBUG_PRINT + return false; #else - if ((void)max_collisions, bitset.test(x)) - fm_warn("test/bitset: %zu collisions at iter %zu id %zu (%d;%d:%d)", ++num_collisions, iter, x, i, j, k); + fm_abort("test/hash: too many collisions"); #endif - bitset.set(x); - } - } + } + else + { +#ifdef FM_TEST_DEBUG_PRINT + DBG_nospace << Debug::color(Debug::Color::Cyan) << "pass" << Debug::resetColor + << ": test/hash(\"" << name << "\") collisions " + << num_collisions << " <= " << MaxCollisions + << " (iters:" << iters << " buckets:" << BucketCount << ")"; +#endif + return true; } } @@ -67,7 +88,38 @@ void test_collisions() void Test::test_hash() { test_simple(); - test_collisions(); + + bool success = true; + +#ifdef FM_TEST_DEBUG_PRINT + DBG_nospace << ""; +#endif + + success &= test_collisions< 3, 0, 0 >("small1"); + success &= test_collisions< 6, 0, 4 >("mid2"); + success &= test_collisions< 7, 0, 5 >("mid2"); + success &= test_collisions< 8, 0, 13 >("mid2"); + success &= test_collisions< 9, 0, 19 >("mid2"); + success &= test_collisions< 10, 0, 26 >("large1"); + success &= test_collisions< 12, 0, 46 >("large2"); + success &= test_collisions< 14, 0, 83 >("large3"); + success &= test_collisions< 15, 0, 109 >("large4"); + success &= test_collisions< 16, 0, 127 >("large5"); + success &= test_collisions< 3, 1, 2 >("zsmall2"); + success &= test_collisions< 4, 1, 6 >("zsmall3"); + success &= test_collisions< 2, 3, 1 >("zmid1"); + success &= test_collisions< 6, 1, 17 >("zmid3"); + success &= test_collisions< 6, 2, 37 >("zmid4"); + success &= test_collisions< 7, 1, 27 >("zmid5"); + success &= test_collisions< 10, 1, 107 >("zlarge2"); + success &= test_collisions< 10, 4, 271 >("zlarge3"); + success &= test_collisions< 16, 8, 1114 >("zlarge4"); + + if (!success) + { + DBG_nospace << ""; + fm_abort("test/hash: too many collisions"); + } } } // namespace floormat -- cgit v1.2.3