Live data from Hacker News

A parallel implementation of gzip for modern multi-processor multi-core machines

github.com

61–70 of 70 posts

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#61
post #24

If you know that what you compress is alphabetised text, and space is more important to you than time, then please use lzips over gzips. For a parallel version: http://www.nongnu.org/lzip/plzip.html

Is this gunzip-compatible? If not, then as long as gzip remains the only viable/compatible compression mode for HTTP I think advances in gzip compression is still valuable.

No it's not. Lzip is more useful for storing text long term, or send very large text file as email attachments.

Text log file and database dump in text usually generate very large text file, lzip can reduce their size by a factor of 5 to 10, compared to gzips.

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#62
post #6

And the same for LZMA: https://github.com/vasi/pixz (it's relatively easy to remember those commands)

Upstream xz supports it too, but not until a relatively recent release. If you're interested, I have a PPA for Ubuntu Trusty which includes up-to-date xz-utils + dpkg-deb set up to use it. This is a lifesaver if you deploy large bundles of software in the deb format:

https://launchpad.net/~mikepurvis/+archive/ubuntu/dpkg

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#63
post #41

Why not just use GNU parallel? `parallel gzip ::: file1 file2` I wish there was a standard for this type of stuff. So that an app will check for existing child spawns and act accordingly (IPC).

That doesn't help if you have only one big file or stream.

cat bigfile | parallel --pipe -k gzip > out.gz

parallel --pipepart -a bigfile -k gzip > out.gz

The last is faster.

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#64
post #42

