diff options
Diffstat (limited to 'hicn-light/src/hicn/test/test-hash.cc')
-rw-r--r-- | hicn-light/src/hicn/test/test-hash.cc | 114 |
1 files changed, 104 insertions, 10 deletions
diff --git a/hicn-light/src/hicn/test/test-hash.cc b/hicn-light/src/hicn/test/test-hash.cc index 2b72e194a..3b03a08a6 100644 --- a/hicn-light/src/hicn/test/test-hash.cc +++ b/hicn-light/src/hicn/test/test-hash.cc @@ -22,14 +22,18 @@ #include <sys/socket.h> #include <sys/un.h> #include <unistd.h> -// #include <hicn/transport/utils/hash.h> +#include <unordered_set> +#include <hicn/test/test-utils.h> extern "C" { -#include <hicn/base/hash.h> +#include <hicn/util/hash.h> #include <hicn/core/address_pair.h> #include <hicn/core/listener.h> } +static constexpr uint32_t init_val = 2166136261UL; +static constexpr int N_HASHES = 50000; + TEST(HashTest, MultipleHashesForSameAddrPair) { address_pair_t pair = address_pair_factory(_ADDRESS4_LOCALHOST(1), _ADDRESS4_LOCALHOST(2)); @@ -108,16 +112,106 @@ TEST(HashTest, SameListenerKeys) { } TEST(HashTest, Collisions) { - uint32_t init_val = 2166136261UL; - (void)init_val; - - std::map<u32, uint32_t> hashes; + std::unordered_set<uint32_t> hashes; + int n_collisions = 0; for (int i = 0; i < 50000; i++) { uint32_t seg = i; - // u32 h = utils::hash::fnv32_buf (&seg, sizeof (seg)); - // u32 h = cumulative_hash32 (&seg, sizeof (seg), init_val); + // u32 h = utils::hash::fnv32_buf(&seg, sizeof(seg)); + // u32 h = cumulative_hash32(&seg, sizeof(uint32_t), init_val); u32 h = hash(&seg, sizeof(seg)); - EXPECT_FALSE(hashes.find(h) != hashes.end()) << seg << " - " << hashes[h]; - hashes[h] = seg; + + if (hashes.find(h) != hashes.end()) n_collisions++; + hashes.insert(h); } + EXPECT_EQ(n_collisions, 0); +} + +/*** Compare FNV with Jenkins ***/ + +typedef struct { + uint32_t data[6]; +} small_struct_t; // Same size as 'NameBitvector' + +typedef struct { + uint64_t data[32]; +} big_struct_t; // Same size as 'address_pair_t' + +TEST(HashTest, PerformanceComparisonSmallStruct) { + small_struct_t small_struct; + + // FNV + auto time_fnv = get_execution_time([&]() { + for (int i = 0; i < N_HASHES; i++) { + small_struct.data[0] = i; + cumulative_hash32(&small_struct, sizeof(small_struct_t), init_val); + } + }); + + // Jenkins + auto time_jenkins = get_execution_time([&]() { + for (int i = 0; i < N_HASHES; i++) { + small_struct.data[0] = i; + hash(&small_struct, sizeof(small_struct_t)); + } + }); + + std::cout << "Small struct (size = " << sizeof(small_struct_t) << " bytes)\n"; + std::cout << "FNV: " << time_fnv << "ms\n"; + std::cout << "Jenkins: " << time_jenkins << "ms\n"; +} + +TEST(HashTest, PerformanceComparisonBigStruct) { + big_struct_t big_struct; + + // FNV + auto time_fnv = get_execution_time([&]() { + for (int i = 0; i < N_HASHES; i++) { + big_struct.data[0] = i; + cumulative_hash32(&big_struct, sizeof(big_struct_t), init_val); + } + }); + + // Jenkins + auto time_jenkins = get_execution_time([&]() { + for (int i = 0; i < N_HASHES; i++) { + big_struct.data[0] = i; + hash(&big_struct, sizeof(big_struct_t)); + } + }); + + std::cout << "Big struct (size = " << sizeof(big_struct_t) << " bytes)\n"; + std::cout << "FNV: " << time_fnv << "ms\n"; + std::cout << "Jenkins: " << time_jenkins << "ms\n"; +} + +TEST(HashTest, CollisionsComparison) { + small_struct_t small_struct = {0}; + std::unordered_set<uint32_t> hashes; + int n_collisions_fnv = 0, n_collisions_jenkins = 0, n_collisions_murmur = 0, + n_collisions_xxhash = 0; + + // FNV + for (int i = 0; i < 10 * N_HASHES; i++) { + small_struct.data[0] = i; + uint32_t h = + cumulative_hash32(&small_struct, sizeof(small_struct_t), init_val); + + if (hashes.find(h) != hashes.end()) n_collisions_fnv++; + hashes.insert(h); + } + + hashes.clear(); + + // Jenkins + for (int i = 0; i < 10 * N_HASHES; i++) { + small_struct.data[0] = i; + uint32_t h = hash(&small_struct, sizeof(small_struct_t)); + + if (hashes.find(h) != hashes.end()) n_collisions_jenkins++; + hashes.insert(h); + } + + std::cout << "Small struct (size = " << sizeof(small_struct_t) << " bytes)\n"; + std::cout << "FNV: " << n_collisions_fnv << " collision/s\n"; + std::cout << "Jenkins: " << n_collisions_jenkins << " collision/s\n"; }
\ No newline at end of file |