zlib-ng: isolating compress_block to measure zng_emit_dist (PR #2363 vs #2364, Apple M5)

zlib-ng-benchmark_compress_block.cc

/* benchmark_compress_block.cc -- benchmark the compress_block emit loop in isolation
 * Copyright (C) 2026 Nathan Moinvaziri
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

#include <stdio.h>
#include <cstring>

#include <benchmark/benchmark.h>

extern "C" {
#  include "zbuild.h"
#  include "zutil_p.h"
#  include "deflate.h"

extern Z_INTERNAL const ct_data static_ltree[L_CODES+2];
extern Z_INTERNAL const ct_data static_dtree[D_CODES];

/* compress_block is made non-static for this benchmark. */
void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree);
}

#define SYM_COUNT     32768u          /* symbols per compress_block call */
#define PENDING_SIZE  (SYM_COUNT * 8u)

/* Emits a synthetic symbol stream through compress_block with the static trees. The
 * stream mix is fixed by a seeded PRNG so every build under test sees identical work. */
class compress_block_bench: public benchmark::Fixture {
protected:
    deflate_state *s = nullptr;
    unsigned char *sym_storage = nullptr;
    uint64_t rs = 0;

    uint32_t rnd(uint32_t n) {
        rs = rs * 6364136223846793005ULL + 1442695040888963407ULL;
        return (uint32_t)((rs >> 33) % n);
    }

    /* lit_pct: share of symbols emitted as literals, the rest are match pairs. */
    void build_syms(uint32_t lit_pct) {
        rs = 0x9E3779B97F4A7C15ULL;
        unsigned char *p = sym_storage;
        for (unsigned i = 0; i < SYM_COUNT; i++) {
            if (rnd(100) < lit_pct) {
                /* literal: dist == 0, lc holds the byte */
                *p++ = 0;
                *p++ = 0;
                *p++ = (unsigned char)rnd(256);
            } else {
                /* match: distances skew short, as in real data. lc is len - STD_MIN_MATCH. */
                uint32_t dist = 1 + rnd(rnd(4) == 0 ? 32768 : 4096);
                uint32_t lc = rnd(256);
                *p++ = (unsigned char)(dist & 0xff);
                *p++ = (unsigned char)((dist >> 8) & 0xff);
                *p++ = (unsigned char)lc;
            }
        }
        s->sym_next = SYM_COUNT * 3;
    }

public:
    void SetUp(const ::benchmark::State&) {
        s = (deflate_state *)zng_alloc_aligned(sizeof(deflate_state), 64);
        memset(s, 0, sizeof(deflate_state));
        s->pending_buf = (unsigned char *)zng_alloc_aligned(PENDING_SIZE, 64);
        sym_storage = (unsigned char *)zng_alloc_aligned(SYM_COUNT * 3 + 8, 64);
        s->sym_buf = sym_storage;
        s->lit_bufsize = SYM_COUNT;
    }

    void Bench(benchmark::State& state, uint32_t lit_pct) {
        build_syms(lit_pct);
        for (auto _ : state) {
            s->pending = 0;
            s->bi_buf = 0;
            s->bi_valid = 0;
            compress_block(s, static_ltree, static_dtree);
            benchmark::DoNotOptimize(s->pending);
        }
        state.counters["bytes_out"] = benchmark::Counter((double)s->pending);
    }

    void TearDown(const ::benchmark::State&) {
        /* zng_alloc_aligned stores the original pointer, so it needs zng_free_aligned. */
        zng_free_aligned(s->pending_buf);
        zng_free_aligned(sym_storage);
        zng_free_aligned(s);
    }
};

/* all_match isolates zng_emit_dist, all_lit isolates zng_emit_lit, mixed is realistic. */
BENCHMARK_DEFINE_F(compress_block_bench, all_match)(benchmark::State& state) { Bench(state, 0); }
BENCHMARK_REGISTER_F(compress_block_bench, all_match);

BENCHMARK_DEFINE_F(compress_block_bench, mixed)(benchmark::State& state) { Bench(state, 70); }
BENCHMARK_REGISTER_F(compress_block_bench, mixed);

