bzip3
github.com
github.com
“Hi, tool author here.” A useful explanation of Burrows-Wheelers transform as used by bzip3: https://news.ycombinator.com/item?id=42902407
“bzip3 is not yet listed on the large text compression benchmark” It is now: https://mattmahoney.net/dc/text.html
(2 years ago, 176 comments) https://news.ycombinator.com/item?id=42899713
(4 years ago, 104 comments) https://news.ycombinator.com/item?id=31324439
And it comes in relatively well, in my opinion. I'm a compression amateur, but bzip3 is the first entry I recognize as a general purpose compression program.
On my desktop, decompressing with zstd requires 128 MB and 1 s, while bzip3 uses 3.2 GB and 90 s.
Without `-b 511`, bzip3's ratio decreases and decompression requires about the same memory as zstd. But the decompression is still two orders of magnitude slower.
Might still be useful as an archival compression format even if it will be less useful for distribution.
FWIW, the Burrows-Wheelers transform is also used by bzip2, so this isn’t a new feature even though that quote kinda sounds like it is.
https://arxiv.org/abs/1502.05937
https://github.com/nicolaprezza/lz-rlbwt
Which leads me to wonder if someone did, in fact, solve how to ‘combine zstd and bzip’ (so to speak) since the last time.
Matt added bzip3 to the benchmark seemingly after the last year thread. If the zstd benchmark, last update at max 22 in 2016, were to be updated for today’s zstd (for long-range if nothing else) after coming across this thread, what would be the most compact possible list of option sets to benchmark to reflect the value of LR et al.?
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
(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.
Yep, i found it in the source here:
- https://github.com/facebook/zstd/blob/d9c0c7e2cf8a8bf9fb98d3...
- https://github.com/facebook/zstd/blob/d9c0c7e2cf8a8bf9fb98d3...
Also, zstd docs say:
> Note: If windowLog is set to larger than 27, --long=windowLog or --memory=windowSize needs to be passed to the decompressor.
That always seemed annoying to me. They couldn't allocate 5 more bits somewhere to let the decompressor autodetect longer window sizes?
I believe this is just to prevent the decompressor from arbitrarily blowing up memory usage based on the input; I think if you want to accept long windows you can just always decompress with --long=63 regardless of whether the input needs it? (you will run out of RAM decompressing a long=63 file though of course)
It's actually 8 bits: https://www.rfc-editor.org/rfc/rfc8878.html#name-window-desc...
These command line parameters change the maximum the decompressor will allow. It's 128 MiB by default in the command line decompressor; other uses (like the "zstd" content coding for HTTP in web browsers) use a lower limit of 8 MiB (see https://www.rfc-editor.org/rfc/rfc9659.html).
If the header says the file is bigger than it really is, it can get you to allocate a pointlessly large window. But if a large allocation is the goal, they can make the file actually decompress that big without affecting the compressed size. So lying is pointless.
The benchmarks report 687M for their run of zstd, and 12178M and 18301M for the two runs of BZip3. Which itself is a bit eyebrow raising
it has been a long time since: "lies, damn lies, benchmarks" failed to hold true. Sometimes I wonder why gaming benchmarks has become so common.
I got some really good results with bzip3 compression Wikipedia XML dumps, and I would like to check if it's actually better or if I was just calling zstd wrong.
Sorry! That was a typo, it should have been 512MB (now fixed). Still huge.
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...
So I stripped out formatting, got rid of dupes, and tried out zstd, which was the hot new thing, along with the dictionary feature you describe, figuring it'd help. It didn't. I tried having one per book, one per multiple books, one for the whole archive.
It didn't work, or the gains were so marginal that I ended up scrapping the approach.
So it's not impossible that it can work, but stuff like regular json already compresses extremely well, I haven't found a scenario where it's a major boon.
When I studied at school, I used ZFS with lz4 enabled on my working machine. During that times I had a task of parsing Wikipedia's data. I had enough brain cells to find compressed dumps and download them with aria2 but not enough to leave the file compressed. I ran a decompressor. It'd been taking longer than I expected so I went out to walk a dog.
Imagine how fast me and the dog ran back 30 minutes later when I realized how cooked I was. I only had 10 GB left on my disks after I downloaded that 20 GB file. This decompressed file would have blown the machine up. I was terrified to find a frozen system with no storage space left.
Instead, the process finished and `df -h` reported 8 GB of the free space left. Files were decompressed. I could `less` them! That made no sense! Only many many minutes later I finally figured out to run a `zfs get compressratio` command which showed ZFS successfully and transparently recompressed everything on the fly. That was too impressive for that teenager and he never switched to a different file system.
Sun was a really cool company.
\[T]/
https://facebook.github.io/zstd/index.html
Pretrained dictionaries have never been intended to help with book sized or bigger compression. zstd automatically learns the most efficient dictionary it can within a few kilobytes. Pretrained dictionaries are only useful when you're independently compressing very small records.
Because JSON is an inefficient text encoding, compression (with custom dictionary) are likely to really well on those.
Books have recurring words, but probably much less.
I don't know much about duckdb but it looks like it supports zstd too: https://duckdb.org/docs/lts/data/json/loading_json
Writing your files directly into a compressed stream and decompressing on the fly has become almost a standard workflow for any files I'm going to read and write sequentially anyways. No need for the data to ever exist uncompressed on the file system. Previous formats never did that for me because they either had too much overhead or too little gain, often both
Here are my benchmarks for 2.3 GB of jsonl, on a laptop. Compressed size, compress time, decompress time; using defaults.
gzip 7.3% 21s 9s
bzip2 4.6% 251s 50s
bzip3 3.3% 82s 69s
zstd 6.9% 2s 3s
lzma 4.7% 51s 3sUnder most r/w workloads, using parquet/lance/vortex/native-duckdb, with their built-in columnar compression will result in more performance AND space savings. Non-solid compression. Then, the query engine can push down your query predicate to a column row group level, instead of forcing it to decompress the entire dataset to operate.
Practical example: duckdb has syntax - https://duckdb.org/docs/lts/data/multiple_files/overview - to glob multiple files at once, but that really only works if you're applying push down query predicates instead of re-decompressing your entire data set per SELECT. I would say for most dataset, even 20%+ size is worth not having to decompress (or even download!) the entire dataset, to figure out if something fits the predicate.
After all, if you have to download and decompress the dataset back again to operate, then the "space savings" are gone.
Since we kind of need a default "Need to compress something? Use this!" setting - would you prefer zlib over zstd, or something else for that role?
If your platform/sdk/browser/standard-library comes with zlib/gzip/.. then it's often easier to just pick that.
No new dependencies is always a win. App size. Security, etc.
Otherwise, if zstd is easy to add, IMO I would always prefer, zstd, lz4 or brotli.
It's hard to understand what point you're trying to make. Can you clarify?
A go-to thing means it's a sensible default choice and has no little to no downsides (versus not using compression), it doesn't mean it's the best for everything.
Until now the go-to has been DEFLATE (gzip and zip) but zstd is definitely competing against it because it is better in almost every way.
If your JSON file has many of the same object, you could see ratios in the single digits.
So why would anybody, hobbyist or enterprise, use this? Or does something older like 7zip also have this caveat that I've never experienced.
I wish I could use something better :D but it must be implemented in Javascript to run inside a browser, and the library should not be too large (mine is about 8 kB ZIPped). I would love to switch to ZSTD once someone implements a compressor in Javascript that is under 40 - 60 kB. Or do you think that bzip3 could be re-implemented easily in JS using some AI?
I really admire you for being so smart at such a young age :) I wish you best of luck in your scientific career! I visited Warsaw this year, but I am not sure if that is where you are from :D
Please send me an e-mail! Perhaps we can figure something out.
> THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE....
Also practically, this isn't MIT. It is LGPL 3, which I believe includes the warranty terms of GPL 3, i.e., no warranty. So we're in the same place anyway.
Sounds like perhaps a nice testcase for formalization + AI?
For something like these compression algos, though, I imagine it would be much easier since they already have actual proofs out there.
But having your decompression algorithm not produce what you compressed earlier is also ridiculously bad.
So, seems worth the effort, given that AI can do lots the heavy lifting these days.
If you don't like it, you're entitled to not using it.
bzip3 not a terribly impressive or useful compression algo.
benchmark on enwik: https://www.mattmahoney.net/dc/text.html#1703
But later I've read that there was some kind of Anime called Iczelion (or it was the hero name, whatever). Author also is interested in anime, I guess that's the reason for nickname similarity. Mystery solved.
Although you do have a point that the compressed data might be more difficult to decipher, if it doesn't have sufficient redundancy to skip bad parts, or if it is essential that the data is aligned in a certain way (e.g. disk images, and probably many other formats) and the format doesn't take this into account. Shorter window sizes, window reset markers, and explicit offset information could mitigate those problems.
I have not seen his tool before, or even was aware of it. However, once you take a closer look, you notice that these two tools could not be more dissimilar. Agiannis' compressor uses a compact context representation to group bytes, followed by RLE and prefix coding. Bzip3 combines repetition removal (here via a run-length code -- prior to the BWT -- and LZP of Charles Bloom), a full Burrows–Wheeler transform, and a richer (thus slower) statistical arithmetic coder. The use of RLE for post-coding the BWT output dates as far back to Julian Seward, perhaps even further. The RLE and LZP are applied before the Burrows-Wheeler transform (as opposed to the implementation in `text', which makes a big difference). Bzip3 uses a proper SAIS library for the forward and backward transforms. Konstantinos' entropy coder seems to use FPC (bytewise prefix codes over adaptively selected subblocks), bzip3 uses an idea similar to this of bcm, which itself descends from Mahoney and ancient work of JS Vitter on arihtmetic coding, where a bitwise arihtmetic coder is input mixed probability estimates from exponential-moving averages with probability refinement.
You are welcome to conduct your own analysis, but this is the gist of it -- perhaps Konstantinos has convinced himself that he had invented run-length coding?
agiannis_text enc 0m16,319s dec 0m15,594s size 270365918
bzip3 enc 1m36,544s dec 1m43,699s size 169990721
The claim “stronger than bzip2” is strange. What does it even mean?
Also, comparing parallel decompression benchmarks with bzip2 instead of pbzip2 seems unfair.
pbzip2 only can do parallel decompression on archives created with pbzip2, otherwise it'll fall back to single thread. There nowadays seems to be lbzip2, though, which claims to be able to add SMP support for standard bzip2 archives.
I'll need to try that next time I'm working with large archives - I learned about the pbzip2 limitations the hard way last time I was shuffling around a few multi-10GB archives, and was trying to speed things up fully utilising my 32 core threadripper.
Oh I didn’t know that.
As for your claim that "the build is failing", that is false, and it was false when you wrote this. The CI job for cross compiling to armv6 was failing, but all the other builds were green. You can still check CI status for older releases to confirm my assertion. Now armv6 is fixed too.
Maybe dial back the FUD.
It is a matter of good compromises: speed and efficacy. I even wonder if LZMA2 is worth replacing bzip2.
(According to recent article on HN[1]. So LLMs _are_ compression!)
Initially I was extremely impressed with it, because in a lot of tests it succeeded to compress hard-to-compress files, like movies, and in many cases it demonstrated a much better compromise between speed and compression ratio than zstd, i.e. depending on the command parameters I could make it either compress better than zstd at similar compression/decompression speed, or compress/decompress faster at a similar compression ratio.
Alas, the initial extremely favorable conclusion was short-lived, because trying later bzip3 on other data files gave worse results than zstd.
So the final conclusion was that the performance of bzip3 was somewhat unpredictable, being highly data dependent. For some files it provided outstanding compression ratio or speed, but for others it was inferior.
The problem was that without doing a compression there was no way to guess whether a file would be among those preferred by bzip3 or by zstd or by xz.
So now I would use it only for a file for which I want maximum compression and which I would compress once and decompress many times, so I can afford a very long compression time, during which I would test multiple compression algorithms, including bzip3 and zstd, with multiple parameter choices, and I would eventually choose the one that offers the best compromise between compression ratio and decompression time, for that particular file.
It certainly is a competitive compression algorithm, but unless it has changed since I last tested it, you cannot guess for which files it would win the compression competition.
But developing the heuristics for choosing the appropriate compression algorithm for a stream of data is likely to need a very long time for compression tests of a lot of diverse training data, similarly to the training of a specialized ML model that classifies patterns.
Such heuristics should provide not only algorithm selection, but also parameter selection, when given only some simple input, e.g. the relative importances of compression ratio, decompression speed and compression speed.
The lrzip test is interesting but it omits for example zstd and doesn't even have (de-)compression timings.
A lot more numbers are needed to present a fair and informative comparison.
I don't want this to be a swipe against bzip3, I only want to point out the presented benchmarks could be a lot better.
how is this an honest benchmark:
bzip3 ... 12178M memory
zstd ... 687M memoryEven if the examples are highly cherry-picked, it is quite suprising to me that such pareto-dominance is possible at all.
edit: Tested it myself and found that it often also does slightly worse than zstd -19 in compression ratio but faster (it was slower in one case on "uncompressible" input).
Compression performance vs "zstd -19" seems to depends a lot on actual input data in a very unpredictable way. I'd assume the benchmarks that they show are definitely somewhat cherry-picked.
probably somebody should use a coding agent to do auto-research to optimize params for each compression algo, while matching one fixed goal - time, memory or size