I love it! I just wish somebody can make a GPU based compression library (doesn't have to be gzip or bzip), every mobile device today is shipping with a GPU, there are some techniques out there like this ( http://on-demand.gputechconf.com/gtc/2014/presentations/S445... ), but I am still waiting for a solid implementation.

Pied Piper already made it.

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#65
post #42

I love it! I just wish somebody can make a GPU based compression library (doesn't have to be gzip or bzip), every mobile device today is shipping with a GPU, there are some techniques out there like this ( http://on-demand.gputechconf.com/gtc/2014/presentations/S445... ), but I am still waiting for a solid implementation.

Doesn't transferring all the data to/from the GPU kill any potential speedup the GPU may offer?

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#66
post #48
post #2

My guess is that this compresses less efficiently as you would have to shard the dictionaries. Might be close though for large files. I was surprised that there were no speed or efficiency comparisons in the README.

Actually, it does not compress less efficiently, but you do not learn this fact from the README. Instead you have to look inside the man page ( https://raw.githubusercontent.com/madler/pigz/master/pigz.1 ): The input blocks, while compressed independently, have the last 32K of the previous block loaded as a preset dictionary to preserve the compression effectiveness of deflating in a single thread.

I'll check it out. However, if you have to wait for the previous block to compress the following block, I don't see how you can parallelize it completely. My assumption is that you would have to shard the file at a higher level and still compress those shards independently. That should get close to the same results as using a sequential compressor but for small file sizes both this effect and Amdahl's law would start to show its head. I suppose you could get around that by not parallelizing compression at some minimum size automatically.

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#67
post #48

Earlier quoted context omitted.

Actually, it does not compress less efficiently, but you do not learn this fact from the README. Instead you have to look inside the man page ( https://raw.githubusercontent.com/madler/pigz/master/pigz.1 ): The input blocks, while compressed independently, have the last 32K of the previous block loaded as a preset dictionary to preserve the compression effectiveness of deflating in a single thread.

I'll check it out. However, if you have to wait for the previous block to compress the following block, I don't see how you can parallelize it completely. My assumption is that you would have to shard the file at a higher level and still compress those shards independently. That should get close to the same results as using a sequential compressor but for small file sizes both this effect and Amdahl's law would start…

> However, if you have to wait for the previous block to compress the following block, I don't see how you can parallelize it completely.

That above is not what the man-page says. The block size for any given session is fixed, so you know the boundaries of each block prior to compression.

Each block has a copy of the last 32kbytes of data at the end of the prior block.

The algorithm used by gzip compresses by finding repetitive strings in the last seen 32kbyte window of uncompressed data, so there is no compression dependency between blocks, even with a copy of the last 32k of uncompressed data from a prior block being present for the current block.

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#68
post #32
post #16

Earlier quoted context omitted.

The main purpose of this "pixz" appears to be its chunking of the compressed data so that is it partially decompressible (i.e. random access). "xz" has -T/--threads= already for multithreaded processing (although it does seem like pixz has a different default value "all cores" instead of "1 thread") .

xz in multithreaded mode supports random access too, at least theoretically. But there's no reasonable way with xz to actually find the file in a tarball you want to access, it's that bit that pixz provides. Another nice thing about pixz is it does parallel decompression, as well as compression. (Disclaimer: I'm the original author of pixz.)

I was thinking about that "no reasonable way" comment. When you uncompress the first block, you will find the first tar header. From that you can know the uncompressed offset of the next tar header. If the compressed stream does support random access, you should be able to uncompress a block (assuming uncompressed block size was a multitple of 512 bytes) to get to the next tar header. You can repeat this until you get to the file you are looking for.

With large files, this approach would be of huge value. If the files tend to be no larger than block_size - 512, there will be no speedup.

Of course, this would need to be implemented directly in tar, not by piping the output of a decompression command through tar.

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#69
post #67

Earlier quoted context omitted.

I'll check it out. However, if you have to wait for the previous block to compress the following block, I don't see how you can parallelize it completely. My assumption is that you would have to shard the file at a higher level and still compress those shards independently. That should get close to the same results as using a sequential compressor but for small file sizes both this effect and Amdahl's law would start…

> However, if you have to wait for the previous block to compress the following block, I don't see how you can parallelize it completely. That above is not what the man-page says. The block size for any given session is fixed, so you know the boundaries of each block prior to compression. Each block has a copy of the last 32kbytes of data at the end of the prior block. The algorithm used by gzip compresses by finding…

So the lossage there is that you don't get to compress and generate that dictionary at the same time. Interesting.

Re: A parallel implementation of gzip for modern multi-processor multi-core machines

#70
post #67

Earlier quoted context omitted.

> However, if you have to wait for the previous block to compress the following block, I don't see how you can parallelize it completely. That above is not what the man-page says. The block size for any given session is fixed, so you know the boundaries of each block prior to compression. Each block has a copy of the last 32kbytes of data at the end of the prior block. The algorithm used by gzip compresses by finding…

So the lossage there is that you don't get to compress and generate that dictionary at the same time. Interesting.

There's no "generating" of a dictionary. The gzip algorithm is based upon the "dictionary" being the last seen 32k bytes of uncompressed data based upon where in the file the compressor is presently working (technically in compression circles it is a 'windowed' algorithm, not a 'dictionary' algorithm). It compresses by finding a repetitive string in that 32k window that matches a string at the current location, and outputting an instruction that says (in effect): "seek backwards in the uncompressed data 200 bytes, then copy 100 bytes from there to here".

So as long as each parallel block has pre-pended the final 32k of the prior block, the output from the compression algorithm will be identical between a straight sequential compression and a pigz parallel compression. Because at byte 0 of the current block, the 32k window of the uncompressed prior block is available to perform matching against, just as if it were running sequentially.

The only growth from pigz comes from needing to round each parallel compressed block up to a multiple of 8 bits (the huffman codes that are output are bitstrings that don't match with 8-bit byte boundaries). But worst case that is 7 bits per block for each parallel block. Given the performance gains on multiple CPU systems, a few hundred bytes net increase is not likely to matter. If those few hundred bytes did matter, then one should use bzip2 or lzip or xz and get much higher compression ratios (at the expense of much longer time).

Post reply on HN