commit 29046f6f3dccac7a6033556e1e40ed2afc304911
Author: Mikołaj Lenczewski <mblenczewski@gmail.com>
Date: Mon, 12 May 2025 14:09:15 +0000
Initial commit
Diffstat:
| A | .editorconfig | | | 17 | +++++++++++++++++ |
| A | .gitignore | | | 3 | +++ |
| A | LICENSE | | | 18 | ++++++++++++++++++ |
| A | README | | | 4 | ++++ |
| A | arena.h | | | 46 | ++++++++++++++++++++++++++++++++++++++++++++++ |
| A | benchmark.c | | | 472 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | build.sh | | | 10 | ++++++++++ |
| A | clean.sh | | | 5 | +++++ |
| A | hash.h | | | 19 | +++++++++++++++++++ |
| A | http.h | | | 16 | ++++++++++++++++ |
| A | list.h | | | 88 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
11 files changed, 698 insertions(+), 0 deletions(-)
diff --git a/.editorconfig b/.editorconfig
@@ -0,0 +1,17 @@
+root = true
+
+[*]
+end_of_line = lf
+insert_final_newline = true
+trim_trailing_whitespace = true
+charset = utf-8
+
+guidelines = 80, 120, 160
+
+[*.{c,h}]
+indent_style = tab
+indent_size = 8
+
+[*.{md,txt}]
+indent_style = space
+indent_size = 2
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,3 @@
+bin/
+
+**/.*.swp
diff --git a/LICENSE b/LICENSE
@@ -0,0 +1,18 @@
+The MIT-Zero License
+
+Copyright (c) 2025 Mikołaj Lenczewski <mikolaj@lenczewski.org>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/README b/README
@@ -0,0 +1,4 @@
+http-bench
+==============================================================================
+A simple test program to benchmark a few ways of handling parsed http headers.
+Basically, benchmarking a linked list v.s. an array v.s. a hashmap.
diff --git a/arena.h b/arena.h
@@ -0,0 +1,46 @@
+#ifndef ARENA_H
+#define ARENA_H
+
+#include <stdalign.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#define IS_POWER_OF_2(v) (((v) & ((v) - 1)) == 0)
+
+#define IS_ALIGNED(v, align) (((v) & ((align) - 1)) == 0)
+#define ALIGN_PREV(v, align) ((v) & ~((align) - 1))
+#define ALIGN_NEXT(v, align) ALIGN_PREV(((v) + ((align) - 1)), (align))
+
+struct arena {
+ void *ptr;
+ size_t cap, len;
+};
+
+static inline void
+arena_reset(struct arena *arena)
+{
+ arena->len = 0;
+}
+
+static inline void *
+arena_alloc(struct arena *arena, size_t size, size_t alignment)
+{
+ uintptr_t cur_ptr = (uintptr_t) arena->ptr + arena->len;
+ uintptr_t end_ptr = (uintptr_t) arena->ptr + arena->cap;
+
+ uintptr_t aligned_ptr = ALIGN_NEXT(cur_ptr, alignment);
+ if (end_ptr < aligned_ptr + size)
+ return NULL;
+
+ arena->len = (aligned_ptr + size) - (uintptr_t) arena->ptr;
+
+ return (void *) aligned_ptr;
+}
+
+#define ARENA_ALLOC_ARRAY(arena, T, n) \
+ arena_alloc((arena), sizeof(T) * (n), alignof(T))
+
+#define ARENA_ALLOC_SIZED(arena, T) \
+ ARENA_ALLOC_ARRAY((arena), T, 1)
+
+#endif /* ARENA_H */
diff --git a/benchmark.c b/benchmark.c
@@ -0,0 +1,472 @@
+#define _XOPEN_SOURCE 700
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+
+#include "arena.h"
+#include "list.h"
+#include "http.h"
+#include "hash.h"
+
+// ===========================================================================
+
+struct linked_list_header_entry {
+ struct http_header header;
+ struct list_node list_node;
+};
+
+struct linked_list_header_map {
+ struct list_node list;
+ struct arena *arena;
+};
+
+static inline void
+linked_list_header_map_clear(struct linked_list_header_map *map)
+{
+ map->list = LIST_INIT(map->list);
+ arena_reset(map->arena);
+}
+
+static inline void
+linked_list_header_map_init(struct linked_list_header_map *map, struct arena *arena)
+{
+ map->arena = arena;
+
+ linked_list_header_map_clear(map);
+}
+
+static inline int
+linked_list_header_map_insert(struct linked_list_header_map *map, struct http_header *header)
+{
+ struct linked_list_header_entry *ent = ARENA_ALLOC_SIZED(map->arena, struct linked_list_header_entry);
+ if (!ent) return -1;
+
+ ent->header = *header;
+ ent->list_node.prev = ent->list_node.next = NULL;
+
+ list_push_tail(&map->list, &ent->list_node);
+
+ return 0;
+}
+
+static inline int
+linked_list_header_map_get(struct linked_list_header_map *const map,
+ struct str key, struct http_header *out)
+{
+ struct linked_list_header_entry *it;
+ 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;
+
+ *out = it->header;
+ return 0;
+ }
+
+ return -1;
+}
+
+struct array_header_entry {
+ struct http_header header;
+};
+
+struct array_header_map {
+ struct array_header_entry *arr;
+ size_t cap, len;
+};
+
+static inline void
+array_header_map_clear(struct array_header_map *map)
+{
+ map->len = 0;
+}
+
+static inline void
+array_header_map_init(struct array_header_map *map, struct arena *arena, size_t cap)
+{
+ arena_reset(arena);
+ map->arr = ARENA_ALLOC_ARRAY(arena, struct array_header_entry, cap);
+ assert(map->arr);
+
+ map->cap = cap;
+
+ array_header_map_clear(map);
+}
+
+static inline int
+array_header_map_insert(struct array_header_map *map, struct http_header *header)
+{
+ if (map->len == map->cap) return -1;
+
+ struct array_header_entry *ent = &map->arr[map->len++];
+ ent->header = *header;
+
+ return 0;
+}
+
+static inline int
+array_header_map_get(struct array_header_map *const map,
+ struct str key, struct http_header *out)
+{
+ for (size_t i = 0; i < map->len; i++) {
+ struct array_header_entry *ent = &map->arr[i];
+
+ if (ent->header.key.len != key.len)
+ continue;
+
+ if (strncmp(ent->header.key.ptr, key.ptr, key.len))
+ continue;
+
+ *out = ent->header;
+ return 0;
+ }
+
+ return -1;
+}
+
+struct hashmap_header_entry {
+ uint32_t hash;
+ int32_t valid;
+ struct http_header header;
+};
+
+struct hashmap_header_map {
+ struct hashmap_header_entry *buckets;
+ size_t cap;
+};
+
+static inline void
+hashmap_header_map_clear(struct hashmap_header_map *map)
+{
+ memset(map->buckets, 0, sizeof *map->buckets * map->cap);
+}
+
+static inline void
+hashmap_header_map_init(struct hashmap_header_map *map, struct arena *arena, size_t cap)
+{
+ arena_reset(arena);
+ map->buckets = ARENA_ALLOC_ARRAY(arena, struct hashmap_header_entry, cap);
+ assert(map->buckets);
+
+ map->cap = cap;
+
+ hashmap_header_map_clear(map);
+}
+
+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];
+
+ // if bucket is empty, we are inserting a new value
+ if (!ent->valid) {
+ ent->hash = hash;
+ ent->valid = 1;
+ ent->header = *header;
+ return 0;
+ }
+
+ // if our hash matches, we are inserting a duplicate value
+ if (ent->hash == hash)
+ return 0;
+
+ // if our hash does not match, check next bucket
+ }
+
+ return -1;
+}
+
+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);
+
+ for (size_t off = 0; off < map->cap; off++) {
+ size_t idx = (hash + off) % map->cap;
+ struct hashmap_header_entry *ent = &map->buckets[idx];
+
+ // if bucket is empty, we have failed to find our key
+ if (!ent->valid)
+ return -1;
+
+ // if our hash matches, we have found our key
+ if (ent->hash == hash) {
+ *out = ent->header;
+ return 0;
+ }
+
+ // if our hash does not match, check next bucket
+ }
+
+ return -1;
+}
+
+// ===========================================================================
+
+#define HTTP_HEADER(key, val) \
+ ((struct http_header) { { (key), strlen((key)), }, { (val), strlen((val)), }, })
+
+static struct http_header http_headers[] = {
+ // common headers
+ HTTP_HEADER("Host", "localhost:8080"),
+ HTTP_HEADER("User-Agent", "curl/8.5.0"),
+ HTTP_HEADER("Accept", "*/*"),
+ HTTP_HEADER("Accept-Charset", "utf-8"),
+ HTTP_HEADER("Accept-Encoding", "gzip, deflate"),
+ HTTP_HEADER("Accept-Language", "en-US"),
+ HTTP_HEADER("Connection", "keep-alive"),
+ HTTP_HEADER("Content-Encoding", "gzip"),
+ HTTP_HEADER("Content-Length", "384"),
+ HTTP_HEADER("Origin", "http://localhost:8080"),
+
+ // uncommon headers
+ HTTP_HEADER("Authorization", "Basic QWxhZGRpbjpvcGVuIHNlc2FtZQ=="),
+ HTTP_HEADER("Cookie", "$Version=1; Skin=new;"),
+ HTTP_HEADER("Proxy-Authorization", "Basic QWxhZGRpbjpvcGVuIHNlc2FtZQ=="),
+ HTTP_HEADER("Range", "bytes=500-999"),
+ HTTP_HEADER("Referrer", "http://localhost:8080"),
+ HTTP_HEADER("Transfer-Encoding", "chunked"),
+ HTTP_HEADER("Via", "1.0 localhost:8888"),
+
+ // extra headers
+ HTTP_HEADER("If-Modified-Since", ""),
+ HTTP_HEADER("If-None-Match", ""),
+ HTTP_HEADER("X-Requested-With", ""),
+ HTTP_HEADER("Upgrade-Insecure-Request", ""),
+ HTTP_HEADER("ETag", ""),
+ HTTP_HEADER("Expires", ""),
+ HTTP_HEADER("Strict-Transport-Security", ""),
+ HTTP_HEADER("Content-Security-Policy", ""),
+ HTTP_HEADER("X-Content-Type-Options", ""),
+ HTTP_HEADER("X-Frame-Options", ""),
+ HTTP_HEADER("X-Forwarded-For", ""),
+ HTTP_HEADER("X-Api-Key", ""),
+ HTTP_HEADER("Correlation-ID", ""),
+};
+
+static inline void
+generate_input_permutation(struct http_header *source, int len)
+{
+ for (int i = 0; i < len - 2; i++) {
+ int j = i + (random() % (len - i));
+
+ // swap source[i] and source[j]
+ {
+ struct http_header tmp = source[i];
+ source[i] = source[j];
+ source[j] = tmp;
+ }
+ }
+}
+
+// ===========================================================================
+
+#define ARRLEN(arr) (sizeof (arr) / sizeof (arr)[0])
+
+struct benchmark_stats {
+ uint64_t total_ns, min_ns_per_round, max_ns_per_round, avg_ns_per_round, rounds;
+};
+
+static inline void
+benchmark_stats_clear(struct benchmark_stats *stats)
+{
+ memset(stats, 0, sizeof *stats);
+
+ stats->min_ns_per_round = UINT64_MAX;
+}
+
+static inline uint64_t
+timespec_to_ns(struct timespec *ts)
+{
+ return (ts->tv_sec * 1000000000) + ts->tv_nsec;
+}
+
+static inline void
+benchmark_stats_add_round(struct benchmark_stats *stats,
+ struct timespec *restrict begin,
+ struct timespec *restrict end)
+{
+ uint64_t round_ns = timespec_to_ns(end) - timespec_to_ns(begin);
+
+ stats->total_ns += round_ns;
+ stats->rounds++;
+
+ if (round_ns < stats->min_ns_per_round)
+ stats->min_ns_per_round = round_ns;
+
+ if (round_ns > stats->max_ns_per_round)
+ stats->max_ns_per_round = round_ns;
+}
+
+static inline void
+benchmark_stats_print(struct benchmark_stats *const stats, char const *title)
+{
+ printf("Benchmark results: %s\n", title);
+ printf("==================\n");
+ printf("Rounds : %lu\n", stats->rounds);
+ printf("Total ns: %lu\n", stats->total_ns);
+ printf("Min ns: %lu\n", stats->min_ns_per_round);
+ printf("Max ns: %lu\n", stats->max_ns_per_round);
+ printf("Avg ns: %lu\n", stats->total_ns / stats->rounds);
+ printf("==================\n\n");
+}
+
+int
+main(int argc, char **argv)
+{
+ if (argc < 2) {
+ fprintf(stderr, "Usage: %s <iters> [arena-cap-mib]\n", argv[0]);
+ exit(EXIT_FAILURE);
+ }
+
+ int iters = atoi(argv[1]);
+
+ fprintf(stderr, "Iters: %d\n", iters);
+
+ size_t arena_cap = 8 * 1024 * 1024;
+ if (argc > 2)
+ arena_cap = atoi(argv[2]) * 1024 * 1024;
+
+ struct arena arena = { .ptr = malloc(arena_cap), .cap = arena_cap, .len = 0, };
+ assert(arena.ptr);
+
+ arena_reset(&arena);
+
+ srandom(time(NULL));
+ struct http_header *source = http_headers;
+ size_t len = ARRLEN(http_headers);
+
+ struct timespec insert_begin, insert_end, get_begin, get_end;
+ struct benchmark_stats insert_stats, get_stats;
+ int benchmark_clock_source = CLOCK_MONOTONIC;
+
+ float hashmap_target_load_factor = 0.75;
+
+ // test linked list
+ {
+ benchmark_stats_clear(&insert_stats);
+ benchmark_stats_clear(&get_stats);
+
+ struct linked_list_header_map map;
+ linked_list_header_map_init(&map, &arena);
+
+ for (int i = 0; i < iters; i++) {
+ generate_input_permutation(source, len);
+
+ clock_gettime(benchmark_clock_source, &insert_begin);
+ for (size_t j = 0; j < len; j++) {
+ int res = linked_list_header_map_insert(&map, &source[j]);
+ assert(res >= 0);
+ }
+ clock_gettime(benchmark_clock_source, &insert_end);
+
+ generate_input_permutation(source, len);
+
+ clock_gettime(benchmark_clock_source, &get_begin);
+ for (size_t j = 0; j < len; j++) {
+ struct http_header out;
+ int res = linked_list_header_map_get(&map, source[j].key, &out);
+ assert(res >= 0);
+ }
+ clock_gettime(benchmark_clock_source, &get_end);
+
+ benchmark_stats_add_round(&insert_stats, &insert_begin, &insert_end);
+ benchmark_stats_add_round(&get_stats, &get_begin, &get_end);
+
+ linked_list_header_map_clear(&map);
+ }
+
+ benchmark_stats_print(&insert_stats, "Linked List Insert");
+ benchmark_stats_print(&get_stats, "Linked List Get");
+ }
+
+ // test array
+ {
+ benchmark_stats_clear(&insert_stats);
+ benchmark_stats_clear(&get_stats);
+
+ struct array_header_map map;
+ array_header_map_init(&map, &arena, len);
+
+ for (int i = 0; i < iters; i++) {
+
+ generate_input_permutation(source, len);
+
+ clock_gettime(benchmark_clock_source, &insert_begin);
+ for (size_t j = 0; j < len; j++) {
+ int res = array_header_map_insert(&map, &source[j]);
+ assert(res >= 0);
+ }
+ clock_gettime(benchmark_clock_source, &insert_end);
+
+ generate_input_permutation(source, len);
+
+ clock_gettime(benchmark_clock_source, &get_begin);
+ for (size_t j = 0; j < len; j++) {
+ struct http_header out;
+ int res = array_header_map_get(&map, source[j].key, &out);
+ assert(res >= 0);
+ }
+ clock_gettime(benchmark_clock_source, &get_end);
+
+ benchmark_stats_add_round(&insert_stats, &insert_begin, &insert_end);
+ benchmark_stats_add_round(&get_stats, &get_begin, &get_end);
+
+ array_header_map_clear(&map);
+ }
+
+ benchmark_stats_print(&insert_stats, "Array Insert");
+ benchmark_stats_print(&get_stats, "Array Get");
+ }
+
+ // test hashmap
+ {
+ benchmark_stats_clear(&insert_stats);
+ benchmark_stats_clear(&get_stats);
+
+ struct hashmap_header_map map;
+ hashmap_header_map_init(&map, &arena, len / hashmap_target_load_factor);
+
+ for (int i = 0; i < iters; i++) {
+ generate_input_permutation(source, len);
+
+ clock_gettime(benchmark_clock_source, &insert_begin);
+ for (size_t j = 0; j < len; j++) {
+ int res = hashmap_header_map_insert(&map, &source[j]);
+ assert(res >= 0);
+ }
+ clock_gettime(benchmark_clock_source, &insert_end);
+
+ generate_input_permutation(source, len);
+
+ clock_gettime(benchmark_clock_source, &get_begin);
+ for (size_t j = 0; j < len; j++) {
+ struct http_header out;
+ int res = hashmap_header_map_get(&map, source[j].key, &out);
+ assert(res >= 0);
+ }
+ clock_gettime(benchmark_clock_source, &get_end);
+
+ benchmark_stats_add_round(&insert_stats, &insert_begin, &insert_end);
+ benchmark_stats_add_round(&get_stats, &get_begin, &get_end);
+
+ hashmap_header_map_clear(&map);
+ }
+
+ benchmark_stats_print(&insert_stats, "Hashmap Insert");
+ benchmark_stats_print(&get_stats, "Hashmap Get");
+ }
+
+ exit(EXIT_SUCCESS);
+}
diff --git a/build.sh b/build.sh
@@ -0,0 +1,10 @@
+#!/bin/sh
+
+WARNINGS="-Wall -Wextra -Wpedantic ${WERROR:+-Werror} -Wno-unused-parameter"
+FLAGS="-std=c11 -Og -g"
+
+set -ex
+
+mkdir -p bin
+
+clang -o bin/benchmark benchmark.c $WARNINGS $FLAGS
diff --git a/clean.sh b/clean.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+
+set -ex
+
+rm -rf bin
diff --git a/hash.h b/hash.h
@@ -0,0 +1,19 @@
+#ifndef HASH_H
+#define HASH_H
+
+#include <stdint.h>
+
+static inline uint32_t
+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;
+
+ unsigned char const *ptr = buf, *end = ptr + len;
+ while (ptr < end)
+ hash = (hash ^ *ptr++) * prime;
+
+ return hash;
+}
+
+#endif /* HASH_H */
diff --git a/http.h b/http.h
@@ -0,0 +1,16 @@
+#ifndef HTTP_H
+#define HTTP_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+struct str {
+ char *ptr;
+ size_t len;
+};
+
+struct http_header {
+ struct str key, val;
+};
+
+#endif /* HTTP_H */
diff --git a/list.h b/list.h
@@ -0,0 +1,88 @@
+#ifndef LIST_H
+#define LIST_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+#define TO_PARENT(ptr, T, member) \
+ ((T *) ((uintptr_t) ptr - offsetof(T, member)))
+
+struct list_node {
+ struct list_node *prev, *next;
+};
+
+#define FROM_LIST_NODE(node, T, member) \
+ TO_PARENT((node), T, member)
+
+#define LIST_INIT(list) \
+ ((struct list_node) { &(list), &(list), })
+
+#define LIST_HEAD(list) ((list)->next)
+#define LIST_TAIL(list) ((list)->prev)
+
+#define LIST_EMPTY(list) \
+ (LIST_HEAD((list)) == (list) && LIST_TAIL((list)) == (list))
+
+#define LIST_NODE_ITER(list, it) \
+ for ((it) = LIST_HEAD((list)); (it) != (list); (it) = (it)->next)
+
+#define LIST_NODE_RITER(list, it) \
+ for ((it) = LIST_TAIL((list)); (it) != (list); (it) = (it)->prev)
+
+#define LIST_NODE_ENTRY(node, it, member) \
+ FROM_LIST_NODE((node), __typeof__ (*(it)), member)
+
+#define LIST_ENTRY_ITER(list, it, member) \
+ for ((it) = LIST_NODE_ENTRY(LIST_HEAD((list)), (it), member); \
+ &(it)->member != (list); \
+ (it) = LIST_NODE_ENTRY((it)->member.next, (it), member))
+
+#define LIST_ENTRY_RITER(list, it, member) \
+ for ((it) = LIST_NODE_ENTRY(LIST_TAIL((list)), (it), member); \
+ &(it)->member != (list); \
+ (it) = LIST_NODE_ENTRY((it)->member.prev, (it), member))
+
+static inline void
+list_node_link(struct list_node *node, struct list_node *prev, struct list_node *next)
+{
+ prev->next = node;
+ node->prev = prev;
+ next->prev = node;
+ node->next = next;
+}
+
+static inline struct list_node *
+list_node_unlink(struct list_node *node)
+{
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+ return node;
+}
+
+static inline void
+list_push_head(struct list_node *list, struct list_node *node)
+{
+ list_node_link(node, list, LIST_HEAD(list));
+}
+
+static inline void
+list_push_tail(struct list_node *list, struct list_node *node)
+{
+ list_node_link(node, LIST_TAIL(list), list);
+}
+
+static inline struct list_node *
+list_pop_head(struct list_node *list)
+{
+ struct list_node *res = list_node_unlink(LIST_HEAD(list));
+ return res;
+}
+
+static inline struct list_node *
+list_pop_tail(struct list_node *list)
+{
+ struct list_node *res = list_node_unlink(LIST_TAIL(list));
+ return res;
+}
+
+#endif /* LIST_H */
