matchlen

README

matchlen

MatchLen(a, b []byte) int — the length of the common prefix of two byte slices. It is the core primitive of every LZ-family compressor's match-finder (LZ4, zstd, LZFSE/LZVN, brotli, …) and the single most SIMD-amenable spot in LZ encoding.

The hot comparison loop is real SIMD on all six 64-bit Go targets, assembly generated by go-asmgen — on plain go build, no cgo, no GOEXPERIMENT:

arch	ISA	how
amd64	SSE2 + AVX2	(V)PCMPEQB+(V)PMOVMSKB, BSF; AVX2 (32-byte) auto-selected
arm64	NEON	VEOR, first non-zero byte via RBIT+CLZ
loong64	LSX	VXORV, lane→GPR via VMOVQ V.V[i], CTZV
riscv64	RVV	VXOR+VMSNE, vfirst.m
ppc64le	VSX	LXVD2X+VCMPEQUB, mask→GPR via MFVSRD, CNTTZD
s390x	vector facility (big-endian)	VL+VFENEBS (find-element-not-equal w/ CC), index via VLGVB

VSX is baseline on POWER8+ and the vector facility is baseline on z13+, so ppc64le and s390x need no runtime feature dispatch — the SIMD path is simply the arch's only path (build-tagged), like riscv64 and loong64. s390x is the one big-endian target: VL puts the lowest memory address in the high-order lane, and VFENEBS scans lane 0 upward, so the byte index it returns is already the memory offset of the first differing byte — no scan-direction reversal needed (the little-endian arches count trailing zeros of a least-significant-byte-first word instead). ppc64le's LXVD2X loads the low-address 8 bytes into the first doubleword in little-endian byte order, which CNTTZD then scans.

Other architectures use a portable 8-byte-word scalar fallback. The result is bit-identical everywhere (checked vs a byte-by-byte reference and fuzzed).

Test coverage

The Go code is at 100 % statement coverage, gated in CI on every architecture (native amd64 + arm64, and riscv64 + loong64 + ppc64le + s390x under QEMU); the build fails below 100 %. Six SIMD targets, validated on seven architectures: the portable scalar fallback is additionally proven bit-exact on real POWER9 silicon as ppc64 (big-endian) — a big-endian target distinct from s390x's vector kernel. Both amd64 dispatch branches (AVX2 and the SSE fallback) are exercised on the native amd64 runner by toggling the feature flag. The coverage figure is of the Go code only — the generated .s SIMD kernels are not measured by go test -cover; they are validated by differential tests against the scalar reference plus a fuzz target.

n := matchlen.MatchLen(a, b) // a[:n] == b[:n], n maximal

Performance

SIMD MatchLen vs the 8-byte-word scalar reference, ~4 KiB shared prefix (-count=6, medians, as of 2026-06-14):

arch	host	SIMD	scalar ref	speedup
arm64	Apple Silicon (native)	~31.3 GB/s	~3.0 GB/s	~10.4x
amd64	x86_64 QEMU VM (ratio valid, absolute MB/s low)	—	—	~10.6x

The match-counter alone (native amd64, GitHub runner): SSE2 ~17.6 GB/s, AVX2 ~36.6 GB/s (~2.08x) — AVX2 is picked at runtime when available. The verdict holds: SIMD is ~10x the scalar fallback on both native arches.

ppc64le — measured on real POWER10

Measured on real POWER10 (ppc64le VSX, GCC Compile Farm, Go 1.26.4, June 2026): the VSX MatchLen runs at ~6.3x the scalar baseline (5320 vs 841 MB/s). This supersedes the earlier llvm-mca pwr9 cycle-model estimate — on real POWER10 silicon the VSX path is a clear win over the scalar word loop.

riscv64 — measured on real SpacemiT X60

Measured on a real SpacemiT X60 (riscv64 RVV 1.0, GCC Compile Farm, Go 1.26.4, June 2026): the RVV MatchLen runs at ~5.8x the scalar baseline (1236 vs 214 MB/s) — a strong RVV win. Caveat: the X60 is a low-power, in-order core and is currently the only widely-available RVV 1.0 silicon, so absolute MB/s are modest; the ratio is the meaningful signal. On this arithmetic/compare-bound kernel RVV wins clearly; an out-of-order RVV core would likely lift it further.

s390x — llvm-mca cycle-model estimate

Static analysis, NOT a hardware measurement; native perf still pending real silicon. There is no GitHub-hosted IBM Z runner and qemu's TCG is not cycle-accurate (s390x is QEMU-validated for correctness only), so the only defensible throughput signal is a cycle model. These numbers come from llvm-mca (LLVM 22) fed the steady-state (no-match) inner loop translated to LLVM asm syntax. They model the no-mismatch iteration — the throughput-determining path — not the data-dependent early-exit tail.

arch	cpu model	SIMD cyc/iter	SIMD B/cyc	scalar B/cyc	ratio
s390x	z14	1.2 (16 B)	~13.3	~5.3 (8 B / 1.5 cyc)	~2.5x (estimate)

Honest read: on z14 the vector path is ~2.5x (estimate) because VFENEBS does the find-not-equal in-lane and the only GPR extraction is a single VLGVB. Caveats: llvm-mca idealizes the frontend (perfect dispatch, no branch-mispredict, no cache misses), so these are upper bounds on the kernel's compute; it models VFENEBS's condition-code side effect only approximately (the CC-setting vfeneb form is used). Real IBM Z silicon may differ.

Regenerating

go-asmgen is a generate-time tool, not a dependency (the *_gen.go are //go:build ignore; the .s are committed). To regenerate, add the tool, run each generator, then drop it back out of the module graph:

go get github.com/go-asmgen/asmgen@v0.5.0
for g in *_gen.go; do go run "$g"; done
go mod edit -droprequire github.com/go-asmgen/asmgen && go mod tidy

License

BSD-3-Clause.

Documentation

Overview

Package matchlen finds the length of the common prefix of two byte slices — the core primitive of every LZ-family compressor's match-finder (LZ4, zstd, LZFSE/LZVN, brotli, …). The hot comparison loop is SIMD on amd64, arm64, loong64 and riscv64 (assembly generated by go-asmgen) and a portable 8-byte scalar elsewhere — all on plain `go build`, no cgo, no GOEXPERIMENT.

Index

• func MatchLen(a, b []byte) int

Functions

func MatchLen

func MatchLen(a, b []byte) int

MatchLen returns the number of leading bytes that a and b share: the largest n <= min(len(a), len(b)) with a[:n] == b[:n].