Sequence Compression Benchmark

[SolidComp]

Hi all – @Kirr made an incredibly powerful compression benchmark website called the Sequence Compression Benchmark.

It lets you select a bunch of options and run it yourself, with outputs including graphs, column charts, and tables. It can run every single level of every compressor.

The only limitation I see at this point is the lack of text datasets – it's mostly genetic data.

@Kirr, four things:

1. Broaden it to include text? Would that require a name change or ruin your vision for it? It would be great to see web-based text, like the HTML, CSS, and JS files of the 100 most popular websites for example.
2. The gzipper you currently use is the GNU gzip utility program that comes with most Linux distributions. If you add some text datasets, especially web-derived ones, the zlib gzipper will make more sense than the GNU utility. That's the gzipper used by virtually all web servers.
3. In my limited testing the 7-Zip gzipper is crazy good, so good that it approaches Zstd and brotli levels. It's long been known to be better than GNU gzip and zlib, but I didn't know it approached Zstd and brotli. It comes with the 7-Zip Windows utility released by Igor Pavlov. You might want to include it.
4. libdeflate is worth a look. It's another gzipper. The overarching message here is that gzip ≠ gzip. There are many implementations, and the GNU gzip utility is likely among the worst.

[Kirr]

Thanks for kind words, SolidComp.

Broaden it to include text? Would that require a name change or ruin your vision for it? It would be great to see web-based text, like the HTML, CSS, and JS files of the 100 most popular websites for example.

I work with tons of biological data, which motivated me to first make a compressor for such data, and then this benchmark. I'll probably add FASTQ data in the future, if time allows. As for text, HTML, CSS and other data, I have no immediate plans for it. There are three main obstacles: 1. Computation capacity. 2. Selecting relevant data. 3. My time needed to work on it. Possibly it will require cooperating with other compression enthusiasts. I'll need to think about it.

The gzipper you currently use is the GNU gzip utility program that comes with most Linux distributions. If you add some text datasets, especially web-derived ones, the zlib gzipper will make more sense than the GNU utility. That's the gzipper used by virtually all web servers.

I'm under the impression that "zlib" is a compression library, and "gzip" is a command line interface to this same library. Since I benchmark command line compression tools, it's the "gzip" that is included, rather than "zlib". However please let me know if there is some alternative command line "zlib gzipper" that I am missing.

In my limited testing the 7-Zip gzipper is crazy good, so good that it approaches Zstd and brotli levels. It's long been known to be better than GNU gzip and zlib, but I didn't know it approached Zstd and brotli. It comes with the 7-Zip Windows utility released by Igor Pavlov. You might want to include it.

Igor Pavlov's excellent LZMA algorithm (which powers 7-Zip) is represented by the "xz" compressor in the benchmark. Igor's unfortunate focus on Windows releases allowed "xz" to become standard LZMA implementation on Linux (as far as I understand).

libdeflate is worth a look. It's another gzipper. The overarching message here is that gzip ≠ gzip. There are many implementations, and the GNU gzip utility is likely among the worst.

You mean this one - https://github.com/ebiggers/libdeflate ? Looks interesting, I'll take a look at it. I noticed this bit in the GitHub readme: "libdeflate itself is a library, but the following command-line programs which use this library are also provided: gzip (or gunzip), a program which mostly behaves like the standard equivalent, except that it does not yet have good streaming support and therefore does not yet support very large files" - Not supporting very large files sounds alarming. Especially without specifying what exactly they mean by "very large".

Regarding gzip, don't get me started! Every single biological database shares data in gzipped form, wasting huge disk space and bandwidth. There is a metric ton of research on biological sequence compression, in addition to excellent general-purpose compressors. Yet the field remains stuck with gzip. I want to show that there are good alternatives to gzip, and that there are large benefits in switching. Whether this will have any effect remains to be seen. At least I migrated all my own data to a better format (saving space and increasing access speed).

[SolidComp]

"gzip" as such isn't a command line interface to the zlib library. It's just a format, one of three that zlib supports (the other two are raw DEFLATE and a "zlib" format, also DEFLATE-based). GNU gzip is just a specific app that produces gzip files (and maybe others?).

