Ebiggers/libdeflate: Heavily optimized DEFLATE/zlib/gzip library | Hacker News Reader

gzip library

github.com

3 pointsxioxox12 comments

Open articleView on HN

You can use TurboBench [1] to benchmark libdeflate against zlib, igzip, zlib-ng and others.

Download TurboBench from Releases [2]

Here Some Benchmarks:

- https://github.com/zlib-ng/zlib-ng/issues/1486

- https://github.com/powturbo/TurboBench/issues/43

[1] https://github.com/powturbo/TurboBench

[2] https://github.com/powturbo/TurboBench/releases

Based on my benchmarks, ISA-l/igzip is more than twice(!) as fast as libdeflate and zlib for decompression. I'm almost enamored with ISA-l because of its speed. And yes, it works on AMD and also has Assembler code for ARM, so probably also works on ARM.

For parallelized decompression of gzip, I recommended my own tool, rapidgzip. I have measured up to 10 GB/s decompression bandwidth with it (>20 GB/s if an index already exists). I'm currently working on integrating ISA-l for even more special cases into rapidgzip and hope to release version 0.9.0 in the next days. It will have another +30-100% performance boost for many cases, thanks to ISA-l.

How were you comparing ISA-L and libdeflate? For decompression I've found that the latest version of libdeflate is slightly faster than ISA-L.

My extended benchmarks [0] use the rapidgzip, igzip, gzip, and pigz command line utilities and simply redirect the output to /dev/null to minimize I/O write interference. That's where I got the comparison of igzip to "zlib" as it is used in pigz. I did not compare libdeflate very often to these benchmarks, but before posting my comment, I quickly ran "time libdeflate-gzip -f -k -d 4GiB-base64.gz" inside /dev/shm, which took 20s vs. 9s for igzip.

libdeflate-gzip is something I built and installed a while ago from libdeflate/programs/gzip.c. lideflate-gzip -V prints: "gzip compression program v1.18. Copyright 2016 Eric Biggers". I am aware that lots of care also has to be taken with I/O, which might make the command line utility slower than the library interface, but doing the tests in /dev/shm hopefully alleviated this. I am also aware that base64-encoded random data is a weird test case but it has its pros because it is a kind of minimal benchmark for raw Huffman decoding speed without (many) LZ references that need to be resolved.

I redid the benchmark as outlined above with the three test files that I am also using for my extended benchmarks [0]:

    4GiB-base64.gz            -> libdeflate: 20.5 s, igzip: 9.4 s, rapidgzip: 1.5 s
    20xsilesia.tar.gz         -> libdeflate:  5.4 s, igzip: 6.6 s, rapidgzip: 1.8 s
    10xSRR22403185_2.fastq.gz -> libdeflate:  5.8 s, igzip: 5.5 s, rapidgzip: 1.9 s

File Sizes: Compressed -> Uncompressed:

    4GiB-base64.gz            : 4294967296 -> 3263906203
    20xsilesia.tar.gz         : 1364776140 -> 4239155200
    10xSRR22403185_2.fastq.gz :  970458140 -> 3618153020

In conclusion, it seems that it highly depends on the test case and the one I tested to, too quickly, check my statement is one of the outliers.

[0] https://github.com/mxmlnkn/rapidgzip#scaling-benchmarks-on-2...

I also did benchmarks with zlib and libarchivemount via their library interface here [0]. It has been a while that I have run them, so I forgot. Unfortunately, I did not add libdeflate. I did not even add ISA-l. At that point, I was already would have been glad if my custom-written gzip decompressor could match the speed of the gzip command line utility, which for some weird reason is half as fast as zlib.

[0] https://github.com/mxmlnkn/rapidgzip/blob/master/src/benchma...

libdeflate compress better and has faster decompression than igzip.

See the silesia single core in-memory benchmark here [1] comparing zlib,libdeflate,igzip,...

https://github.com/powturbo/TurboBench/issues/4

I assume you wanted to link to TurboBench and not that particular issue, which for some reason also contains a link for some car listing?

Secondly, did you not see my answer to ebiggers under this comment you replied to? Yes, for Silesia, libdeflate is faster, I can confirm, but there are at least two cases for which igzip is faster and one for which igzip is twice as fast. But yes, it heavily depends on the input data.

Edit: I was then wondering why I could not find any igzip benchmarks on the repository's ReadMe and then found https://github.com/powturbo/TurboBench/issues/43 , so I guess this is the one you wanted to link to and the 3 got cut off.

