streamvbyte

README

streamvbyte

Pure-Go Stream VByte integer (uint32) compression with a SIMD encoder and decoder on all six of Go's 64-bit SIMD targets — amd64, arm64, ppc64le, s390x, riscv64, loong64 — and a portable scalar fallback everywhere else. No cgo, no GOEXPERIMENT, plain go build.

Stream VByte is the byte-oriented integer codec of Lemire, Kurz & Rupp (arXiv:1709.08990). A []uint32 is stored as a control stream of 2-bit lengths (one byte per four integers) followed by a data stream of each integer's significant little-endian bytes (1–4). Each control byte indexes a 256-entry shuffle LUT that, in a single PSHUFB / VTBL / VPERM / vrgather / vshuf.b, decodes four packed integers' bytes into four zero-extended uint32 lanes — or, with the mirror-image LUT, encodes four uint32 lanes by compacting their significant bytes back into the data stream. (Per-group length classification stays scalar; the byte movement is the vectorised part.)

The wire format is byte-for-byte identical to the reference C library (github.com/lemire/streamvbyte, standard 1234 variant), so output interoperates in both directions.

Install

go get github.com/go-simd/streamvbyte

Usage

import "github.com/go-simd/streamvbyte"

src := []uint32{1, 280, 70000, 0xFFFFFFFF, 42}

// Encode.
buf := make([]byte, streamvbyte.EncodedMaxLen(len(src)))
n := streamvbyte.Encode(buf, src)
buf = buf[:n] // the compressed bytes

// Decode (the integer count is carried out-of-band, like the C library).
out := make([]uint32, len(src))
streamvbyte.Decode(out, buf, len(src))
// out == src

API:

Function	Description
EncodedMaxLen(n int) int	upper bound on the encoded size of n integers
Encode(dst []byte, src []uint32) int	encode; returns bytes written
Decode(dst []uint32, src []byte, n int) int	decode n integers; returns bytes read

Decode(Encode(x)) round-trips exactly. The count n is not stored in the stream (store it yourself), matching the reference format.

How the SIMD kernels work

Decode. Per group of four integers the kernel loads 16 data bytes, looks up the control byte's 16-byte shuffle mask, performs one vector permute that drops each integer's bytes into a zero-extended lane, and stores 16 result bytes. The Go wrapper runs the kernel only over groups that have a full 16-byte data lookahead and finishes the < 4 remainder (and any short-input tail) with the shared scalar decoder, so the wide load never over-reads.

Encode is the inverse. The Go wrapper classifies each group's four integers into 2-bit length codes (the control byte) and walks the resulting per-group data lengths; the kernel then, per group, loads the 16 source bytes, looks up the control byte's compaction mask (the mirror of the decode LUT), permutes the significant low bytes of each lane contiguously into the data stream, and stores 16 bytes at the running data cursor (only 1..16 of them significant; the rest are overwritten by the next group). The kernel runs only over groups with a full 16-byte store lookahead; the < 4 remainder uses the shared scalar encoder. Both directions share the 256-entry LUT family in tables.go, so the wire bytes are identical on every path. Length classification stays scalar, so encode's SIMD speedup is smaller than decode's.

• amd64 — PSHUFB (SSSE3; runtime-detected via golang.org/x/sys/cpu, scalar fallback otherwise).
• arm64 — VTBL (NEON, baseline).
• riscv64 — vrgather.vv (RVV, VLEN >= 128).
• loong64 — vshuf.b (LSX) with a zero companion register.
• ppc64le — VPERM on POWER8+ (LXVB16X / STXVB16X byte-order-stable loads keep the index == memory-offset identity; zero companion register).
• s390x — VPERM on z13+. Big-endian: a uint32 is stored most-significant-byte-first while the data stream stays LSB-first, so the LUT reverses each lane's bytes (decode permTableBE, encode encodeShuffleTablePermBE; see tables.go). The byte order is pinned by a position-dependent test.

Each arch has both a decode and an encode kernel using the same primitive. The assembly is generated by go-asmgen; regenerate with go run decode_<arch>_gen.go / go run encode_<arch>_gen.go (the .s files are committed).

Performance

go test -bench . on a 4096-element mixed-width slice (16 KiB of uint32):

Target	Decode (SIMD)	Decode (scalar)	Speedup
arm64 (Apple M-series, native)	~18.6 GB/s	~1.9 GB/s	~10×
amd64 (emulated VM*)	~0.73 GB/s	~0.32 GB/s	~2.3×
ppc64le (POWER9, VSX, native)	~3695 MB/s	~311 MB/s	~11.6×
riscv64 (SpacemiT X60, RVV 1.0, native)	~829 MB/s	~184 MB/s	~4.5×
s390x	qemu-validated; native perf pending	—	—
loong64 (Loongson 3A5000, LSX, native)	~11.8× scalar (real silicon, 2026-06-26)	—	~11.8×

Target	Encode (SIMD)	Encode (scalar)	Speedup
arm64 (Apple M-series, native)	~2.23 GB/s	~2.06 GB/s	~1.08×
amd64 (emulated VM*)	~0.24 GB/s	~0.20 GB/s	~1.2×
ppc64le (POWER9, VSX, native)	full SIMD encode+decode	—	—
riscv64 (SpacemiT X60, RVV 1.0, native)	full SIMD encode+decode	—	—
s390x	qemu-validated; native perf pending	—	—
loong64 (Loongson 3A5000, LSX, native)	full SIMD encode+decode	—	—

