Bug 51719 – [chromium] PNG compression settings optimized for speed

• Status: RESOLVED
• Resolution: FIXED
• Component: Images

[Cosmin Truta]

I noticed that, in bug 51455, PNG compression was modified to use the Z_HUFFMAN_ONLY compression strategy, in order to achieve extra speed.

Z_HUFFMAN_ONLY is indeed the fastest on hard-to-compress (e.g. photorealistic) images, but, unfortunately, it is also the most imbalanced: it is by far the slowest on easy-to-compress (e.g. business graphics, icons, screenshots, etc.) images. This may sound counterintuitive, but the explanation lies behind the fact that the Huffman coder has to work the hardest under Z_HUFFMAN_ONLY. On a photorealistic image, the Ziv-Lempel coder spends some effort with little results, and the Huffman coder has to work hard, regardless how good are the results that come out of the Ziv-Lempel stage. On the other hand, on a highly-compressible image, the Ziv-Lempel coder finds a lot of pattern matches, and that will significantly reduce the amount of work of the Huffman coder.

But PNG is mostly used on highly-compressible artificial imagery. Photorealistic images are better handled by JPEG, and are rarely encoded in PNG. This means that the optimization implemented in bug 51455 is for the sake of the statistically rare cases.

Out of curiosity, I run a performance test on all *.png images found in LayoutTests/, using a HP Z600 workstation with 3GHz Intel Xeon multicore processor running a single-threaded PNG encoder on Ubuntu Lucid.

The results are highly intriguing, and I run the tests several times to make sure that there weren't any system anomalies affecting the results. In the table below, "zs" is the zlib strategy (0 for default, 1 for filtered, 2 for huffman, 3 for rle), "zc" is the compression level (min=1, max=9, default=6, ignored by zlib if zs=2 or zs=3), "zm" is the zlib memory level (typically set to 8 or 9, but not making much difference in compression speed), and "f" is the PNG delta filter (0 for unfiltered, 1 for "sub", 2 for "up", ..., 5 for adaptive filtering).

All tests are run at zm=9.
f=0 zs=0 zc=3:   7min 45sec
f=1 zs=1 zc=3:   8min
f=1 zs=2     : 135min
f=1 zs=3     : 128min
f=5 zs=2     : 134min
f=5 zs=3     : 133min 30sec

Can you believe this?!

The differences are abnormally large because LayoutTests/*.png are abnormally compressible. These numbers do, however, prove my point.

Here are more details about the choices I that made and the tools that I used:
I used OptiPNG with the following parameters enabled:
-simulate (i.e. dry-run, to avoid the I/O overhead incurred by writing files to disc)
-full (run the compression until the end; OptiPNG by default stops when the compressed size grows beyond the input file size)
-quiet (do not write anything to stdout or stderr)

I chose zc=3 because it's the highest zlib method that doesn't do lazy matching. The zlib methods 1..3 are non-lazy, and the zlib methods 4..9 are lazy. The lazy Ziv-Lempel searches compress a little better, but are a little slower.
I tried both f=0 (unfiltered) and f=1 (filtered with "sub") to see how they compare. They are fairly equal in performance, as I expected them to be. The adaptive filter (f=5) is a little slower than f=1, because that tries all filters. The difference was largely overwhelmed by the extremely slow huffman coder from zs=2 and zs=3.
I used zs=0 with f=0 and zs=1 with f=1 because that's how these zlib strategies are designed to work with PNG delta filtering.
Moreover, I used the option -nx to disable to image reductions, i.e. to maintain the RGBA color type, as it's done inside Chrome.

So here are the OptiPNG options that I used:
  optipng -simulate -full -nx -zm9 -zc3 -zs0 -f0
  optipng -simulate -full -nx -zm9 -zc3 -zs1 -f1
  optipng -simulate -full -nx -zm9 -zs2 -f1
  optipng -simulate -full -nx -zm9 -zs3 -f1
  optipng -simulate -full -nx -zm9 -zs2 -f5
  optipng -simulate -full -nx -zm9 -zs3 -f5
and here is the actual command line:
  find LayoutTests/ -name "*.png" | xargs optipng ...

[Cosmin Truta]

Oh, and I forgot the conclusion:

In my experience with PNG compression, the speed-optimized parameters to use are the following:
zc=3 (zc=1 and zc=2 are too low; zc=4 uses lazy matching)
f=1, zs=1, zm=9 (for RGB, RGB+alpha, grayscale and grayscale+alpha images with 8 or more bits per sample)
f=0, zs=0, zm=8 (for palette images, and for grayscale images with less than 8 bits per sample -- not applicable to Chromium/WebKit)

[Cosmin Truta]

Created attachment 77641 [details]
Patch

[Cosmin Truta]

In my patch above, there's a slight change from my analysis before: the zlib memory level is still zm=8 (the libpng default) instead of zm=9 (what I used in my tests).
I thought I should stick to the libpng defaults as closely as possible. The memory level makes almost no difference in speed, and if there are differences at all, they can go either way (up or down) between 8 or 9. Choosing between these two is a black art.

[Adam Barth]

I'm not really an expert here.  If you can Noel can come to agreement, that's fine with me.

[Peter Kasting]

FWIW your analysis seems compelling to me and I have no problem with this patch (nice comment, too).  Like Adam, though, I'm not an expert, and I'm also not a reviewer.

[Cosmin Truta]

(In reply to comment #4)
> I'm not really an expert here.  If you can Noel can come to agreement, that's fine with me.

I don't think there actually is a disagreement between me and Noel. It _looks_ like a disagreement between my analysis here, and my other analysis from an article that I wrote 10+ years ago that Noel quoted -- in fact, it's just me clarifying what I wrote in that article.

As far as I understood from Noel's notes in bug 51455, he quoted my Z_RLE compression strategy proposal that I pitched to the zlib developers. (That pitch worked: Z_RLE is now in zlib.)
http://optipng.sourceforge.net/pngtech/z_rle.html

That article was about proposing a compression strategy (namely Z_RLE) that is as fast as, but gives better compression than Z_HUFFMAN_ONLY. Otherwise, Z_RLE inherits both the strenghts and weaknesses of Z_HUFFMAN_ONLY, although I didn't say that explicitly. That probably lead to this confusion.

The image test set used in that proposal was restricted to photographs; this is where these two strategies are good at. On the other hand, in my experiements here, I'm outlining the weakness of both of these strategies. I should probably update my PNGTech site with a new article, to alleviate the confusion that I created here, and, who knows, maybe elsewhere...

[Eric Seidel (no email)]

Comment on attachment 77641 [details]
Patch

rs=me.

[WebKit Commit Bot]

Comment on attachment 77641 [details]
Patch

Clearing flags on attachment: 77641

Committed r75032: <http://trac.webkit.org/changeset/75032>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.