streamvbyte

README

streamvbyte

Pure-Go Stream VByte integer (uint32) compression with a SIMD 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). Decode is the SIMD star: each control byte indexes a 256-entry shuffle LUT that, in a single PSHUFB / VTBL / VPERM / vrgather / vshuf.b, spreads four packed integers' bytes into four zero-extended uint32 lanes.

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 decoder works

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.

• 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 decoded uint32 is stored most-significant-byte-first while the data stream stays LSB-first, so the shuffle table reverses each lane's bytes (see tables.go/permTableBE). The byte order is pinned by a position-dependent test.

The decode assembly is generated by go-asmgen; regenerate with go run decode_<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 / s390x	qemu-validated; native perf pending	—	—
riscv64 / loong64	qemu-validated; native perf pending	—	—

* The amd64 figure was measured inside an emulated x86-64 VM (no hardware virtualization on the development host), so it understates native silicon by a large margin; treat it as a correctness-grade lower bound, not a hardware number. Throughput is len(src)*4 bytes per decoded slice. Decode is the algorithm's strong suit; encode is scalar and runs at a few GB/s.

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 a SIMD decoder 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). 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.

Decode is the SIMD star: each control byte indexes a 256-entry shuffle LUT that, in a single PSHUFB/VTBL/VPERM/vrgather/VSHUF, spreads four packed integers' bytes into four zero-extended uint32 lanes. The hot decode loop is 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. 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.

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.