Sorry, a digit was missing, but now https://github.com/powturbo/TurboBench/issues/43

Well, a correct benchmarking is not done with special data, but with datasets that represent a large set of distributions. Such datasets are for ex. einwik8/9 for text, silesia for a mixed dataset. As a corner case example, RLE-compressible data is not representative for benchmarking compression libraries.

If you provide a link for a dataset 10-100MB, I can verify your claims, because I'm not aware of a dataset where igzip is 2 times faster than libdeflate. In TurboBench there is no I/O or other overhead involved, additionally it's single threaded. It's also possible that you're comparing two different CLI programs, one (igzip) I/O optimized and the other as a simple CLI.

EDIT: I've seen the file you're referencing is 4Gi-Base64. This file is not very compressible (75% with gzip). It's possible that igzip is simply storing the file or some parts of it without compression. This explain why it can be faster that libdeflate, because in this case igzip is using memcpy at decompression.

That is not the case. I have compressed the file with gzip and then tested decompression with multiple gzip decompressors. I.e., they all are fed the same compressed binary. Furthermore, I have used rapidgzip --analyze, to print out all deflate blocks, their compression types, and other information and statistics. All of the blocks are Dynamic Huffman compressed blocks.

I have already incorporated the ISA-L Huffman decoder into rapidgzip but that did not give full ISA-L speed. Ergo, I think the last performance comes from the inflate loop (decode Huffman, decode distance code if necessary, resolve references, repeat). This part is written in Assembler and seems to do some kind of speculative prefetching, i.e., already get the next Huffman Code symbol assuming that the current symbol is a literal or something like that. It's quite interesting but I doubt, or rather, I already tried a bit and failed to reproduce this kind of prefetching inside the C++ code but failed to do so. The compiler is probably rearranging everything anyway.

rapidgzip --analyze 4GiB-base64.gz | tail -100

    == Benchmark Profile (Cumulative Times) ==

    readDynamicHuffmanCoding : 0.903727 s (3.38252 %)
    readData                 : 25.8139 s (96.6175 %)
    Dynamic Huffman Initialization in Detail:
        Read precode       : 0.00975829 s (1.07978 %)
        Create precode HC  : 0.0341786 s (3.78196 %)
        Apply precode HC   : 0.0667695 s (7.38823 %)
        Create distance HC : 0.114097 s (12.6252 %)
        Create literal HC  : 0.678924 s (75.1249 %)


    == Alphabet Statistics ==

    Precode  : 123274 duplicates out of 126748 (97.2591 %)
    Distance : 597 duplicates out of 126748 (0.471013 %)
    Literals : 13799 duplicates out of 126748 (10.887 %)

    == Precode Code Length Count Distribution ==

    16 |==================== (126748)

    == Distance Code Length Count Distribution ==

    30 |==================== (126748)

    == Literal Code Length Count Distribution ==

             259 |=============        (50635)
    2.601250e+02 |==================== (74281)
                 |                     (1809)
             262 |                     (23)


    == Encoded Block Size Distribution ==

    185942 bits |                     (1)
                |                     
                |                     
                |                     
                |                     
                |                     
                |                     (2)
    207391 bits |==================== (126745)


    == Decoded Block Size Distribution ==

    30579 Bytes |                     (1)
                |                     
                |                     
                |                     
                |                     
                |                     
                |                     (1)
    34112 Bytes |==================== (126746)


    == Compression Ratio Distribution ==

    1.314967e+00 Bytes |                     (9)
                       |                     (1327)
                       |======               (17906)
    1.315808e+00 Bytes |==================== (52698)
                       |================     (42890)
                       |====                 (10876)
                       |                     (1001)
    1.316891e+00 Bytes |                     (41)

    == Deflate Block Compression Types ==

    Dynamic Huffman : 126748

Thank for your analyse. It seems it's a corner case, benchmarking a base64 encoded random file is not a typical case. igzip has no more advantage above libdeflate. It has only fast compression at the levels 0,1,2 but with mediocre compression ratio.

One nice thing about this is that the compression factor seems quite a bit higher than standard gzip. This is very useful if you need compatibility with gzip/zlib formats (e.g. PNG files). For my use case, the compressed output was 8% smaller using libdeflate compression=12 than with gzip compression=9. The compression was also a lot faster with a single thread. It would be nice to see a comparison with a larger number of inputs, however.

Reply on news.ycombinator.com