tree cfe7f409aa3b26d02ddfeb2b79322938337b7ab4
parent 818b583387a5288cb2778031655a5e764e5ad124
author Alkis Evlogimenos <alkis@google.com> 1485504636 +0100
committer Alkis Evlogimenos <alkis@google.com> 1485504636 +0100

Improve zippy decompression speed.

The CL contains the following optimizations:

1) rewrite IncrementalCopy routine: single routine that splits the code into sections based on typical probabilities observed across a variety of inputs and helps reduce branch mispredictions both for FDO and non-FDO builds. IncrementalCopy is an adaptive routine that selects the best strategy based on input.
2) introduce UnalignedCopy128 that copies 128 bits per cycle using SSE2.
3) add branch hint for the main decoding loop. The non-literal case is taken more often in benchmarks. I expect this to be a noop in production with FDO. Note that this became apparent after step 1 above.
4) use the new IncrementalCopy in ZippyScatteredWriter.

I test two archs: x86_haswell and ppc_power8.

For x86_haswell I use FDO. For ppc_power8 I do not use FDO.

x86_haswell + FDO

name                   old speed      new speed      delta
BM_UCord/0             1.97GB/s ± 1%  3.19GB/s ± 1%  +62.08%  (p=0.000 n=19+18)
BM_UCord/1             1.28GB/s ± 1%  1.51GB/s ± 1%  +18.14%  (p=0.000 n=19+18)
BM_UCord/2             15.6GB/s ± 9%  15.5GB/s ± 7%     ~     (p=0.620 n=20+20)
BM_UCord/3              811MB/s ± 1%   808MB/s ± 1%   -0.38%  (p=0.009 n=17+18)
BM_UCord/4             12.4GB/s ± 4%  12.7GB/s ± 8%   +2.70%  (p=0.002 n=17+20)
BM_UCord/5             1.77GB/s ± 0%  2.33GB/s ± 1%  +31.37%  (p=0.000 n=18+18)
BM_UCord/6              900MB/s ± 1%  1006MB/s ± 1%  +11.71%  (p=0.000 n=18+17)
BM_UCord/7              858MB/s ± 1%   938MB/s ± 2%   +9.36%  (p=0.000 n=19+16)
BM_UCord/8              921MB/s ± 1%   985MB/s ±21%   +6.94%  (p=0.028 n=19+20)
BM_UCord/9              824MB/s ± 1%   800MB/s ±20%     ~     (p=0.113 n=19+20)
BM_UCord/10            2.60GB/s ± 1%  3.67GB/s ±21%  +41.31%  (p=0.000 n=19+20)
BM_UCord/11            1.07GB/s ± 1%  1.21GB/s ± 1%  +13.17%  (p=0.000 n=16+16)
BM_UCord/12            1.84GB/s ± 8%  2.18GB/s ± 1%  +18.44%  (p=0.000 n=16+19)
BM_UCord/13            1.83GB/s ±18%  1.89GB/s ± 1%   +3.14%  (p=0.000 n=17+19)
BM_UCord/14            1.96GB/s ± 2%  1.97GB/s ± 1%   +0.55%  (p=0.000 n=16+17)
BM_UCord/15            1.30GB/s ±20%  1.43GB/s ± 1%   +9.85%  (p=0.000 n=20+20)
BM_UCord/16             658MB/s ±20%   705MB/s ± 1%   +7.22%  (p=0.000 n=20+19)
BM_UCord/17            1.96GB/s ± 2%  2.15GB/s ± 1%   +9.73%  (p=0.000 n=16+19)
BM_UCord/18             555MB/s ± 1%   833MB/s ± 1%  +50.11%  (p=0.000 n=18+19)
BM_UCord/19            1.57GB/s ± 1%  1.75GB/s ± 1%  +11.34%  (p=0.000 n=20+20)
BM_UCord/20            1.72GB/s ± 2%  1.70GB/s ± 2%   -1.01%  (p=0.001 n=20+20)
BM_UCordStringSink/0   2.88GB/s ± 1%  3.15GB/s ± 1%   +9.56%  (p=0.000 n=17+20)
BM_UCordStringSink/1   1.50GB/s ± 1%  1.52GB/s ± 1%   +1.96%  (p=0.000 n=19+20)
BM_UCordStringSink/2   14.5GB/s ±10%  14.6GB/s ±10%     ~     (p=0.542 n=20+20)
BM_UCordStringSink/3   1.06GB/s ± 1%  1.08GB/s ± 1%   +1.77%  (p=0.000 n=18+20)
BM_UCordStringSink/4   12.6GB/s ± 7%  13.2GB/s ± 4%   +4.63%  (p=0.000 n=20+20)
BM_UCordStringSink/5   2.29GB/s ± 1%  2.36GB/s ± 1%   +3.05%  (p=0.000 n=19+20)
BM_UCordStringSink/6   1.01GB/s ± 2%  1.01GB/s ± 0%     ~     (p=0.055 n=20+18)
BM_UCordStringSink/7    945MB/s ± 1%   939MB/s ± 1%   -0.60%  (p=0.000 n=19+20)
BM_UCordStringSink/8   1.06GB/s ± 1%  1.07GB/s ± 1%   +0.62%  (p=0.000 n=18+20)
BM_UCordStringSink/9    866MB/s ± 1%   864MB/s ± 1%     ~     (p=0.107 n=19+20)
BM_UCordStringSink/10  3.64GB/s ± 2%  3.98GB/s ± 1%   +9.32%  (p=0.000 n=19+20)
BM_UCordStringSink/11  1.22GB/s ± 1%  1.22GB/s ± 1%   +0.61%  (p=0.001 n=19+20)
BM_UCordStringSink/12  2.23GB/s ± 1%  2.23GB/s ± 1%     ~     (p=0.692 n=19+20)
BM_UCordStringSink/13  1.96GB/s ± 1%  1.94GB/s ± 1%   -0.82%  (p=0.000 n=17+18)
BM_UCordStringSink/14  2.09GB/s ± 2%  2.08GB/s ± 1%     ~     (p=0.147 n=20+18)
BM_UCordStringSink/15  1.47GB/s ± 1%  1.45GB/s ± 1%   -0.88%  (p=0.000 n=20+19)
BM_UCordStringSink/16   908MB/s ± 1%   917MB/s ± 1%   +0.97%  (p=0.000 n=19+19)
BM_UCordStringSink/17  2.11GB/s ± 1%  2.20GB/s ± 1%   +4.35%  (p=0.000 n=18+20)
BM_UCordStringSink/18   804MB/s ± 2%  1106MB/s ± 1%  +37.52%  (p=0.000 n=20+20)
BM_UCordStringSink/19  1.67GB/s ± 1%  1.72GB/s ± 0%   +2.81%  (p=0.000 n=18+20)
BM_UCordStringSink/20  1.77GB/s ± 3%  1.77GB/s ± 3%     ~     (p=0.815 n=20+20)

