compress/flate: Add optimizations and re+balance.

[klauspost]

We should merge optimizations added to https://github.com/klauspost/compress

Typical speedup is around 1.7x for web content, when maintaining roughly the same compression.

With re-balanced compression settings, the default level will be 3.1x faster at a 7% compression loss. Mixed content (disk images) show a 3.1x speedup with a 3% compression loss.

Extensive benchmarks in this google spreadsheet.

[gopherbot]

CL https://golang.org/cl/19336 mentions this issue.

[gopherbot]

CL https://golang.org/cl/20513 mentions this issue.

[rsc]

@nigeltao, @klauspost, what is left here? Did the rebalancing happen?

[nigeltao]

Some optimizations landed. Others didn't make the code freeze deadline. @klauspost would probably know better than me what's out that he'd still like to bring over from https://github.com/klauspost/compress

Re-balancing, in terms of tweaking what parameter settings correspond to "compression level == 6", didn't happen, but when compared to Go 1.6, I believe that compression is still generally faster on GOARCH=amd64 at the default setting. I don't have any numbers on me right now.

Also, "compression level == 1" aka "best speed" now uses the Snappy algorithm, for higher throughput but larger encoded size. That encoding size can come down with further algorithmic changes, but there was a correctness bug found in the fancier algorithm just before code freeze, so that will have to wait for Go 1.8.

Issue #15622 is that compress/flate's minimum LZW-style match length increased from 3 bytes to 4 bytes, as 32-bit ops can be a lot faster. However, compressing RGB images can often want 3-byte matches, corresponding to an RGB tuple. We're still investigating how big a regression this is: whether it's "TIFF and PNG images are consistently e.g. 10% to 20% larger" or if it's "some are larger, some are smaller, and it's mostly a wash, although you can always find examples where it's significantly worse", or if it's somewhere in between. The current proposal is to re-introduce 3-byte matches for higher levels of the compression size-vs-throughput knob, although that will be more (as-yet-unwritten-and-untested) code.

I don't think there are any open CLs. Please correct me if I'm wrong.

[klauspost]

I think the overall goal has been achieved, with some details left.

Did the rebalancing happen?

No - I haven't tested the current build, but I suspect it could need a re-balance and that "standard" is quite close to "best" in terms of both compression and speed.

There are a few things that I would like to look at in the future, mainly:

• Split lazy/non-lazy matching, and add 3-length matching to the lazy matcher as an elegant fix for compress/flate: add 3-byte matching for higher compression levels #15622. Not sure if Nigel agrees through.
• Re-balance. If lazy is made capable of 3 byte matches, that will be even more relevant, and "lazy" belongs to level 7-9 or thereabout.
• The token storage can be made to avoid bounds checks. This is trivial and can be quite nicely implmented, but I couldn't make the 1.7 deadline.

I don't think there are any open CLs. Please correct me if I'm wrong.

Correct, AFAIK.