memcpy-decomp

What It Is

memcpy-decomp turns a memcpy whose length is only known at runtime into a short sequence of copies whose lengths are known at compile time. Every copy it issues is a power of two, so every copy lowers to plain register loads and stores — no call into the C runtime and no size-class dispatch hidden behind it.

Small, variable-length copies are everywhere in parsers and serializers: string fields, escaped runs, key names, number buffers. They are almost always shorter than a cache line, and they are almost always paid for with a full out-of-line library call. memcpy-decomp is the technique Jsonifier uses internally to avoid that call, pulled out on its own so it can be measured in isolation.

Why

For any length n with std::bit_width(n) == k, n lies in [2^k−1, 2^k). Let b = 2^k−1. Then b ≤ n < 2b, which means a copy of b bytes anchored at the front and a copy of b bytes anchored at the back together cover every byte exactly once or twice and never step outside [0, n). The overlap is harmless: it rewrites the same bytes with the same values.

So the only runtime decision left is which bucket. That decision is a balanced tree of comparisons against powers of two, generated at compile time: three or four conditional branches straight on the length, with no lookup table and no indirect jump. Everything after that is straight-line code with constant sizes the compiler can schedule freely. Buckets wider than the vector register are split into register-width chunks, and a compile-time upper bound (memcpy_decomp_up_to<N>) removes every comparison and bucket that can't occur.

Earlier versions dispatched with a switch on std::bit_width(n). GCC compiled it to a jump table that cost extra taken branches on every copy, and that was enough to lose to glibc on a few ranges. The compare tree compiles to the same branch-only shape on GCC and Clang alike.

A few comparisons. No jump table. Two overlapping fixed-size copies.

The Algorithm

top_bucket_index<max_bytes> is the bit width of the bound, capped at the std::memcpy fallback, so a bounded call site only builds the part of the tree it can reach — memcpy_decomp_up_to<15> never even compares against 16. Lengths of 256 bytes and up fall through to std::memcpy, where the library's bulk-copy paths are the right tool.

Bucket Map

Features

Quick Start

CMake pulls BenchmarkSuite and rt-ut automatically via FetchContent. Requires C++20.

Correctness

Every run opens with an exhaustive sweep: every length from 0 to 300, at every source and destination misalignment from 0 to 31, copied into a buffer surrounded by guard bytes. Each byte inside the copy is checked against the source, and each byte outside it is checked to be untouched. The bounded variant is swept the same way at every bucket boundary (0, 1, 2, 3, 4, 7, 8, … 255, 256, 257).

Before each benchmark, every contender then replays 16 iterations of that test's exact workload into its own buffer, and the final buffers are compared byte-for-byte against std::memcpy's. Nothing is timed until it has been proven correct on that machine, with that compiler, on that exact input. Validation runs across the full Windows MSVC, Ubuntu GCC, Ubuntu Clang, macOS Clang, and macOS GCC matrix on every push.

Benchmark Methodology

Throughput is measured in megabytes copied per second (MB/s), benchmarked against std::memcpy with a runtime length on identical hardware. Every timed iteration performs 4,096 copies between two 64 KiB buffers. Copy i starts at offset (i × 192) & 0xFF00, plus a small jitter ((i × 5) & 63 on the source, (i × 11 + 3) & 63 on the destination), so copies land at varied alignments while the address stream stays regular and cache-resident.

Lengths come from a fixed 65,536-entry table generated by a seeded LCG over each test's range. Every iteration starts 12,347 entries further into the table, so consecutive iterations replay different length sequences. Every length also passes through a volatile read, so the compiler can never treat a size as a constant. There are two stages, each a head-to-head against std::memcpy on the identical workload, and both run the same six ranges: 1–15, 1–16, 1–17, 1–31, 1–32, 1–33, 1–63, 1–64, 1–65, 1–127, 1–128 and 1–129 bytes.

The ranges come in triplets around each power of two from 16 to 128. A range ending at 2^k − 1 exactly fills its top bucket. Ending at 2^k adds a single length that falls into the next bucket up, and ending at 2^k + 1 adds two. For memcpy_decomp that is a rare extra branch; for memcpy_decomp_up_to<N> it is one more bucket compiled in. Each triplet shows what crossing that boundary costs, and the 127–129 triplet reaches into the 128-byte bucket.

The harness uses adaptive epoch sampling. The exact iteration counts, thresholds, and timing bounds for each run are read live from that run's own results CSV, since they can vary per run. Each epoch runs a fresh batch of iterations, starting at the configured measured-iteration count and doubling every epoch, and is scored on a trailing window of k = clamp(iterations / 10, MinK, MaxK) samples. An epoch's score is its relative standard error plus its mean shift from the previous epoch.

Sampling does not stop at the first good epoch. It keeps running until the time limit or the total iteration budget is exhausted, and the lowest-scoring epoch is kept as the canonical result, whether or not it met the convergence thresholds. That result counts as converged only if its RSE and mean shift are both at or under their configured thresholds. Non-converged results are still included in the rankings and in win/tie/loss tallying, so a result that missed those thresholds should be read with its reduced statistical confidence in mind.

All results are ranked by throughput. Neighbouring results are checked for a statistical tie with Welch's t-test on per-iteration timings, using Bessel-corrected variance and Welch–Satterthwaite degrees of freedom at roughly 95% confidence, so a small delta inside the noise floor doesn't get dressed up as a victory. CPU caches are evicted before each contender's run.

Every range stays at or below 129 bytes — the regime that small-copy-heavy workloads like serialization actually live in. The CPU, OS, and compiler for each run are detected at build time and recorded in that platform's result file.

Platforms: Windows, Linux, macOS — Compilers: MSVC, GCC, Clang — Harness: BenchmarkSuite

Results

Acknowledgments

• Jsonifier — where this decomposition was first built and battle-tested on real serialization workloads.
• The overlapping-copy trick — a long-standing idiom in high-performance libc memcpy implementations for handling sub-vector tails without a loop.
• BenchmarkSuite — the measurement harness powering the comparisons here.