7 ms·

Show HN: Rapidgzip – Truly Parallel Gzip Decompression with 10 GB/s

35 points by mxmlnkn 3y ago

I have posted a much earlier version of this over a year ago [0]. Since then a lot has changed. Obviously, the name has changed. This happened for the paper publication [1]. I have also optimized the speed, integrated ISA-L for special cases, limited the compression-ratio-dependent maximum memory consumption, and finally added parallelized CRC32 computation, which adds ~5% overhead no matter the number of cores used. At this point, I am leaning towards calling it production-ready although there are still many ideas for improvements. Redoing the benchmarks of the older Show HN, would look like this: time pigz -d -c 4GiB-base64.gz | wc -c # real ~13.4 s -> ~320 MB/s time rapidgzip -d -c 4GiB-base64.gz | wc -c # real ~1.26 s -> ~3.4 GB/s However, at this point, the piping itself becomes a problem. Rapidgzip is actually slightly faster than cat when comparing the piped bandwidth! E.g., compare these additional benchmarks: time cat 4GiB-base64.gz | wc -c # real ~1.06 s -> ~3.1 GB/s time fcat 4GiB-base64.gz | wc -c # real ~0.41 s -> ~8.0 GB/s time rapidgzip -o /dev/null -d 4GiB-base64.gz # real ~0.68 s -> ~6.5 GB/s fcat is an alternative cat implementation that uses vmsplice to speed up piping. According to the ReadMe it currently is broken, but it works fine on my system and piping it to md5sum yields consistent results [2]. So, at this point, I/O and actually also allocations have become a limiting factor and if you want full speed, you would have to interface with the rapidgzip library interface directly (in C++ or via the Python bindings) and process the decompressed data in memory. The project ReadMe contains further benchmarks with Silesia and FASTQ data and scaling up to 128 cores, for which rapidgzip achieves 12 GB/s for Silesia and 24 GB/s when an index has been created with --export-index and is used with --import-index. It can also be tested with ratarmount 0.14.0, which now uses rapidgzip as a backend by default for .gz and .tar.gz files [3]. [0] https://news.ycombinator.com/item?id=32366959 https://news.ycombinator.com/item?id=32366959 [1] https://dl.acm.org/doi/10.1145/3588195.3592992 https://dl.acm.org/doi/10.1145/3588195.3592992 [2] https://github.com/mre/fcat https://github.com/mre/fcat [3] https://github.com/mxmlnkn/ratarmount https://github.com/mxmlnkn/ratarmount

ComputerGuru 3y ago
Nice work! How much manual SIMD are you using?
- mxmlnkn 3y ago
  Currently, none. ISA-L might use some, I'm not sure. I have also tried to accelerate some crucial algorithms with SIMD and my trial and errors are still inside the src/benchmarks subfolder. But, in all of those cases, a simple std::string_view::find, std::transform, or lookup tables turned out to be equally fast or faster and, of course, is more portable. Even the CRC32 algorithm uses "simple" lookup tables (slice-by-16) and avoids any SIMD while still achieving ~4.5 GB/s per core. However, there is some Intel Whitepaper [0] showing how to use PCLMULQDQ for CRC32, which might not be much faster but it would reduce cache pressure. AVX-512 even has a VPCLMULQDQ. [0] https://www.intel.com/content/dam/develop/external/us/en/documents/clmul-wp-rev-2-02-2014-04-20.pdf https://www.intel.com/content/dam/develop/external/us/en/doc...
  - ack_complete 3y ago
    The Intel algorithm should be much faster. The slicing algorithms are limited by load unit bandwidth, which appears to be 2 loads/cycle on Zen 2, while PCLMULQDQ should be able to process 16 bytes every 2 cycles (8 bytes/cycle peak). 4.5GB/s is about 1-1.5 bytes/cycle. zlib-ng has an implementation.
    - mxmlnkn 3y ago
      That sounds more than I, for some reason, expected. I'm not sure why, but I was expecting "only" 2x speedup at maximum, while the CRC32 adds "only" 5% overhead. But, 5-8x speedup would be really nice. With that, the the CRC32 overhead would become immeasurable. I'll definitely have to look into it now.
  - doophus 3y ago
    For portable SIMD, have a look at ISPC. It allows you to write a function once, compile it for multiple instruction sets, and then automatically select the best one to use at runtime. You don't get the precision of hand-crafted SIMD, but it can grant some easy wins!
