The simple beauty of XOR floating point compression

A normal network runs at 10Gbps or 1.25GiB/s.

200MiB/s is too slow by a factor of 7. Though obviously some people have optimised it.

People in the HPC/classical supercomputing space have done this sort of thing for a while. There's a fair amount of literature on lossless floating point compression, such as Martin Burtscher's work or stuff out of LLNL (fpzip):

https://userweb.cs.txstate.edu/~burtscher/ https://computing.llnl.gov/projects/floating-point-compressi...

but it tends to be very application specific, where there tends to be high correlation / small deltas between neighboring values in a 2d/3d/4d/etc floating point array (e.g., you are compressing neighboring temperature grid points in a PDE weather simulation model; temperature differences in neighboring cells won't differ by that much).

In a lot of other cases (e.g., machine learning) the floating point significand bits (and sometimes the sign bit) tends to be incompressible noise. The exponent is the only thing that is really compressible, and the xor trick does not help you as much because neighboring values could still vary a bit in terms of exponents. An entropy encoder instead works well for that (encode closer to the actual underlying data distribution/entropy), and you also don't depend upon neighboring floats having similar exponents as well.

In 2022, I created dietgpu, a library to losslessly compress/decompress floating point data at up to 400 GB/s on an A100. It uses a general-purpose asymmetric numeral system encoder/decoder on GPU (the first such implementation of general ANS on GPU, predating nvCOMP) for exponent compression.

We have used this to losslessly compress floating point data between GPUs (e.g., over Infiniband/NVLink/ethernet/etc) in training massive ML models to speed up overall wall clock time of training across 100s/1000s of GPUs without changing anything about how the training works (it's lossless compression, it computes the same thing that it did before).

https://github.com/facebookresearch/dietgpu

As the article states, you need to apply some heuristics to choose between cases (2) and (3). I'm not a big fan of that, because it means the encoding is not deterministic (as in, it leaves room for interpretation/optimization by encoders).

Just for fun I implemented this algorithm: https://go.dev/play/p/72GyYmVnwyc

The algorithm described in the article uses prefixes 0, 10, and 11. My algorithm uses different prefixes: 0, 10, 110, 1110, 11110, [...]. By default, the subsequence that is used is identical to that containing differing bits during the previous iteration. The prefixes describe previously can be used to widen the subsequence:

- 0: Keep the subsequence the same width.

- 10: Make the subsequence (1<<1)-1 = 1 bit wider, both on the left and right side.

- 110: Make the subsequence (1<<2)-1 = 3 bits wider, both on the left and right side.

- 1110: Make the subsequence (1<<3)-1 = 7 bits wider, both on the left and right side.

- ...

For the sequence of numbers presented under "Tweaking the algorithm", the algorithm in the article produces 969 bits of data. My algorithm produces just 823.

Edit: Tiny bug in original code.

Edit 2: maybe it’s smarter to widen the subsequence using triangular numbers. Doing it exponentially is a bit too aggressive, it seems.

How does this compare to regular dictionary compression?

One of the things we've learned from columnar data stores and compression formats is that choosing the correct stride order really matters.

I noticed this a decade ago when I stumbled on a voxel engine that used some complex height map compression scheme for game map data. It seemed gratuitous to me, so I tried the simplest thing I could come up with: gzipping a 3D array of voxel colors. It didn't really work until I chose the right stride order (xyz, zyx, yzx, etc) and then suddenly it was 5x better.

The parquet format has the BYTE_STREAM_SPLIT encoding strategy which basically splits an array of floats/doubles into 4/8 arrays of bytes so they can be compressed independently. https://parquet.apache.org/docs/file-format/data-pages/encod...

Just choosing the correct stride order before compression is still underutilized. It's also undersupported in our tools too; e.g. that voxel engine used numpy, but it was a pita to get numpy to transparently change the stride order in the memory representation without also affecting the indexing order.

IIRC, there was a WAV-era audio format that used PCM delta compression by recording differences rather than absolute values.

This algorithm is pretty neat. I wonder if for the use case outlined by the post they could get even better compression through the use of fewer significant digits. For the purposes of recording times, 0. 00768 is likely just as useful as 0.0076792240142822266

In the first several examples, the input seems to have a mantissa with all zeros beyond the first 15 bits. Why isn't the author using float32 for this instead of float64?

I did something similar in a messaging application... We had a data structure consisting of several tables describing various message queues in 4GB of persistent storage. The initialization of those tables was quite regular, as they were just pointers into blocks in the persistent memory. When the application was ported to run on AWS instances, people decided to try to run the application on instances with the crappiest 20MB/s storage. I had specified during implementation that the journalling layer would not work well on crappy storage, as the actual persistent memory the system was originally designed for had gobs of bandwidth (it was supercap backed DRAM on a PCIe card built using an FPGA and a pair of 10Gbps SFP+ ports to mirror to another host -- you had a couple of GB/s of write throughput). Customers ignored the requirement, and opened a bug saying the system couldn't reinitialize the table within the 30 second limit for commands on the CLI. To fix the "bug", I ended up delta encoding the persistent memory tables to make the data more regular, ran it through libz at the lowest compression level, then wrote the compressed data out to disk. 4GB of data ended up taking less than 100MB in the journal. gzip compression on its own was not able to get under the 600MB requirement. It was a total hack, but it worked and took a few hours to implement. Domain specific knowledge really helps improve compression ratios!

Its largely a variation of delta encoding (https://en.wikipedia.org/wiki/Delta_encoding) which is using xor to determine the variation between values. Both are exploiting the fact that in certain kinds of series/samples the range (relative entropy) between values is far less than the range of the underlying value representation.

Whether or not the resulting ranges are encoded in a space saving manner (as this algorithm is doing) or used as input into a BW transform/Huffman/etc sorta depends on the resulting value sequences.

Much of this though should apply the understanding that data being compressed can frequently lead to data specific preprocessing that can significantly increase the compression ratios over generic encoders. Just taking the output of this routine and running it through deflate might yield another couple percent if it were tuned. Or put another way, all the bit prefix/shifting decisions might be redundant for certain cases because the 0's would end up being single bit tokens in a Huffman encoder.

I wonder how it compares to traditional compression?

I've tried their "Integer that increments by 1 at every timestep." case on 10000 integer. The algorithm described said "6.98x compression"

bzip2 gave 80000/8642 = 9.2x compression

zstd gave 80000/11316 = 7.1x compression

For integer values, just subtracting bytes is enough to allow much better compression ratios. See the table at https://opensource.quarq.com/zfit/zfit.pdf

We then immediately write out the subsequence of the XORed value that has the same starting index and length as the last subsequence we wrote.

I don't really understand this. Is there an example?

This appears to be working because the data are highly correlated, i.e. similar magnitudes across the vector. I wonder how well it would do with completely random input, not just uniform floats in the [0, 1] interval, but floats across all exponent combinations.

Here's discussion of an article from 2020 that explains this and other time series compression approaches: https://news.ycombinator.com/item?id=31379344

Excellent stuff

XOR'ing consecutive elements is the mark of people used to sequential, rather than parallel, processing.

Most of the approaches described in that paper should work well enough with a base + offset scheme, where the base is RLE-compressed or just set once every N elements.

The biggest issue with this approach is that it's bit-aligned, and the alignment is determined by fields within the data. It's hard to make this run fast on most CPUs; a typical implementation ends up having to maintain a bit buffer, and shifts bits in/out of it a couple times for every codeword.

I bet you could improve the performance of this algorithm significantly, without harming its compression too badly, by one or both of:

A) Adjusting the sizes of some bit fields to make them evenly divide the system word size, e.g. requiring the run length of the 11-prefix to be a multiple of 4, so that it can be encoded in 4 bits instead of 6. (This is a net space savings of half a bit; you have to include an average of 1.5 more bits of nonzero data, but the length is two bits shorter.)

B) Writing the streams of bits for e.g. "mode", "number of leading zeroes", and "bit subsequences" separately for each block of compressed data, rather than combining them into a single stream. As a bonus, each of those streams will now be more amenable to compression by generic compressors.

One question: it is possible for the XOR of two consecutive floating-point numbers to have 32-63 leading zeros; the numbers 32-63 do not fit in 5 bits. I imagine this is treated by Gorilla like 31 leading zeros?

For those interested in the topic, I highly recommend the series of posts from Charles Bloom:

http://cbloomrants.blogspot.com/2023/07/notes-on-float-and-m...

TLDR:

For S16 deltas, bias by 0x8080 , for S32 deltas, bias by 0x80808080.

De-interleaving multi-byte integers into homogenous streams can help, particularly with weaker back-end compressors.

TLDR:

For floats, just reinterpret F32 as U32.

If the floats have a mix of positive and negative, convert the sign bit to two's-complement signed S32.

Consider lossy elimination of negative zero -0.f

If you didn't actually want the huge precision for floats near zero, a simple lossy encoding is just to do float += constant, which works for non-negative floats where you don't know the high end of the range so you can't just use fixed point.

TLDR:

The best way to compress numeric data that is larger than bytes (F32,F16,S32,S16) is usually to delta them in their original size integer, then de-interleave after the delta.

Sometimes no filter or no deinterleave is best, particularly with stronger compressors, so being able to select filter on/off per-file can give big wins.

What if the floating point number is, for example, a number of seconds coming from a millisecond time source? Binary floating point numbers notoriously can't represent decimals precisely.

You would obviously be better off timing in the proper unit so that you have an integer number of milliseconds but that's the kind of situation where performance starts to drop, no one understands why until some dev starts digging deeply into the encoding and maybe even write a blog post about how he got a massive speedup by multiplying numbers by 1000.