* The amd64 figures were measured inside an emulated x86-64 VM (no hardware virtualization on the development host), so they understate native silicon by a large margin; treat them as correctness-grade lower bounds, not hardware numbers. Throughput is len(src)*4 bytes per slice. Decode is the algorithm's strong suit (the whole hot loop vectorises); encode's gain is modest because only the byte compaction is vectorised — the per-group length classification stays scalar.

Measured on real POWER9 (ppc64le VSX, GCC Compile Farm, Go 1.26.4, 2026-06-26): SIMD decode ~11.6× the scalar baseline (3695 vs 311 MB/s), plus full SIMD encode+decode. Also measured on real riscv64 (SpacemiT X60, RVV 1.0, GCC Compile Farm, Go 1.26.4, 2026-06-26): SIMD decode ~4.5× the scalar baseline (829 vs 184 MB/s). The X60 is a low-power in-order RVV 1.0 core — currently the only widely-available RVV silicon — so this vrgather-bound decode would likely do better on an out-of-order RVV part; treat it as a real but conservative win. Also measured on real loong64 (Loongson 3A5000, LSX, GCC Compile Farm cfarm401, Go 1.26.4, 2026-06-26): SIMD decode ~11.8× the scalar baseline, plus full SIMD encode+decode (correctness-validated on real silicon). s390x throughput stays an estimate/pending — no GitHub-hosted IBM Z runner — so we never quote a native s390x number.

Other Go ports

Existing Go implementations (thempatel/streamvbyte-simdgo, bmkessler/streamvbyte, mhr3/streamvbyte, nelz9999/stream-vbyte-go) ship SIMD only for amd64 (and scalar elsewhere). This package is, to our knowledge, the first to provide SIMD encode and decode on all six of Go's 64-bit SIMD architectures from one code base.

Validation

Round-trip table tests plus FuzzRoundTrip (Decode(Encode(x)) == x) run with 100% statement coverage on every architecture: amd64 and arm64 natively, and ppc64le, s390x, riscv64, loong64 under QEMU (the same matrix the CI runs). ppc64le and riscv64 are additionally exercised natively on real POWER9 / SpacemiT X60 (RVV 1.0) silicon (GCC Compile Farm). The portable scalar fallback is also build+test validated on ppc64 (big-endian) on real POWER9 silicon — proving it bit-exact on a big-endian target distinct from s390x's vector kernel. So: six SIMD targets, validated on seven architectures. Format interop with the reference C library was verified bidirectionally and byte-for-byte (Go→C decode, C→Go decode, identical wire bytes).

License

BSD-3-Clause. See LICENSE.

Documentation

Overview

Package streamvbyte implements Stream VByte — the SIMD-friendly byte-oriented integer compression codec of Lemire, Kurz & Rupp (Information Processing Letters 130, 2018; arXiv:1709.08990). A []uint32 is encoded as a *control stream* of 2-bit lengths (one byte per four integers, four 2-bit codes each, least-significant code first) followed by a *data stream* of each integer's significant little-endian bytes (1..4, code+1).

The wire format is byte-for-byte identical to the reference C library (github.com/lemire/streamvbyte, standard 1234 variant), so encoded output interoperates in both directions.

Both directions are SIMD: each control byte indexes a 256-entry shuffle LUT that, in a single PSHUFB/VTBL/VPERM/vrgather/VSHUF, either spreads four packed integers' bytes into four zero-extended uint32 lanes (decode) or, with the mirror-image LUT, compacts four uint32 lanes' significant bytes back into the data stream (encode). The hot loops are assembly (generated by go-asmgen) on all six of Go's 64-bit SIMD targets — amd64, arm64, ppc64le, s390x, riscv64, loong64 — with a portable scalar fallback elsewhere. Per-group length classification stays scalar, so decode (a fully vectorised loop) gains more than encode. No cgo, no GOEXPERIMENT, plain `go build`.

Index

• func Decode(dst []uint32, src []byte, n int) int
• func Encode(dst []byte, src []uint32) int
• func EncodedMaxLen(n int) int

Functions

func Decode

func Decode(dst []uint32, src []byte, n int) int

Decode reads n integers in Stream VByte format from src (control bytes followed by data bytes, as produced by Encode) into dst and returns the number of bytes consumed from src. dst must have length >= n; Decode panics otherwise. Decode(dst, Encode(dst2, src), len(src)) reproduces src exactly.

func Encode

func Encode(dst []byte, src []uint32) int

Encode writes the Stream VByte encoding of src into dst and returns the number of bytes written. dst must have length >= EncodedMaxLen(len(src)); Encode panics otherwise. The layout is [control bytes][data bytes], matching the canonical reference format.

On the six 64-bit SIMD targets the data-compaction step runs in assembly (one shuffle per group of four integers, the inverse of the decode shuffle); the portable build and the < 4 tail use the shared scalar encoder. The wire bytes are identical on every path.

func EncodedMaxLen

func EncodedMaxLen(n int) int

EncodedMaxLen returns an upper bound on the number of bytes Encode needs for n integers: the control stream ((n+3)/4 bytes) plus the worst case of 4 data bytes per integer. dst passed to Encode must be at least this long.