http-bench

commit 6ff57c9d22bff5f8d2a396c14b1e1b8a88389ea4
parent 204e7da2509223e874f1c0ee2c295ca32b82ada2
Author: Mikołaj Lenczewski <mblenczewski@gmail.com>
Date:   Mon, 12 May 2025 15:18:02 +0000

Initial fibbonaci hash to map hashes to slots

Diffstat:
M
benchmark.c
 | 
27
++++++++++++++++++++-------

1 file changed, 20 insertions(+), 7 deletions(-)
diff --git a/benchmark.c b/benchmark.c
@@ -61,7 +61,7 @@ linked_list_header_map_get(struct linked_list_header_map *const map,
 	LIST_ENTRY_ITER(&map->list, it, list_node) {
 		if (it->header.key.len != key.len)
 			continue;
-		
+
 		if (strncmp(it->header.key.ptr, key.ptr, key.len))
 			continue;
 
@@ -159,14 +159,27 @@ hashmap_header_map_init(struct hashmap_header_map *map, struct arena *arena, siz
 	hashmap_header_map_clear(map);
 }
 
+// https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/
+static inline size_t
+fibbonaci_map(size_t hash)
+{
+	const uint64_t phi_1 = 11400714819323198485llu, shift = 32;
+#if 1
+	hash ^= hash >> shift;
+	return (phi_1 * hash) >> shift;
+#else
+	return phi_1 * hash);
+#endif
+}
+
 static inline int
 hashmap_header_map_insert(struct hashmap_header_map *map, struct http_header *header)
 {
 	uint32_t hash = fnv32a(header->key.ptr, header->key.len);
 
 	for (size_t off = 0; off < map->cap; off++) {
-		size_t idx = (hash + off) % map->cap;
-		struct hashmap_header_entry *ent = &map->buckets[idx];
+		size_t idx = fibbonaci_map(hash) + off;
+		struct hashmap_header_entry *ent = &map->buckets[idx % map->cap];
 
 		// if bucket is empty, we are inserting a new value
 		if (!ent->valid) {
@@ -193,8 +206,8 @@ hashmap_header_map_get(struct hashmap_header_map *const map,
 	uint32_t hash = fnv32a(key.ptr, key.len);
 
 	for (size_t off = 0; off < map->cap; off++) {
-		size_t idx = (hash + off) % map->cap;
-		struct hashmap_header_entry *ent = &map->buckets[idx];
+		size_t idx = fibbonaci_map(hash) + off;
+		struct hashmap_header_entry *ent = &map->buckets[idx % map->cap];
 
 		// if bucket is empty, we have failed to find our key
 		if (!ent->valid)
@@ -301,7 +314,7 @@ benchmark_stats_add_round(struct benchmark_stats *stats,
 
 	stats->total_ns += round_ns;
 	stats->rounds++;
-	
+
 	if (round_ns < stats->min_ns_per_round)
 		stats->min_ns_per_round = round_ns;
 
@@ -351,7 +364,7 @@ main(int argc, char **argv)
 	struct benchmark_stats insert_stats, get_stats;
 	int benchmark_clock_source = CLOCK_MONOTONIC;
 
-	float hashmap_target_load_factor = 0.75;
+	float hashmap_target_load_factor = 1;
 
 	// test linked list
 	{