jzwinck 3y ago
Does this work with files compressed using the usual gzip command line program? I thought you had to write "sync points" inside a gzip file to support reading from locations other than the start. If you somehow bypass that requirement, can you explain how?
- mxmlnkn 3y ago
  Yes, it works with files produced by the usual gzip! That's why it is novel. If you make requirements on the compressor, then a multitude of competing gzip implementations exist already, the most popular of which, I think, is bgzip [0]. Rapidgzip can actually leverage the additional metadata stored in bgzip files to speed up decompression by roughly a factor of 2 compared to files compressed with the usual gzip. Rapidgzip does not require sync points because it simply looks for them. The approach is similar to gzrecover [1], i.e., you "simply" try to start decompression at every possible >bit< position. Of course that would be too slow (~200 kB/s), so instead I use several skip and lookup tables to speed up this search to achieve roughly (~70 MB/s). However, that search for deflate block boundaries can yield positions that look valid but which actually aren't, e.g., think of gzip-compressed gzip files. These cases also need to be detected and filtered. Rapidgzip does this filtering and the parallelization by using a cache which stores prefetched decompressed results with the start bit position as key. When the previous block has finished decoding, we know the start position of the next block, and if it exists in the cache, then that result is used. This implicitly filters out valid-looking duds, i.e., false positives. The proof of concept of looking for block boundaries and to resolve and parallelize interdependencies between consecutive blocks, was introduced by pugz [1]. However, it had no detection for false positives and therefore did only work for compressed text files. I built upon this to make it work without assumptions on the compressed data, and I also added capabilities for random access, for which the prefetch-cache architecture also is very suited, so that I can use it in ratarmount. [0] http://www.htslib.org/doc/bgzip.html http://www.htslib.org/doc/bgzip.html [1] https://github.com/arenn/gzrt https://github.com/arenn/gzrt [2] https://arxiv.org/abs/1905.07224 https://arxiv.org/abs/1905.07224
  - jzwinck 3y ago
    Thank you for the thorough answer. That is all quite methodical and impressive, bringing together good ideas from disparate projects into a single solution with new benefits. For people like me who have battled this demon before, it would help to explicitly say that you support any gzip file by way of this special magic. At least on my cursory reading of your page I did not understand this. And I never heard of gzrecover, so thanks for that too. I like how the pugz paper starts with "Decompressing a file made by the gzip program at an arbitrary location is in principle impossible." Until today I believed the same!
