diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | CMakeLists.txt | 6 | ||||
| -rw-r--r-- | README.md | 14 | ||||
| -rw-r--r-- | base_bench.c | 148 | ||||
| -rw-r--r-- | generate_benchmarks.py | 39 | ||||
| -rw-r--r-- | hash_distribution.py | 93 | ||||
| -rw-r--r-- | mise.toml | 15 | ||||
| -rw-r--r-- | src/json/bench_json.c | 17 |
8 files changed, 320 insertions, 13 deletions
@@ -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) @@ -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() @@ -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; +} |