entropack-alp

Lossless floating-point compression at multi-GB/s

From the SIGMOD 2024 best-artifact paper — decodes faster than the C++ reference on Apple Silicon.

English | 简体中文

Pure-Rust implementation of ALP — Adaptive Lossless floating-Point compression (SIGMOD 2024). Zero dependencies, #![forbid(unsafe_code)], MSRV 1.75.

The paper

This crate independently implements the algorithm from:

Azim Afroozeh, Leonardo X. Kuffo, and Peter Boncz. ALP: Adaptive Lossless floating-Point Compression. Proc. ACM Manag. Data 1(4), Article 230, December 2023. ACM · DOI · author self-archive (CWI) · official C++ reference implementation

@article{afroozeh2023alp,
  author    = {Afroozeh, Azim and Kuffo, Leonardo X. and Boncz, Peter},
  title     = {ALP: Adaptive Lossless floating-Point Compression},
  journal   = {Proceedings of the ACM on Management of Data},
  volume    = {1},
  number    = {4},
  articleno = {230},
  year      = {2023},
  doi       = {10.1145/3626717}
}

Not affiliated with CWI. This is an independent implementation of the published algorithm; the compressed layout is this crate's own and is not wire-compatible with the C++ reference.

What is implemented

• ALP scheme — encodes doubles that originated as decimals into small integers via d = round(n × 10^e × 10^-f) with one (e, f) per 1024-value vector; SIMD-friendly magic-number rounding (2⁵¹ + 2⁵²); every value is verified by decoding it back and comparing raw bits, failures go to an exception side-channel (64-bit value + 16-bit position).
• FFOR — frame-of-reference (subtract min) + LSB-first bit-packing at a per-vector width, all widths 0..=64.
• ALP_rd fallback — for "real doubles" (high-precision data): each 64-bit pattern is cut at position p ≥ 48 into a left part (≤ 16 bits, dictionary of ≤ 8 entries with exceptions) and a verbatim bit-packed right part. Chosen per row group when sampling shows the decimal scheme cannot compress.
• Two-level adaptive sampling (paper §3.2) — per row group: full search over 190 (e, f) combinations on a small sample, keep the top 5; per vector: early-exit search among those candidates.
• Outlier demotion (extension beyond the paper) — before packing, a value is demoted to the exception path whenever that lowers total bits (1024 × bit-width for the packed stream vs. 80 bits per exception), so a handful of stray wide values cannot widen a whole vector.
• float32 (paper §4.4) — full ALP + ALP_rd for f32 via compress_f32/decompress_f32 (e ≤ 10, 48-bit exceptions, ALP_rd cut at p ∈ 16..=31). ML-weight-style data compresses to ~27 bits/value via ALP_rd (the paper reports 28.1 on real model weights). Compressed (f64) and Compressed32 share the same container layout but are not interchangeable — a future wire format must carry the precision flag out of band.
• Fused kernels (paper §4.2) — single-pass unFFOR+decode on the decompression path and FOR-subtract fused into bit-packing on the compression path, width-specialized at compile time.
• Cascaded DICT/RLE + ALP (paper Table 4) — row groups dominated by repeated values are DICTIONARY-encoded (bitwise-deduplicated sorted dictionary + bit-packed codes), row groups with long constant runs are RLE-encoded (bit-packed run lengths); the dictionary values / run values are then compressed by the plain ALP/ALP_rd path, so cascade depth is structurally fixed at one. Each row group picks among the four schemes by estimated physical bits; repetition detection compares raw bits, never float equality, so NaN runs and -0.0 stay lossless.
• Compressed::validate() — structural check for untrusted inputs; decompress itself trusts its input (documented contract).

Losslessness contract: decompress(&compress(data)) reproduces data bit-exactly for every input — including NaN payloads, -0.0, infinities and denormals. Enforced by property tests over the full u64 and u32 bit-pattern domains. Compression is also deterministic: the same input always produces a bit-identical compressed representation (locked by tests).

Compression ratios

Measured on synthetic data with deterministic seeds — reproduce with cargo run --release --example compression_ratio:

dataset	values	bits/value	vs 64-bit
two-decimal prices	250,000	24.12	2.65x
integers stored as doubles	10,000	20.57	3.11x
constant column	5,000	0.09	727x
random bit patterns (ALP_rd)	120,000	64.44	0.99x
half prices, half random	102,400	52.05	1.23x
100 distinct prices shuffled (DICT+ALP)	100,000	7.13	8.98x
long constant runs (RLE+ALP)	150,000	0.23	281x

float32 (baseline is 32 bits per value):

f32 dataset	values	bits/value	vs 32-bit
two-decimal prices	250,000	20.10	1.59x
random bit patterns (ALP_rd)	120,000	32.22	0.99x
ML-weight-style (ALP_rd)	8,192	27.00	1.19x

Truly random bit patterns are incompressible by design; ALP_rd bounds the overhead to well under 1%. The paper reports 21.7 bits/value on average across its 30 real-world datasets (18.8 with the same DICT/RLE cascade this crate implements), and 28.1 bits/value on real f32 model weights; numbers here are synthetic and not directly comparable.

Quick start

Not yet published to crates.io — use a git dependency for now.

use entropack_alp::{compress, decompress};

let data: Vec<f64> = vec![8.0605, 1.23, 4.56];
let compressed = compress(&data);
println!("{:.2} bits/value", compressed.bits_per_value());

let restored = decompress(&compressed);
assert!(data.iter().zip(&restored).all(|(a, b)| a.to_bits() == b.to_bits()));

// float32 uses the parallel entry points:
let weights: Vec<f32> = vec![0.1, 0.2, 0.3];
let c32 = entropack_alp::compress_f32(&weights);
let restored32 = entropack_alp::decompress_f32(&c32);

Benchmarks

cargo bench --bench codec — representative single-core numbers on an Apple M-series laptop (throughput varies with hardware):

benchmark	throughput
end-to-end decompress (prices)	2.80 Gelem/s (≈22 GB/s of doubles)
end-to-end compress (prices)	235 Melem/s
decode kernel (fused unFFOR+decode)	8.2 Gelem/s
bit-unpack kernels (widths 4–48)	6.2–9.9 Gelem/s

The structural result transfers across hardware even if the numbers do not: the paper's central claim — branch-free fixed-length loops auto-vectorize — holds for this implementation. The decode kernel compiles to 4x-unrolled NEON (scvtf.2d + fmul.2d, verified in the final binary after thin-LTO), and force-disabling both LLVM vectorizers slows it down by 2.16x — essentially the full theoretical gain of NEON's two f64 lanes.

Against the C++ reference (cwida/ALP) — same machine, same data, symmetric accounting, upstream's arm64 NEON falp kernel linked, medians of 3 A/B-interleaved groups (run-to-run spread < 1%):

path (ns/value, lower is better)	cwida/ALP (C++)	this crate
decompress (fused kernels)	scalar 0.405 / NEON 0.411	0.360
compress (full pipeline)	3.18	4.39

Compression ratios on scheme-matched datasets are bit-for-bit identical between the two implementations. On two-decimal prices this crate wins 24.12 vs 31.02 bits/value: the reference's int64-multiply decode path overflows at (e=14, f=12), turning 7.8% of values into exceptions, while the all-float path here has none. The upstream hand-written NEON kernel ties its own auto-vectorized scalar build — independently reproducing the paper's Figure 4 result on Apple Silicon.

Testing

cargo test          # 119 tests: unit + integration + property-based
cargo clippy --all-targets -- -D warnings

Coverage includes: per-module unit tests (bit-packing round-trips at every width, the paper's 8.0605 example, -0.0/NaN-payload/denormal exception paths), end-to-end integration tests for both precisions (multi-row-group data, boundary lengths, determinism), cascade suites (scheme-selection contracts, the estimate-equals-encoded-payload invariant), robustness tests against malformed Compressed values (deep nesting, corrupted streams, inflation caps), fused-vs-unfused differential tests over every bit width, and property tests over the full u64 and u32 bit-pattern domains.

License

Apache-2.0.