Intel's fast OSS deflate implementation

[Bulat Ziganshin]

https://software.intel.com/en-us/art...r-genomic-data

https://software.intel.com/sites/def.../igzip_042.zip

http://www.intel.com/content/dam/www...sion-paper.pdf

these are just libraries providig API described in ReleaseNotes.txt and lacks main() code. for benchmarking purposes i've attached demo executables from IPP itself. it may be good alternative to lz4/zstd


ADD: two more optimized zlib implementations are mentioned and benchmarked at http://www.htslib.org/benchmarks/zlib.html (note than intel zlib != igzip):

• https://github.com/jtkukunas/zlib # Intel
• https://github.com/cloudflare/zlib # CloudFlare

[just a worm]

Is anyone able to assemble/compile the source code for Windows 32 bit?

It's a shame that the compression ratio is much lower than the output of zlib

[Bulat Ziganshin]

it's 3-4x faster, so why you expect the same compression ratio?

[Bulat Ziganshin]

Is anyone able to assemble/compile the source code for Windows 32 bit?

these are just libraries providig API described in ReleaseNotes.txt. it may be good alternative to lz4/zstd

i've attached demo executables from IPP itself to the first post

[JamesB]

I've looked into these before. While the BAM specific one is good, it is perhaps not so helpful long term. It gets the speed by having precomputed huffman tables and simply working on the (reasonable) asumption that what is good for one BAM file is good for another. The compression ratio suffers a little bit, but not as much as you'd think, while speed is highly significant.

However you can get better speed and compression out of using things like zstd. That's no good for actual "external" BAM files, but for temporary intermediate files (such as generated during a merge sort) we don't need to stick to deflate at all. Indeed some tools are using Snappy or LZ4 already for such internal temporary files.

Intel also have a more general purpose zlib speed up, which isn't BAM specific. I did some benchmarks, related to BAM, at http://www.htslib.org/benchmarks/zlib.html to compare vanilla zlib, intel zlib and also the optimised CloudFlare one. As expected Intel wins out at their level 1 compression as they chose speed over ratio (a useful tradeoff to have), but otherwise CloudFlare look to be a solid contender too.

[Bulat Ziganshin]

thank you, but it's a different library. just compare code at https://github.com/jtkukunas/zlib and https://software.intel.com/sites/def.../igzip_042.zip

[JamesB]

I'm aware of that, but it's primarily designed for genomic data compression and it is in that context that I tested it. The other bit was "Intel *also* have...". . I thought I'd even commented on this library here at some stage.

Intel have a pull request to make Samtools (the primary C code for manipulating SAM/BAM) deal with igzip. Unfortunately the complicated build environment has stalled it. Our hope is it can be achieved via a plugin system so that maintaining and building the code is punted back to the authors!

https://github.com/samtools/htslib/pull/112
https://github.com/samtools/htslib/pull/115

There are some benchmarks I did in the discussions there. What I hadn't noticed until looking at it again is that they have a static huffman table for non-genomic data too. Presumably it's a "best guess" thing which works on some data and just expands on other data.

[Bulat Ziganshin]

you are probably still talking about intel zlib from github, that is separate project

[JamesB]

I'm talking about igzip, not zlib. igzip is not zlib compatible and has a different API, although it matches the deflate RFC.

[Bulat Ziganshin]

oh, sorry, i was misparsed you post. but still, you benchmarked only intel zlib that has much less asm-optimized code. i just hope that people don't take this as benhcmark of igzip. and thank you - i just added link to your post to the header. once again, we need the Compression Wiki :)

btw, it's also interesting download: https://01.org/intel%C2%AE-storage-a...source-version - Intel open-sourced asm-optimized implementation of erasure codes that can be used to add recovery record to the archiver. it implements the reed-solomon codes in GF(2^8) meaning that number of cooperating original+recovery blocks is limited to 256

[JamesB]

The pull request I linked to has some benchmarks too, but admittedly rather poorly done (which is entirely my own fault as it was just a noddy quick test and I couldn't be bothered with a full blown analysis). Stupidly I didn't even write down the vanilla zlib timings and sizes, nor which file I used. Duh.

Basically on that 1GB BAM file:

Intel zlib -1: 553508373 bytes, 13.1s round trip
Intel zlib -2: 414335449 bytes, 22.4s
igzip1c: 430955563 bytes, 16.9s
igzip0c: 446580855 bytes, 11.3s
ZSTD: 405947800 bytes, 10.8s

So igzip0c beats their optimised deflate on both speed and size, but ZSTD beats both. For temporary files therefore Deflate is the wrong algorithm to be trying to optimised. They were also trying to get us to just merge in a prebuilt .a file and store that in github. Umm, no thanks! Our (the samtools development team) stance on this is to just facilitate this via a plugin so people can use prebuilt run-time libraries if they wish, while also absolving ourselves from having to maintain an assembly/C++ hybrid in an otherwise pure-C library.

I see there is definite potential here for tools that *must* use deflate as it's clearly the fastest out there and if you can accept lower compression ratios then it rocks.

Edit: I also notice the htslib.org benchmarks I originally referred to also has an igzip benchmark on it too. It showed it being around 13% larger than the default zlib on the BAM file, while being ~4 times as fast.

[JamesB]

Ugh: This table was produced with "Go Advanced". Why did it bork its own system? Well the numbers are in there somewhere...

Enwiki9 timings on a local 64-bit machine.

No code has to be inserted here.

I didn't check decompression time as igzip doesn't do this from what I can tell (you'd need one of the other zlib implementations). I expect lz4 to beat it considerably on decompression speed.

rANS here is my hack of Ryg's 32-bit one (so not the fastest implementation out there) with an order-1 model added.

Based on this, igzip0c is pretty solid for text files although igzip1c doesn't add much as it's similar speed to zstd but beaten on ratio. Like I say, I've no idea how decompression speed compares.

I tried it on a tarball of /usr/bin for this linux system and I get around igzip0c 163887608 1.81s, igzip1c 156849910 2.69s, lz4 176497040 1.47s, zstd 145205961 2.45s.

So in the right ballpark for binary data too. Not too shabby.

[Jaff]

The table above... as picture

.

[lorents17]

Please, compile igzip for Windows

[Bulat Ziganshin]

isn't it attached to the first post?

[lorents17]

Bulat Ziganshin
At start of ipp_gzip to me gives an error message. Prompt ipp_gzip and igzip one and too?

[load]

• https://github.com/cloudflare/zlib # CloudFlare

this needs SSE4 it seems