benchmark.c (12482B)
1 #define _XOPEN_SOURCE 700 2 3 #include <assert.h> 4 #include <stdio.h> 5 #include <stdlib.h> 6 #include <string.h> 7 #include <time.h> 8 #include <unistd.h> 9 10 #include "arena.h" 11 #include "list.h" 12 #include "http.h" 13 #include "hash.h" 14 15 #define HASHMAP_64BIT_HASH 0 16 17 // =========================================================================== 18 19 struct linked_list_header_entry { 20 struct http_header header; 21 struct list_node list_node; 22 }; 23 24 struct linked_list_header_map { 25 struct list_node list; 26 struct arena *arena; 27 }; 28 29 static inline void 30 linked_list_header_map_clear(struct linked_list_header_map *map) 31 { 32 map->list = LIST_INIT(map->list); 33 arena_reset(map->arena); 34 } 35 36 static inline void 37 linked_list_header_map_init(struct linked_list_header_map *map, struct arena *arena) 38 { 39 map->arena = arena; 40 41 linked_list_header_map_clear(map); 42 } 43 44 static inline int 45 linked_list_header_map_insert(struct linked_list_header_map *map, struct http_header *header) 46 { 47 struct linked_list_header_entry *ent = ARENA_ALLOC_SIZED(map->arena, struct linked_list_header_entry); 48 if (!ent) return -1; 49 50 ent->header = *header; 51 ent->list_node.prev = ent->list_node.next = NULL; 52 53 list_push_tail(&map->list, &ent->list_node); 54 55 return 0; 56 } 57 58 static inline int 59 linked_list_header_map_get(struct linked_list_header_map *const map, 60 struct str key, struct http_header *out) 61 { 62 struct linked_list_header_entry *it; 63 LIST_ENTRY_ITER(&map->list, it, list_node) { 64 if (it->header.key.len != key.len) 65 continue; 66 67 if (strncmp(it->header.key.ptr, key.ptr, key.len)) 68 continue; 69 70 *out = it->header; 71 return 0; 72 } 73 74 return -1; 75 } 76 77 struct array_header_entry { 78 struct http_header header; 79 }; 80 81 struct array_header_map { 82 struct array_header_entry *arr; 83 size_t cap, len; 84 }; 85 86 static inline void 87 array_header_map_clear(struct array_header_map *map) 88 { 89 map->len = 0; 90 } 91 92 static inline void 93 array_header_map_init(struct array_header_map *map, struct arena *arena, size_t cap) 94 { 95 arena_reset(arena); 96 map->arr = ARENA_ALLOC_ARRAY(arena, struct array_header_entry, cap); 97 assert(map->arr); 98 99 map->cap = cap; 100 101 array_header_map_clear(map); 102 } 103 104 static inline int 105 array_header_map_insert(struct array_header_map *map, struct http_header *header) 106 { 107 if (map->len == map->cap) return -1; 108 109 struct array_header_entry *ent = &map->arr[map->len++]; 110 ent->header = *header; 111 112 return 0; 113 } 114 115 static inline int 116 array_header_map_get(struct array_header_map *const map, 117 struct str key, struct http_header *out) 118 { 119 for (size_t i = 0; i < map->len; i++) { 120 struct array_header_entry *ent = &map->arr[i]; 121 122 if (ent->header.key.len != key.len) 123 continue; 124 125 if (strncmp(ent->header.key.ptr, key.ptr, key.len)) 126 continue; 127 128 *out = ent->header; 129 return 0; 130 } 131 132 return -1; 133 } 134 135 struct hashmap_header_entry { 136 uint64_t hash; 137 int64_t valid; 138 struct http_header header; 139 }; 140 141 struct hashmap_header_map { 142 struct hashmap_header_entry *buckets; 143 size_t cap; 144 }; 145 146 static inline void 147 hashmap_header_map_clear(struct hashmap_header_map *map) 148 { 149 memset(map->buckets, 0, sizeof *map->buckets * map->cap); 150 } 151 152 static inline void 153 hashmap_header_map_init(struct hashmap_header_map *map, struct arena *arena, size_t cap) 154 { 155 arena_reset(arena); 156 map->buckets = ARENA_ALLOC_ARRAY(arena, struct hashmap_header_entry, cap); 157 assert(map->buckets); 158 159 map->cap = cap; 160 161 hashmap_header_map_clear(map); 162 } 163 164 // https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ 165 static inline size_t 166 fibbonaci_map(size_t hash) 167 { 168 const uint64_t phi_1 = 11400714819323198485llu; 169 170 #if HASHMAP_64BIT_HASH 171 hash ^= hash >> 63; 172 return (phi_1 * hash) >> 63; 173 #else 174 return phi_1 * hash; 175 #endif 176 } 177 178 static inline int 179 hashmap_header_map_insert(struct hashmap_header_map *map, struct http_header *header) 180 { 181 #if HASHMAP_64BIT_HASH 182 size_t hash = fnv64a(header->key.ptr, header->key.len); 183 #else 184 size_t hash = fnv32a(header->key.ptr, header->key.len); 185 #endif 186 187 for (size_t off = 0; off < map->cap; off++) { 188 size_t idx = fibbonaci_map(hash) + off; 189 struct hashmap_header_entry *ent = &map->buckets[idx % map->cap]; 190 191 // if bucket is empty, we are inserting a new value 192 if (!ent->valid) { 193 ent->hash = hash; 194 ent->valid = 1; 195 ent->header = *header; 196 return 0; 197 } 198 199 // if our hash matches, we are inserting a duplicate value 200 if (ent->hash == hash) 201 return 0; 202 203 // if our hash does not match, check next bucket 204 } 205 206 return -1; 207 } 208 209 static inline int 210 hashmap_header_map_get(struct hashmap_header_map *const map, 211 struct str key, struct http_header *out) 212 { 213 #if HASHMAP_64BIT_HASH 214 size_t hash = fnv64a(key.ptr, key.len); 215 #else 216 size_t hash = fnv32a(key.ptr, key.len); 217 #endif 218 219 for (size_t off = 0; off < map->cap; off++) { 220 size_t idx = fibbonaci_map(hash) + off; 221 struct hashmap_header_entry *ent = &map->buckets[idx % map->cap]; 222 223 // if bucket is empty, we have failed to find our key 224 if (!ent->valid) 225 return -1; 226 227 // if our hash matches, we have found our key 228 if (ent->hash == hash) { 229 *out = ent->header; 230 return 0; 231 } 232 233 // if our hash does not match, check next bucket 234 } 235 236 return -1; 237 } 238 239 // =========================================================================== 240 241 #define HTTP_HEADER(key, val) \ 242 ((struct http_header) { { (key), strlen((key)), }, { (val), strlen((val)), }, }) 243 244 static struct http_header http_headers[] = { 245 // common headers 246 HTTP_HEADER("Host", "localhost:8080"), 247 HTTP_HEADER("User-Agent", "curl/8.5.0"), 248 HTTP_HEADER("Accept", "*/*"), 249 HTTP_HEADER("Accept-Charset", "utf-8"), 250 HTTP_HEADER("Accept-Encoding", "gzip, deflate"), 251 HTTP_HEADER("Accept-Language", "en-US"), 252 HTTP_HEADER("Connection", "keep-alive"), 253 HTTP_HEADER("Content-Encoding", "gzip"), 254 HTTP_HEADER("Content-Length", "384"), 255 HTTP_HEADER("Origin", "http://localhost:8080"), 256 257 // uncommon headers 258 HTTP_HEADER("Authorization", "Basic QWxhZGRpbjpvcGVuIHNlc2FtZQ=="), 259 HTTP_HEADER("Cookie", "$Version=1; Skin=new;"), 260 HTTP_HEADER("Proxy-Authorization", "Basic QWxhZGRpbjpvcGVuIHNlc2FtZQ=="), 261 HTTP_HEADER("Range", "bytes=500-999"), 262 HTTP_HEADER("Referrer", "http://localhost:8080"), 263 HTTP_HEADER("Transfer-Encoding", "chunked"), 264 HTTP_HEADER("Via", "1.0 localhost:8888"), 265 266 // extra headers 267 HTTP_HEADER("If-Modified-Since", ""), 268 HTTP_HEADER("If-None-Match", ""), 269 HTTP_HEADER("X-Requested-With", ""), 270 HTTP_HEADER("Upgrade-Insecure-Request", ""), 271 HTTP_HEADER("ETag", ""), 272 HTTP_HEADER("Expires", ""), 273 HTTP_HEADER("Strict-Transport-Security", ""), 274 HTTP_HEADER("Content-Security-Policy", ""), 275 HTTP_HEADER("X-Content-Type-Options", ""), 276 HTTP_HEADER("X-Frame-Options", ""), 277 HTTP_HEADER("X-Forwarded-For", ""), 278 HTTP_HEADER("X-Api-Key", ""), 279 HTTP_HEADER("Correlation-ID", ""), 280 }; 281 282 static inline void 283 generate_input_permutation(struct http_header *source, int len) 284 { 285 for (int i = 0; i < len - 2; i++) { 286 int j = i + (random() % (len - i)); 287 288 // swap source[i] and source[j] 289 { 290 struct http_header tmp = source[i]; 291 source[i] = source[j]; 292 source[j] = tmp; 293 } 294 } 295 } 296 297 // =========================================================================== 298 299 #define ARRLEN(arr) (sizeof (arr) / sizeof (arr)[0]) 300 301 struct benchmark_stats { 302 uint64_t total_ns, min_ns_per_round, max_ns_per_round, avg_ns_per_round, rounds; 303 }; 304 305 static inline void 306 benchmark_stats_clear(struct benchmark_stats *stats) 307 { 308 memset(stats, 0, sizeof *stats); 309 310 stats->min_ns_per_round = UINT64_MAX; 311 } 312 313 static inline uint64_t 314 timespec_to_ns(struct timespec *ts) 315 { 316 return (ts->tv_sec * 1000000000) + ts->tv_nsec; 317 } 318 319 static inline void 320 benchmark_stats_add_round(struct benchmark_stats *stats, 321 struct timespec *restrict begin, 322 struct timespec *restrict end) 323 { 324 uint64_t round_ns = timespec_to_ns(end) - timespec_to_ns(begin); 325 326 stats->total_ns += round_ns; 327 stats->rounds++; 328 329 if (round_ns < stats->min_ns_per_round) 330 stats->min_ns_per_round = round_ns; 331 332 if (round_ns > stats->max_ns_per_round) 333 stats->max_ns_per_round = round_ns; 334 } 335 336 static inline void 337 benchmark_stats_print(struct benchmark_stats *const stats, char const *title) 338 { 339 printf("Benchmark results: %s\n", title); 340 printf("==================\n"); 341 printf("Rounds : %lu\n", stats->rounds); 342 printf("Total ns: %lu\n", stats->total_ns); 343 printf("Min ns: %lu\n", stats->min_ns_per_round); 344 printf("Max ns: %lu\n", stats->max_ns_per_round); 345 printf("Avg ns: %lu\n", stats->total_ns / stats->rounds); 346 printf("==================\n\n"); 347 } 348 349 int 350 main(int argc, char **argv) 351 { 352 if (argc < 2) { 353 fprintf(stderr, "Usage: %s <iters> [arena-cap-mib]\n", argv[0]); 354 exit(EXIT_FAILURE); 355 } 356 357 int iters = atoi(argv[1]); 358 359 fprintf(stderr, "Iters: %d\n", iters); 360 361 size_t arena_cap = 8 * 1024 * 1024; 362 if (argc > 2) 363 arena_cap = atoi(argv[2]) * 1024 * 1024; 364 365 struct arena arena = { .ptr = malloc(arena_cap), .cap = arena_cap, .len = 0, }; 366 assert(arena.ptr); 367 368 arena_reset(&arena); 369 370 srandom(time(NULL)); 371 struct http_header *source = http_headers; 372 size_t len = ARRLEN(http_headers); 373 374 struct timespec insert_begin, insert_end, get_begin, get_end; 375 struct benchmark_stats insert_stats, get_stats; 376 int benchmark_clock_source = CLOCK_MONOTONIC; 377 378 float hashmap_target_load_factor = 1; 379 380 // test linked list 381 { 382 benchmark_stats_clear(&insert_stats); 383 benchmark_stats_clear(&get_stats); 384 385 struct linked_list_header_map map; 386 linked_list_header_map_init(&map, &arena); 387 388 for (int i = 0; i < iters; i++) { 389 generate_input_permutation(source, len); 390 391 clock_gettime(benchmark_clock_source, &insert_begin); 392 for (size_t j = 0; j < len; j++) { 393 int res = linked_list_header_map_insert(&map, &source[j]); 394 assert(res >= 0); 395 } 396 clock_gettime(benchmark_clock_source, &insert_end); 397 398 generate_input_permutation(source, len); 399 400 clock_gettime(benchmark_clock_source, &get_begin); 401 for (size_t j = 0; j < len; j++) { 402 struct http_header out; 403 int res = linked_list_header_map_get(&map, source[j].key, &out); 404 assert(res >= 0); 405 } 406 clock_gettime(benchmark_clock_source, &get_end); 407 408 benchmark_stats_add_round(&insert_stats, &insert_begin, &insert_end); 409 benchmark_stats_add_round(&get_stats, &get_begin, &get_end); 410 411 linked_list_header_map_clear(&map); 412 } 413 414 benchmark_stats_print(&insert_stats, "Linked List Insert"); 415 benchmark_stats_print(&get_stats, "Linked List Get"); 416 } 417 418 // test array 419 { 420 benchmark_stats_clear(&insert_stats); 421 benchmark_stats_clear(&get_stats); 422 423 struct array_header_map map; 424 array_header_map_init(&map, &arena, len); 425 426 for (int i = 0; i < iters; i++) { 427 428 generate_input_permutation(source, len); 429 430 clock_gettime(benchmark_clock_source, &insert_begin); 431 for (size_t j = 0; j < len; j++) { 432 int res = array_header_map_insert(&map, &source[j]); 433 assert(res >= 0); 434 } 435 clock_gettime(benchmark_clock_source, &insert_end); 436 437 generate_input_permutation(source, len); 438 439 clock_gettime(benchmark_clock_source, &get_begin); 440 for (size_t j = 0; j < len; j++) { 441 struct http_header out; 442 int res = array_header_map_get(&map, source[j].key, &out); 443 assert(res >= 0); 444 } 445 clock_gettime(benchmark_clock_source, &get_end); 446 447 benchmark_stats_add_round(&insert_stats, &insert_begin, &insert_end); 448 benchmark_stats_add_round(&get_stats, &get_begin, &get_end); 449 450 array_header_map_clear(&map); 451 } 452 453 benchmark_stats_print(&insert_stats, "Array Insert"); 454 benchmark_stats_print(&get_stats, "Array Get"); 455 } 456 457 // test hashmap 458 { 459 benchmark_stats_clear(&insert_stats); 460 benchmark_stats_clear(&get_stats); 461 462 struct hashmap_header_map map; 463 hashmap_header_map_init(&map, &arena, len / hashmap_target_load_factor); 464 465 for (int i = 0; i < iters; i++) { 466 generate_input_permutation(source, len); 467 468 clock_gettime(benchmark_clock_source, &insert_begin); 469 for (size_t j = 0; j < len; j++) { 470 int res = hashmap_header_map_insert(&map, &source[j]); 471 assert(res >= 0); 472 } 473 clock_gettime(benchmark_clock_source, &insert_end); 474 475 generate_input_permutation(source, len); 476 477 clock_gettime(benchmark_clock_source, &get_begin); 478 for (size_t j = 0; j < len; j++) { 479 struct http_header out; 480 int res = hashmap_header_map_get(&map, source[j].key, &out); 481 assert(res >= 0); 482 } 483 clock_gettime(benchmark_clock_source, &get_end); 484 485 benchmark_stats_add_round(&insert_stats, &insert_begin, &insert_end); 486 benchmark_stats_add_round(&get_stats, &get_begin, &get_end); 487 488 hashmap_header_map_clear(&map); 489 } 490 491 benchmark_stats_print(&insert_stats, "Hashmap Insert"); 492 benchmark_stats_print(&get_stats, "Hashmap Get"); 493 } 494 495 exit(EXIT_SUCCESS); 496 }