http-bench

commit ea82da190a78a7c53b8d04886c4e5f56c033d683
parent 6ff57c9d22bff5f8d2a396c14b1e1b8a88389ea4
Author: Mikołaj Lenczewski <mblenczewski@gmail.com>
Date:   Mon, 12 May 2025 15:49:32 +0000

Support 64-bit hashes

Diffstat:
M
benchmark.c
 | 
29
++++++++++++++++++++---------
M
hash.h
 | 
15
++++++++++++++-

2 files changed, 34 insertions(+), 10 deletions(-)
diff --git a/benchmark.c b/benchmark.c
@@ -12,6 +12,8 @@
 #include "http.h"
 #include "hash.h"
 
+#define HASHMAP_64BIT_HASH 0
+
 // ===========================================================================
 
 struct linked_list_header_entry {
@@ -131,8 +133,8 @@ array_header_map_get(struct array_header_map *const map,
 }
 
 struct hashmap_header_entry {
-	uint32_t hash;
-	int32_t valid;
+	uint64_t hash;
+	int64_t valid;
 	struct http_header header;
 };
 
@@ -163,19 +165,24 @@ hashmap_header_map_init(struct hashmap_header_map *map, struct arena *arena, siz
 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;
+	const uint64_t phi_1 = 11400714819323198485llu;
+
+#if HASHMAP_64BIT_HASH
+	hash ^= hash >> 63;
+	return (phi_1 * hash) >> 63;
 #else
-	return phi_1 * hash);
+	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);
+#if HASHMAP_64BIT_HASH
+	size_t hash = fnv64a(header->key.ptr, header->key.len);
+#else
+	size_t hash = fnv32a(header->key.ptr, header->key.len);
+#endif
 
 	for (size_t off = 0; off < map->cap; off++) {
 		size_t idx = fibbonaci_map(hash) + off;
@@ -203,7 +210,11 @@ static inline int
 hashmap_header_map_get(struct hashmap_header_map *const map,
 		       struct str key, struct http_header *out)
 {
-	uint32_t hash = fnv32a(key.ptr, key.len);
+#if HASHMAP_64BIT_HASH
+	size_t hash = fnv64a(key.ptr, key.len);
+#else
+	size_t hash = fnv32a(key.ptr, key.len);
+#endif
 
 	for (size_t off = 0; off < map->cap; off++) {
 		size_t idx = fibbonaci_map(hash) + off;
diff --git a/hash.h b/hash.h
@@ -4,7 +4,7 @@
 #include <stdint.h>
 
 static inline uint32_t
-fnv32a(void const * buf, size_t len)
+fnv32a(void const *buf, size_t len)
 {
 	// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV_hash_parameters
 	uint32_t hash = 0x811C9DC5, prime = 0x01000193;
@@ -16,4 +16,17 @@ fnv32a(void const * buf, size_t len)
 	return hash;
 }
 
+static inline uint64_t
+fnv64a(void const *buf, size_t len)
+{
+	// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV_hash_parameters
+	uint64_t hash = 0xcbf29ce484222325, prime = 0x00000100000001b3;
+
+	unsigned char const *ptr = buf, *end = ptr + len;
+	while (ptr < end)
+		hash = (hash ^ *ptr++) * prime;
+
+	return hash;
+}
+
 #endif /* HASH_H */