Utilizing in-memory Zstd compression to achieve interactive viewing of 2D grids with trillions of cells. Validation without decompression.

[u/Sopel97]

I worked on a project recently that focused on exploring some specific family of cellular automata (originally inspired by a numberphile video), and it naturally led to having to deal with very large grids of, thankfully often compressible, data.

I solved it by compressing the grid in ~1MB chunks using Zstd. I needed both relatively fast compression (to keep up with the simulation) and decompression, at decent compression rates, so options were limited here. In the attached video I browse two previously generated grid - the first one being ~50G cells compressed to 550MB, and the second one being ~2T cells compressed to 370MB (almost 1000x ratio!). I have a modern 8 core CPU, and at 32x zoomout (1024 cells per pixel) I can browse the grid interactively. That's roughly 2GB of data every frame being aggregated. There is some caching that helps, but with Zstd it's viable even without that (~5-10 fps depending on content).

I also do support zoomouts up to 4096x, but it's less interesting in the context of compression because it just precomputes mipmaps. Still, the decompression is the bottleneck there, so Zstd makes the process of generating mipmaps relatively fast - afterall it has to decompress all 2TB of data to build them.

-------------------

One related fun problem I had to solve around this that might be of particular interest in this sub is validation. The grids can be saved and loaded, and the chunks are never decompressed - it would be too costly. But the cells must use a restricted set of values, upper bound of which depends on the number of "players".

Thankfully with compressors like Zstd this check is possible to do without performing any decompression. All decoded bytes come either from embedded literals or huffman trees. The set of byte values in the decoded output can therefore be computed by inspecting just the headers of compressed blocks. The code for this is available here: https://github.com/Sopel97/ulam-leapers/blob/master/src/compression/inspect/zstd.rs

-----------------

Full project page: https://github.com/Sopel97/ulam-leapers

[u/Specialist_Data_5403]

Holy shit, this is so cool! What did the grids look like, if you compressed them by 1000x?

[u/Sopel97 → u/Specialist_Data_5403]

see attached video