Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fc, a lossless compressor for floating-point streams

github.com

Post reply on HN
Print view View original

11–20 of 35 posts

Re: Fc, a lossless compressor for floating-point streams

#11

Post by magicalhippo »

snissn wrote: post #8
enduku wrote: post #2

I built "fc", a C library for compressing streams of 64-bit floating-point values without quantization. It is not trying to replace zstd or lz4. The idea is narrower: take blocks of doubles, try a set of float-specific predictors/transforms/coders, and emit whichever representation is smallest for that block. It is aimed at time-series, scientific, simulation, and analytics data where the numbers often have structure…

What do you mean by decode is parallel?

It splits the input into blocks which are encoded separately, so the decoder can fire up multiple threads to decode multiple blocks in parallel.

https://github.com/xtellect/fc#how-it-works

Re: Fc, a lossless compressor for floating-point streams

#12

Post by apodik »

userbinator wrote: post #10

It splits the input into adaptively-sized blocks (quanta), runs a competition between many specialized codecs on each block, and emits the smallest result. This is, for lack of a better term, a "metacompressor", but it will be interesting to see which of the choices end up dominating; in my past experiences with metacompression, one algorithm is usually consistently ahead.

I’ve never heard of a metacompressor before, what others exist?

Re: Fc, a lossless compressor for floating-point streams

#13

Post by pella »

> "fc is a lossless compressor for streams of IEEE-754 64-bit doubles."

The new OpenZL SDDL2 (Simple Data Description Language) supports several different floating-point types. It would be worthwhile to contribute some of the FC project's experience to OpenZL. Now the OpenZL supported types:

  | Type           | Size    |Endian|
  |----------------|---------|-----|
  | `Int8`         | 1 byte  | N/A |
  | `UInt8`        | 1 byte  | N/A |
  | `Int16LE/BE`   | 2 bytes | Yes |
  | `UInt16LE/BE`  | 2 bytes | Yes |
  | `Int32LE/BE`   | 4 bytes | Yes |
  | `UInt32LE/BE`  | 4 bytes | Yes |
  | `Int64LE/BE`   | 8 bytes | Yes |
  | `UInt64LE/BE`  | 8 bytes | Yes |
  | `Float16LE/BE` | 2 bytes | Yes |
  | `Float32LE/BE` | 4 bytes | Yes |
  | `Float64LE/BE` | 8 bytes | Yes |
  | `BFloat16LE/BE`| 2 bytes | Yes |
  | `Bytes(n)`     | n bytes | N/A |
Some links:

- https://github.com/facebook/openzl/releases/tag/v0.2.0

- https://openzl.org/getting-started/introduction/

- https://openzl.org/sddl/sddl2-announcement/

- https://openzl.org/sddl/core-concepts/

Re: Fc, a lossless compressor for floating-point streams

#14

Post by whizzter »

apodik wrote: post #12
userbinator wrote: post #10

It splits the input into adaptively-sized blocks (quanta), runs a competition between many specialized codecs on each block, and emits the smallest result. This is, for lack of a better term, a "metacompressor", but it will be interesting to see which of the choices end up dominating; in my past experiences with metacompression, one algorithm is usually consistently ahead.

I’ve never heard of a metacompressor before, what others exist?

I think the idea is that the compressor is "meta" in the sense that it directs compressors as GP mentions by selecting what's actually producing the best results, so it's not just one comrpessor but a series of supported ones plugged in to be used adaptively (controlled at a "meta" level).

Floating point data is a mess to compress, but I think the idea here is to apply different transforms (and perhaps back-end codecs) on data and see if one fits the data so perfectly that you magically get a lot of compression.

Say you have an audio with a sawtooth, it's linear an gradient but if the peaks is "random" values like 1.245 and PI then the mantissa bits of the interpolation range will look fairly "random" to a classic compressor, whilst this compressor can test to see if there are linear gradient spans (or near linear gradient) where it stores the gradient and dumps out the "difference" bits for a regular compressor.

Or 3d coordinates for 3d models (non-stripified), plenty of repeating 8-byte doubles that will be garbage and not help a classic compressor much, building a float aware dictionary and using that would easily bring down the data by quite a few %.

(I don't agree with GP, one method might win out for certain workloads, but the idea here seems to be a pluggable utility that can help a wide range of developers with something "for free").

Re: Fc, a lossless compressor for floating-point streams

#16

Post by enduku »

pella wrote: post #13

> "fc is a lossless compressor for streams of IEEE-754 64-bit doubles." The new OpenZL SDDL2 (Simple Data Description Language) supports several different floating-point types. It would be worthwhile to contribute some of the FC project's experience to OpenZL. Now the OpenZL supported types: | Type | Size |Endian| |----------------|---------|-----| | `Int8` | 1 byte | N/A | | `UInt8` | 1 byte | N/A | | `Int16LE/BE` |…

Thanks, this looks super relevant. I think the transferable part is the per-block selectrover predictors, strides, deltas, exponent/mantissa-ish structure, byte transpose, fallback raw/LZ, etc.sddl2 looks like a natural place to try some of that.

Re: Fc, a lossless compressor for floating-point streams

#17

Post by enduku »

userbinator wrote: post #10

It splits the input into adaptively-sized blocks (quanta), runs a competition between many specialized codecs on each block, and emits the smallest result. This is, for lack of a better term, a "metacompressor", but it will be interesting to see which of the choices end up dominating; in my past experiences with metacompression, one algorithm is usually consistently ahead.

That’s a fair description. One mode does not dominate in my current harness; the winning mode varies quite a bit by dataset/block. If real workloads show one or two modes dominate, I’d rather simplify the portfolio :) For now the extra encode CPU is intentional: spend time once, get smaller blocks and fast parallel decode.

Re: Fc, a lossless compressor for floating-point streams

#18

Post by enduku »

apodik wrote: post #12
userbinator wrote: post #10

It splits the input into adaptively-sized blocks (quanta), runs a competition between many specialized codecs on each block, and emits the smallest result. This is, for lack of a better term, a "metacompressor", but it will be interesting to see which of the choices end up dominating; in my past experiences with metacompression, one algorithm is usually consistently ahead.

I’ve never heard of a metacompressor before, what others exist?

I’m regarding that term loosely here- in this case it is 'try several representations/codecs for a block and store the winner.' Similar ideas show up in columnar formats choosing encodings per column/page, OpenZL selectors (asother commenters pointed here), and shuffle/transpose + backend-compressor pipelines. fc’s version is much narrower: a tournament among f64-specific modes per block.

Re: Fc, a lossless compressor for floating-point streams

#20

Post by enduku »

Scaevolus wrote: post #5

I see you have ALP, but have you tried Chimp128 or Arrow's byte stream split?

I have an XOR128-style mode and a byte-transpose/byte-split-like mode, but I should not claim that as a proper Chimp128 or Arrow Parquet byte-stream-split comparison yet. I willadd direct baselines for Chimp128 and Arrow/Parquet BSS+zstd to the harness.
Post reply on HN