Float Compression 3: Filters | Hacker News Reader

Float Compression 3: Filters

aras-p.info

67 pointsibobev22 comments

That's reporting better figures with general compression than I'd expect from experience. Anyway, I'd expect to reach for zfp.io for arrays of floating point data. It's certainly an old observation that the compression method you want to use is data-dependent, even for similar kinds of data. Long ago it was found that there was a dramatic difference in x-ray crystallography image data depending on whether they were taken with a lab source (low resolution) or at a synchrotron (high resolution -- sharper peaks).

I have a new post (https://aras-p.info/blog/2023/02/03/Float-Compression-5-Scie...) comparing zfp, fpzip, spdp, ndzip, streamvbyte libraries for compressing this same data set. All in lossless, single threaded mode so far (just like all the other experiments before).

zfp performance is... "underwhelming" to say the least :( (fpzip is pretty good though, if only a bit slow at decompression). Maybe zfp is much better on 3D or 4D data, and/or in lossy mode. Which might be a topic for a future post.

Another technique I've read about is "block" floating point. In many problems like signal processing or physics simulations, the order of magnitude of the data is often close to each other within a region. Instead of giving each float its own significand and exponent, they can be grouped together and shared to save some bandwidth or space in a hardware implementation for real-time processing. Unfortunately it's often not very suitable in software, as the non-standard word size is awkward to handle.

We use this at Microsoft for AI! https://proceedings.neurips.cc/paper/2020/file/747e32ab0fea7...

Very cool, thanks for sharing!

GPU drivers have a version of that, and using a standard word size too. Three 9-bit significands and a 5-bit shared exponent.

That’s, loosely, what “Reorder bytes + Delta” does, isn’t it? It groups together the first bytes of floats, delta encodes them and then compresses them, and repeats that for the second, third, and fourth bytes.

The first byte of a IEEE float has 7/8 of the exponent. If these are successive measurements, chances are they have lots of series of identical values, and the delta-encoded stream will have lots of zeroes.

"Kind of". My understanding is that block floating point actually makes a bunch of numbers have the same exponent (probably the largest among the group). That's not exactly the same as reordering bytes where exponents can be different (but maybe similar).

So "block" is not a lossless transformation/compression.

but you can use fp16 and fp32 and there is the hardware today

For comparison how TimescaleDB does it:

https://www.timescale.com/blog/time-series-compression-algor...

For the "Reorder floats + Delta", I wonder if he did anything special to prevent floating-point errors. Floating-point operations (e.g. minus followed by plus) do not necessarily round-trip because their results are not exactly mathematically correct, i.e. sometimes y + (x - y) != x.

Otherwise, the compression is lossy.

(blog post author) I'm not doing operations on floats. The data is floats, yes, but the XOR is obviously not on floats; and Delta is not either. Both are just interpreting data as 4-byte unsigned integers or 1-byte unsigned integers depending on the filter.

The example though uses a three dimensional vector and suggests turning that into an SoA form.

My question is: In the case of component vectors like that, given that many operations wind up in operations like dot products, do the advantages still apply?

I don't have any experience programming with simd instructions specifically, so the memory access patterns get a bit murky to me.

The same goes for cuda, for example, which has a native float4 type. It's making row ordering so convenient, and going for SoA seems like you need to walk away from that.

This is only for serialisation not for in memory use.

This byte reordering trick has also been done elsewhere. For example, the HDF5 file format supports a "shuffle" filter which reorders the bytes.

(post author) All of this has been done elsewhere! I'm just trying to try various approaches that are out there, on "my own data".

Sorry, I didn't mean to suggest you were claiming it was discovered by you. It was more on giving some background and a different name for it.

Interesting to match with the observations from the practice of using ClickHouse[1][2] for time series:

1. Reordering to SOA helps a lot - this is the whole point of column-oriented databases.

2. Specialized codecs like Gorilla[3], DoubleDelta[4], and FPC[5] lose to simply using ZSTD[6] compression in most cases, both in compression ratio and in performance.

3. Specialized time-series DBMS like InfluxDB or TimescaleDB lose to general-purpose relational OLAP DBMS like ClickHouse [7][8][9].

[1] https://clickhouse.com/blog/optimize-clickhouse-codecs-compr...

[2] https://github.com/ClickHouse/ClickHouse

[3] https://clickhouse.com/docs/en/sql-reference/statements/crea...

[4] https://clickhouse.com/docs/en/sql-reference/statements/crea...

[5] https://clickhouse.com/docs/en/sql-reference/statements/crea...

[6] https://github.com/facebook/zstd/

[7] https://arxiv.org/pdf/2204.09795.pdf "SciTS: A Benchmark for Time-Series Databases in Scientific Experiments and Industrial Internet of Things" (2022)

[8] https://gitlab.com/gitlab-org/incubation-engineering/apm/apm... https://gitlab.com/gitlab-org/incubation-engineering/apm/apm...

[9] https://www.sciencedirect.com/science/article/pii/S187705091...

Putting your obvious bias due to affiliation with ClickHouse aside, this is quite disingenuous.

Comparing OLAP and OLTP is usually just a waste of time. They solve different problems.

This blog post linked within your gitlab issue is quite impartial, relatively speaking, and disputes most of these claims: https://www.timescale.com/blog/what-is-clickhouse-how-does-i...

This also similarly matches my experience operating properly tuned instances.

Lastly, regarding the following

> Specialized codecs like Gorilla[3], DoubleDelta[4], and FPC[5] lose to simply using ZSTD[6] compression in most cases, both in compression ratio and in performance.

I'd love to see some data because this is a very broad generalization that has never remotely been true in my experience. At comparable block sizes, with proper tuning, double delta can absolutely smoke zstd. In fact, while zstd can achieve quite impressive compression and performance, I almost never reach for it as it's rarely optimal when I benchmark, compared to lz4 or xz or snappy or even sometimes gzip. It depends on many factors -- what data, how much data, block size, disk or storage medium, network.

Your whole post puts a rather sour taste in my mouth about ClickHouse.

I have tested these codecs on the metrics data (like CPU usage). One experiment is detailed here: https://www.youtube.com/live/0fSp9SF8N8A?feature=share&t=176...

Another experiment is described in the linked blog post: https://clickhouse.com/blog/optimize-clickhouse-codecs-compr... It compares codes on the weather dataset (NOAA).

The comment about "DoubleDelta" codec from the ClickHouse codebase:

    /** NOTE DoubleDelta is surprisingly bad name. The only excuse is that it comes from an academic paper.
      * Most people will think that "double delta" is just applying delta transform twice.
      * But in fact it is something more than applying delta transform twice.
      */

Those who do not understand parquet are doomed to reinvent it.

Those who reinvent it will understand it better than those who thought they understood it.

Reply on news.ycombinator.com