5 ms·

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 thi

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".

greiskul 3y ago
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.
tumultco 3y ago
I was curious about this myself. I extracted the json for the "uncompressed" image: https://gist.github.com/jmfd/8dbb96fcd8a1ba1e8ad6e9167bd70cee 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?)
- jagged-chisel 3y ago
  JSON compresses well in general. Can you do the same with a binary version?
  - tumultco 3y ago
    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%)
    - jakelazaroff 3y ago
      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!
    - dimava 3y ago
      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/ https://qoiformat.org/
  - mattarm 3y ago
    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.
- jryan49 3y ago
  Is it faster though?
ledauphin 3y ago
the storage format may not be the only consideration - it may be preferable to have an in-memory representation that is also inexpensive.
insanitybit 3y ago
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.

greiskul 3y ago

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.

tumultco 3y ago

I was curious about this myself. I extracted the json for the "uncompressed" image: https://gist.github.com/jmfd/8dbb96fcd8a1ba1e8ad6e9167bd70cee 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?)

jagged-chisel 3y ago
JSON compresses well in general. Can you do the same with a binary version?
- tumultco 3y ago
  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%)
  - jakelazaroff 3y ago
    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!
  - dimava 3y ago
    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/ https://qoiformat.org/
- mattarm 3y ago
  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.
jryan49 3y ago
Is it faster though?

ledauphin 3y ago

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

insanitybit 3y ago

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.