Integrate SIMD optimisations for zlib

Integrate SIMD optimisations for zlib

These optimisations have been published on zlib mailing list and at
https://github.com/jtkukunas/zlib/

This change merges the following optimisation patches:
- "For x86, add CPUID check."
- "Adds SSE2 optimized hash shifting to fill_window."
- "add SSE4.2 optimized hash function"
- "add PCLMULQDQ optimized CRC folding"

From Jim Kukunas <james.t.kukunas@linux.intel.com>; and adapts them to the
current zlib version in Chromium.

The optimisations are enabled at runtime if all the necessary CPU features are
present. As the optimisations require extra cflags to enable the compiler to
use the instructions the optimisations are held in their own static library
with a stub implementation to allow linking on other platforms.

TEST=net_unittests(GZipUnitTest) passes, Chrome functions and performance
improvement seen on RoboHornet benchmark on Linux Desktop
BUG=401517
Committed: https://crrev.com/e045ec106de29562ae94eafccde49a7b73848471
Cr-Commit-Position: refs/heads/master@{#300866}

[robert.bradford, 2014-09-12 15:17:44]

robert.bradford@intel.com changed reviewers:
+ agl@chromium.org

[robert.bradford, 2014-09-12 15:17:45]

Hi Adam,

As we discussed by email here is a patch that integrates SIMD optimisations for
zlib deflate().

I believe that the only remaining test failures are these in net_unittests:

SpdyFramerTests/SpdyFramerTest.CreateHeadersCompressed/0
SpdyFramerTests/SpdyFramerTest.CreateHeadersCompressed/1
SpdyFramerTests/SpdyFramerTest.CreateSynReplyCompressed/1
SpdyFramerTests/SpdyFramerTest.CreateSynReplyCompressed/0
SpdyFramerTests/SpdyFramerTest.CreateSynStreamCompressed/0
SpdyFramerTests/SpdyFramerTest.CreateSynStreamCompressed/1

Where the generated SPDY frame gets compared to some reference data (hex
blocks). Do you have any idea how I could validate that the compressed header is
still correct and also how I could conditionally use different reference data?

[agl, 2014-09-12 16:41:11]

(Please note: currently on vacation. It'll probably be Tuesday before
I can get to this.)

To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

[agl, 2014-09-23 21:41:40]

There is a huge amount of #ifdef noise. It would be far better for the runtime
detection of CPU features to drop those code paths on unsupported chips and for
a dummy .c file to include no-op functions for the linker. Then most of the
#ifdefs can be dropped.

The runtime feature detection is racy. Sadly, you can't access LazyInstance from
zlib. Elsewhere we have added functions for Chromium-proper to set the CPU
features at init time, but it's tough to know when zlib will be called. If
you're Linux-only already then it might be best to use pthread_once directly.

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/BUILD.gn
File third_party/zlib/BUILD.gn (right):

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/BUILD.g...
third_party/zlib/BUILD.gn:54: cflags = ["-msse2", "-msse4.2", "-mpclmul"]
These compiler flags allow the compiler to use the given instructions anywhere
in the code, which isn't viable because we don't know if we'll have them at
runtime.

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/crc32.c
File third_party/zlib/crc32.c (right):

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/crc32.c...
third_party/zlib/crc32.c:444: #include "deflate.h"
don't #include in the middle of the file if it can be avoided.

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/crc32.c...
third_party/zlib/crc32.c:484: 
no blank line at end of file.

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/crc_fol...
File third_party/zlib/crc_folding.c (right):

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/crc_fol...
third_party/zlib/crc_folding.c:482: 
no blank line at end.

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/deflate.c
File third_party/zlib/deflate.c (right):

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/deflate...
third_party/zlib/deflate.c:88: ZLIB_INTERNAL int read_buf        OF((z_streamp
strm, Bytef *buf, unsigned size));
you need to adjust the spacing here so that the line doesn't wrap over 80 chars.

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/deflate.h
File third_party/zlib/deflate.h (right):

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/deflate...
third_party/zlib/deflate.h:357: #ifdef USE_SSE4_2_CRC_HASH
don't define internal macros in public headers.

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/zlib.gyp
File third_party/zlib/zlib.gyp (right):

https://codereview.chromium.org/552123005/diff/40001/third_party/zlib/zlib.gy...
third_party/zlib/zlib.gyp:58: 'cflags' : ["-msse2", "-msse4.2", "-mpclmul"],
ditto about these cflags.

[robert.bradford, 2014-09-25 17:52:20]

Hi Adam, PTAL when you're ready. I simplified the #ifdef situation massively and
also moved code around to minimise the change. 

As you pointed out I used pthread_once to avoid the raciness in the
initialisation. Also, all the simd code is in its own static library compiled
with the appropriate flags with stubs for other platforms. The real functions
are now gated by a single global boolean.

If you could trigger a try job run for me that would be appreciated.

[agl, 2014-09-26 18:32:27]

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/deflate.h
File third_party/zlib/deflate.h (right):

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/deflate...
third_party/zlib/deflate.h:110: unsigned __attribute__((aligned(16))) crc0[4 *
5];
I think that this is a place where an #ifdef really is called for. Other
platforms might not be able to parse __attribute__.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/simd_st...
File third_party/zlib/simd_stub.c (right):

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/simd_st...
third_party/zlib/simd_stub.c:1: /* simd_stub.c -- stub implementations
extra space at beginning of file.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.c
File third_party/zlib/x86.c (right):

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.c#n...
third_party/zlib/x86.c:10: 
delete line.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.c#n...
third_party/zlib/x86.c:14: #include <pthread.h>
This file is always built, but includes pthread.h. That'll fail on other
platforms I think.

It would be nice if this file were conditionally compiled and that the stub file
included the dummy x86_check_features.

Note that it shouldn't be conditionally compiled in the zlib_x86_simd library
(although the stub can be in there) because that library may use optional
instructions and this code has to work without them.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.h
File third_party/zlib/x86.h (right):

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.h#n...
third_party/zlib/x86.h:1: /* cpu.h -- check for CPU features
extra space at beginning of file.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.h#n...
third_party/zlib/x86.h:23: #endif
blank line before #endif.

[nathan ciobanu, 2014-10-02 22:46:33]

nathan.d.ciobanu@intel.com changed reviewers:
+ nathan.d.ciobanu@intel.com

[nathan ciobanu, 2014-10-02 22:46:34]

RoboHornet 2D Canvas toDataURL benchmark with this patch applied scored 22%
better than without. Tested on Falco (Haswell) and Expresso (Baytrail) boards
with ToT Chromium.

The results were as follows:
----------------------------
Expresso - before patch - 391.44 (ms)
         - patchset 5 applied - 304.34 (ms)

Falco    - before patch - 343.55 (ms)
         - patchset 5 applied - 263.56 (ms)
---------------------------

[agl, 2014-10-07 20:52:33]

(Note: this is pending updates from Intel.)

[robert.bradford, 2014-10-10 18:09:46]

On 2014/10/07 20:52:33, agl wrote:
> (Note: this is pending updates from Intel.)

I think that all your review feedback was integrated in the most recent version?
There is still an outstanding issue with the some of the SPDY compressed tests
that the author of the original zlib changes (Jim Kukunas) is helping me
resolve.

FYI, these tests are:

    SpdyFramerTests/SpdyFramerTest.CreateHeadersCompressed/0
    SpdyFramerTests/SpdyFramerTest.CreateHeadersCompressed/1
    SpdyFramerTests/SpdyFramerTest.CreateSynReplyCompressed/0
    SpdyFramerTests/SpdyFramerTest.CreateSynReplyCompressed/1
    SpdyFramerTests/SpdyFramerTest.CreateSynStreamCompressed/0
    SpdyFramerTests/SpdyFramerTest.CreateSynStreamCompressed/1

[agl, 2014-10-10 18:44:47]

On 2014/10/10 18:09:46, robert.bradford wrote:
> I think that all your review feedback was integrated in the most recent
version?
> There is still an outstanding issue with the some of the SPDY compressed tests
> that the author of the original zlib changes (Jim Kukunas) is helping me
> resolve.

There was no update to the thread since my 2014-09-26 18:32:27 UTC. Are you
saying that you believe that the current version fixes those issues?

(In general you would reply to the comments/click done and mail that out to
indicate that it's ready for rereview.)

[robert.bradford, 2014-10-15 16:14:40]

Hi Adam, PTAL at this latest version of the patch. I've tested it on Mac OS X
and Windows as well as Linux.

As the optimisation changes the compressed data I have included reference data
based on that new version (and have separately verified that the compressed data
is correct.)

Thanks.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/deflate.h
File third_party/zlib/deflate.h (right):

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/deflate...
third_party/zlib/deflate.h:110: unsigned __attribute__((aligned(16))) crc0[4 *
5];
On 2014/09/26 18:32:27, agl wrote:
> I think that this is a place where an #ifdef really is called for. Other
> platforms might not be able to parse __attribute__.

This was resolved with a zalign macro when full windows support was added.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/simd_st...
File third_party/zlib/simd_stub.c (right):

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/simd_st...
third_party/zlib/simd_stub.c:1: /* simd_stub.c -- stub implementations
On 2014/09/26 18:32:27, agl wrote:
> extra space at beginning of file.

Done.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.c
File third_party/zlib/x86.c (right):

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.c#n...
third_party/zlib/x86.c:10: 
On 2014/09/26 18:32:27, agl wrote:
> delete line.

Done.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.c#n...
third_party/zlib/x86.c:14: #include <pthread.h>
On 2014/09/26 18:32:27, agl wrote:
> This file is always built, but includes pthread.h. That'll fail on other
> platforms I think.

Works on Mac OS X, for Windows we now have a Win32 api equivalent.

> It would be nice if this file were conditionally compiled and that the stub
file
> included the dummy x86_check_features.
> 
> Note that it shouldn't be conditionally compiled in the zlib_x86_simd library
> (although the stub can be in there) because that library may use optional
> instructions and this code has to work without them.

I adopted the model you proposed here with.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.h
File third_party/zlib/x86.h (right):

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.h#n...
third_party/zlib/x86.h:1: /* cpu.h -- check for CPU features
On 2014/09/26 18:32:27, agl wrote:
> extra space at beginning of file.

Done.

https://codereview.chromium.org/552123005/diff/80001/third_party/zlib/x86.h#n...
third_party/zlib/x86.h:23: #endif
On 2014/09/26 18:32:27, agl wrote:
> blank line before #endif.

Done.

[agl, 2014-10-17 00:45:35]

really only nits remaining.

https://codereview.chromium.org/552123005/diff/140001/net/spdy/spdy_framer_te...
File net/spdy/spdy_framer_test.cc (right):

https://codereview.chromium.org/552123005/diff/140001/net/spdy/spdy_framer_te...
net/spdy/spdy_framer_test.cc:2054: #if !defined(ZLIB_X86_SIMD)
Let's not add another #define. How about memcmping the compressed data against
the two possibilities and calling CompareFrame against one of them if neither
match?

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/BUILD.gn
File third_party/zlib/BUILD.gn (right):

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/BUILD....
third_party/zlib/BUILD.gn:8: defines = [ "ZLIB_X86_SIMD" ]
ditto about not adding a #define.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/deflate.c
File third_party/zlib/deflate.c (right):

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/deflat...
third_party/zlib/deflate.c:308: s->hash_bits = memLevel + 7;
indentation. (Also, I think that omitting branches around a conditional with an
else branch is probably too much.)

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/simd_s...
File third_party/zlib/simd_stub.c (right):

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/simd_s...
third_party/zlib/simd_stub.c:12: assert(0);
other files have had 4 space indent.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/simd_s...
third_party/zlib/simd_stub.c:16: unsigned char *dst, const unsigned char *src,
long len) {
indentation.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c
File third_party/zlib/x86.c (right):

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:21: void x86_check_features(void) {
you've switched brace style and indentation here.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:34: #ifdef __i386__
I think it would be better to suffer a little duplication in order to reduce the
amount of preprocessor gunk here:

#if defined(__i386__)
__asm__ __volatile__ (
    "xchg %%ebx, %1\n\t"
    "cpuid\n\t"
    "xchg %1, %%ebx\n\t"
  : "+a" (eax), "=S" (ebx), "=c" (ecx), "=d" (edx));
#else
__asm__ __volatile__ (
    "cpuid\n\t"
  : "+a" (eax), "=b" (ebx), "=c" (ecx), "=d" (edx));
#endif

(check that I actually got that right, of course)

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:65: #endif // (_WIN32_WINNT >= 0x0600)
ditto about two spaces.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:87: #endif // (_WIN32_WINNT >= 0x0600)
nit: two spaces before "//"

Also, does VC++ accept "//" comments in .c files now? I guess the try servers
will tell us.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:88: #endif
#endif  // _MSC_VER

[robert.bradford, 2014-10-20 16:45:54]

Hi Adam, PTAL, I agreed with and implemented all your review feedback.

https://codereview.chromium.org/552123005/diff/140001/net/spdy/spdy_framer_te...
File net/spdy/spdy_framer_test.cc (right):

https://codereview.chromium.org/552123005/diff/140001/net/spdy/spdy_framer_te...
net/spdy/spdy_framer_test.cc:2054: #if !defined(ZLIB_X86_SIMD)
On 2014/10/17 00:45:34, agl wrote:
> Let's not add another #define. How about memcmping the compressed data against
> the two possibilities and calling CompareFrame against one of them if neither
> match?

Sounds good. Only needed memcmp() against one, if we don't match then can use
the existing code to fail with a comparison.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/BUILD.gn
File third_party/zlib/BUILD.gn (right):

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/BUILD....
third_party/zlib/BUILD.gn:8: defines = [ "ZLIB_X86_SIMD" ]
On 2014/10/17 00:45:34, agl wrote:
> ditto about not adding a #define.

Acknowledged.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/deflate.c
File third_party/zlib/deflate.c (right):

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/deflat...
third_party/zlib/deflate.c:308: s->hash_bits = memLevel + 7;
On 2014/10/17 00:45:34, agl wrote:
> indentation. (Also, I think that omitting branches around a conditional with
an
> else branch is probably too much.)

Urgh I agree. Fixed. I'll try and get it fixed in the "upstream" version too.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/simd_s...
File third_party/zlib/simd_stub.c (right):

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/simd_s...
third_party/zlib/simd_stub.c:12: assert(0);
On 2014/10/17 00:45:34, agl wrote:
> other files have had 4 space indent.

Done.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/simd_s...
third_party/zlib/simd_stub.c:16: unsigned char *dst, const unsigned char *src,
long len) {
On 2014/10/17 00:45:34, agl wrote:
> indentation.

Done.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c
File third_party/zlib/x86.c (right):

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:21: void x86_check_features(void) {
On 2014/10/17 00:45:35, agl wrote:
> you've switched brace style and indentation here.

Done.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:34: #ifdef __i386__
On 2014/10/17 00:45:34, agl wrote:
> I think it would be better to suffer a little duplication in order to reduce
the
> amount of preprocessor gunk here:
> 
> #if defined(__i386__)
> __asm__ __volatile__ (
>     "xchg %%ebx, %1\n\t"
>     "cpuid\n\t"
>     "xchg %1, %%ebx\n\t"
>   : "+a" (eax), "=S" (ebx), "=c" (ecx), "=d" (edx));
> #else
> __asm__ __volatile__ (
>     "cpuid\n\t"
>   : "+a" (eax), "=b" (ebx), "=c" (ecx), "=d" (edx));
> #endif
> 
> (check that I actually got that right, of course)

Done.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:65: #endif // (_WIN32_WINNT >= 0x0600)
On 2014/10/17 00:45:35, agl wrote:
> ditto about two spaces.

Done.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:87: #endif // (_WIN32_WINNT >= 0x0600)
On 2014/10/17 00:45:35, agl wrote:
> nit: two spaces before "//"
> 
> Also, does VC++ accept "//" comments in .c files now? I guess the try servers
> will tell us.

Well I did build it with the windows toolchain. But lets play it safe and switch
to C style.

https://codereview.chromium.org/552123005/diff/140001/third_party/zlib/x86.c#...
third_party/zlib/x86.c:88: #endif
On 2014/10/17 00:45:35, agl wrote:
> #endif  // _MSC_VER

Done.

[agl, 2014-10-20 17:50:35]

The CQ bit was checked by agl@chromium.org

[agl, 2014-10-20 17:50:36]

lgtm

[commit-bot: I haz the power, 2014-10-20 17:51:52]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/552123005/180001

[commit-bot: I haz the power, 2014-10-20 18:00:43]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-10-20 18:00:44]

Try jobs failed on following builders:
  android_arm64_dbg_recipe on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/android_arm64_d...)
  android_clang_dbg_recipe on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/android_clang_d...)
  ios_rel_device on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/ios_rel_device/bu...)

[robert.bradford, 2014-10-21 11:01:19]

The CQ bit was checked by robert.bradford@intel.com

[commit-bot: I haz the power, 2014-10-21 11:05:20]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/552123005/240001

[commit-bot: I haz the power, 2014-10-21 13:15:02]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-10-21 13:15:03]

Try jobs failed on following builders:
  linux_chromium_asan_rel on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[robert.bradford, 2014-10-23 10:13:11]

The CQ bit was checked by robert.bradford@intel.com

[commit-bot: I haz the power, 2014-10-23 10:13:34]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/552123005/280001

[commit-bot: I haz the power, 2014-10-23 11:11:11]

Committed patchset #14 (id:280001)

[commit-bot: I haz the power, 2014-10-23 11:11:58]

Patchset 14 (id:??) landed as
https://crrev.com/e045ec106de29562ae94eafccde49a7b73848471
Cr-Commit-Position: refs/heads/master@{#300866}

[robert.bradford, 2014-10-23 14:43:42]

A revert of this CL (patchset #14 id:280001) has been created in
https://codereview.chromium.org/671163003/ by robert.bradford@intel.com.

The reason for reverting is: Strong candidate for: multiple Linux MSan test
failures with:

SUMMARY: MemorySanitizer: use-of-uninitialized-value ??:0 ??

Including: CompressionUtilsTest.GzipCompression
.

[hans, 2014-10-23 16:11:26]

hans@chromium.org changed reviewers:
+ hans@chromium.org

[hans, 2014-10-23 16:11:27]

https://codereview.chromium.org/552123005/diff/280001/third_party/zlib/fill_w...
File third_party/zlib/fill_window_sse.c (right):

https://codereview.chromium.org/552123005/diff/280001/third_party/zlib/fill_w...
third_party/zlib/fill_window_sse.c:195: h = _mm_crc32_u32(h, val);
I think this intrinsic is available in smmintrin.h on GCC and Clang as well. Can
we just include that and avoid the inline asm above?

(The reason I noticed this is because the code failed to build on Clang on
Windows because smmintrin.h isn't included.)