maph 1.0.0 High-Performance Memory-Mapped Key-Value Database with O(1) Lookups

Loading...
Searching...
No Matches
maph_fast.hpp
Go to the documentation of this file.
1
9#pragma once
10
11#include <sys/mman.h>
12#include <fcntl.h>
13#include <unistd.h>
14#include <cstring>
15#include <atomic>
16
17 namespace maph {
18
19// Slot stores the hash that perfect hash already computed
20 struct alignas(64) FastSlot {
21 std::atomic<uint64_t> hash_and_version{0}; // High 32: hash, Low 32: version
22 uint32_t size{0};
23 char value[500]{};
24
25 static constexpr uint64_t EMPTY = 0;
26
27 // Extract hash and version from packed field (no branches!)
28 uint32_t get_hash() const {
29 return hash_and_version.load() >> 32;
30 }
31
32 uint32_t get_version() const {
33 return hash_and_version.load() & 0xFFFFFFFF;
34 }
35
36 void set_hash_version(uint32_t hash, uint32_t version) {
37 hash_and_version.store((uint64_t(hash) << 32) | version);
38 }
39
40 bool is_empty() const {
41 return hash_and_version.load() < (1ULL << 32); // Hash part is 0
42 }
43};
44
45 static_assert(sizeof(FastSlot) == 512);
46
51 template<typename Key>
52 struct PerfectHashWithHash {
53 struct Result {
54 uint32_t hash; // The hash we computed
55 uint32_t index; // The perfect hash index
56 };
57
58 Result operator()(const Key& key, size_t num_slots) const {
59 // Step 1: Compute hash ONCE
60 uint32_t h = compute_hash(key);
61
62 // Step 2: Perfect hash function (simplified)
63 // In practice, use RecSplit or similar
64 uint32_t idx = (h * 0x9E3779B9) % num_slots; // Golden ratio hash
65
66 return {h, idx};
67 }
68
69 private:
70 static uint32_t compute_hash(const Key& key) {
71 // FNV-1a or xxHash - FAST hash
72 if constexpr (std::is_same_v<Key, std::string>) {
73 uint32_t h = 2166136261u;
74 for (char c : key) {
75 h ^= uint8_t(c);
76 h *= 16777619u;
77 }
78 return h;
79 } else {
80 return std::hash<Key>{}(key);
81 }
82 }
83};
84
85 class FastMaph {
86 private:
87 void* mapped_{nullptr};
88 size_t file_size_{0};
89 FastSlot* slots_{nullptr};
90 size_t num_slots_{0};
91 bool readonly_{false};
92
93 PerfectHashWithHash<std::string> hasher_;
94
95 public:
96 static std::unique_ptr<FastMaph> create(const std::string& path,
97 size_t num_slots) {
98 auto m = std::make_unique<FastMaph>();
99
100 size_t file_size = num_slots * sizeof(FastSlot);
101
102 int fd = ::open(path.c_str(), O_RDWR | O_CREAT | O_TRUNC, 0666);
103 if (fd < 0) return nullptr;
104
105 if (ftruncate(fd, file_size) < 0) {
106 ::close(fd);
107 return nullptr;
108 }
109
110 void* mapped = mmap(nullptr, file_size, PROT_READ | PROT_WRITE,
111 MAP_SHARED | MAP_POPULATE, fd, 0); // MAP_POPULATE prefaults pages
112 if (mapped == MAP_FAILED) {
113 ::close(fd);
114 return nullptr;
115 }
116
117 // Zero out (OS might do this but be sure)
118 memset(mapped, 0, file_size);
119
120 ::close(fd); // Can close fd after mmap
121
122 m->mapped_ = mapped;
123 m->file_size_ = file_size;
124 m->slots_ = static_cast<FastSlot*>(mapped);
125 m->num_slots_ = num_slots;
126
127 return m;
128 }
129
130 // ===== ULTRA FAST GET - Hash computed ONCE =====
131 std::string get(const std::string& key) const {
132 // Perfect hash gives us BOTH hash and index
133 auto [hash, index] = hasher_(key, num_slots_);
134
135 const FastSlot& slot = slots_[index];
136
137 // Single comparison - hash already there!
138 if (slot.get_hash() == hash) {
139 return std::string(slot.value, slot.size);
140 }
141
142 return ""; // Not found
143 }
144
145 // ===== ULTRA FAST SET - Reuse computed hash =====
146 bool set(const std::string& key, const std::string& value) {
147 if (readonly_ || value.size() > 500) return false;
148
149 // Perfect hash gives us BOTH hash and index
150 auto [hash, index] = hasher_(key, num_slots_);
151
152 FastSlot& slot = slots_[index];
153
154 // Atomic update with hash we already have
155 uint32_t version = slot.get_version();
156 slot.set_hash_version(hash, version + 1);
157
158 slot.size = value.size();
159 memcpy(slot.value, value.data(), value.size());
160
161 slot.set_hash_version(hash, version + 2);
162
163 return true;
164 }
165
166 // ===== For dynamic adds - probe with hash we have =====
167 bool dynamic_set(const std::string& key, const std::string& value) {
168 if (readonly_ || value.size() > 500) return false;
169
170 // Compute hash ONCE
171 auto [hash, start_index] = hasher_(key, num_slots_);
172
173 // Linear probe - but we already have the hash!
174 for (size_t i = 0; i < 10; ++i) {
175 size_t index = (start_index + i) % num_slots_;
176 FastSlot& slot = slots_[index];
177
178 uint32_t slot_hash = slot.get_hash();
179
180 // Empty or same key - use it
181 if (slot_hash == 0 || slot_hash == hash) {
182 uint32_t version = slot.get_version();
183 slot.set_hash_version(hash, version + 1);
184
185 slot.size = value.size();
186 memcpy(slot.value, value.data(), value.size());
187
188 slot.set_hash_version(hash, version + 2);
189 return true;
190 }
191 }
192
193 return false; // No slot found
194 }
195
196 // ===== Batch operations with hash reuse =====
197 void batch_set(const std::vector<std::pair<std::string, std::string>>& kvs) {
198 for (const auto& [key, value] : kvs) {
199 // Hash computed once per key
200 auto [hash, index] = hasher_(key, num_slots_);
201
202 FastSlot& slot = slots_[index];
203
204 // Super fast update - no redundant hashing
205 uint32_t version = slot.get_version();
206 slot.set_hash_version(hash, version + 1);
207 slot.size = value.size();
208 memcpy(slot.value, value.data(), value.size());
209 slot.set_hash_version(hash, version + 2);
210 }
211 }
212
213 // ===== Zero-copy iteration =====
214 template<typename Callback>
215 void scan(Callback&& cb) const {
216 for (size_t i = 0; i < num_slots_; ++i) {
217 const FastSlot& slot = slots_[i];
218 if (!slot.is_empty()) {
219 // We have the hash right there!
220 cb(slot.get_hash(), std::string_view(slot.value, slot.size));
221 }
222 }
223 }
224
225 ~FastMaph() {
226 if (mapped_) {
227 munmap(mapped_, file_size_);
228 }
229 }
230};
231
232// ===== BENCHMARK: Show the speed =====
233 inline void benchmark_hash_reuse() {
234 auto m = FastMaph::create("bench.maph", 1000000);
235
236 // Test data
237 std::vector<std::pair<std::string, std::string>> data;
238 for (int i = 0; i < 100000; ++i) {
239 data.push_back({
240 "key_" + std::to_string(i),
241 "value_" + std::to_string(i)
242 });
243 }
244
245 auto start = std::chrono::high_resolution_clock::now();
246
247 // Batch insert - hash computed ONCE per key
248 m->batch_set(data);
249
250 auto end = std::chrono::high_resolution_clock::now();
251 auto ns = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);
252
253 std::cout << "Inserts with hash reuse: "
254 << (data.size() * 1e9 / ns.count()) / 1e6
255 << " M ops/sec\n";
256
257 // Now benchmark gets
258 start = std::chrono::high_resolution_clock::now();
259
260 for (int iter = 0; iter < 10; ++iter) {
261 for (const auto& [key, _] : data) {
262 volatile auto result = m->get(key);
263 }
264 }
265
266 end = std::chrono::high_resolution_clock::now();
267 ns = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);
268
269 std::cout << "Gets with hash reuse: "
270 << (data.size() * 10 * 1e9 / ns.count()) / 1e6
271 << " M ops/sec\n";
272}
273
274} // namespace maph
maph::FastMaph
Definition maph_fast.hpp:85
maph::FastMaph::batch_set
void batch_set(const std::vector< std::pair< std::string, std::string > > &kvs)
Definition maph_fast.hpp:197
maph::FastMaph::dynamic_set
bool dynamic_set(const std::string &key, const std::string &value)
Definition maph_fast.hpp:167
maph::FastMaph::get
std::string get(const std::string &key) const
Definition maph_fast.hpp:131
maph::FastMaph::scan
void scan(Callback &&cb) const
Definition maph_fast.hpp:215
maph::FastMaph::create
static std::unique_ptr< FastMaph > create(const std::string &path, size_t num_slots)
Definition maph_fast.hpp:96
maph::FastMaph::~FastMaph
~FastMaph()
Definition maph_fast.hpp:225
maph::FastMaph::set
bool set(const std::string &key, const std::string &value)
Definition maph_fast.hpp:146
maph
Definition maph.hpp:46
maph::open
auto open(const std::string &path)
Definition maph.hpp:958
maph::benchmark_hash_reuse
void benchmark_hash_reuse()
Definition maph_fast.hpp:233
maph::FastSlot
Definition maph_fast.hpp:20
maph::FastSlot::get_hash
uint32_t get_hash() const
Definition maph_fast.hpp:28
maph::FastSlot::value
char value[500]
Definition maph_fast.hpp:23
maph::FastSlot::is_empty
bool is_empty() const
Definition maph_fast.hpp:40
maph::FastSlot::size
uint32_t size
Definition maph_fast.hpp:22
maph::FastSlot::get_version
uint32_t get_version() const
Definition maph_fast.hpp:32
maph::FastSlot::EMPTY
static constexpr uint64_t EMPTY
Definition maph_fast.hpp:25
maph::FastSlot::hash_and_version
std::atomic< uint64_t > hash_and_version
Definition maph_fast.hpp:21
maph::FastSlot::set_hash_version
void set_hash_version(uint32_t hash, uint32_t version)
Definition maph_fast.hpp:36
maph::PerfectHashWithHash
Perfect hash that RETURNS BOTH hash and index This way we compute hash once and reuse it.
Definition maph_fast.hpp:52
maph::PerfectHashWithHash::Result::hash
uint32_t hash
Definition maph_fast.hpp:54
maph::PerfectHashWithHash::operator()
Result operator()(const Key &key, size_t num_slots) const
Definition maph_fast.hpp:58
maph::PerfectHashWithHash::Result::index
uint32_t index
Definition maph_fast.hpp:55
maph::PerfectHashWithHash::Result
Definition maph_fast.hpp:53