Results 1 to 11 of 11

Thread: Efficient deflate implementations

  1. #1
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts

    Efficient deflate implementations

    I know that there are a few more efficient implementations of inflate, i.e. zlib compression. Are there alternative implementations of deflate?

  2. #2
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    667
    Thanks
    204
    Thanked 241 Times in 146 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    I know that there are a few more efficient implementations of inflate, i.e. zlib compression. Are there alternative implementations of deflate?
    Usually the implementations that fare well in simplistic benchmarks do less well in the real world. They can hide more bytes of the stream and lead to worse user experienced latency by allowing less processing (such as png filtering or html parsing and issuing new http fetches) to happen during the data transfer.

  3. #3
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    I'm not quite sure what exactly you're asking*, but I think all implementations referenced in https://encode.ru/threads/3000-defla...ding-benchmark
    have both encoding and decoding.
    I also have my own implementations, just in case.

    * https://en.wikipedia.org/wiki/DEFLAT...mplementations
    Normally deflate decoding is called inflate.

  4. The Following User Says Thank You to Shelwien For This Useful Post:

    Bulat Ziganshin (5th March 2019)

  5. #4
    Member
    Join Date
    Dec 2011
    Location
    Cambridge, UK
    Posts
    437
    Thanks
    137
    Thanked 152 Times in 100 Posts
    Yes, libdeflate is considerably faster at both inflate and deflate.

    https://github.com/ebiggers/libdeflate

  6. The Following User Says Thank You to JamesB For This Useful Post:

    Bulat Ziganshin (5th March 2019)

  7. #5
    Member
    Join Date
    Dec 2011
    Location
    Cambridge, UK
    Posts
    437
    Thanks
    137
    Thanked 152 Times in 100 Posts
    Code:
    perf stat ./libdeflate/gzip < ~/scratch/data/enwik8 > /tmp/en8.1    
           1611.840969      task-clock (msec)         #    0.999 CPUs utilized          
                     7      context-switches          #    0.004 K/sec                  
                     0      cpu-migrations            #    0.000 K/sec                  
                 10643      page-faults               #    0.007 M/sec                  
            5747402857      cycles                    #    3.566 GHz                    
            8327325505      instructions              #    1.45  insn per cycle         
            1292868764      branches                  #  802.107 M/sec                  
              63548088      branch-misses             #    4.92% of all branches        
    
    -rw-r--r-- 1 jkb team117 36648336 Mar  5 12:06 /tmp/en8.1
    
    perf stat gzip < ~/scratch/data/enwik8 > /tmp/en8.2
           4414.007069      task-clock (msec)         #    1.000 CPUs utilized          
                    14      context-switches          #    0.003 K/sec                  
                     0      cpu-migrations            #    0.000 K/sec                  
                   129      page-faults               #    0.029 K/sec                  
           15515069439      cycles                    #    3.515 GHz                    
           19132616220      instructions              #    1.23  insn per cycle         
            3944198987      branches                  #  893.564 M/sec                  
             143047281      branch-misses             #    3.63% of all branches       
     
    -rw-r--r-- 1 jkb team117 36518322 Mar  5 12:05 /tmp/en8.2
    
    [Timings identical for decompression of either en8.1 or en8.2 gzip streams]
    perf stat .libdeflate/gunzip < /tmp/en8.1 > /dev/null
            209.156303      task-clock (msec)         #    0.997 CPUs utilized          
                     0      context-switches          #    0.000 K/sec                  
                     0      cpu-migrations            #    0.000 K/sec                  
                 25022      page-faults               #    0.120 M/sec                  
             732611027      cycles                    #    3.503 GHz                    
            1552244051      instructions              #    2.12  insn per cycle         
             212135090      branches                  # 1014.242 M/sec                  
               8391548      branch-misses             #    3.96% of all branches        
    
    perf stat gunzip < /tmp/en8.2 > /dev/null
            650.145011      task-clock (msec)         #    1.000 CPUs utilized          
                     3      context-switches          #    0.005 K/sec                  
                     0      cpu-migrations            #    0.000 K/sec                  
                   137      page-faults               #    0.211 K/sec                  
            2316086689      cycles                    #    3.562 GHz                    
            3205922792      instructions              #    1.38  insn per cycle         
             484782677      branches                  #  745.653 M/sec                  
              21925077      branch-misses             #    4.52% of all branches
    So around 3x faster at encode/decode. Standard gzip/gunzip here are from native Zlib 1.2.11

    Edit libdeflate's gzip -7 is closer in size to Zlib's gzip -6, but is a bit slower (1.9s). Higher levels become slower (than zlib) but also smaller than zlib's gzip -9.

    NB: Libdeflate has no streaming API either.

  8. The Following User Says Thank You to JamesB For This Useful Post:

    Bulat Ziganshin (5th March 2019)

  9. #6
    Member
    Join Date
    May 2007
    Location
    Poland
    Posts
    85
    Thanks
    8
    Thanked 3 Times in 3 Posts
    I made some test lately and best speed/compression ratio for ZIP (deflate) was Winrar (at least for the big CSV files i had)

    "C:\Program Files\WinRAR\WinRAR.exe" a -afzip -ibck -m4 c:\test.zip c:\test.csv

  10. #7
    Member jibz's Avatar
    Join Date
    Jan 2015
    Location
    Denmark
    Posts
    114
    Thanks
    91
    Thanked 69 Times in 49 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    I know that there are a few more efficient implementations of inflate, i.e. zlib compression. Are there alternative implementations of deflate?
    Actually compressing data in the deflate format is usually called deflating, while decompression is inflating. If you consider the meaning of these names it makes sense, but it is easy read the "de" in deflate to mean decompression.

    +1 for libdeflate, I've used it in a couple of projects as well. I assume you mean speed efficiency, but there are also inflate implementations that try to optimize for size, for instance I wrote one many years ago called tinf.

  11. #8
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts

  12. #9
    Member SolidComp's Avatar
    Join Date
    Jun 2015
    Location
    USA
    Posts
    222
    Thanks
    89
    Thanked 46 Times in 30 Posts
    Klaus Post has done an excellent job of implementing deflate and gzip in the Go programming language. He uses SIMD via Go assembly. https://github.com/klauspost/compress

  13. #10
    Member SolidComp's Avatar
    Join Date
    Jun 2015
    Location
    USA
    Posts
    222
    Thanks
    89
    Thanked 46 Times in 30 Posts
    And he has a parallel implementation here: https://github.com/klauspost/pgzip

  14. #11
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    Got this answer via email:

    There is at least one here: http://unzip-ada.sf.net/
    If it is efficient enough - depends on your criteria
    But at least it is alternative.
    Same for the LZMA encoder BTW.

Similar Threads

  1. List of Asymmetric Numeral Systems implementations
    By Jarek in forum Data Compression
    Replies: 13
    Last Post: 1st March 2018, 00:06
  2. Replies: 41
    Last Post: 24th July 2017, 19:05
  3. Concurrent kernel execution in OpenCL implementations
    By Piotr Tarsa in forum The Off-Topic Lounge
    Replies: 0
    Last Post: 16th April 2011, 16:04
  4. Most efficient/practical compression method for short strings?
    By never frog in forum Data Compression
    Replies: 6
    Last Post: 1st September 2009, 04:05
  5. DEFLATE/zlib implementations
    By GerryB in forum Data Compression
    Replies: 10
    Last Post: 7th May 2009, 17:03

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •