Pigz: Parallel gzip for modern multi-processor, multi-core machines
zlib.net
zlib.net
If you'll excuse the plug, here is the LZ4 story:
Yann was bored and working as a project manager. So he started working on a game for his old HP 48 graphing calculator.
Eventually, this hobby led him to revolutionize the field of data compression, releasing LZ4, ZStandard, and Finite State Entropy coders.
His code ended up everywhere: in games, databases, file systems, and the Linux Kernel because Yann built the world's fastest compression algorithms. And he got started just making a fun game for a graphing calculator he'd had since high school.
When zstd came out – and Brotli before it to a certain extent – they were 3x faster than ZLib with a slightly higher compression ratio. You'd think that such performance jumps in something as well explored as data compression would be hard to come by. We weren't that close to the efficiency frontier.
What's well explored is compression rate, where indeed it's difficult to improve, and true innovations, like arithmetic coding, are rare.
Compressing speed on the other hand it's not very interesting to academics, it's more of an engineering problem. And there is plenty of work to do here, starting with stuff as simple as multi-threading and SIMD.
ZLib and ZStandard are probably in the same complexity class, but with different constant factors, which academics don't care about but which have massive practical consequences.
Exactly! And this seems like a shame to me with something burning so many cpu cycles.
> true innovations, like arithmetic coding, are rare.
Yeah, Yann tried to explain arithmetic coding to me, but I didn't get it.
Consider this example: you want to transmit two completely random variables, both of which can have 5 states. The obvious way is to concatenate two bit fields of size ceil(log2(5)), so 3+3 = 6 bits.
But alternatively, you can count the total number of states possible for both variables together, 5*5 = 25 and encode it as a single integer of size ceil(log2(25)) = 5, so both variables can be stored with just 5 bits.
So we arrive at the idea that there can be a fractional number of bits, which we often round up to the nearest integer for simplicity (or, in practice, the nearest multiple of 8 since most protocols are based on bytes).
The other part is just assigning shorter sequences of bits to more common symbols, except, of course unlike in Huffman coding, our symbols can have a fractional number of bits. This allows them to match the actual symbol probabilities more closely. If your data is highly repetitive, you can fit dozens of (common) symbols per bit.
The coolest part IMO is how easy it is to plug in custom models for symbol probabilities. Usually a simple counter for each symbol is enough, but you can go crazy and start predicting the next symbol based on previous ones.
PPM-based [0] compression can work quite well for text but on its own it's not enough to unseat the Lempel-Ziv family as the top general purpose compressor.
[0] https://en.wikipedia.org/wiki/Prediction_by_partial_matching
No one ever tweaks that one setting even though they should, file sizes are a significantly smaller bottleneck than they were with MB hard drives and dial-up modems.
If your justification for not serving up larger .png is that not everyone has fast internet, then you should be either detecting and handling that case separately, downscaling the images, and/or serving .jpeg instead.
One time I was using Topaz AI to upscale video, and I spliced that into their ffmpeg filter and took a whole day off of a week long encode. Low hanging fruit.
My gut feeling is that if you are pulling down data faster than 40 Megabits and have a CPU made within the past 7 years (possibly including mobile), you won't be bottlenecked by I/O generally speaking.
It's not just about bottlenecks, but aggregate energy expenditure from millions of decompressions. On the whole, it can make a real measurable difference. My point was only really that it's not so cut and dry that it's a good trade off to take a 5% file size loss for 20% improved compression performance. You'd have to benchmark and actually estimate the total number of decompressions to see the tipping point.
According to this benchmark [1] zstd does not drop its decompression speed as the compression ratio increases. It stays about the same level.
[1] https://www.truenas.com/community/threads/zstd-speed-ratio-b...
That entirely depends on the use-case. Most people running FFMpeg do it as a once off thing - and if those people like me, when I rip a movie I want the highest quality and lowest size I can get, and I'm happy that the default sacrifices speed for quality and size. The processing can be slow because I'm doing it only once. If you're in the business of encoding video and do it all day everyday, your calculus will be different and you won't be using the defaults regardless.
If the target is a console you may know exactly what hardware is there so you can justify the effort in tuning. (it’s more complex today because you have a choice of what kind of storage to use with your XBOX). With a PC or phone your results may vary a lot more.
https://aras-p.info/blog/2020/12/08/Texture-Compression-in-2...
We're now more than two decades later, so all the important data compression patents should have expired.
There are also optimizations that only work on today's larger cores, and you have to actively update old code to get the advantages (happily some work is going into that): https://news.ycombinator.com/item?id=32533061 / https://news.ycombinator.com/item?id=32537545
That's not to minimize the clever ideas and amazing implementation work in new stuff. It's more that people were making smart decisions both then and now, more so than you might guess just from comparisons on today's hardware.
So for example take logfiles. You can train up a dictionary on some sample log data. Then you can compress individual log rows, and all it actually stores is a diff of the compression dictionary (if any new entries were added) and the compressed data. So you get very efficient compression of small amounts of data which are part of a collection that may be very self-similar, but with the option of decompressing any individual element at will. (Of course, you'd need to hold onto the original trained dictionary for both compression and decompression, for any row you want to be able to decompress in the future. And you might want to retrain the dictionary every so often for slowly-changing types of data, which might prevent "drift" of the efficiency towards less-efficient over time)
I believe Postgres already uses this under the hood for some columnar data. It wouldn't take much to index it before compressing it and just decompress it at will. Or maybe it just got added? https://devm.io/databases/postgresql-release
`zstd --train <path/to/directory/of/many/small/example/files/>`
will output a dictionary file, and then the `-D <path/to/dictionary/file>` option when used for either compression or decompression will then use that dictionary first.
You can also investigate "man zstd" or google "zstd --train" for more details. The directory for the training must consist of many small files each of which is an example artifact; if you want to split, say, a single log file into files of each line, you can use, say, a bash script like this (note that I just created this with ChatGPT and eyeballed it, it looks correct but I haven't run it yet!): https://gist.github.com/pmarreck/91124e761e45d6860834eb046d6... (Also, don't forget to set it as executable with `chmod +x split_file.bash` before you try to run it directly)
Depending upon the data, the non-threaded versions of these utilities can have higher performance when run with some kind of dispatcher on multiple files.
The GNU xargs utility is able to do this, and the relevant features are also in busybox.
One fine day, I finished my physics exam an hour early and so opened up an enjoyable game on my calculator. 45 minutes went by and so I went up and handed in my paper. It was at this point that the professor noted, “were you planning on leaving the second page blank?”
Oh.
Teachers were completely stumped. Their initial suspicions were always that someone brought a universal remote control to class, but they would painstakingly search everyone's desks to find nothing. And then after asking everyone to put their hands up in the ai, the TV would still have a mind of its own.
Yeah, your TI-89 was no fun.
I work in VMWare Fusion on a Mac, in a Mint guest OS, and zipping these huge instances for backup will take forever with a single core. Pigz punishes all 12 cores on my Mac mini and saves me a ton of time.
If you have suitable hardware running Windows, you can try this out for yourself using Microsoft's DirectStorage GPU decompression benchmark [2].
A reference implementation of a single threaded compressor and multi (CPU) threaded decompressor can be found at [3]. It is Apache-2 licensed.
1. https://developer.nvidia.com/blog/accelerating-load-times-fo...
2. https://github.com/microsoft/DirectStorage/tree/main/Samples...
3. https://github.com/microsoft/DirectStorage/blob/main/GDeflat...
Disclaimer: I work for NVIDIA, have nothing to do with this, and am not speaking for NVIDIA.
Edit: oops, lost the last sentence in the first paragraph during an edit.
I assume this is for decompressing multiple independent deflate streams in parallel?
What's the throughput if you only have a single stream? I realise this is the unhappy-case for GPU acceleration, hence my question! (I've been thinking about some approaches to parallelize decompression of a single stream, it's not easy)
https://github.com/microsoft/DirectStorage/blob/main/GDeflat...
The GPU decompression benchmark I linked earlier allows you to specify a single file that it will compress with GDeflate (and zlib for comparison). The numbers presented in the docs that come with the benchmark and presented elsewhere are consistent with my own runs using a source file that is highly compressible.
Part of the trick of achieving this speedup is to read the data fast enough. I don't know of any NVMe drive that can reach full speed with a queue depth of 1. While running the benchmark in a windows VM with a GPU passed through, on the linux host I observed that the average read size was about 512k and the queue depth was sometimes over 30.
You saw this, right?
That said, the approach I intend to take is similar. The idea is that one thread is dedicated to "looking ahead", parsing as fast as it can (or even jumping far ahead and using heuristics to re-sync the parse state. There will be false-positives but you can verify them later), building an index but not actually doing decompression, while secondary threads are spawned to do decompression from the identified block start points. The hard part is dealing with missing LZ references to data that hasn't yet been decompressed. Worst-case performance will be abysmal, but I think on most real-world data, you'll be able to beat a serial decompressor if you can throw enough threads at it.
>I started a tar with bzip command on a big directory, and it has been running for two days. Of course, it is only using 1.07 cores out of the 128 available. The Unix pipeline tool philosophy often isn’t aligned with parallel performance.
https://twitter.com/ID_AA_Carmack/status/1656708636570271768...
Not if the files are similar. If you're compressing the files separately you'll start with a clean state rather than reusing previous fragments. Compressing a BMP after a TXT may not be beneficial, but compressing 3 tar'ed TXTs is definitely better than doing them separately.
AFAIK the gzip command still cannot compress directory information and therefore needs tar in front of it if you want to retain a folder structure.
Compressing first can also be slower if the average file size is smaller than the block size, because the main thread cannot queue new jobs as fast as cores complete them (this happens e.g. with 7zip at fast compression settings with solid archive turned off). Tarring then compressing means small files can be aggregated into a single block, giving both good speed and compression ratio.
TIL: you can use method 93 - Zstandard (zstd) Compression - with ZIPs
If anything, I wonder what kind of hard drive John has. If you're reading them off a network drive backed by tape drums it's probably going to take a while ;P
You can complain about philosophies but this is just using the wrong tool for the job. Complain about bzip if you feel the bzip authors should have made multithreaded implementation for you.
Do you know if there are any tests showing which compressor is better (compression wise) for which data?
Other algorithms like zstd and gz resulted in much lower compression rates.
I'm sure there is a more efficient solution, but changing three letters in a script was pretty much the maximum amount of effort I was going to put in.
On an unrelated note, has someone already made a meta-compression algorithm which simply picks the best performing compression algorithm for each input?
The old approach was that programs don't need internal parallelism because you can get it by just piping stuff and relying on the kernel's buffering to keep multiple processes busy.
Eg, tar is running on one core dealing with the filesystem, gzip is running on another core compressing stuff.
In the early days, Windows would have a single program doing everything (eg, Winzip) on a single core, while Unix would have a pipeline with the task split into multiple programs that would allow for this implicit parallelism and perform noticeably better.
Today this is all old and doesn't cut it anymore on 128 core setups.
This is purely speculation though
http://compression.great-site.net/pbzip2/
which should solve the 'my cores are idle' issue.
And yes, use zstandard (or xz, where the default binary in your distro is already multithreaded) where you can.
... should really reconsider their choice of compression algorithm at this point.
Instead you should use zstd as it compresses faster, decompresses faster, and yields smaller files. It also supports parallelism (via “-T”) which supplants the pigz use case. There literally are no trade-offs; it is better in every objective way.
In 2023, friends don’t let friends use gzip.
tar --create --zstd --file $ tar -caf dst.tar.zst /src
$ tar -xaf src.tar.zst
There literally are trade-offs, you started your comment describing one of them. If you want as wide out-of-the-box support as possible, you'd go with gzip.
The Compression Streams browser API only supports gzip (+ deflate) so if you wanna compress something natively in the browser without 3rd party libraries (or slow JS implementation), gzip seems to be the only option.
I've lost count how many compressors have been marketed as a replacement for gzip over the decades. And it's always a replacement for gzip. Every time a new compressor starts getting popular, people start promoting a new even better replacement, and gzip never gets properly replaced.
zstd finally has some potential to replace gzip, but only if people accept it's good enough and stop trying to replace it with something even better.
bzip2 and xz have had the potential to replace gzip for the vast majority of users and use cases since more than a decade - and in many cases they have.
gzip is still the default compressor people use when they are not sure about the appropriateness of other compressors in their specific use case, and they don't have the time or energy to find out. To replace it, the a compressor must satisfy two requirements:
* It must not be substantially worse than gzip on any relevant metric. bzip2 failed this by being slow.
* It must be ubiquitous enough that the idea of installing it no longer makes sense. xz never reached this point, before people started replacing it with better compressors.
I work in bioinformatics, where people typically use either gzip or domain-specific compressors. gzip is used for the reasons I mentioned. It works, it's usually good enough, and if people in another organization you've never heard of want to use your compressed files, they can do so without bothering you with support requests.
zstd would be faster and compress better, but because you can't be sure everyone else can use it, you don't even bother thinking about it. The saved computational resources are probably not worth it. On the other hand, anything that makes gzip faster is valuable, as it allows saving computational resources without taking any interoperability risks.
I didn't say the gzip replacement must be better than gzip in every aspect. I said it must not be substantially worse. bzip2 was substantially worse, because it was substantially slower.
Zstd is getting there but I personally don't bother with it on a daily basis except in situations where both performance and compression ratio are important, like build artifact pipelines or large archives.
"The recipients" are for example millions of browsers that don't understand zstd.
zstd & xz support the "-T" argument for setting thread count. If you pass "-T 0" it will attempt to detect and use a thread per physical core.
You can force this property by introducing synchronisation points though, gzip has an `—-rsyncable` which makes that a lot more likely, at a small compression cost.
Edit: apparently zstd has also had —-rsyncable for the last 5 years.
I used pbzip2 on an old octo core xeon server with a decent sas raid and was able to compress at well over 200MB/sec, closer to 300MB in some cases.
I’ve integrated pigz into different build and CI pipelines a few times. Don’t expect wonders since some steps still need to run serially, but a few seconds here and there might still add up to a few minutes on a large build.
Take something like enwik8 (100megs), gzip will get that down to 36megs, with LZMA down to ~24-25. The top of the line stuff will get it down to the ~15meg range. Thats a huge difference.
If you've ever screwed around with mysqldump -> tar -> scp -> untar -> mysql<, you'll appreciate the speedup on this, in cases where you're setting up a slave and want to have the freshest possible data before kicking off binlog replication - this is the best.
This is of course more of a problem of the gz format than pigz although last time I looked hacks are possible to parallelize decompression.
https://github.com/oracle/solaris-userland/blob/master/compo...
Shortly after submitting a PR the code went through major surgery, and my patch then needed a similar amount of surgery. Oracle then whacked most of the Solaris org, and I don’t think this ever got updated to work with the current pigz.
1. https://github.com/oracle/solaris-userland/tree/master/compo...
I thought I had opened a PR for that a long while ago, but it doesn't show up on github these days. In any case, I did ask Mark Adler to review it. It was never a priority, then the code changed in ways that I don't really want to deal with.
While looking through the PRs, I noticed a PR for Blocked GZip Format (BGZF) [2]. That's very interesting, and perhaps suggests that bgzip is a tool you would be interested in.
I've got news for you buddy :)
As s side note, this isn't always desirable for this class of coders. In some scenarios (like web server) you might want to favor throughput over response time.
[1] https://community.ibm.com/community/user/power/blogs/brian-v...
Hopefully my tweet response was the one to tip you off! ;P Though in all likelihood I'm quite sure a number of people commented pointing at pigz.
Hats off to all who write extraordinarily performant multithreaded versions of originally-slow-at-scale UNIX system tools.
I am only disappointed with this one: "It is not pronounced like the plural of pig."
Me and my colleagues always pronounced it like pigs, die Schweine - and it was so much fun!
function ccm() {
tar -cf - $1 | pigz > $1.tar.gz
}You wouldn't go outside without pants. You shouldn't use a variable without quotes. Put pants on all variables. Also, you shouldn't use () with 'function' it "works" in Bash but it's not standard:
ccm() {
tar c "${1}" | pigz > "${1}.tar.gz"
}
ccm() {
for i in $@; do
tar c "${i}" | pigz > "${i}.tar.gz"
done
}
See: https://mywiki.wooledge.org/Quotes
See: https://mywiki.wooledge.org/BashGuide/CompoundCommands#Funct...
$ gzip -c a > a.gz
$ gzip -c b > b.gz
$ cat a b > c1
$ cat a.gz b.gz> c.gz
$ gzip -dc c.gz > c2
$ cmp c1 c2
[no output, files match]Then don't spell it like that. And I'll continue to say GIF with a hard G also.
Also - you'll never forget it.
I thought we had learned that from the GIMP[1].
[1] https://www.theregister.com/2019/08/28/gimp_open_source_imag...