51719 2010-12-29 11:57:31 -0800 [chromium] PNG compression settings optimized for speed 2011-01-04 17:15:11 -0800 1 1 1 Unclassified WebKit Images 528+ (Nightly build) All OS X 10.5 RESOLVED FIXED P2 Normal --- 0 ctruta webkit-unassigned abarth brettw commit-queue eric noel.gordon pkasting oldest_to_newest 327652 0 ctruta 2010-12-29 11:57:31 -0800 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 ... 327656 1 ctruta 2010-12-29 12:07:23 -0800 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) 327681 2 77641 ctruta 2010-12-29 13:17:30 -0800 Created attachment 77641 Patch 327682 3 ctruta 2010-12-29 13:20:55 -0800 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. 327807 4 abarth 2010-12-29 19:39:55 -0800 I'm not really an expert here. If you can Noel can come to agreement, that's fine with me. 328032 5 pkasting 2010-12-30 13:48:23 -0800 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. 329155 6 ctruta 2011-01-04 13:02:31 -0800 (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... 329167 7 77641 eric 2011-01-04 13:22:17 -0800 Comment on attachment 77641 Patch rs=me. 329309 8 77641 commit-queue 2011-01-04 17:15:04 -0800 Comment on attachment 77641 Patch Clearing flags on attachment: 77641 Committed r75032: <http://trac.webkit.org/changeset/75032> 329310 9 commit-queue 2011-01-04 17:15:11 -0800 All reviewed patches have been landed. Closing bug. 77641 2010-12-29 13:17:30 -0800 2011-01-04 17:15:04 -0800 Patch wk51719.diff.submit text/plain 2408 ctruta ZGlmZiAtLWdpdCBhL1dlYkNvcmUvQ2hhbmdlTG9nIGIvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXgg ZmVmM2I0NS4uMWMwZTA2OSAxMDA2NDQKLS0tIGEvV2ViQ29yZS9DaGFuZ2VMb2cKKysrIGIvV2Vi Q29yZS9DaGFuZ2VMb2cKQEAgLTEsMyArMSwyMSBAQAorMjAxMC0xMi0yOSAgQ29zbWluIFRydXRh ICA8Y3RydXRhQGNocm9taXVtLm9yZz4KKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9P UFMhKS4KKworICAgICAgICBbY2hyb21pdW1dIFBORyBjb21wcmVzc2lvbiBzZXR0aW5ncyBvcHRp bWl6ZWQgZm9yIHNwZWVkCisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVn LmNnaT9pZD01MTcxOQorCisgICAgICAgIEFsdGhvdWdoIFpfSFVGRk1BTl9PTkxZIGlzIHRoZSBm YXN0ZXN0IG9uIGhhcmQtdG8tY29tcHJlc3MgaW1hZ2VzLAorICAgICAgICBpdCBpcyBhbHNvIHRo ZSBzbG93ZXN0LCBieSBhIHdpZGUgbWFyZ2luLCBvbiBlYXN5LXRvLWNvbXByZXNzIGltYWdlcy4K KyAgICAgICAgVXNlIGEgbW9yZSBiYWxhbmNlZCBjb25maWd1cmF0aW9uLCBiYXNlZCBvbiB0aGUg bGlicG5nIGNvbXByZXNzaW9uIGRlZmF1bHRzLAorICAgICAgICBidXQgd2l0aCBhIGZhc3RlciBj b21wcmVzc2lvbiBsZXZlbCAoMyBpbnN0ZWFkIG9mIDYpLCBhbmQgYSBmYXN0ZXIgZmlsdGVyCisg ICAgICAgICgic3ViIiBpbnN0ZWFkIG9mICJhbGwiKS4KKworICAgICAgICBObyBjaGFuZ2UgaW4g YmVoYXZpb3VyLCBzbyBubyBuZXcgdGVzdHMuCisKKyAgICAgICAgKiBwbGF0Zm9ybS9pbWFnZS1l bmNvZGVycy9za2lhL1BOR0ltYWdlRW5jb2Rlci5jcHA6CisgICAgICAgIChXZWJDb3JlOjpQTkdJ bWFnZUVuY29kZXI6OmVuY29kZSk6CisKIDIwMTAtMTItMjkgIEFsZXhhbmRlciBQYXZsb3YgIDxh cGF2bG92QGNocm9taXVtLm9yZz4KIAogICAgICAgICBSZXZpZXdlZCBieSBZdXJ5IFNlbWlraGF0 c2t5LgpkaWZmIC0tZ2l0IGEvV2ViQ29yZS9wbGF0Zm9ybS9pbWFnZS1lbmNvZGVycy9za2lhL1BO R0ltYWdlRW5jb2Rlci5jcHAgYi9XZWJDb3JlL3BsYXRmb3JtL2ltYWdlLWVuY29kZXJzL3NraWEv UE5HSW1hZ2VFbmNvZGVyLmNwcAppbmRleCAyNjVjMTRhLi43OGY3MzdlIDEwMDY0NAotLS0gYS9X ZWJDb3JlL3BsYXRmb3JtL2ltYWdlLWVuY29kZXJzL3NraWEvUE5HSW1hZ2VFbmNvZGVyLmNwcAor KysgYi9XZWJDb3JlL3BsYXRmb3JtL2ltYWdlLWVuY29kZXJzL3NraWEvUE5HSW1hZ2VFbmNvZGVy LmNwcApAQCAtODMsOCArODMsMTcgQEAgYm9vbCBQTkdJbWFnZUVuY29kZXI6OmVuY29kZShjb25z dCBTa0JpdG1hcCYgYml0bWFwLCBWZWN0b3I8dW5zaWduZWQgY2hhcj4qIG91dHAKICAgICAgICAg cmV0dXJuIGZhbHNlOwogICAgIH0KIAotICAgIHBuZ19zZXRfY29tcHJlc3Npb25fbGV2ZWwocG5n LCBaX0JFU1RfU1BFRUQpOwotICAgIHBuZ19zZXRfY29tcHJlc3Npb25fc3RyYXRlZ3kocG5nLCBa X0hVRkZNQU5fT05MWSk7CisgICAgLy8gT3B0aW1pemUgY29tcHJlc3Npb24gZm9yIHNwZWVkLgor ICAgIC8vIFRoZSBwYXJhbWV0ZXJzIGFyZSB0aGUgc2FtZSBhcyB3aGF0IGxpYnBuZyB1c2VzIGJ5 IGRlZmF1bHQgZm9yIFJHQiBhbmQgUkdCQSBpbWFnZXMsIGV4Y2VwdDoKKyAgICAvLyAtIHRoZSB6 bGliIGNvbXByZXNzaW9uIGxldmVsIGlzIDMgaW5zdGVhZCBvZiA2LCB0byBhdm9pZCB0aGUgbGF6 eSBaaXYtTGVtcGVsIG1hdGNoIHNlYXJjaGluZzsKKyAgICAvLyAtIHRoZSBkZWx0YSBmaWx0ZXIg aXMgMSAoInN1YiIpIGluc3RlYWQgb2YgNSAoImFsbCIpLCB0byByZWR1Y2UgdGhlIGZpbHRlciBj b21wdXRhdGlvbnMuCisgICAgLy8gVGhlIHpsaWIgbWVtb3J5IGxldmVsICg4KSBhbmQgc3RyYXRl Z3kgKFpfRklMVEVSRUQpIHdpbGwgYmUgc2V0IGluc2lkZSBsaWJwbmcuCisgICAgLy8KKyAgICAv LyBBdm9pZCB0aGUgemxpYiBzdHJhdGVnaWVzIFpfSFVGRk1BTl9PTkxZIG9yIFpfUkxFLgorICAg IC8vIEFsdGhvdWdoIHRoZXkgYXJlIHRoZSBmYXN0ZXN0IGZvciBwb29ybHktY29tcHJlc3NpYmxl IGltYWdlcyAoZS5nLiBwaG90b2dyYXBocyksCisgICAgLy8gdGhleSBhcmUgdmVyeSBzbG93IGZv ciBoaWdobHktY29tcHJlc3NpYmxlIGltYWdlcyAoZS5nLiB0ZXh0LCBkcmF3aW5ncyBvciBidXNp bmVzcyBncmFwaGljcykuCisgICAgcG5nX3NldF9jb21wcmVzc2lvbl9sZXZlbChwbmcsIDMpOwor ICAgIHBuZ19zZXRfZmlsdGVyKHBuZywgUE5HX0ZJTFRFUl9UWVBFX0JBU0UsIFBOR19GSUxURVJf U1VCKTsKIAogICAgIHBuZ19zZXRfd3JpdGVfZm4ocG5nLCBvdXRwdXQsIHdyaXRlT3V0cHV0LCAw KTsKICAgICBwbmdfc2V0X0lIRFIocG5nLCBpbmZvLCBpbWFnZVNpemUud2lkdGgoKSwgaW1hZ2VT aXplLmhlaWdodCgpLAo=