lifthrasiir 3y ago
Long time ago (probably around 2010 or something) I had a similar idea [1] and concluded that it is infeasible due to the LZ77 window but... wow, I never thought that starting a speculative parsing at every possible position can be good enough! Great job! Just in case, my own idea was that, due to the fact that there is exactly one end-of-block symbol per block and the longest codes in dynamic Huffman trees should be lexicographically last due to the canonical encoding. So if you have a long row of 1 bits there is a good chance that this codes the EOB symbol (because it should be the rarest symbol and any reasonable compressor will assign the longest code) and a new block follows. I don't know if this is better than the current brute-force approach. [1] https://news.ycombinator.com/item?id=29586865 https://news.ycombinator.com/item?id=29586865
- mxmlnkn 3y ago
  Interesting, I never thought about looking for the EOB symbol like that but it makes sense. I would guess that some blocks you wouldn't be finding with this are, e.g., compressed zeros, because there would basically be only two Huffman codes, 0 for repeating the last symbol as much times as possible, and 1 for EOB it might even be the other way around. The overhead of looking for deflate blocks can actually be made arbitrarily small by simply increasing the chunk size because you only have to check the first ~64 kiB of the chunk for a valid start position. 99% of compressors limit the produced deflate block size to something below 128 KiB, that's why. Of course, lager chunk sizes have their own problems, like decreased performance for "small" files and higher memory usage because at least one chunk per core has to be kept in memory. The performance improvements on the block finder I made over the one in pugz made it possible to reduce the optimal chunk size from 16 MiB down to 4 MiB and thereby slash the memory usage by 4. 1 MiB chunks might also be fine if you can stomach the ~10% slowdown. The LZ77 windows are something that I skipped over in my other answer. They are a problem. In order to decompress at a position without knowing the LZ77 window, the idea proposed by pugz was to use a dummy 16-bit LZ77 window initialized with unique IDs. That way, you can decompress into a 16-bit data stream and in a second step, when the window becomes known, you do a one-to-one replacement of the 16-bit unique IDs into 8-bit actual data from the real LZ77 window that has become known at this point. Decoding to 16-bit instead of 8-bit requires to modify the decompressor or write one from scratch and it also adds overhead because more memory needs to be traversed and of course because of the second replacement step that now has to be done.

35 points by mxmlnkn 3y ago

ComputerGuru 3y ago

Nice work! How much manual SIMD are you using?

mxmlnkn 3y ago
Currently, none. ISA-L might use some, I'm not sure. I have also tried to accelerate some crucial algorithms with SIMD and my trial and errors are still inside the src/benchmarks subfolder. But, in all of those cases, a simple std::string_view::find, std::transform, or lookup tables turned out to be equally fast or faster and, of course, is more portable. Even the CRC32 algorithm uses "simple" lookup tables (slice-by-16) and avoids any SIMD while still achieving ~4.5 GB/s per core. However, there is some Intel Whitepaper [0] showing how to use PCLMULQDQ for CRC32, which might not be much faster but it would reduce cache pressure. AVX-512 even has a VPCLMULQDQ. [0] https://www.intel.com/content/dam/develop/external/us/en/documents/clmul-wp-rev-2-02-2014-04-20.pdf https://www.intel.com/content/dam/develop/external/us/en/doc...
- ack_complete 3y ago
  The Intel algorithm should be much faster. The slicing algorithms are limited by load unit bandwidth, which appears to be 2 loads/cycle on Zen 2, while PCLMULQDQ should be able to process 16 bytes every 2 cycles (8 bytes/cycle peak). 4.5GB/s is about 1-1.5 bytes/cycle. zlib-ng has an implementation.
  - mxmlnkn 3y ago
    That sounds more than I, for some reason, expected. I'm not sure why, but I was expecting "only" 2x speedup at maximum, while the CRC32 adds "only" 5% overhead. But, 5-8x speedup would be really nice. With that, the the CRC32 overhead would become immeasurable. I'll definitely have to look into it now.
- doophus 3y ago
  For portable SIMD, have a look at ISPC. It allows you to write a function once, compile it for multiple instruction sets, and then automatically select the best one to use at runtime. You don't get the precision of hand-crafted SIMD, but it can grant some easy wins!

jzwinck 3y ago

Does this work with files compressed using the usual gzip command line program? I thought you had to write "sync points" inside a gzip file to support reading from locations other than the start. If you somehow bypass that requirement, can you explain how?

