Compression: breaking the memory wall.

Making things go faster is pretty simple:

1. Move less data
2. Over a more efficient channel
3. Using a more efficient protocol

k made vectors the unit of thought. l makes compressed vectors the unit of execution. The focus is squarely on move less data.

Modern analytical throughput is bound by memory traffic, not compute. CPUs have more execution units than memory systems can feed. Once a vector exceeds L1/2/3 cache, execution is a streaming problem: cache lines must move from DRAM to registers. This is the memory wall. l scales it from day 0.

The roofline view

A reduction has low arithmetic intensity. A dense 64-bit sum does one operation per eight bytes loaded. The kernel is optimal: 4-way-unrolled AVX-512 vpaddq, independent accumulators, aligned loads, prefetch.

The roofline is brutal. At low intensity, sustained bandwidth sets the ceiling. A dense sum is optimal but slow: it waits on bytes, not arithmetic.

On AMD EPYC 9B45, the dense 64-bit integer sum baseline over a 4 GB working set measures:

dense KJ sum, 4 GB:  95.4 ms  ~45 GB/s

A strong streaming result. Bandwidth is the bottleneck.

Most engines treat compression as a storage detail. This saves disk space, but not bandwidth: the hot primitive still runs over the expanded form.

l treats compression as execution layout. Any vector, table, or structure can be transparently encoded. The logical value stays unchanged; only the physical form changes: dense, packed, dictionary, run, fused.

The programmer writes standard code, but the runtime sees a physical planning problem: logical type, physical layout, working-set size, cache behavior, decode cost, SIMD path, threads. Compression is part of the physical algebra.

Easy: integer compression

Integer columns are locally narrow. Timestamps are 64-bit, but adjacent deltas are tiny. A date is 32-bit, but a chunk’s Frame of Reference residual fits in a byte. Price, size, count all carry less entropy than declared.

l uses custom Frame of Reference over bit-packed residuals. Each chunk stores a base, a bit width, and packed deltas. The primitive runs a tiled pipeline:

read compressed tile
decode into L1
run SIMD primitive
discard tile
repeat

The dense vector never lands in DRAM. Only a decoded tile lives in L1. Decode is fused into the primitive, avoiding memory streams.

AMD EPYC example

The result is not subtle. AMD EPYC 9B45, AVX-512, single-threaded, 4 GB working set:

primitive	time	vs. dense
dense KJ sum	95.4 ms	—
XCMP W=8 sum	15.7 ms	6.07x faster
XCMP W=4 sum	13.0 ms	7.18x faster

The gain tracks working-set size, exactly as the memory model predicts:

working set	XCMP W=8	XCMP W=4
4 GB (DRAM)	6.07x	7.18x
512 MB	6.26x	7.32x
16 MB	3.88x	3.28x
1 MB (approximately L2)	2.37x	1.90x

At DRAM scale, compression wins by moving fewer bytes. As the working set shrinks into cache, the advantage fades because bandwidth pressure drops and decode overhead shows. The roofline predicts both ends.

The key equation

For bandwidth-bound primitives, dense is bounded by bytes moved. Compression wins when the bandwidth saved exceeds decode cost. The inequality holds for sum, min, max, and avg, but not for everything.

Compression as layout

k attributes, sorted and unique, describe values; encoding describes layout. A compressed vector is logically identical: same count, type, indexing. Only physical form differs. Compression changes execution, not meaning.

If a primitive has an encoding-aware path, it runs over compressed tiles; otherwise it materializes. The runtime decides.

Compression claim

l does not claim encoding makes every operation faster. It makes a narrower, stronger claim:

In an array runtime, physical encoding belongs in primitive dispatch.

Encoding is a first-class execution choice, not just a storage format. Bandwidth-bound primitives run compressed and beat dense SIMD; other operations fall back. The runtime is asymmetric because hardware is. The fastest byte is never moved.

That is the progression from k to l:

k:  vectors are the unit of expression
l:  encoded vectors are the unit of execution

References

• Drepper, What Every Programmer Should Know About Memory
• Williams, Waterman, Patterson, Roofline: An Insightful Visual Performance Model
• Boncz, Zukowski, Nes, MonetDB/X100: Hyper-Pipelining Query Execution
• Abadi, Madden, Ferreira, Integrating Compression and Execution in Column-Oriented Database Systems
• Zukowski, Heman, Nes, Boncz, Super-Scalar RAM-CPU Cache Compression
• Lemire et al., SIMD-BP128 / FastPFOR integer compression