Benchmark framework

8 files changed, 320 insertions, 13 deletions

diff --git a/.gitignore b/.gitignore
index c49a7e9..09c6adb 100644
--- a/.gitignore
+++ b/.gitignore
@@ -5,5 +5,6 @@ Release/
 Profile/
 
 test.c
+bench.c
 *MB.json
 callgrind.out
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 2b6c97a..9944497 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -4,6 +4,8 @@ set(CMAKE_C_STANDARD 23)
 
 file(GLOB_RECURSE SOURCES "src/**/*.c")
 list(FILTER SOURCES EXCLUDE REGEX ".*/test_.*\\.c$")
+list(FILTER SOURCES EXCLUDE REGEX ".*/bench_.*\\.c$")
+
 
 add_compile_options(-Wall -pedantic -Wextra -mavx2 -mno-avx512f)
 
@@ -14,3 +16,7 @@ target_compile_options(main PRIVATE)
 add_executable(test test.c ${SOURCES})
 target_link_libraries(test m)
 target_compile_options(test PRIVATE)
+
+add_executable(bench bench.c ${SOURCES})
+target_link_libraries(bench m)
+target_compile_options(bench PRIVATE)
diff --git a/README.md b/README.md
index fd7c32b..a8ebb8e 100644
--- a/README.md
+++ b/README.md
@@ -29,20 +29,8 @@ SDL_DestroyRenderer(renderer);
 SDL_DestroyWindow(window);
 ```
 
-## Benchmarks
-
-| version          | result                                                              | throughput  | ram     |
-| ---------------- | ------------------------------------------------------------------- | ----------- | ------- |
-| json.loads       | 652 ms ± 6.65 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) | 137.73 MB/s |         |
-| orjson.loads     | 535 ms ± 8.64 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) | 167.85 MB/s |         |
-| v1               | 336 ms ± 163 ms per loop (mean ± std. dev. of 10 runs, 1 loop each) |             |         |
-| no 0 mem alloc   | 299 ms ± 8 ms per loop (mean ± std. dev. of 10 runs, 1 loop each)   |             |         |
-| Str_view         | 272 ms ± 6 ms per loop (mean ± std. dev. of 10 runs, 1 loop each)   | 330.46 MB/s | 1255 MB |
-| simd             | 254 ms ± 6 ms per loop (mean ± std. dev. of 10 runs, 1 loop each)   | 353.36 MB/s | 1255 MB |
-| negative         | 206 ms ± 6 ms per loop (mean ± std. dev. of 10 runs, 1 loop each)   | 436.25 MB/s | 1255 MB |
-| init 6 obj array | 186 ms ± 6 ms per loop (mean ± std. dev. of 10 runs, 1 loop each)   | 483.96 MB/s | 1026 MB |
-
 ## Resources
 
 - https://nullprogram.com/blog/2023/10/08/
 - https://danielchasehooper.com/posts/typechecked-generic-c-data-structures/
+- Hashing: https://github.com/aappleby/smhasher/
diff --git a/base_bench.c b/base_bench.c
new file mode 100644
index 0000000..52ab639
--- /dev/null
+++ b/base_bench.c
@@ -0,0 +1,148 @@
+#include <math.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "src/std/memory.h"
+#include "src/std/time.h"
+#include "src/std/types.h"
+
+#define BENCH_DURATION_MS 100.0f
+
+typedef struct {
+    f32 ns;
+    f32 stddev;
+    size peak;
+    size net;
+    f32 total_ms;
+} BenchResult;
+
+typedef void (*BenchSetup)(Arena *a);
+typedef i32 (*BenchFn)(Arena *a);
+
+static inline BenchResult bench_run(BenchSetup setup, BenchFn fn) {
+    Arena scratch = Arena_new(32 * 1024 * 1024);
+    u64 calls = 0;
+    size peak = 0;
+    size net = 0;
+    double mean = 0, m2 = 0;
+    double total_ns = 0;
+
+    Time wall_start = Time_get();
+    Duration limit = Duration_from_ms(BENCH_DURATION_MS);
+    u64 limit_ns = limit.ns + limit.s * (u64)1e9;
+
+    for (;;) {
+        Time wall_now = Time_get();
+        Duration wall_elapsed = Time_diff(wall_now, wall_start);
+        if (wall_elapsed.s > 0 ||
+            wall_elapsed.ns >= limit_ns)
+            break;
+
+        Arena_reset(&scratch);
+        setup(&scratch);
+        size before = Arena_get_used(scratch);
+        Time start = Time_get();
+        fn(&scratch);
+        Time end = Time_get();
+        size after = Arena_get_used(scratch);
+        Duration d = Time_diff(end, start);
+        double sample = (double)d.ns + (double)d.s * 1e9;
+        total_ns += sample;
+        calls++;
+        double delta = sample - mean;
+        mean += delta / (double)calls;
+        m2 += delta * (sample - mean);
+        if (after > peak) peak = after;
+        net = after - before;
+    }
+
+    if (calls == 0) calls = 1;
+    return (BenchResult){
+        .ns = (f32)(total_ns / (double)calls),
+        .stddev = calls > 1 ? (f32)sqrt(m2 / (double)(calls - 1)) : 0,
+        .peak = peak,
+        .net = net,
+        .total_ms = (f32)(total_ns / 1e6),
+    };
+}
+
+#define MAX_RESULTS 64
+typedef struct {
+    const char *name;
+    BenchResult result;
+} BenchEntry;
+static BenchEntry _bench_registry[MAX_RESULTS];
+static i32 _bench_count = 0;
+
+static void _bench_register(const char *name, BenchResult r) {
+    if (_bench_count < MAX_RESULTS) {
+        _bench_registry[_bench_count].name = name;
+        _bench_registry[_bench_count].result = r;
+        _bench_count++;
+    }
+}
+
+static BenchResult *_bench_find(const char *name) {
+    for (i32 i = 0; i < _bench_count; i++)
+        if (strcmp(_bench_registry[i].name, name) == 0)
+            return &_bench_registry[i].result;
+    return NULL;
+}
+
+static void _fmt_mem(char *buf, size_t bufsz, size bytes) {
+    if (bytes >= 1024 * 1024)
+        snprintf(buf, bufsz, "%.1f MB", (double)bytes / (1024 * 1024));
+    else if (bytes >= 1024)
+        snprintf(buf, bufsz, "%.1f KB", (double)bytes / 1024);
+    else
+        snprintf(buf, bufsz, "%zu B", bytes);
+}
+
+static void _fmt_ratio(char *buf, size_t bufsz, double val, double ref) {
+    if (ref == 0) {
+        buf[0] = '\0';
+        return;
+    }
+    double ratio = val / ref;
+    if (ratio >= 1.005)
+        snprintf(buf, bufsz, "(x%.0f)", ratio);
+    else if (ratio < 0.995)
+        snprintf(buf, bufsz, "(x%.2f)", ratio);
+    else
+        snprintf(buf, bufsz, "(x1)");
+}
+
+static void _bench_print_row(const char *name, BenchResult r,
+                              const char *compare) {
+    BenchResult *ref = compare ? _bench_find(compare) : NULL;
+
+    char ns_ratio[16] = "", peak_ratio[16] = "", net_ratio[16] = "";
+    if (ref) {
+        _fmt_ratio(ns_ratio, sizeof(ns_ratio), r.ns, ref->ns);
+        _fmt_ratio(peak_ratio, sizeof(peak_ratio), (double)r.peak,
+                   (double)ref->peak);
+        _fmt_ratio(net_ratio, sizeof(net_ratio), (double)r.net,
+                   (double)ref->net);
+    }
+
+    char peak[16], net[16];
+    _fmt_mem(peak, sizeof(peak), r.peak);
+    _fmt_mem(net, sizeof(net), r.net);
+
+    printf("  %-38s %10.0f ±%7.0f %-6s   %10s %-6s   %10s %-6s   %6.0f ms\n",
+           name, r.ns, r.stddev, ns_ratio, peak, peak_ratio, net, net_ratio,
+           r.total_ms);
+}
+
+static void bench_group(const char *label) {
+    printf("\n[%s]\n", label);
+    printf("  %-38s %10s %-14s   %10s %-6s   %10s %-6s   %9s\n", "name",
+           "ns/call", "± stddev", "peak mem", "", "net mem", "", "total");
+}
+
+#define bench(name, setup, func, compare)                                      \
+    do {                                                                       \
+        BenchResult _r = bench_run(setup, func);                               \
+        _bench_register(name, _r);                                             \
+        _bench_print_row(name, _r, compare);                                   \
+    } while (0)
diff --git a/generate_benchmarks.py b/generate_benchmarks.py
new file mode 100644
index 0000000..cadeaf2
--- /dev/null
+++ b/generate_benchmarks.py
@@ -0,0 +1,39 @@
+import re
+from pathlib import Path
+
+bench_files = sorted(Path("src").rglob("bench_*.c"))
+
+lines: list[str] = []
+
+for f in bench_files:
+    lines.append(f'#include "{f}"')
+
+lines.append("")
+lines.append(Path("base_bench.c").read_text())
+lines.append("i32 main() {")
+
+for f in bench_files:
+    # group label from filename: bench_vec.c -> "vec", bench_vec_sort.c -> "vec sort"
+    stem = f.stem.removeprefix("bench_").replace("_", " ")
+
+    src = f.read_text()
+
+    # find setup function (setup_* in this file)
+    setup_match = re.search(r"void (setup_\w+)\(", src)
+    setup = setup_match.group(1) if setup_match else None
+
+    funcs = re.findall(r"i32 (bench_\w+)\(", src)
+
+    if not funcs:
+        continue
+
+    reference = funcs[0]
+    print(f"Group '{stem}' from {f}: {funcs}")
+    lines.append(f'    bench_group("{stem}");')
+    for i, func in enumerate(funcs):
+        compare_arg = f'"{reference}"' if i > 0 else "NULL"
+        lines.append(f'    bench("{func}", {setup}, {func}, {compare_arg});')
+
+lines.append("    return 0;\n}\n")
+
+Path("bench.c").write_text("\n".join(lines))
diff --git a/hash_distribution.py b/hash_distribution.py
new file mode 100644
index 0000000..7fe633a
--- /dev/null
+++ b/hash_distribution.py
@@ -0,0 +1,93 @@
+"""Analyze distribution quality of a polynomial rolling hash function."""
+
+import math
+import random
+import string
+from collections import Counter
+
+
+MAX_BUCKETS = 1000
+MULTIPLIER = 31
+
+
+def hashstring(s: str) -> int:
+    h = 0
+    for c in s:
+        h = h * MULTIPLIER + ord(c)
+    return h % MAX_BUCKETS
+
+
+def chi_squared(counts: list[int], n_samples: int) -> float:
+    """Chi-squared statistic vs uniform distribution."""
+    expected = n_samples / MAX_BUCKETS
+    return sum((c - expected) ** 2 / expected for c in counts)
+
+
+def generate_words(n: int) -> list[str]:
+    """Random lowercase alpha strings of length 3-10."""
+    rng = random.Random(42)
+    return [
+        "".join(rng.choices(string.ascii_lowercase, k=rng.randint(3, 10)))
+        for _ in range(n)
+    ]
+
+
+def analyze(label: str, keys: list[str]) -> None:
+    buckets = Counter(hashstring(k) for k in keys)
+    counts = [buckets.get(i, 0) for i in range(MAX_BUCKETS)]
+
+    filled = sum(1 for c in counts if c > 0)
+    max_count = max(counts)
+    min_count = min(counts)
+    mean = len(keys) / MAX_BUCKETS
+    variance = sum((c - mean) ** 2 for c in counts) / MAX_BUCKETS
+    std_dev = math.sqrt(variance)
+    chi2 = chi_squared(counts, len(keys))
+    # Degrees of freedom = MAX_BUCKETS - 1 = 999
+    # chi2 critical value at p=0.05 is approx 1073.6
+    chi2_critical = 1073.6
+
+    print(f"\n=== {label} ({len(keys)} keys) ===")
+    print(
+        f"  Filled buckets : {filled} / {MAX_BUCKETS} ({100 * filled / MAX_BUCKETS:.1f}%)"
+    )
+    print(f"  Min / Mean / Max count : {min_count} / {mean:.2f} / {max_count}")
+    print(f"  Std dev : {std_dev:.3f}  (ideal ≈ {math.sqrt(mean):.3f})")
+    print(f"  Chi² : {chi2:.1f}  (critical at p=0.05: {chi2_critical})")
+    print(f"  Verdict: {'GOOD' if chi2 < chi2_critical else 'POOR'} distribution")
+
+    # Simple ASCII histogram of top/bottom 5 buckets
+    top5 = sorted(range(MAX_BUCKETS), key=lambda i: -counts[i])[:5]
+    print("  Top-5 hottest buckets:")
+    for b in top5:
+        bar = "#" * min(counts[b], 60)
+        print(f"    bucket {b:4d}: {counts[b]:4d}  {bar}")
+
+
+def sequential_integers(n: int) -> list[str]:
+    return [str(i) for i in range(n)]
+
+
+def short_keys(n: int) -> list[str]:
+    """Single-character and two-character keys to expose low-entropy edge cases."""
+    keys: list[str] = []
+    for c in string.ascii_lowercase:
+        keys.append(c)
+    for a in string.ascii_lowercase:
+        for b in string.ascii_lowercase:
+            keys.append(a + b)
+            if len(keys) >= n:
+                return keys
+    return keys
+
+
+def main() -> None:
+    print(f"Hash parameters: MAX_BUCKETS={MAX_BUCKETS}, MULTIPLIER={MULTIPLIER}")
+
+    analyze("Random strings", generate_words(10_000))
+    analyze("Sequential integers", sequential_integers(10_000))
+    analyze("Short keys (1-2 chars)", short_keys(700))
+
+
+if __name__ == "__main__":
+    main()
diff --git a/mise.toml b/mise.toml
index 48658a0..90a67a9 100644
--- a/mise.toml
+++ b/mise.toml
@@ -27,6 +27,21 @@ run = [
     "kcachegrind callgrind.out"
 ]
 
+[tasks.generate-bench]
+run = [
+    "uv run python generate_json.py 1",
+    "uv run python generate_benchmarks.py"
+]
+
+[tasks.bench]
+depends = ["generate-bench"]
+run = [
+    "mkdir -p Release",
+    "cmake -DCMAKE_BUILD_TYPE=Release -B Release",
+    "cmake --build Release",
+    "./Release/bench"
+]
+
 [tasks.test]
 depends = ["debug"]
 run = "./Debug/test"
diff --git a/src/json/bench_json.c b/src/json/bench_json.c
new file mode 100644
index 0000000..1aeecf0
--- /dev/null
+++ b/src/json/bench_json.c
@@ -0,0 +1,17 @@
+#include "../std/memory.h"
+#include "../std/testing.h"
+#include "../std/types.h"
+#include "json.h"
+
+#define BENCH_FILE "descriptive-1MB.json"
+
+static MemoryFile json_parse_input;
+
+static void setup_json_parse(Arena *a) {
+    json_parse_input = load_file(a, BENCH_FILE);
+}
+
+i32 bench_json_parse(Arena *a) {
+    JSON_parse(a, json_parse_input.content, json_parse_input.size);
+    return 0;
+}