Reland "Integrate SIMD optimisations for zlib"

Reland "Integrate SIMD optimisations for zlib"

This version uses a "pthread_once" implementation, using Windows
synchronisation primitives, imported from tcmalloc.

Previous CLs:
https://codereview.chromium.org/677713002/
https://codereview.chromium.org/552123005

This version of the CL also runs fine on Windows Server 2003.

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/02a95e3084f979084fa8586e1718a6e6dd4c22da
Cr-Commit-Position: refs/heads/master@{#302799}

[robert.bradford, 2014-10-29 14:52:20]

Hi Adam, third time's the charm :-) . I was able to setup a Windows Server 2003
system and reproduce the problem seen on XP. This was due to a runtime linking
problem as InitOnceExecuteOnce was only made available from Windows Vista
onwards. There was nothing in the logs as the OS pops up a little window to tell
you about the missing symbol.

The solution to this is to resolve the symbol at runtime using GetProcAddress().

[robert.bradford, 2014-10-29 15:02:38]

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

[robert.bradford, 2014-10-29 15:02:38]

Actually +agl this time, fumbled the original form.

[agl, 2014-10-30 01:25:43]

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

https://codereview.chromium.org/678423002/diff/40001/third_party/zlib/x86.c#n...
third_party/zlib/x86.c:65: #if (_WIN32_WINNT >= 0x0600)
I assume that this #if check was supposed to catch this? What's it doing if it
doesn't?

https://codereview.chromium.org/678423002/diff/40001/third_party/zlib/x86.c#n...
third_party/zlib/x86.c:69: once_func =
(INIT_ONCE_FUNC)GetProcAddress(GetModuleHandle(TEXT("kernel32.dll")),
It seems that GetProcAddress might be a really expensive function to call often.
Are you sure that this doesn't cause performance to tank?

[robert.bradford, 2014-10-30 14:31:50]

New version uploaded, PTAL when you can. Thanks.

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

https://codereview.chromium.org/678423002/diff/40001/third_party/zlib/x86.c#n...
third_party/zlib/x86.c:65: #if (_WIN32_WINNT >= 0x0600)
On 2014/10/30 01:25:43, agl wrote:
> I assume that this #if check was supposed to catch this? What's it doing if it
> doesn't?

It checked the presence in the header file, as we no longer reference the API
call from the header file. I've removed them. Thanks.

https://codereview.chromium.org/678423002/diff/40001/third_party/zlib/x86.c#n...
third_party/zlib/x86.c:69: once_func =
(INIT_ONCE_FUNC)GetProcAddress(GetModuleHandle(TEXT("kernel32.dll")),
On 2014/10/30 01:25:43, agl wrote:
> It seems that GetProcAddress might be a really expensive function to call
often.
> Are you sure that this doesn't cause performance to tank?

I've uploaded a revised version that saves the function pointer. I don't think
this is racey as the address for the symbol will always be the same.

[agl, 2014-10-31 17:08:10]

Adding "volatile" and using a CAS operation where the return value is ignored
does not make a safe operation :) Data-races are undefined behaviour I believe
so we really do want to avoid them.

Surely locks are in Windows XP? (Or whatever Windows calls them: "critical
sections" I think.) It sucks that you can't access any useful library code from
zlib, but just having the flag be behind a lock should be safe.

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

On 2014/10/31 17:08:10, agl wrote:
> Adding "volatile" and using a CAS operation where the return value is ignored
> does not make a safe operation :) Data-races are undefined behaviour I believe
> so we really do want to avoid them.

My rationale for thinking that this would be sufficient is the following:

On any physical platform the cpuid is always going to be constant so a function
that returns whether we should turn on the optimisations is always going to
return the same value.

What we definitely want to avoid is the global variable changing value for any
thread once the deflate() process has started, otherwise bad things will happen.
The first thing we do in deflate() is try and set the value:

1. If we've not initialised the value, then we've got the sentinel value (-1),
query whether to enable the optimisation and then CAS to update the global.
2. We could race with another thread that's also trying to set up the global at
the same time, and it might win so it does the exchange. It doesn't matter that
we didn't get the exchange as the cpuid would have returned the same result
anyway, updating the value to our one. The most important thing is that the
value is set to something other than the sentinel (hence the assert)
3. The global gets queried and we can use it to enable the optimisations.

I think we're in a special case here where ignoring the CAS return value is fine
as either we won or the other guy did but we're both playing for the same team
:-)

> Surely locks are in Windows XP? (Or whatever Windows calls them: "critical
> sections" I think.) It sucks that you can't access any useful library code
from
> zlib, but just having the flag be behind a lock should be safe.

Yes that's definitely possible, the CAS was my idea about optimising further,
and in fact I was hoping we could do it for Linux too. 

Wouldn't this be insufficient for actually protecting against a data race on
x86_cpu_simd_enable, only on the initialised state?

Lock(&initialised_mutex);
if (!initialised) {
   x86_simd_enable = do_cpuid();
   initialised = TRUE;
}
Unlock(&initialised_mutex);

Whereas the CAS should give a memory barrier for the data itself. Which now
worries me that pthread_once() might not guarantee that all threads have the
same view of x86_cpu_simd_enable in the current implementation.

I really appreciate you taking the time over this (long running) review.

[robert.bradford, 2014-11-03 14:58:58]

> Wouldn't this be insufficient for actually protecting against a data race on
> x86_cpu_simd_enable, only on the initialised state?
> 
> Lock(&initialised_mutex);
> if (!initialised) {
>    x86_simd_enable = do_cpuid();
>    initialised = TRUE;
> }
> Unlock(&initialised_mutex);
> 
> Whereas the CAS should give a memory barrier for the data itself. Which now
> worries me that pthread_once() might not guarantee that all threads have the
> same view of x86_cpu_simd_enable in the current implementation.

To answer my own question, obviously the mutex unlock must apply a memory
barrier, otherwise there would be no guarantee that the side effects of the
critical section was visible everywhere which is the whole point of mutex
protected critical sections. :-)

[robert.bradford, 2014-11-04 16:09:38]

Patchset #6 (id:100001) has been deleted

[robert.bradford, 2014-11-04 16:14:45]

Hi Adam, PTAL my latest patch version:

Looking into this a bit further I found a pthread_once() implementation in
tcmalloc that is build around Windows primitives that are available in XP and
later.

I imported this into x86.c and renamed it, I think this should solve the race
(and removes the need for the global itself to be volatile.)

Thank you.

[agl, 2014-11-04 23:07:45]

lgtm

[robert.bradford, 2014-11-05 14:08:56]

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

[commit-bot: I haz the power, 2014-11-05 14:09:18]

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

[commit-bot: I haz the power, 2014-11-05 14:59:43]

Committed patchset #6 (id:120001)

[commit-bot: I haz the power, 2014-11-05 15:00:19]

Patchset 6 (id:??) landed as
https://crrev.com/02a95e3084f979084fa8586e1718a6e6dd4c22da
Cr-Commit-Position: refs/heads/master@{#302799}

[dcheng, 2014-11-05 18:19:14]

On 2014/11/05 at 15:00:19, commit-bot wrote:
> Patchset 6 (id:??) landed as
https://crrev.com/02a95e3084f979084fa8586e1718a6e6dd4c22da
> Cr-Commit-Position: refs/heads/master@{#302799}

I think this is causing a layout test failure:
inspector/layers/layer-canvas-log.html

Is it expected that the zlib changes only impact Win/Linux and not Mac? I'm
guessing this might be because SIMD extensions aren't available on some of the
bots?

[recbradford, 2014-11-05 20:58:40]

On 2014/11/05 18:19:14, dcheng wrote:
> On 2014/11/05 at 15:00:19, commit-bot wrote:
> > Patchset 6 (id:??) landed as
> https://crrev.com/02a95e3084f979084fa8586e1718a6e6dd4c22da
> > Cr-Commit-Position: refs/heads/master@{#302799}
> 
> I think this is causing a layout test failure:
> inspector/layers/layer-canvas-log.html
> 
> Is it expected that the zlib changes only impact Win/Linux and not Mac? I'm
> guessing this might be because SIMD extensions aren't available on some of the
> bots?

(Using my alternative account as I can't sign into my other one right now.)

For the Macs, yes unfortunately I had to disable it in the zlib.gyp file as gyp
on Mac is not applying the cflags: http://crbug.com/420616 but would love to
enable it when that gyp issue is fixed. I was able to verify, using a gn build,
that the optimisations worked on Mac.

Looking at the failing test,
https://chromium.googlesource.com/chromium/blink/+/master/LayoutTests/inspect...
there is a base64 encoded image in there. Which with these zlib optimisations
will be different (in representation, not pixel by pixel.)

A new baseline version is needed with this different representation,
unfortunately that would then be incorrect on Mac runs. Would suppressing this
for now, and then rebaselining once we can run it on the Mac be a possible
solution?

[Noel Gordon, 2014-11-06 03:05:55]

On 2014/11/05 20:58:40, recbradford wrote:
> On 2014/11/05 18:19:14, dcheng wrote:
> > On 2014/11/05 at 15:00:19, commit-bot wrote:
> > > Patchset 6 (id:??) landed as
> > https://crrev.com/02a95e3084f979084fa8586e1718a6e6dd4c22da
> > > Cr-Commit-Position: refs/heads/master@{#302799}
> > 
> > I think this is causing a layout test failure:
> > inspector/layers/layer-canvas-log.html
> > 
> > Is it expected that the zlib changes only impact Win/Linux and not Mac? I'm
> > guessing this might be because SIMD extensions aren't available on some of
the
> > bots?
> 
> (Using my alternative account as I can't sign into my other one right now.)
> 
> For the Macs, yes unfortunately I had to disable it in the zlib.gyp file as
gyp
> on Mac is not applying the cflags: http://crbug.com/420616 but would love to
> enable it when that gyp issue is fixed. I was able to verify, using a gn
build,
> that the optimisations worked on Mac.

We have other libraries that use SSE on mac (libyuv, libjpeg_turbo, qcms) on mac
without cflags.  Perhaps look at their gyp files.

> Looking at the failing test,
>
https://chromium.googlesource.com/chromium/blink/+/master/LayoutTests/inspect...
> there is a base64 encoded image in there. Which with these zlib optimisations
> will be different (in representation, not pixel by pixel.)

Are we sure the result is the same (pixel-by-pixel) when the dataURL is decoded?

[Nico, 2014-11-18 19:16:44]

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

[Nico, 2014-11-18 19:16:45]

Why do we want these changes? Neither the CL description nor the bug really say
(except a vague "it's recommended" and "robohornet improvements on linux
desktop" without actual numbers), and they are cost maintenance: There were two
changes trying to get this building in the win/gn build (and it's still not
right), and it currently doesn't work right on our clang/win bot either.

All of that is fairly easy to fix, but I don't think we should add assembly /
intrinsic reimplementations without there being a really strong reason for doing
so.

[robert.bradford, 2014-11-20 12:37:47]

On 2014/11/18 19:16:45, Nico wrote:
> Why do we want these changes? Neither the CL description nor the bug really
say
> (except a vague "it's recommended" and "robohornet improvements on linux
> desktop" without actual numbers), and they are cost maintenance: There were
two
> changes trying to get this building in the win/gn build (and it's still not
> right), and it currently doesn't work right on our clang/win bot either.
> 
> All of that is fairly easy to fix, but I don't think we should add assembly /
> intrinsic reimplementations without there being a really strong reason for
doing
> so.

Hi Nico, i'm sorry for the inconvenience caused with the Windows builds. I
didn't even realise that clang on Windows was a possibility before your original
feedback on the first version of the patch.

I've asked our performance team to provide some more metrics showing the value
of these optimisations. These compression optimisations are also the ground work
for some patches under development to provide SIMD acceleration for
decompression which will have a wide impact.