ppc_power8

name                   old speed      new speed      delta
BM_UCord/0              918MB/s ± 6%  1262MB/s ± 0%   +37.56%  (p=0.000 n=17+16)
BM_UCord/1              671MB/s ±13%   879MB/s ± 2%   +30.99%  (p=0.000 n=18+16)
BM_UCord/2             12.6GB/s ± 8%  12.6GB/s ± 5%      ~     (p=0.452 n=17+19)
BM_UCord/3              285MB/s ±10%   284MB/s ± 4%    -0.50%  (p=0.021 n=19+17)
BM_UCord/4             5.21GB/s ±12%  6.59GB/s ± 1%   +26.37%  (p=0.000 n=17+16)
BM_UCord/5              913MB/s ± 4%  1253MB/s ± 1%   +37.27%  (p=0.000 n=16+17)
BM_UCord/6              461MB/s ±13%   547MB/s ± 1%   +18.67%  (p=0.000 n=18+16)
BM_UCord/7              455MB/s ± 2%   524MB/s ± 3%   +15.28%  (p=0.000 n=16+18)
BM_UCord/8              489MB/s ± 2%   584MB/s ± 2%   +19.47%  (p=0.000 n=17+17)
BM_UCord/9              410MB/s ±33%   490MB/s ± 1%   +19.64%  (p=0.000 n=17+18)
BM_UCord/10            1.10GB/s ± 3%  1.55GB/s ± 2%   +41.21%  (p=0.000 n=16+16)
BM_UCord/11             494MB/s ± 1%   558MB/s ± 1%   +12.92%  (p=0.000 n=17+18)
BM_UCord/12             608MB/s ± 3%   793MB/s ± 1%   +30.45%  (p=0.000 n=17+16)
BM_UCord/13             545MB/s ±18%   721MB/s ± 2%   +32.22%  (p=0.000 n=19+17)
BM_UCord/14             594MB/s ± 4%   748MB/s ± 3%   +25.99%  (p=0.000 n=17+17)
BM_UCord/15             628MB/s ± 1%   822MB/s ± 3%   +30.94%  (p=0.000 n=18+16)
BM_UCord/16             277MB/s ± 2%   280MB/s ±15%    +0.86%  (p=0.001 n=17+17)
BM_UCord/17             864MB/s ± 1%  1001MB/s ± 3%   +15.96%  (p=0.000 n=17+17)
BM_UCord/18             121MB/s ± 2%   284MB/s ± 4%  +134.08%  (p=0.000 n=17+18)
BM_UCord/19             594MB/s ± 0%   713MB/s ± 2%   +19.93%  (p=0.000 n=16+17)
BM_UCord/20             553MB/s ±10%   662MB/s ± 5%   +19.74%  (p=0.000 n=16+18)
BM_UCordStringSink/0   1.37GB/s ± 4%  1.48GB/s ± 2%    +8.51%  (p=0.000 n=16+16)
BM_UCordStringSink/1    969MB/s ± 1%   990MB/s ± 1%    +2.16%  (p=0.000 n=16+18)
BM_UCordStringSink/2   13.1GB/s ±11%  13.0GB/s ±14%      ~     (p=0.858 n=17+18)
BM_UCordStringSink/3    411MB/s ± 1%   415MB/s ± 1%    +0.93%  (p=0.000 n=16+17)
BM_UCordStringSink/4   6.81GB/s ± 8%  7.29GB/s ± 5%    +7.12%  (p=0.000 n=16+19)
BM_UCordStringSink/5   1.35GB/s ± 5%  1.45GB/s ±13%    +8.00%  (p=0.000 n=16+17)
BM_UCordStringSink/6    653MB/s ± 8%   653MB/s ± 3%    -0.12%  (p=0.007 n=17+19)
BM_UCordStringSink/7    618MB/s ±13%   597MB/s ±18%    -3.45%  (p=0.001 n=18+18)
BM_UCordStringSink/8    702MB/s ± 5%   702MB/s ± 1%    -0.10%  (p=0.012 n=17+16)
BM_UCordStringSink/9    590MB/s ± 2%   564MB/s ±13%    -4.46%  (p=0.000 n=16+17)
BM_UCordStringSink/10  1.63GB/s ± 2%  1.76GB/s ± 4%    +8.28%  (p=0.000 n=17+16)
BM_UCordStringSink/11   630MB/s ±14%   684MB/s ±15%    +8.51%  (p=0.000 n=19+17)
BM_UCordStringSink/12   858MB/s ±12%   903MB/s ± 9%    +5.17%  (p=0.000 n=19+17)
BM_UCordStringSink/13   806MB/s ±22%   879MB/s ± 1%    +8.98%  (p=0.000 n=19+19)
BM_UCordStringSink/14   854MB/s ±13%   901MB/s ± 5%    +5.60%  (p=0.000 n=19+17)
BM_UCordStringSink/15   930MB/s ± 2%   964MB/s ± 3%    +3.59%  (p=0.000 n=16+16)
BM_UCordStringSink/16   363MB/s ±10%   356MB/s ± 6%      ~     (p=0.050 n=20+19)
BM_UCordStringSink/17   976MB/s ±12%  1078MB/s ± 1%   +10.52%  (p=0.000 n=20+17)
BM_UCordStringSink/18   227MB/s ± 1%   355MB/s ± 3%   +56.45%  (p=0.000 n=16+17)
BM_UCordStringSink/19   751MB/s ± 4%   808MB/s ± 4%    +7.70%  (p=0.000 n=18+17)
BM_UCordStringSink/20   761MB/s ± 8%   786MB/s ± 4%    +3.23%  (p=0.000 n=18+17)