mxmlnkn 3y ago
Yes, it works with files produced by the usual gzip! That's why it is novel. If you make requirements on the compressor, then a multitude of competing gzip implementations exist already, the most popular of which, I think, is bgzip [0]. Rapidgzip can actually leverage the additional metadata stored in bgzip files to speed up decompression by roughly a factor of 2 compared to files compressed with the usual gzip. Rapidgzip does not require sync points because it simply looks for them. The approach is similar to gzrecover [1], i.e., you "simply" try to start decompression at every possible >bit< position. Of course that would be too slow (~200 kB/s), so instead I use several skip and lookup tables to speed up this search to achieve roughly (~70 MB/s). However, that search for deflate block boundaries can yield positions that look valid but which actually aren't, e.g., think of gzip-compressed gzip files. These cases also need to be detected and filtered. Rapidgzip does this filtering and the parallelization by using a cache which stores prefetched decompressed results with the start bit position as key. When the previous block has finished decoding, we know the start position of the next block, and if it exists in the cache, then that result is used. This implicitly filters out valid-looking duds, i.e., false positives. The proof of concept of looking for block boundaries and to resolve and parallelize interdependencies between consecutive blocks, was introduced by pugz [1]. However, it had no detection for false positives and therefore did only work for compressed text files. I built upon this to make it work without assumptions on the compressed data, and I also added capabilities for random access, for which the prefetch-cache architecture also is very suited, so that I can use it in ratarmount. [0] http://www.htslib.org/doc/bgzip.html http://www.htslib.org/doc/bgzip.html [1] https://github.com/arenn/gzrt https://github.com/arenn/gzrt [2] https://arxiv.org/abs/1905.07224 https://arxiv.org/abs/1905.07224
- jzwinck 3y ago
  Thank you for the thorough answer. That is all quite methodical and impressive, bringing together good ideas from disparate projects into a single solution with new benefits. For people like me who have battled this demon before, it would help to explicitly say that you support any gzip file by way of this special magic. At least on my cursory reading of your page I did not understand this. And I never heard of gzrecover, so thanks for that too. I like how the pugz paper starts with "Decompressing a file made by the gzip program at an arbitrary location is in principle impossible." Until today I believed the same!

lifthrasiir 3y ago

Long time ago (probably around 2010 or something) I had a similar idea [1] and concluded that it is infeasible due to the LZ77 window but... wow, I never thought that starting a speculative parsing at every possible position can be good enough! Great job! Just in case, my own idea was that, due to the fact that there is exactly one end-of-block symbol per block and the longest codes in dynamic Huffman trees should be lexicographically last due to the canonical encoding. So if you have a long row of 1 bits there is a good chance that this codes the EOB symbol (because it should be the rarest symbol and any reasonable compressor will assign the longest code) and a new block follows. I don't know if this is better than the current brute-force approach. [1] https://news.ycombinator.com/item?id=29586865 https://news.ycombinator.com/item?id=29586865

mxmlnkn 3y ago
Interesting, I never thought about looking for the EOB symbol like that but it makes sense. I would guess that some blocks you wouldn't be finding with this are, e.g., compressed zeros, because there would basically be only two Huffman codes, 0 for repeating the last symbol as much times as possible, and 1 for EOB it might even be the other way around. The overhead of looking for deflate blocks can actually be made arbitrarily small by simply increasing the chunk size because you only have to check the first ~64 kiB of the chunk for a valid start position. 99% of compressors limit the produced deflate block size to something below 128 KiB, that's why. Of course, lager chunk sizes have their own problems, like decreased performance for "small" files and higher memory usage because at least one chunk per core has to be kept in memory. The performance improvements on the block finder I made over the one in pugz made it possible to reduce the optimal chunk size from 16 MiB down to 4 MiB and thereby slash the memory usage by 4. 1 MiB chunks might also be fine if you can stomach the ~10% slowdown. The LZ77 windows are something that I skipped over in my other answer. They are a problem. In order to decompress at a position without knowing the LZ77 window, the idea proposed by pugz was to use a dummy 16-bit LZ77 window initialized with unique IDs. That way, you can decompress into a 16-bit data stream and in a second step, when the window becomes known, you do a one-to-one replacement of the 16-bit unique IDs into 8-bit actual data from the real LZ77 window that has become known at this point. Decoding to 16-bit instead of 8-bit requires to modify the decompressor or write one from scratch and it also adds overhead because more memory needs to be traversed and of course because of the second replacement step that now has to be done.