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 %. 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

16-byte SIMD strides vs a naive byte loop, ~4 KiB shared prefix (Apple Silicon, arm64 NEON): ~34.7 GB/s vs ~3.3 GB/s — ~10x.

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.

ppc64le (VSX) and s390x (vector facility) are qemu-validated for correctness; native perf is pending — there is no GitHub-hosted POWER or IBM Z runner, and qemu's TCG is not cycle-accurate, so no throughput numbers are quoted for them.

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].