From 57da910f0f257f47b7d07739b231da1d502a4096 Mon Sep 17 00:00:00 2001 From: Fabrice Date: Mon, 13 Apr 2026 10:23:24 +0200 Subject: benchmarks adding unordered_map vs. cheesemap bench adds tidwall's hashmap adds abseil bench plotting the results --- benches/bench_common.hpp | 543 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 543 insertions(+) create mode 100644 benches/bench_common.hpp (limited to 'benches/bench_common.hpp') diff --git a/benches/bench_common.hpp b/benches/bench_common.hpp new file mode 100644 index 0000000..732ffb4 --- /dev/null +++ b/benches/bench_common.hpp @@ -0,0 +1,543 @@ +#ifndef CHEESEMAP_BENCH_COMMON_HPP +#define CHEESEMAP_BENCH_COMMON_HPP + +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "cheesemap.h" +#include "tidwall/hashmap.h" +#include "absl/container/flat_hash_map.h" + +namespace cmbench { + +inline constexpr std::int64_t kEntryCount = 1'000'000; +inline constexpr std::string_view kProtocolVersion = "1"; +inline constexpr std::string_view kDatasetVersion = "1"; +inline constexpr std::string_view kHashQuality = "good"; +inline constexpr std::string_view kHashName = "xxh_avalanche"; + +[[noreturn]] inline void panic_impl(const char* file, cm_u32 line, + const char* fmt, ...) { + std::fprintf(stderr, "panic at %s:%u: ", file, line); + va_list args; + va_start(args, fmt); + std::vfprintf(stderr, fmt, args); + va_end(args); + std::fputc('\n', stderr); + std::abort(); +} + +inline cm_u8* default_alloc(cm_usize size, cm_usize align, cm_u8* user) { + (void)user; + return static_cast(std::aligned_alloc(align, size)); +} + +inline void default_dealloc(cm_u8* ptr, cm_u8* user) { + (void)user; + std::free(ptr); +} + +inline std::uint64_t rotl64(std::uint64_t x, unsigned bits) { + return (x << bits) | (x >> (64 - bits)); +} + +inline std::uint64_t xxh64_avalanche(std::uint64_t x) { + x ^= x >> 33; + x *= 0xc2b2ae3d27d4eb4fULL; + x ^= x >> 29; + x *= 0x165667b19e3779f9ULL; + x ^= x >> 32; + return x; +} + +template +inline std::array as_words(const T& value) { + static_assert(std::is_trivially_copyable_v); + std::array words{}; + std::memcpy(words.data(), &value, sizeof(T)); + return words; +} + +template +inline std::uint64_t hash_xxh_avalanche(const T& value) { + auto words = as_words(value); + std::uint64_t acc = 0x165667b19e3779f9ULL ^ sizeof(T); + for (std::uint64_t word : words) { + acc += word * 0x9e3779b185ebca87ULL; + acc = rotl64(acc, 31); + acc *= 0xc2b2ae3d27d4eb4fULL; + } + return xxh64_avalanche(acc); +} + +template +inline bool byte_equal(const T& lhs, const T& rhs) { + static_assert(std::is_trivially_copyable_v); + return std::memcmp(&lhs, &rhs, sizeof(T)) == 0; +} + +struct ScalarValue { + std::uint64_t value; +}; + +struct EntityId { + std::uint32_t index; + std::uint32_t generation; +}; + +struct ComponentPayload { + float position[3]; + float velocity[3]; + std::uint32_t archetype; + std::uint32_t chunk; +}; + +struct ComponentKey { + std::uint64_t archetype_mask; + std::uint32_t component_id; + std::uint32_t chunk; + std::uint32_t row; + std::uint32_t generation; +}; + +struct ComponentMeta { + std::uint64_t entity_mask; + std::uint32_t dense_index; + std::uint32_t sparse_index; + std::uint64_t version; +}; + +template +struct Workload { + std::vector keys; + std::vector miss_keys; + std::vector values; +}; + +template +inline void shuffle_keys(std::vector& keys, std::mt19937_64& rng) { + std::shuffle(keys.begin(), keys.end(), rng); +} + +inline Workload make_scalar_workload( + std::size_t count) { + Workload workload{ + .keys = std::vector(count), + .miss_keys = std::vector(count), + .values = std::vector(count), + }; + + std::mt19937_64 rng(0xc0ffee5eedULL); + for (std::size_t i = 0; i < count; ++i) { + workload.keys[i] = xxh64_avalanche(i + 1); + workload.miss_keys[i] = xxh64_avalanche(i + 1 + count); + workload.values[i] = + ScalarValue{xxh64_avalanche(i ^ 0x123456789abcdef0ULL)}; + } + shuffle_keys(workload.keys, rng); + shuffle_keys(workload.miss_keys, rng); + return workload; +} + +inline Workload make_entity_workload( + std::size_t count) { + Workload workload{ + .keys = std::vector(count), + .miss_keys = std::vector(count), + .values = std::vector(count), + }; + + std::mt19937_64 rng(0xEC500123ULL); + for (std::size_t i = 0; i < count; ++i) { + workload.keys[i] = EntityId{static_cast(i), + static_cast(i >> 12)}; + workload.miss_keys[i] = EntityId{static_cast(i), + static_cast((i >> 12) + 1)}; + + float base = static_cast(i & 0xffff); + workload.values[i] = ComponentPayload{ + .position = {base + 0.1f, base + 0.2f, base + 0.3f}, + .velocity = {base + 1.1f, base + 1.2f, base + 1.3f}, + .archetype = static_cast(xxh64_avalanche(i) & 0xffff), + .chunk = static_cast(i / 64), + }; + } + shuffle_keys(workload.keys, rng); + shuffle_keys(workload.miss_keys, rng); + return workload; +} + +inline Workload make_component_workload( + std::size_t count) { + Workload workload{ + .keys = std::vector(count), + .miss_keys = std::vector(count), + .values = std::vector(count), + }; + + std::mt19937_64 rng(0xA11CECC5ULL); + for (std::size_t i = 0; i < count; ++i) { + std::uint64_t archetype = xxh64_avalanche(i * 0x9e3779b97f4a7c15ULL); + workload.keys[i] = ComponentKey{ + .archetype_mask = archetype, + .component_id = static_cast((i * 17) & 0xffff), + .chunk = static_cast(i / 64), + .row = static_cast(i % 64), + .generation = static_cast(i >> 10), + }; + workload.miss_keys[i] = ComponentKey{ + .archetype_mask = archetype ^ 0xfeedfacecafebeefULL, + .component_id = static_cast((i * 17) & 0xffff), + .chunk = static_cast(i / 64), + .row = static_cast(i % 64), + .generation = static_cast(i >> 10), + }; + workload.values[i] = ComponentMeta{ + .entity_mask = xxh64_avalanche(i + 7), + .dense_index = static_cast(i), + .sparse_index = + static_cast(xxh64_avalanche(i) & 0xffffffffU), + .version = xxh64_avalanche(i ^ 0xabcdef01ULL), + }; + } + shuffle_keys(workload.keys, rng); + shuffle_keys(workload.miss_keys, rng); + return workload; +} + +inline const Workload& scalar_workload() { + static const auto workload = make_scalar_workload(kEntryCount); + return workload; +} + +inline const Workload& entity_workload() { + static const auto workload = make_entity_workload(kEntryCount); + return workload; +} + +inline const Workload& component_workload() { + static const auto workload = make_component_workload(kEntryCount); + return workload; +} + +template +inline cm_hash_t cheesemap_hash_adapter(const cm_u8* key, cm_u8* user) { + (void)user; + return hash_xxh_avalanche(*reinterpret_cast(key)); +} + +template +inline bool cheesemap_equal_adapter(const cm_u8* lhs, const cm_u8* rhs, + cm_u8* user) { + (void)user; + return byte_equal(*reinterpret_cast(lhs), + *reinterpret_cast(rhs)); +} + +struct Meta { + std::string_view implementation; + std::string_view language; + std::string_view dataset; + std::string_view workload_category; +}; + +inline void set_common_metadata(benchmark::State& state, const Meta& meta) { + std::string label; + label.reserve(128); + label.append("implementation="); + label.append(meta.implementation); + label.append(",language="); + label.append(meta.language); + label.append(",dataset="); + label.append(meta.dataset); + label.append(",workload="); + label.append(meta.workload_category); + label.append(",hash_quality="); + label.append(kHashQuality); + label.append(",hash="); + label.append(kHashName); + label.append(",protocol="); + label.append(kProtocolVersion); + label.append(",dataset_version="); + label.append(kDatasetVersion); + state.SetLabel(label); + state.counters["entry_count"] = + benchmark::Counter(static_cast(kEntryCount)); +} + +template +struct CheesemapAdapter { + cheesemap map; + + CheesemapAdapter() { + cm_init(&map, sizeof(Key), alignof(Key), sizeof(Value), alignof(Value), + nullptr, cheesemap_hash_adapter, cheesemap_equal_adapter, + default_alloc, default_dealloc); + } + + ~CheesemapAdapter() { cm_drop(&map); } + + CheesemapAdapter(const CheesemapAdapter&) = delete; + CheesemapAdapter& operator=(const CheesemapAdapter&) = delete; + + void reserve(std::size_t count) { + if (!cm_reserve(&map, count)) + panic_impl(__FILE__, __LINE__, "reserve failed"); + } + + void insert(const Key& key, const Value& value) { + if (!cm_insert(&map, reinterpret_cast(&key), + reinterpret_cast(&value))) { + panic_impl(__FILE__, __LINE__, "insert failed"); + } + } + + Value* lookup_hit(const Key& key) { + cm_u8* value_ptr = nullptr; + if (!cm_lookup(&map, reinterpret_cast(&key), &value_ptr)) + panic_impl(__FILE__, __LINE__, "lookup hit failed"); + return reinterpret_cast(value_ptr); + } + + void lookup_miss(const Key& key) { + cm_u8* value_ptr = nullptr; + if (cm_lookup(&map, reinterpret_cast(&key), &value_ptr)) + panic_impl(__FILE__, __LINE__, "lookup miss failed"); + benchmark::DoNotOptimize(value_ptr); + } + + void erase(const Key& key) { + if (!cm_remove(&map, reinterpret_cast(&key), nullptr)) + panic_impl(__FILE__, __LINE__, "erase failed"); + } +}; + +template +struct UnorderedHashAdapter { + std::size_t operator()(const Key& key) const noexcept { + return static_cast(hash_xxh_avalanche(key)); + } +}; + +template +struct UnorderedEqualAdapter { + bool operator()(const Key& lhs, const Key& rhs) const noexcept { + return byte_equal(lhs, rhs); + } +}; + +template +struct UnorderedMapAdapter { + using Map = std::unordered_map, + UnorderedEqualAdapter>; + + Map map; + + void reserve(std::size_t count) { map.reserve(count); } + + void insert(const Key& key, const Value& value) { + map.insert_or_assign(key, value); + } + + Value* lookup_hit(const Key& key) { + auto it = map.find(key); + if (it == map.end()) panic_impl(__FILE__, __LINE__, "lookup hit failed"); + return &it->second; + } + + void lookup_miss(const Key& key) { + auto it = map.find(key); + if (it != map.end()) panic_impl(__FILE__, __LINE__, "lookup miss failed"); + benchmark::DoNotOptimize(it); + } + + void erase(const Key& key) { + if (map.erase(key) != 1) panic_impl(__FILE__, __LINE__, "erase failed"); + } +}; + +template +struct TidwallEntry { + Key key; + Value value; +}; + +template +struct TidwallAdapter { + using Entry = TidwallEntry; + + hashmap* map = nullptr; + + static std::uint64_t hash_entry(const void* item, std::uint64_t seed0, + std::uint64_t seed1) { + (void)seed0; + (void)seed1; + const auto* entry = static_cast(item); + return hash_xxh_avalanche(entry->key); + } + + static int compare_entry(const void* lhs, const void* rhs, void* udata) { + (void)udata; + const auto* left = static_cast(lhs); + const auto* right = static_cast(rhs); + return byte_equal(left->key, right->key) ? 0 : 1; + } + + TidwallAdapter() { + map = hashmap_new(sizeof(Entry), static_cast(kEntryCount), 0, + 0, hash_entry, compare_entry, nullptr, nullptr); + if (map == nullptr) panic_impl(__FILE__, __LINE__, "hashmap_new failed"); + } + + ~TidwallAdapter() { + if (map != nullptr) hashmap_free(map); + } + + TidwallAdapter(const TidwallAdapter&) = delete; + TidwallAdapter& operator=(const TidwallAdapter&) = delete; + + void reserve(std::size_t count) { benchmark::DoNotOptimize(count); } + + void insert(const Key& key, const Value& value) { + const Entry entry{key, value}; + if (hashmap_set(map, &entry) == nullptr && hashmap_oom(map)) + panic_impl(__FILE__, __LINE__, "insert failed"); + } + + Value* lookup_hit(const Key& key) { + const Entry query{key, Value{}}; + auto* found = static_cast(hashmap_get(map, &query)); + if (found == nullptr) panic_impl(__FILE__, __LINE__, "lookup hit failed"); + return const_cast(&found->value); + } + + void lookup_miss(const Key& key) { + const Entry query{key, Value{}}; + auto* found = static_cast(hashmap_get(map, &query)); + if (found != nullptr) panic_impl(__FILE__, __LINE__, "lookup miss failed"); + benchmark::DoNotOptimize(found); + } + + void erase(const Key& key) { + const Entry query{key, Value{}}; + if (hashmap_delete(map, &query) == nullptr) + panic_impl(__FILE__, __LINE__, "erase failed"); + } +}; + +template +struct AbseilAdapter { + using Map = absl::flat_hash_map, + UnorderedEqualAdapter>; + + Map map; + + void reserve(std::size_t count) { map.reserve(count); } + + void insert(const Key& key, const Value& value) { + map.insert_or_assign(key, value); + } + + Value* lookup_hit(const Key& key) { + auto it = map.find(key); + if (it == map.end()) panic_impl(__FILE__, __LINE__, "lookup hit failed"); + return &it->second; + } + + void lookup_miss(const Key& key) { + auto it = map.find(key); + if (it != map.end()) panic_impl(__FILE__, __LINE__, "lookup miss failed"); + benchmark::DoNotOptimize(it); + } + + void erase(const Key& key) { + if (map.erase(key) != 1) panic_impl(__FILE__, __LINE__, "erase failed"); + } +}; + +template +inline void fill_container(Adapter& adapter, + const Workload& workload) { + adapter.reserve(workload.keys.size()); + for (std::size_t i = 0; i < workload.keys.size(); ++i) + adapter.insert(workload.keys[i], workload.values[i]); +} + +template +inline void bench_insert(benchmark::State& state, + const Workload& workload, + const Meta& meta) { + set_common_metadata(state, meta); + for (auto _ : state) { + Adapter adapter; + fill_container(adapter, workload); + benchmark::ClobberMemory(); + } +} + +template +inline void bench_lookup_hit(benchmark::State& state, + const Workload& workload, + const Meta& meta) { + set_common_metadata(state, meta); + for (auto _ : state) { + state.PauseTiming(); + Adapter adapter; + fill_container(adapter, workload); + state.ResumeTiming(); + + for (const Key& key : workload.keys) { + Value* value_ptr = adapter.lookup_hit(key); + benchmark::DoNotOptimize(value_ptr); + } + benchmark::ClobberMemory(); + } +} + +template +inline void bench_lookup_miss(benchmark::State& state, + const Workload& workload, + const Meta& meta) { + set_common_metadata(state, meta); + for (auto _ : state) { + state.PauseTiming(); + Adapter adapter; + fill_container(adapter, workload); + state.ResumeTiming(); + + for (const Key& key : workload.miss_keys) adapter.lookup_miss(key); + benchmark::ClobberMemory(); + } +} + +template +inline void bench_erase(benchmark::State& state, + const Workload& workload, + const Meta& meta) { + set_common_metadata(state, meta); + for (auto _ : state) { + state.PauseTiming(); + Adapter adapter; + fill_container(adapter, workload); + state.ResumeTiming(); + + for (const Key& key : workload.keys) adapter.erase(key); + benchmark::ClobberMemory(); + } +} + +} // namespace cmbench + +#endif -- cgit v1.2.3