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 four 64-bit Go targets, assembly generated by go-asmgen — on plain go build, no cgo, no GOEXPERIMENT:

arch	ISA	how
amd64	SSE2	PCMPEQB+PMOVMSKB, BSF first diff
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

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

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.

Regenerating

go-asmgen is a generate-time tool, not a dependency (the *_gen.go are //go:build ignore; the .s are committed). To regenerate:

go get github.com/go-asmgen/asmgen@v0.4.0 && go generate ./... && 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].