alp

README

ALP: Adaptive Lossless floating-Point Compression

A small Go implementation of the ALP compression algorithm for IEEE 754 float64 data.

Install

go get github.com/axiomhq/alp

Use

ALP operates on fixed blocks of 1,024 values. Sample representative data once, then reuse the returned state for blocks with similar values.

package main

import (
	"fmt"

	"github.com/axiomhq/alp"
)

func main() {
	values := make([]float64, alp.VectorSize)
	for i := range values {
		values[i] = float64(i) / 100
	}

	state := alp.Sample(values)

	var vector alp.Vector
	alp.Encode(&vector, values, state)

	packed := alp.Pack(&vector)
	fmt.Printf("compressed to %d bytes\n", len(packed))

	var restored alp.Vector
	alp.Unpack(&restored, packed)

	decoded := make([]float64, alp.VectorSize)
	alp.Decode(decoded, &restored)
}

Encode and Decode do not allocate. Pack returns the serialized form of a vector, while PackedSize reports its size before allocation.

Algorithm

ALP finds an exponent and factor that transform decimal floating-point values into integers without losing their exact IEEE 754 representation. Each block is then frame-of-reference encoded and bit-packed. Values that do not round-trip through the integer transform, including NaNs, infinities, and negative zero, are stored as exceptions using their original bits.

See ALP: Adaptive Lossless floating-Point Compression for the algorithm described at SIGMOD 2024.

License

MIT License. See LICENSE.

Documentation

Overview

Package alp implements Adaptive Lossless floating-Point compression.

ALP is a lossless compression scheme for floating-point data from SIGMOD 2024. It exploits the fact that most real-world floats are human-friendly decimals that can be represented as integers scaled by powers of 10.

Reference: https://dl.acm.org/doi/10.1145/3626717

Index

• Constants
• func Decode(dst []float64, src *Vector)
• func DecodeRD48(dst []float64, leftCodes, rightParts []byte, prefixes [2]uint16)
• func Encode(dst *Vector, src []float64, s State)
• func Pack(vector *Vector) []byte
• func PackedSize(vector *Vector) int
• func Unpack(dst *Vector, src []byte)
• type State
  • func Sample(data []float64) State
• type Vector

Constants

const VectorSize = 1024

VectorSize is the number of values per compression block. This matches the paper's recommendation for cache efficiency.

Functions

func Decode

func Decode(dst []float64, src *Vector)

Decode decompresses src into dst. dst must contain exactly VectorSize elements.

func DecodeRD48

func DecodeRD48(dst []float64, leftCodes, rightParts []byte, prefixes [2]uint16)

DecodeRD48 decodes the common ALP-RD layout with two 16-bit prefixes and one packed 48-bit suffix per value. Each bit in leftCodes selects one of the prefixes; rightParts stores six little-endian bytes per value.

DecodeRD48 panics if leftCodes or rightParts are too short for dst.

func Encode

func Encode(dst *Vector, src []float64, s State)

Encode compresses src into dst using s. src must contain exactly VectorSize values.

func Pack

func Pack(vector *Vector) []byte

Pack serializes a Vector to bytes.

The format is a 13-byte header, bit-packed encoded values, then exceptions. The header contains frame-of-reference (8 bytes), bit width, exponent, factor, and exception count (2 bytes), all in little-endian order.

func PackedSize

func PackedSize(vector *Vector) int

PackedSize returns the number of bytes Pack will produce for vector.

func Unpack

func Unpack(dst *Vector, src []byte)

Unpack deserializes src into dst. If src is incomplete, Unpack decodes all complete fields and leaves unavailable data at its zero value.

Types

type State

type State struct {
	Exp    uint8 // Exponent: multiply by 10^Exp before rounding
	Factor uint8 // Factor: divide by 10^Factor after rounding
}

State holds the encoding parameters learned from sampling. A single State can encode many vectors of similar data.

func Sample

func Sample(data []float64) State

Sample analyzes data to find encoding parameters.

type Vector

type Vector struct {
	// Encoded contains the integers after ALP transformation.
	Encoded [VectorSize]int64

	// FrameOfRef is the minimum encoded value subtracted for bit-packing.
	FrameOfRef int64

	// BitWidth is the number of bits needed to represent max-min.
	BitWidth uint8

	// Exp and Factor are the encoding parameters used for this vector.
	Exp    uint8
	Factor uint8

	// ExceptionPos and ExceptionBits contain the positions and raw float bits
	// for values that do not round-trip through the integer transform. Only the
	// first NumExceptions entries are valid.
	NumExceptions uint16
	ExceptionPos  [VectorSize]uint16
	ExceptionBits [VectorSize]uint64
}

Vector is a compressed block of VectorSize float64 values.