Hacker News Reader

Comment by Retr0id | Hacker News Reader

OP implements their own RLE-based compression scheme. I bet you'd get better results from emitting an uncompressed binary format, and then passing the whole thing through a general-purpose compressor like zstd.

I'd also be interested to see what zstd (or even just gzip) would make of their original un-optimised format - I bet you'd get most of the way there "for free".

View on HN

I was curious about this myself. I extracted the json for the "uncompressed" image:

https://gist.github.com/jmfd/8dbb96fcd8a1ba1e8ad6e9167bd70ce...

And then tried these commands against it:

  gzip:        39.56kb    (93.7%)
  zstd:        35.86kb    (94.3%)
  gzip -9:     35.51kb    (94.4%)
  bzip2:       24.35kb    (96.1%)
  zstd -19:    24.01kb    (96.2%)
  brotli:      21.42kb    (96.6%)

(I'm not up-to-date on default web server configs, but I imagine most would automatically transmit with gzip over the wire for json?)

JSON compresses well in general. Can you do the same with a binary version?

I only have the "final" 13.5kb version to test against. It compresses very well:

  gzip:     6.95kb    (98.9%)
  brotli:   5.99kb    (99.0%)

Man, I should have done this — would've been a much nicer number for the headline. Thanks for the analysis, though, this is really cool!

I compared it to image in PNG and QOI formats [0]

    img:         13.552kb (100%)
    img.png:      1.877kb (13.8%)
    img.qoi:     10.316kb (76.1%)
    img.qoi.gz:   1.167kb (8.6%)

While it does compress by 50%, it's not a format optimized for compression unlike png or qoi

[0]: https://qoiformat.org/

Given equivalent data stored in both JSON and BSON format I would expect them both to compress down to blobs of roughly equivalent sizes. This is because both encode roughly the same amount of information, so the compression algorithm will tend to compress down to the same final result. I haven't run this as an experiment though..that would be fun.

Is it faster though?

the storage format may not be the only consideration - it may be preferable to have an in-memory representation that is also inexpensive.

General compression algorithms like zstd will do way, way better on previously encoded data. Sorting, RLE, etc, are all going to lead to a smaller resulting binary after going through the generalized algorithm.

You're also going to be relying on heuristics that may fail. Zstd has no idea that your UUIDs are going to repeat, it doesn't know to dictionary encode them or to create frequency mappings. What it ends up doing is unlikely to be as effective as doing the work ahead of time, then allowing zstd to find the interesting and complex patterns that arise out of your encoded format.

I wonder if using the rsync algorithm would also help? From looking at the state changes done in one CRDT in one machine and another, both states still share a lot of things in common. So to merge A in machine 1, with B in machine 2, you can rsync A to B in machine 2 without overwriting B, but just having to send the deltas. My understanding is that there are crdts that are able to send over just the operations done, but for simplicity, for a full state crdt, this might be easier and almost as efficient than a specific algorithm.

Reply on news.ycombinator.com