10 ms·
Bzip3: A spiritual successor to BZip2
- linsomniac 2y agoHighlight (benchmark of Perl source code): The results follow: xz -T16 -9 -k - 2'056'645'240 bytes (c=12m09s, d=4m40s) bzip2 -9 -k - 3'441'163'911 bytes (c=17m16s, d=9m22s) bzip3 -b 256 - 1'001'957'587 bytes (c=7m10s, d=4m6s? Unclear on source page) bzip3 -b 511 - 546'456'978 bytes (c=7m08s, d=4m6s? Unclear) zstd -T12 -16 - 3'076'143'660 bytes (c=6m32s, d=3m51s) edit: Adding times and compression levels
- miohtama 2y agoIn Linux source benchmark results are interestingly more equal, LZMA still holding up well. What makes Perl source benchmark special? Deduplication?
- sevg 2y agoTo make your comment more useful you’ll want to include compression and decompression time. Using the results from the readme, seems like bzip3 performs competitively with zstd on both counts.
- dralley 2y agoAlso the compression levels..
- linsomniac 2y agoI believe the compression levels are included in the list above.
- dralley 2y agoNot for zstd or lzma
- linsomniac 2y agoAdded, thanks.
- idoubtit 2y agoI've experimented a bit with bzip3, and I think the results in the readme are not representative. I think it's a handmade pick, with an uncommon input and unfair choices of parameters. And it's made with a HDD, which skews the results even more. For instance, with a 800 MB SQL file, for the same compression time and optimal parameters (within my capacity), bzip3 produced a smaller file (5.7 % compression ration) than zstd (6.1 % with `--long -15`). But the decompression was about 20× slower (with all cores or just one). I'm not claim my stupid benchmark is better or even right. It's just that my results were very different from bzip3's readme. So I'm suspicious.
- jl6 2y agoA 4x improvement over lzma is an extraordinary claim. I see the author has also given a result after applying lrzip (which removes long-range redundancies in large files), and the difference isn’t so great (but bzip3 still wins). Does the amazing result without lrzip mean bzip3 is somehow managing to exploit some of that long-range redundancy natively? I’d be astonished if such a 4x result generalized to tarballs that aren’t mostly duplicated files.
- wongarsu 2y agoCurrently running my own benchmarks, my preliminary results are that zstd becomes competitive again once you add the --long option (so `zstd --long -16 all.tar` instead of `zstd -16 all.tar`). Which is an option that not everyone might be aware of, but whose usefulness should be intuitive for this benchmark of >200 very similar files.
- JoshTriplett 2y ago...using zstd level 16, when zstd goes up to 22. And without turning on zstd's long-range mode.
- linsomniac 2y agoMy standard test is compressing a "dd" disc image of a Linux install (I use these for work), with unused blocks being zeroed. Results: Uncompressed: 7,516,192,768 zstd: 1,100,323,366 bzip3 -b 511 -j 4: 1,115,125,019
- deleted 2y ago[deleted]
- palaiologos 2y agoHi, tool author here! Thank you for your benchmark! As you may be aware, different compression tools fill in different data type niches. In particular, less specialised statistical methods (bzip2, bzip3, PPMd) generally perform poorly on vaguely defined binary data due to unnatural distribution of the underlying data that at least in bzip3's case does not lend well to suffix sorting. Conversely, Lempel-Ziv methods usually perform suboptimally on vaguely defined "textual data" due to the fact that the future stages of compression that involve entropy coding can not make good use of the information encoded by match offsets while maintaining fast decompression performance - it's a long story that I could definitely go into detail about if you'd like, but I want to keep this reply short. All things considered, data compression is more of an art than science, trying to fit in an acceptable spot on the time to compression ratio curve. I created bzip2 as an improvement to the original algorithm, hoping that we can replace some uses of it with a more modern and worthwhile technology as of 2022. I have included benchmarks against LZMA, zstandard, etc. mostly as a formality; in reality if you were to choose a compression method it'd be very dependent on what exactly you're trying to compress, but my personal stance is that bzip3 would likely be strictly better than bzip2 in all of them. bzip3 usually operates on bigger block sizes, up to 16 times bigger than bzip2. additionally, bzip3 supports parallel compression/decompression out of the box. for fairness, the benchmarks have been performed using single thread mode, but they aren't quite as fair towards bzip3 itself, as it uses a way bigger block size. what bzip3 aims to be is a replacement for bzip2 on modern hardware. what used to not be viable decades ago (arithmetic coding, context mixing, SAIS algorithms for BWT construction) became viable nowadays, as CPU Frequencies don't tend to change, while cache and RAM keep getting bigger and faster.
- loeg 2y agoWhy -T12 for zstd and T16 for xz? How many threads is bzip3 using?
- zimpenfish 2y agoFrom the source, it looks like bzip3 defaults to 1 thread if not explicitly set by arguments.
- zimpenfish 2y agoDid a test on a 1.3G text file (output of `find -f -printf ...`); Macbook Pro M3 Max 64GB. All timings are "real" seconds from bash's builtin `time`. files.txt 1439563776 bzip2 -9 -k 1026805779 71.3% c=67 d=53 zstd --long -19 1002759868 69.7% c=357 d=9 xz -T16 -9 -k 993376236 69.0% c=93 d=9 zstd -T12 -16 989246823 68.7% c=14 d=9 bzip3 -b 256 975153650 67.7% c=174 d=187 bzip3 -b 256 -j12 975153650 67.7% c=46 d=189 bzip3 -b 511 974113769 67.6% c=172 d=187 bzip3 -b 511 -j12 974113769 67.6% c=77s d=186 I'll stick with zstd for now (unless I need to compress the Perl source, I guess.) (edited to add 12 thread runs of bzip3 and remove superfluous filenames)
- zimpenfish 2y agoSince I only have 12 perf cores on this Mac, I tried the xz test again with 12 threads. xz -T12 -9 -k 993376236 69.0% c=83 d=9 ~10% faster for compression with the same size output.
- yencabulator 2y agoThat d=9 sure wins the day there, for me.
- wongarsu 2y agoAdditional benchmarks on the same dataset: uncompressed - 19'291'709'440 bzip2 -9 - 3'491'493'993 (sanity check) zstd -16 --long - 593'915'849 zstd -16 --long=31 - 122'909'756 (requires equivalent argument in decompressor due to needing ~4GB RAM) zstd -19 --long - 505'728'419 zstd -19 --long=31 - 106'601'594 (requires equivalent argument in decompressor) zstd --ultra -22 - 240'330'522 zstd --ultra -22 --long=31 - 64'899'008 (requires equivalent argument in decompressor) rar a -m5 -md4g -s -mt8 - 64'837'044 As you notice my sanity check actually has a slightly different size. Not sure why. The benchmark is a bit underspecified because new perl versions were released in the interim. I used all releases up to perl-5.37.1 to get to the correct number of files. Just treat all numbers to have about 2% uncertainty to account for this difference. I can't provide compression/decompression times, but the --long or --long=31 arguments should not have major impact on speed, they mostly impact used memory. --long=31 requires setting the same in the decompressor, making that option mostly useful for internal use, not archives meant for public consumption. As you can see, the benchmark chosen by the author mostly comes down to finding similar data that's far away. I wonder if bzip3 can do this better than other algorithms (especially in less memory) or simply chose default parameters that use more memory. Edit: added more benchmarks
- SeptiumMMX 2y agoGiven that it's BWT, the difference should be the most prominent on codebases with huge amounts of mostly equivalent files. Most compression algorithms won't help if you get an exact duplicate of some block when it's past the compression window (and will be less efficient if near the end of the window). But here's a practical trick: sort files by extension and then by name before putting them into an archive, and then use any conventional compression. It will very likely put the similar-looking files together, and save you space. Done that in practice, works like a charm.
- hcs 2y agoHandy tip for 7-Zip, the `-mqs` command line switch (just `qs` in the Parameters field of the GUI) does this for you. https://7-zip.opensource.jp/chm/cmdline/switches/method.htm#qs https://7-zip.opensource.jp/chm/cmdline/switches/method.htm#...
- ku1ik 2y agoOoh, that’s neat. How much improved do you get from this? Is it more single or double digit % diff?
- eqvinox 2y agoI'd argue that's actually the lowlight of the README since that is a very poor choice of benchmark. Combining a multitude of versions of the same software massively favors an algorithm good at dealing with this kind of repetitiveness in a way that will not be seen in typical applications. The "Corpus benchmarks" further down in the README are IMHO much more practically relevant. The compression ratio of bzip3 is not significantly better, but the runtime seems quite a bit lower than lzma at least.
- otterley 2y ago(2022)
- froh 2y agowhat do you mean?? usually this signifies the year some article was finalized and published. and this is a GitHub repo with recent commits so this is not correct here.
- otterley 2y agoThe date signifies that this tool is not new; and this is ostensibly a "news" site.
- lifthrasiir 2y agoBut there seem to have been no major updates since the original submission (every release up to 1.5.1 is for minor maintenances), so the year would be indeed useful for the vast majority who do remember that.
- mmastrac 2y agoI've studied the Burrows-Wheeler Transform, I understand the transformation, I've re-implemented it countless times for kicks, I see how it improves compressability, but for the life of me the intuition of _why_ it works has never really clicked. It's a fantastic bit of algorithmic magic that will always impress me to see it.
- deleted 2y ago[deleted]
- mnw21cam 2y agoI remember the lecturer commenting on what sort of sick and twisted mind could come up with such a ridiculous convoluted notion when I was taught it at university.
- ajb 2y agoWheeler was also one of the inventors of the "closed subroutine" AKA function, which had to be implemented via a hack as machines of the time did not include ISA support for "return": https://en.m.wikipedia.org/wiki/Wheeler_Jump https://en.m.wikipedia.org/wiki/Wheeler_Jump
- mnw21cam 2y agoYes. He also happened to be in residence just down the hall from the lecture theatre at the time.
- unnah 2y agoThe Burroughs-Wheeler transform has been described as a unique algorithm idea in that there are no non-trivial variations or related algorithms, unlike more conventional compression algorithms, which can be tweaked and improved in so many ways. There is no general compression theory in which BWT could be described as a special case. It looks to me that the above still holds: Bzip2 and Bzip3 are simply combining more conventional compression algorithms with the BWT, which itself is still the same old transform. Bzip2 does Huffman coding after BWT, and Bzip3 does arithmetic coding.
- hulitu 2y ago> Bzip3: A better and stronger spiritual successor to BZip2 Please, no. What's next ? BZip4 and BZip5, each one incompatible with each other ?
- sitkack 2y agothis is the way.
- snvzz 2y agoThe format gets a new major version precisely because it is incompatible.
- chefandy 2y agoYeah I'm sick of this. Did you know you can't even use ext2/3/4 together on the same partition? What a mess.
- wakawaka28 2y agoIf they have to be incompatible then it's better to not conceal that. Generalized file formats require you to implement more stuff to support them, and we can't tell the format by looking at the file name.
- pxeger1 2y agoThe author is super cool. They are one of very few people to write any substantial programs in Malbolge, a programming language designed to be cryptographically hard to use (or something like that)
- matthberg 2y agoThe Wikipedia page on Malbolge was quite the horrific read, downright amazing to have a lisp written in it. Here's the program as talked about on HN: https://news.ycombinator.com/item?id=38850961 https://news.ycombinator.com/item?id=38850961 https://github.com/kspalaiologos/malbolge-lisp https://github.com/kspalaiologos/malbolge-lisp The cursed language: https://en.wikipedia.org/wiki/Malbolge https://en.wikipedia.org/wiki/Malbolge And the variant used by the program: https://esolangs.org/wiki/Malbolge_Unshackled https://esolangs.org/wiki/Malbolge_Unshackled
- jgalt212 2y agoI poke around in this space periodically, but I've never found a compelling reason to move away from gzip.
- loeg 2y agozstd is faster and provides better compression than gzip at every point on the curve. There is no reason to use gzip these days other than backwards compatibility.
- idoubtit 2y agoI've reached the same conclusion, and I've been using zstd unless I want extremely fast (de)compression with lz4. And even when I still have to use gzip (the format), the executables of libdeflate are fully compatible and noticeably faster than gzip/gunzip (the tool).
- jrockway 2y agoThis was on HN a while ago https://jolynch.github.io/posts/use_fast_data_algorithms/ https://jolynch.github.io/posts/use_fast_data_algorithms/ and reaches the same conclusion. I am inclined to use Zstd even in cases where people would use lz4. Zstd is very fast.
- ThatGuyRaion 2y agozstd is a great setup, for sure, but the build system they use is patently awful. Can someone make an autoconf or hell, even CMake build system for them pleasee???
- loeg 2y agoJust install the binary package from whatever distro you use? Why do you need to build it? But if it matters, FreeBSD has a pretty trivial BSDmake build of it: https://github.com/freebsd/freebsd-src/blob/main/lib/libzstd/Makefile https://github.com/freebsd/freebsd-src/blob/main/lib/libzstd... https://github.com/freebsd/freebsd-src/blob/main/usr.bin/zstd/Makefile https://github.com/freebsd/freebsd-src/blob/main/usr.bin/zst... You could easily do something similar in GNU make or whatever without the dependencies on the FBSD build system. It's basically just the classic "cc -c a bunch of C files, then link them."
- lexicality 2y ago> DO NOT COMPRESS ANY DATA WITH THIS PROGRAM UNLESS YOU ARE PREPARED TO ACCEPT THE POSSIBILITY, HOWEVER SMALL, THAT THE DATA WILL NOT BE RECOVERABLE. I know every open source project (and quite a lot of expensive proprietary ones!) come with a "btw this software might wipe your computer, if it does that's your fault lol" clause in their license but I can't imagine trying to convince anyone else that using this for anything remotely serious is a good idea with that line in the readme.
- cwillu 2y agoSimple enough to be safe, at the cost of performance: uncompress and compare to the original.
- lexicality 2y agoAnd what do you do if it doesn't match?
- vardump 2y agoIsn't it obvious? Warn the user, who can now use something else instead.
- lexicality 2y agoThat only works if the "user" is an interactive TTY with a human on the other end of it though. What if I tried using this for compressing automatic backups? Do I need an error handling routine that uses something else?
- vardump 2y agoA backup system should be reliable and be able to report errors. No matter what they may be.
- jeroenhd 2y agoYour automatic backups may actually be corrupted by random bit flips. Happens quite a lot with ZFS NAS systems where the admin forgot to set up a scrub job and still uses incremental backups. Any read or write could fail for a multitude of reasons. The chance of an entire file being lost is rather small, but it's still an edge case that can happen in the real world if the FS flips to read only at just the wrong time. Hell, on platforms like macOS, you can't even assume fsync returning success will actually write floating data to storage!
- wood_spirit 2y agostrange that bzip3 is not yet listed on the large text compression benchmark http://mattmahoney.net/dc/text.html http://mattmahoney.net/dc/text.html
- aidenn0 2y agoBut it does have many, many BWT based implementations. Might be interesting to benchmark it against e.g. bsc[1] 1: https://github.com/IlyaGrebnov/libbsc https://github.com/IlyaGrebnov/libbsc
- ggm 2y agoSmall request: write a header or tail block which records the compression efficiency. Bzip2 doesn't. Gzip does. Knowing the uncompressed size can be vital. Yes, there is a risk of lying and making zip bombs.
- Zamiel_Snawley 2y agoShouldn’t knowing how big it’s supposed to be make it easier to stop a zip bomb? Just stop decompressing once you hit the size from the header.
- jeroenhd 2y agoThat only works if the standard actually describes what you're supposed to do with extra data at the end, and everyone agrees. In practice, there have been antivirus bypasses that made use of AV scanners treating the additional data differently from common extraction software (I believe it was winrar?). One could argue that a text document with a corrupt file size byte should still be decodeable. One could also argue that the file is completely corrupt and should be treated as such. Knowing that there will be tools that will take the first approach regardless, I'd stick to just decoding the extra data and marking the file as potentially damaged rather than send the user down a data recovery rabbit hole for a file that'll decompress just fine.
- o11c 2y agoIIRC to decode raw zlib or deflate using only command-line tools, you have to prepend the gzip header and stream while ignoring errors at EOF.
- twotwotwo 2y agoA random thought that Might Work, Who Knows(tm): first compress long-ish repetitions in the input and store the copies separately from the literals (like zstd). Then run just blocks of literals through the BWT before entropy coding. The idea is that the BWT can help take advantage of however much context remains after the copies are snipped out, whether that's one byte or a few, and shrinking the input with the LZ-ish step may make it faster. It might be strictly worse than using PPM or basic context modeling like Brotli's; either of those can be "aware" of the preceding bytes even when they come from copies rather than literals. It's implied in "successor to bzip2" and a lot of the comments, but it's worth highlighting that high-compression algorithms, especially those that are also slow to decompress, are a pretty specialized niche now. Using zstd or brotli at low to medium settings sometimes speeds things up by reducing network or storage transfers more than their CPU use slows you down. (Especially when your storage transfers are network transfers.) Even when compressing isn't a net speedup, you pay fairly little time for the saved space. Even lowish levels of zstd and brotli often eke out decent compression ratios for big inputs since, with modern quantities of RAM, their MBs-long history windows let them take advantage of long-range matches.
- jwr 2y agoI still remember going crazy about bzip (the first one) and re-compressing all my data with it. And then I remember discovering, several years later, that bzip (the first one) is an obsolete format that is now difficult to even decompress. I learned my lesson and now use horribly sub-optimal formats that I'm sure will stick around for a long time, if not forever.
- self_awareness 2y agoThis is true for every new thing. New frameworks, new languages, new cars, new heating systems. If you want to have a stable solution, use "boring" things. They are boring for a reason; not much stuff is changing in them anymore. They are stable. I use boring stuff all the time.
- Scaevolus 2y agoHow does this compare to existing BWT-based compressors on things like the Large Text Compression Benchmark?
- biglost 2y agoEverytime someone says I'm too smart, i remember this kind of black magic and inmediately answer: no, im not
- thomasmg 2y agoImproving BWT is great! In my view, improving "long range" compression has the biggest potential. There are many, many algorithms and implementations for very short range (huffman, arithmetic, ANS) and short range (LZ, BWT), but not that much research has gone into "long range" yet. There's deduplication, and large-window LZ / BWT.. but not much more yet. What is missing is efficietly (and with little memory) finding similarities on multi-GB data sets. I think sorting by similarity would help there. Or did I miss research in this area?
- t43562 2y ago> bzip2 -9 -k all.tar 981.78s user 9.77s system 95% cpu 8M memory 17:16.64 total > bzip3 -e -b 256 -j 12 all.tar 2713.81s user 16.28s system 634% cpu 18301M memory 7:10.10 total The difference in memory usage might be worth noting: 8M v 18301M
- Groxx 2y agoProbably worth noting that bzip2 also did by far the worst in this. ~7x larger files than the best bzip3. Large memory use is generally required for good compression. I'm curious how well gzip would have handled this though, as it's generally low memory too, and all the others in that list have FAR more than 8M memory used.
- t43562 2y agoI think gzip was 5M. This all depends where you are using it e.g. on a Raspberry Pico I'd be using gzip no matter the extra bytes probably.
- onetom 2y agoHow come https://www.nongnu.org/lzip/ https://www.nongnu.org/lzip/ is not mentioned in its readme? I agree w other commenters, that Lzip would be a good baseline to compare it to, besides bzip2. Nice job though on testing it on so many CPU architectures!