I think zlib has a program that you can easily build. It might be called minizip. Someone please correct me if I'm wrong.

The 7-Zip gzipper is unrelated to the .7z or LZMA formats. I'm speaking of 7-Zip the app. It can produce .7z, .xz, gzip (.gz), .zip, .bz2, and perhaps more compression formats. Pavlov wrote his own gzipper from scratch, apparently, and it's massively better than any other gzipper, like GNU gzip or libdeflate. I assume it's better than zlib's gzipper as well. I don't understand how he did it. So if you want to compare the state of the art to gzip, it would probably make sense to use the best gzipper. His gzip files are 17% smaller than libdeflate's on text...

[Kirr]

"gzip" as such isn't a command line interface to the zlib library. It's just a format, one of three that zlib supports (the other two are raw DEFLATE and a "zlib" format, also DEFLATE-based). GNU gzip is just a specific app that produces gzip files (and maybe others?).

Yeah, the two are a tool and a library implementing DEFLATE algorith, this is more accurate to say. In my benchmark, by "gzip" I refer to the software tool, not to the "gzip" file format.

I think zlib has a program that you can easily build. It might be called minizip. Someone please correct me if I'm wrong.

zlib has "zpipe.c" in "examples" directory. This may be what you mean. I guess there is no point testing it, but perhaps I should benchmark it to confirm this.

The 7-Zip gzipper is unrelated to the .7z or LZMA formats. I'm speaking of 7-Zip the app. It can produce .7z, .xz, gzip (.gz), .zip, .bz2, and perhaps more compression formats. Pavlov wrote his own gzipper from scratch, apparently, and it's massively better than any other gzipper, like GNU gzip or libdeflate. I assume it's better than zlib's gzipper as well. I don't understand how he did it. So if you want to compare the state of the art to gzip, it would probably make sense to use the best gzipper. His gzip files are 17% smaller than libdeflate's on text...

It seems 7-Zip is still Windows-exclusive. However there is a more portable "p7zip" - I will think about adding it to the benchmark.

[JamesB]

I think Libdeflate is the fastest tool out there right now, unless limiting to light-weight "level 1" style in which case maybe libslz wins out.

We integrated libdeflate support into Samtools; for (de)compression of sequencing alignment data in the BAM format. I suspect this is the cause of libdeflate becoming an official Ubuntu package as Samtools/htslib have it as a dependency. I recently retested several deflater algorithms on enwik8.

Tool         Encode    Decode     Size
------------------------------------------
vanilla      0m5.003s  0m0.517s   36548933
intel        0m3.057s  0m0.503s   36951028
cloudflare   0m2.492s  0m0.443s   36511793
jtkukunas    0m2.956s  0m0.357s   36950998
ng           0m2.022s  0m0.377s   36881293
zstd (gz-6)  0m4.674s  0m0.468s   36548933
libdeflate   0m1.769s  0m0.229s   36648336

Note the file sizes fluctuate a bit. That's within the difference between gzip -5 vs -6 so arguably you'd include that in the time difference too.


I also tried them at level 1 compression:

Tool         Encode    Decode     Size
------------------------------------------
vanilla      0m1.851s  0m0.546s   42298786
intel        0m0.866s  0m0.524s   56046821
cloudflare   0m1.163s  0m0.470s   40867185
jtkukunas    0m1.329s  0m0.392s   40867185
ng           0m0.913s  0m0.397s   56045984
zstd (gz)    0m1.764s  0m0.475s   42298786
libdeflate   0m1.024s  0m0.235s   39597396

Level 1 is curious as you can see very much how different versions have traded off the encoder algorithm speed vs size efficiency, with cloudflare and jtkukunas apparently using the same algorithm and intel/ng likewise. Libdeflate is no longer the fastest here, but it's not far off and is the smallest so it's in a sweet spot.

And for fun, level 9:

Tool         Encode    Decode     Size
------------------------------------------
vanilla      0m6.113s  0m0.516s   36475804
intel        0m5.153s  0m0.516s   36475794
cloudflare   0m2.787s  0m0.442s   36470203
jtkukunas    0m5.034s  0m0.365s   36475794
ng           0m2.872s  0m0.371s   36470203
zstd (gz)    0m5.702s  0m0.467s   36475804
libdeflate   0m9.124s  0m0.237s   35197159

All remarkably similar sizes, bar libdeflate which took longer but squashed it considerably more. Libdeflate actually goes up to -12, but it's not a good tradeoff on this file:

libdeflate   0m14.660s 0m0.236s   35100586

Edit: I tested 7z max too, but it was comparable to libdeflate max and much slower.

[Kirr]

Thanks James, looks like I'll have to add libdeflate soon. I'm still worrying about it's gzip replacement not supporting large files. I guess I'll see what they mean.

[JamesB]

It's good for block based formats, but the lack of streaming may be an issue for general purpose zlib replacement. However even for a streaming gzip you could artificially chunk it into relatively large blocks. It's not ideal, but may be the better speed/ratio tradeoff still means it's a win for most data types.

We use it in bgzf (wrapper for BAM and BCF formats), which has pathetically small block sizes, as a replacement for zlib.

[SolidComp]

James, what about SLZ? That's the fastest gzip implementation on earth as far as I know. It doesn't compress as well though. But it's incredibly fast, and super light in terms of CPU and memory consumption.

[JamesB]

James, what about SLZ? That's the fastest gzip implementation on earth as far as I know. It doesn't compress as well though. But it's incredibly fast, and super light in terms of CPU and memory consumption.

I just tried the latest version. It's as I recall - very fast but very light levels of compression. It also has no decompression support at all, so obviously it can't compete on that front.

On the above file with the same machine, level 1 only. Redoing these encode timings as I realise I had I/O time in there which doesn't help the ultra fast ones:

Tool         Encode    Decode     Size
------------------------------------------
vanilla      0m1.657s  0m0.546s   42298786
intel        0m0.569s  0m0.524s   56046821
cloudflare   0m0.974s  0m0.470s   40867185
jtkukunas    0m1.106s  0m0.392s   40867185
ng           0m0.695s  0m0.397s   56045984
zstd (gz)    0m1.582s  0m0.475s   42298786
libdeflate   0m0.838s  0m0.235s   39597396
libslz       0m0.482s  N/A        55665941

So yes it's the fastest. libslz has levels up to -9, but they're barely any different in size/speed.

[Kirr]

I guess this discussion is about deflate-based libraries. Since I benchmark command line tools rather than bare libraries, each lib would need a command line interface before it can be tested. I already added p7zip and libdeflate's streaming gzip replacement to my to-do benchmark queue. If you have more suggestions in mind, please post here with links. Thanks!

[SolidComp]

@Kirr, you might be interested in this report on Intel's QuickAssist with genomic data. QuickAssist is a hardware accelerator from Intel that comes in a couple of forms. One is a PCIe card, and the other is built into some Xeon D server chips. QuickAssist accelerates compression and encryption workloads beyond what is possible with conventional CPU-based code.

https://01.org/sites/default/files/d...uickassist.pdf

[JamesB]

Interesting link, although it's a bit of a sales pitch.

"Reduce storage system cost: In the face of a 10 Tb genetic data growth on a daily basis, BGI needs to increase data compression ratio, improve storage density and reduce data storage costs."

Fair enough, sounds good. They then compare it to gzip -1 where their system is much faster, but slightly larger. How is being slightly larger than gzip -1 "inceas[ing] data compression ratio"? 3 times faster than gzip -1 puts it into the zstd or brotli level 1 speeds. They're using 32-cores too, so a threaded tool clearly helps here (pigz vs zstd for example).

Edit, 1GB of uncompressed BAM input:

$ time gzip -1 < /tmp/_1g|wc -c
427760970
real    0m15.498s
user    0m15.331s
sys    0m0.631s

