bzip3: A spiritual successor to BZip2 that compresses 26 years of Perl source code to 546 MB

I was processing compressed .jsonl files recently (JSON lines format). I found that lzma gave a much better compression than gzip or bzip2, which helps for archival costs, but it's challenging to work with as software support is lacking. I do duckdb processing which supports gzip transparently. There's an extension for bzip2, but not for lzma or bzip3.

I ended up using gzip because it's best supported by the software I use and most likely to have support in software I adopt. But it gave the worst compression results of the options I tried. These bzip3 numbers certainly give me FOMO...

The benchmarks are disingenuous, to the point of looking cherry-picked. The block size for bzip3 is set to 512MB, but the window size for zstd is left to its default (8MB I believe for high levels). So in this corpus, which is made up of all versions of Perl source code concatenated, the window is too small to see all the identical files and just match them.

Also corpora made out of very long repetitions are pretty much the best case scenario for BWT-based compressors.

If we match the window size of zstd to that of bzip3 we get dramatically different results:

% gzcat *.gz | time zstd -T8 -16 | wc -c # baseline

2819113884

zstd -T8 -16 2054.50s user 3.47s system 783% cpu 4:22.80 total

% gzcat *.gz | time zstd -T8 -16 --long=29 | wc -c

196405076

zstd -T8 -16 --long=29 1083.06s user 2.41s system 783% cpu 2:18.55 total

Almost 15x smaller than the baseline, and more than 2x smaller than bzip3, also CPU time halves (since long matches are found earlier, so there's less work to do).

(the baseline number is slightly different because I don't have the exact Perl version set used by the author)

Also, in the benchmarks using lrzip, which would make the window size less relevant, zstd is not even compared.

An interesting unintentional benchmark is to go to https://github.com/iczelia/bzip3/releases and see to what degree bzip3 compresses its own release archives; and go to https://github.com/iczelia/bzip3/blob/master/.github/workflo... to see what options have been chosen for the other compressors here.

I think this should include benchmarks zstd with larger windows and long range mode. I wouldn't be surprised if the window they used is smaller than an individual version tar file, which would prevent useful compression.

> However, the complexity of the algorithms, and, in particular, the presence of various special cases in the code which occur with very low but non-zero probability make it impossible to rule out the possibility of bugs remaining in the program.

Sounds like perhaps a nice testcase for formalization + AI?

faster than gzip now or still slower? (sorry I did not read readme)

I think compression algorithms are ripe for significant improvement with LLMs. It’s an ideal candidate problem you can have in a closed loop evaluation, and you can just let agent try things.