BENCHMARK_DEFINE_F(compress_block_bench, all_lit)(benchmark::State& state) { Bench(state, 100); }
BENCHMARK_REGISTER_F(compress_block_bench, all_lit);

zlib-ng-compress-block-benchmark.md

zlib-ng: isolating compress_block to measure zng_emit_dist (#2363 vs #2364)

#2363 (A) and #2364 (B) swap zng_emit_dist's base + extra tables for mask + extra tables. Full deflate calls both noise. Wrong instrument. An isolated compress_block benchmark puts A at about 10% on the match emit path.

Why full deflate misses it

level	compress_block	longest_match
3	~13%	43%
6	~4.5%	62%
9	~3.3%	72%

Matches are only part of the symbol stream. 10% off zng_emit_dist lands at 0.3% to 1.3% of deflate, under benchmark noise.

Benchmark

benchmark_compress_block.cc runs the real compress_block over a synthetic symbol buffer with the static trees. A seeded PRNG fixes the stream, so every build does identical work.

• all_match: isolates zng_emit_dist, the function both PRs change.
• all_lit: isolates zng_emit_lit, which neither PR touches. Null control. True delta is zero, so it reads the noise floor.
• mixed: 70% literals.

Needs compress_block non-static. Measurement hack, not a patch.

Results

Apple M5, arm64, clang -O2. Base and contenders interleaved round by round. Minimum of 20 rounds.

case	dev baseline	A minΔ	A medΔ	B minΔ	B medΔ
all_match (isolates zng_emit_dist)	113.93 us	-9.83%	-9.32%	-7.72%	-8.07%
mixed (~30% matches)	62.03 us	-2.51%	-1.91%	-1.15%	-1.17%
all_lit (control, emit_dist unused)	51.47 us	+1.45%	+0.69%	-0.90%	-0.34%

Emitted bytes identical across dev, A and B.

The control reads plus or minus 1.5% where truth is zero. That is the noise floor; the match-path effects sit six times above it. Dilution checks out: mixed is 30% matches, and 0.30 x -9.8% is about -2.9% against -2.5% measured.

Why A beats B

Each base is aligned to its extra-bit width, so (lc - base) & mask == lc & mask. Both PRs drop the base subtraction and the mask computation. On aarch64 four instructions become one, twice:

develop:  lsr w15, w12, #8          A/B:  and w11, w11, w12
          sub w11, w11, w12, uxtb
          lsl w15, w28, w15
          bic w11, w11, w15

They differ in table storage. A bit-packs mask and extra into one word. B uses a struct, costing an extra load per entry: the compiler will not refold the adjacent byte fields.

A:  ldrh w12, [x15, x12, lsl #1]     ; one 16-bit load
    add  w12, w13, w12, lsr #8       ; extra extraction folds into the add, free

B:  add  x12, x15, x12, lsl #1
    ldrb w15, [x12]                  ; .mask
    ldrb w12, [x12, #1]              ; .extra, second load

deflate_quick translation unit, aarch64:

variant	instructions	scalar loads
develop	402	60
A	395	60
B	399	62

A also frees the mov w28, #-1 mask constant, letting the allocator park _functable in x28 and drop an adrp/ldr pair.

The A to B gap of about 2 points is roughly 1.4 times the noise floor. Timing alone is suggestive, not decisive. Instruction and load counts point the same way.

B reads better. lmex.mask and lmex.extra are self-documenting. A needs a comment explaining why ANDing lc against the whole packed word is safe: it holds only because lc never has bits above 7 and dist never above 15. Correctness by invariant, quiet to break.

x86

Cross-compiled, A is worth roughly double: 443 to 429 instructions, against 402 to 395 on aarch64. Not benchmarked. The host is arm64, so x86 runs under Rosetta and would measure translation, not codegen. Needs real x86 hardware.

Machine

• Apple M5, 4 performance + 6 efficiency cores, 32 GB
• macOS 26.5.2
• Apple clang 21.0.0 (clang-2100.1.1.101)
• CMake Release, -D BUILD_SHARED_LIBS=OFF, separate build directory per variant
• zlib-ng develop @ 55fb5eb0, A = #2363, B = #2364