$ time ~/ftp/compression/libdeflate/gzip -1 < /tmp/_1g|wc -c
416714103
real    0m8.711s
user    0m8.418s
sys    0m0.372s

$ time bro --quality 1 < /tmp/_1g|wc -c
418622612
real    0m5.753s
user    0m5.599s
sys    0m0.411s

$ time zstd -1 < /tmp/_1g|wc -c
402699667
real    0m3.953s
user    0m4.096s
sys    0m0.392s

$ time zstd --fast=3 < /tmp/_1g|wc -c
581488734
real    0m2.428s
user    0m2.624s
sys    0m0.472s

[JamesB]

I take it back, maybe they have something impressive.

I was pointed to https://github.com/intel/isa-l recently and initially just assumed it would be a regurgitation of their intel-zlib, but it's not. It's totally different. Firstly it's not a zlib replacement, having no common API. Secondly it's got huge swathes of assembly. Thirdly and most importantly, it's seriously quick at both compression and decompression. It favours light weight compression, but given the decompression is also fast this is clearly also some good software engineering too and not simply aiming for a different speed vs size balance.

Quoting from above with igzip -0 to -3 (the max) added in:

    Tool         Encode    Decode     Size                                      
    ------------------------------------------                                  
    vanilla      0m1.657s  0m0.546s   42298786                                  
    intel        0m0.569s  0m0.524s   56046821                                  
    cloudflare   0m0.974s  0m0.470s   40867185                                  
    jtkukunas    0m1.106s  0m0.392s   40867185                                  
    ng           0m0.695s  0m0.397s   56045984                                  
    zstd (gz)    0m1.582s  0m0.475s   42298786                                  
    libdeflate   0m0.838s  0m0.235s   39597396                                  
    libslz       0m0.482s  N/A        55665941                     
    igzip -0     0m0.298s  0m0.178s   43286313
    igzip -1     0m0.328s  0m0.174s   41738193
    igzip -2     0m0.340s  0m0.171s   40705159
    igzip -3     0m0.625s  0m0.162s   39481657
(non gzip:)        
    zstd -1      0m0.465s  0m0.156s   40748555
    bro -q0      0m0.665s  0m0.413s   43426928
    lz4          0m0.377s  0m0.077s   57285984

Dataset is enwik8 on my work desktop (Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz).

I'm particularly impressed with how it stacks up against zstd -1 and bro --quality 0 with regards to speed vs size tradeoffs, while still using a compliant gzip stream. It's not a millin miles away from lz4 - faster for compression anyway!

The take home message here is the other Deflate implementations still have something to learn about fast decoding. (Not igzip could decode libdeflate -9 output, so it's not just customised for specific predefined huffman trees). Encoding, igzip -3 is comparable to libdeflate -1 for size, but is still faster. So it's not just shallower search algorithms. However igzip -0 to -2 are *considerably* quicker so that probably is something to do with how hard it's looking for LZ matches.

[Kirr]

I was pointed to https://github.com/intel/isa-l recently and initially just assumed it would be a regurgitation of their intel-zlib, but it's not. It's totally different. Firstly it's not a zlib replacement, having no common API. Secondly it's got huge swathes of assembly. Thirdly and most importantly, it's seriously quick at both compression and decompression. It favours light weight compression, but given the decompression is also fast this is clearly also some good software engineering too and not simply aiming for a different speed vs size balance.

Interesting, thanks for pointing out. I added this link to my to-do notes, and will try to add it to the benchmark (sooner or later).

[Bulat Ziganshin]

> igzip could decode libdeflate -9 output, so it's not just customised for specific predefined huffman trees

it may contain BOTH customized decoder and generic one. You should check decompression speed specifically on the libdefalte -9 output

> I'm particularly impressed with how it stacks up against zstd -1 and bro --quality 0 with regards to speed vs size tradeoffs, while still using a compliant gzip stream. It's not a millin miles away from lz4 - faster for compression anyway!

modern compressors are optimized toward binary data and large dictionaries. in particular, zstd -1 has min_match_len=5 or so, and also includes tricks such as repdist useless for text data. brotli format seems to be optimized toward high compression modes