Vectorised Byte Operations

原文はこちら。
The original entry was written by Richard Startin.
https://richardstartin.github.io/posts/vectorised-byte-operations

JDK13 以降、byte[]での多くの演算がC2でベクトル化できるようになりました。これらの改善は、IntelがC2のAVX+命令の使用を改善するために行った長年の貢献に由来しており、x86で実行される多くのJavaプログラムを高速化する可能性があります。これが理想的な状況でどれだけ大きな影響を与えることができるかを調べるだけでなく、Unsafeを使用する古い、きちんと理解するのが難しい代替案と単純なルーチンを比較したくて仕方ありません。

Enhance auto vectorization for x86
https://bugs.openjdk.java.net/browse/JDK-8222074

このエントリでは、論理右または符号なし右シフト(>>>)と符号を保持する算術右シフト(>>)に焦点を当てます。これらの演算は典型的なJavaプログラムでは必ずしもあまり一般的とはいえませんが、最初の演算は圧縮アルゴリズムで、2番目の演算は低精度の符号付き演算で見られる可能性があります。これらの演算が文字列処理に有用であることは想像に難くありませんし、符号なしシフトはvector bit count algorithmで byte (octet, 8 bits) から nibble (4bit) を抽出するために使用されます。

これらのベンチマークをノートPCで実行しました。マシンはCPUはmobile SkyIake、AVX2を搭載しており、OSはUbuntu 18です。これは必ずしもベンチマーク実行に当たって最適な環境とはいえませんが、バージョン間の大まかな違いを把握する上では十分ですし、診断プロファイラ(diagnostic profiler)へのアクセスもできます。今回はJDK 11とJDK 13早期アクセスビルドで比較しました。

まずは論理右シフトからです。これは符号ビットも含め全てのビットをゼロにシフトするというものです。

  @Benchmark
  public void shiftLogical(ByteShiftState state, Blackhole bh) {
    byte[] data = state.data;
    byte[] target = state.target;
    int shift = state.shift;
    shiftLogical(data, target, shift);
    bh.consume(target);
  }

  void shiftLogical(byte[] data, byte[] target, int shift) {
    for (int i = 0; i < data.length; ++i) {
      target[i] = (byte)((data[i] & 0xFF) >>> shift);
    }
  }

ブラックホール(benchmark smell)がイテレーション内で生成される個別の値を消費しない理由に疑問を持つ人もいるかと思いますが、それはベンチマークのポイントがどのループで最適化が発生するかを見るためだからです。

What’s Wrong With My Benchmark Results? Studying Bad Practices in JMH Benchmarks
https://www.researchgate.net/publication/333825812_What’s_Wrong_With_My_Benchmark_Results_Studying_Bad_Practices_in_JMH_Benchmarks

マスクは何をしているのでしょうか。マスクがない場合、この演算には全く意味がないのです。仕様上、シフト前にbyteはint(符号拡張付き)にキャストされ、シフト後にbyteに戻されるため、その結果負になる可能性があるからです。Javaでは常にこのように動作してきましたが、これが常に価値があるのか、という下位互換性についての疑問を投げかけています。既存のコードにマスクされていないシフトが含まれている場合、それは本当に作者の意図したものなのでしょうか。いずれにしても、Intel がこのような無茶苦茶な演算をベクトル化して時間を無駄にしなかったと願っていますので、JDK13 でベンチマークのスループットが大幅に向上したマスク付きシフトだけを見ることにします。

以下は、shiftLogical のスループットを JDK11 および JDK13 と比較した棒グラフ(生データつき)です。サイズの選択は、ベクトル幅の倍数を選択することで、ポストループの効果を捕捉することを目的としています(数値が大きいほどよいです)。

Unsigned Shift Right JDK11 vs JDK13
JDKBenchmarkModeThreadsSamplesScoreScore Error (99.9%)UnitParam: shiftParam: size
13shiftLogicalthrpt1518.1912790.281667ops/us0250
13shiftLogicalthrpt1520.2742410.482750ops/us0256
13shiftLogicalthrpt1523.6666732.447062ops/us0262
13shiftLogicalthrpt159.3158000.289419ops/us01018
13shiftLogicalthrpt159.7064620.275737ops/us01024
13shiftLogicalthrpt1510.3672620.183024ops/us01030
13shiftLogicalthrpt1518.3011141.095593ops/us1250
13shiftLogicalthrpt1525.8236250.463037ops/us1256
13shiftLogicalthrpt1523.4560420.533061ops/us1262
13shiftLogicalthrpt159.3115970.117147ops/us11018
13shiftLogicalthrpt1511.1063541.126994ops/us11024
13shiftLogicalthrpt1510.2500770.242414ops/us11030
13shiftLogicalthrpt1518.6098861.933992ops/us7250
13shiftLogicalthrpt1525.2422000.667229ops/us7256
13shiftLogicalthrpt1523.1114500.521140ops/us7262
13shiftLogicalthrpt159.2707540.563155ops/us71018
13shiftLogicalthrpt159.8913470.052645ops/us71024
13shiftLogicalthrpt1510.3905280.225605ops/us71030
13shiftLogicalthrpt1518.4913620.388118ops/us8250
13shiftLogicalthrpt1525.3195090.176510ops/us8256
13shiftLogicalthrpt1522.9324180.470137ops/us8262
13shiftLogicalthrpt159.3632120.024503ops/us81018
13shiftLogicalthrpt1510.8798060.108640ops/us81024
13shiftLogicalthrpt1510.5526290.497255ops/us81030
11shiftLogicalthrpt157.5197000.107267ops/us0250
11shiftLogicalthrpt157.4645310.308817ops/us0256
11shiftLogicalthrpt157.4739770.122781ops/us0262
11shiftLogicalthrpt151.9633510.061825ops/us01018
11shiftLogicalthrpt151.9658830.139291ops/us01024
11shiftLogicalthrpt152.0087360.188627ops/us01030
11shiftLogicalthrpt157.5251090.047179ops/us1250
11shiftLogicalthrpt157.3417250.183424ops/us1256
11shiftLogicalthrpt157.5063340.127763ops/us1262
11shiftLogicalthrpt151.9879590.009052ops/us11018
11shiftLogicalthrpt151.9660360.095510ops/us11024
11shiftLogicalthrpt151.9498980.074998ops/us11030
11shiftLogicalthrpt157.5714520.133089ops/us7250
11shiftLogicalthrpt157.4221290.542094ops/us7256
11shiftLogicalthrpt157.4296090.154287ops/us7262
11shiftLogicalthrpt151.9654600.076335ops/us71018
11shiftLogicalthrpt151.9698990.096004ops/us71024
11shiftLogicalthrpt151.9830310.016293ops/us71030
11shiftLogicalthrpt157.5319410.139384ops/us8250
11shiftLogicalthrpt157.3675930.215386ops/us8256
11shiftLogicalthrpt157.4565740.160798ops/us8262
11shiftLogicalthrpt152.0278010.066184ops/us81018
11shiftLogicalthrpt152.0965560.005543ops/us81024
11shiftLogicalthrpt151.9484050.007283ops/us81030

マイナーJDKリリースで大幅に改善されています。おそらくは1年ごとに2バージョンのJDKをリリースすることが結局のところよいのでしょうか。以下はperfasmのJDK13ベクトル化ループ部分です(vpsrlw を参照)。

  0.29%           ││││        │   0x00007f0090365bf3:   vmovdqu 0x10(%rdi,%r9,1),%ymm2
  0.86%    0.58%  ││││        │   0x00007f0090365bfa:   vextracti128 $0x1,%ymm2,%xmm4
  0.57%    0.29%  ││││        │   0x00007f0090365c00:   vpmovsxbw %xmm4,%ymm4
  0.19%    1.16%  ││││        │   0x00007f0090365c05:   vpmovsxbw %xmm2,%ymm5
  0.19%    0.19%  ││││        │   0x00007f0090365c0a:   vpsrlw %xmm3,%ymm4,%ymm4
  2.30%    2.42%  ││││        │   0x00007f0090365c0e:   vpsrlw %xmm3,%ymm5,%ymm5
  1.25%    1.16%  ││││        │   0x00007f0090365c12:   vpand  -0x7ab00da(%rip),%ymm4,%ymm4        # Stub::vector_short_to_byte_mask
                  ││││        │                                                             ;   {external_word}
  1.15%    1.55%  ││││        │   0x00007f0090365c1a:   vpand  -0x7ab00e2(%rip),%ymm5,%ymm5        # Stub::vector_short_to_byte_mask
                  ││││        │                                                             ;   {external_word}
  0.96%    0.87%  ││││        │   0x00007f0090365c22:   vpackuswb %ymm4,%ymm5,%ymm5
  1.34%    0.58%  ││││        │   0x00007f0090365c26:   vpermq $0xd8,%ymm5,%ymm5
  3.35%    4.95%  ││││        │   0x00007f0090365c2c:   vmovdqu %ymm5,0x10(%r11,%r9,1)
  2.20%    1.75%  ││││        │   0x00007f0090365c33:   vmovdqu 0x30(%rdi,%r9,1),%ymm2
           0.10%  ││││        │   0x00007f0090365c3a:   vextracti128 $0x1,%ymm2,%xmm4
  0.96%    0.58%  ││││        │   0x00007f0090365c40:   vpmovsxbw %xmm4,%ymm4
                  ││││        │   0x00007f0090365c45:   vpmovsxbw %xmm2,%ymm5
  1.53%    1.55%  ││││        │   0x00007f0090365c4a:   vpsrlw %xmm3,%ymm4,%ymm4
  1.05%    1.16%  ││││        │   0x00007f0090365c4e:   vpsrlw %xmm3,%ymm5,%ymm5
  1.72%    1.45%  ││││        │   0x00007f0090365c52:   vpand  -0x7ab011a(%rip),%ymm4,%ymm4        # Stub::vector_short_to_byte_mask
                  ││││        │                                                             ;   {external_word}
           0.10%  ││││        │   0x00007f0090365c5a:   vpand  -0x7ab0122(%rip),%ymm5,%ymm5        # Stub::vector_short_to_byte_mask
                  ││││        │                                                             ;   {external_word}
  1.05%    0.78%  ││││        │   0x00007f0090365c62:   vpackuswb %ymm4,%ymm5,%ymm5
           0.10%  ││││        │   0x00007f0090365c66:   vpermq $0xd8,%ymm5,%ymm5
  4.02%    3.69%  ││││        │   0x00007f0090365c6c:   vmovdqu %ymm5,0x30(%r11,%r9,1) 

以下は、ずっと低速なJDK 11のスカラーループです(shrを参照)。

  1.66%           ││   0x00007f30c4758943: movzbl 0x10(%r8,%rbp,1),%r11d 
  0.09%    0.09%  ││   0x00007f30c4758949: shr    %cl,%r11d
  1.29%    2.34%  ││   0x00007f30c475894c: mov    %r11b,0x10(%rdi,%rbp,1) 
  0.18%           ││   0x00007f30c4758951: movzbl 0x11(%r8,%rbp,1),%r11d  
           0.09%  ││   0x00007f30c4758957: shr    %cl,%r11d
  2.68%           ││   0x00007f30c475895a: mov    %r11b,0x11(%rdi,%rbp,1)

以前このようなことをする必要があって、妥当な効率性を必要とした場合、Unsafeを使用するSIMD Within A Register (SWAR) アプローチを採用したことがあるかもしれません。C言語のような低レベルの言語では、キャスティングによって異なる幅の整数型間で曖昧にすることが可能で、その際パフォーマンスのオーバーヘッドはありません。Javaでは、8個の要素を持つbyte配列からlongを組み立てるのは非常にコストがかかりますが、Unsafeを使えばC言語のプログラマーと同じようなアプローチが可能です。以下のコードは、shiftLogicalと同じことを実現していますが、一度に8バイトに対して作用しています。最初にシフトを適用し、続いてマスクを適用してbyteの各々の上位端へのビットの流れを取り除きます。(0と8を含む)9シフトしかできないため、マスクをルックアップテーブルに書き込むことができますが、その際は16進ではなくバイナリでルックアップテーブルに書き込まれます。

  public static final long[] MASKS = new long[]{
          0b1111111111111111111111111111111111111111111111111111111111111111L,
          0b0111111101111111011111110111111101111111011111110111111101111111L,
          0b0011111100111111001111110011111100111111001111110011111100111111L,
          0b0001111100011111000111110001111100011111000111110001111100011111L,
          0b0000111100001111000011110000111100001111000011110000111100001111L,
          0b0000011100000111000001110000011100000111000001110000011100000111L,
          0b0000001100000011000000110000001100000011000000110000001100000011L,
          0b0000000100000001000000010000000100000001000000010000000100000001L,
          0b0000000000000000000000000000000000000000000000000000000000000000L
  };

以下はUnsafeを使ったSWARの実装です。

  @Benchmark
  public void shiftLogicalUnsafe(ByteShiftState state, Blackhole bh) {
    byte[] data = state.data;
    byte[] target = state.target;
    int shift = state.shift;
    shiftLogicalUnsafe(data, target, shift);
    bh.consume(target);
  }

  void shiftLogicalUnsafe(byte[] data, byte[] target, int shift) {
    long mask = MASKS[shift];
    int i = 0;
    for (; i + 7 < data.length; i += 8) {
      long word = UNSAFE.getLong(data, BYTE_ARRAY_OFFSET + i);
      word >>>= shift;
      word &= mask;
      UNSAFE.putLong(target, BYTE_ARRAY_OFFSET + i, word);
    }
    for (; i < data.length; ++i) {
      target[i] = (byte)((data[i] & 0xFF) >>> shift);
    }
  }

この実装はほとんど労力をしないため、JDK11のシンプルなアプローチよりもはるかに優れています。JDK13では、単純なコードは高度に最適化されているため、ギャップは事実上ゼロになっています。そのため、より長い配列で一層高速になりますが、このベンチマークでは、短い配列でもなおまさっています。

以下のグラフはベンチマーク結果を示しています。ここで赤色の系列は各JDKバージョンと配列サイズに対して測定されたスループット(高いほどよい)であり、青色の系列は各ケースでUnsafeを使うことによって得られるアドバンテージです。素データは下に記載してあります。

Unsigned Right Shift Chart
JDKBenchmarkModeThreadsSamplesScoreScore Error (99.9%)UnitParam: shiftParam: size
13shiftLogicalthrpt1518.1912790.281667ops/us0250
13shiftLogicalthrpt1520.2742410.482750ops/us0256
13shiftLogicalthrpt1523.6666732.447062ops/us0262
13shiftLogicalthrpt159.3158000.289419ops/us01018
13shiftLogicalthrpt159.7064620.275737ops/us01024
13shiftLogicalthrpt1510.3672620.183024ops/us01030
13shiftLogicalthrpt1518.3011141.095593ops/us1250
13shiftLogicalthrpt1525.8236250.463037ops/us1256
13shiftLogicalthrpt1523.4560420.533061ops/us1262
13shiftLogicalthrpt159.3115970.117147ops/us11018
13shiftLogicalthrpt1511.1063541.126994ops/us11024
13shiftLogicalthrpt1510.2500770.242414ops/us11030
13shiftLogicalthrpt1518.6098861.933992ops/us7250
13shiftLogicalthrpt1525.2422000.667229ops/us7256
13shiftLogicalthrpt1523.1114500.521140ops/us7262
13shiftLogicalthrpt159.2707540.563155ops/us71018
13shiftLogicalthrpt159.8913470.052645ops/us71024
13shiftLogicalthrpt1510.3905280.225605ops/us71030
13shiftLogicalthrpt1518.4913620.388118ops/us8250
13shiftLogicalthrpt1525.3195090.176510ops/us8256
13shiftLogicalthrpt1522.9324180.470137ops/us8262
13shiftLogicalthrpt159.3632120.024503ops/us81018
13shiftLogicalthrpt1510.8798060.108640ops/us81024
13shiftLogicalthrpt1510.5526290.497255ops/us81030
13shiftLogicalUnsafethrpt1522.0772461.081037ops/us0250
13shiftLogicalUnsafethrpt1523.8928960.443875ops/us0256
13shiftLogicalUnsafethrpt1520.0374000.197346ops/us0262
13shiftLogicalUnsafethrpt155.7733760.094510ops/us01018
13shiftLogicalUnsafethrpt156.1651000.164495ops/us01024
13shiftLogicalUnsafethrpt155.6357490.096095ops/us01030
13shiftLogicalUnsafethrpt1522.8030002.328542ops/us1250
13shiftLogicalUnsafethrpt1524.3066970.415944ops/us1256
13shiftLogicalUnsafethrpt1519.9326820.397168ops/us1262
13shiftLogicalUnsafethrpt155.7837510.070052ops/us11018
13shiftLogicalUnsafethrpt156.1768600.087320ops/us11024
13shiftLogicalUnsafethrpt155.6724050.309824ops/us11030
13shiftLogicalUnsafethrpt1522.3986956.500715ops/us7250
13shiftLogicalUnsafethrpt1524.0169021.427922ops/us7256
13shiftLogicalUnsafethrpt1519.8394270.253299ops/us7262
13shiftLogicalUnsafethrpt155.6512630.285734ops/us71018
13shiftLogicalUnsafethrpt156.0214680.372450ops/us71024
13shiftLogicalUnsafethrpt155.6604590.332135ops/us71030
13shiftLogicalUnsafethrpt1521.7436510.919695ops/us8250
13shiftLogicalUnsafethrpt1524.1343600.649705ops/us8256
13shiftLogicalUnsafethrpt1519.8444680.083193ops/us8262
13shiftLogicalUnsafethrpt155.7608630.832170ops/us81018
13shiftLogicalUnsafethrpt156.1478890.058199ops/us81024
13shiftLogicalUnsafethrpt155.6158990.098102ops/us81030

ベンチマークをより良いマシン上で実行すれば異なる結果になるかもしれませんが、AVX-512チップには当てはまらないでしょうし、自動ベクトル化の利点にも賭けています。

算術シフトについてどうでしょう。算術シフトの場合、最も重要なビットをセットする際には常に1を、そうでないときにはゼロで埋めて符号を保持するため、符号なしシフトではなくマスキングなしのbyte配列に適用した方が意味があります。この簡単なコードは、JDK13の自動ベクトル化の対象となっているため、ほほぼ同じです。

  @Benchmark
  public void shiftArithmetic(ByteShiftState state, Blackhole bh) {
    byte[] data = state.data;
    byte[] target = state.target;
    int shift = state.shift;
    shiftArithmetic(data, target, shift);
    bh.consume(target);
  }

  void shiftArithmetic(byte[] data, byte[] target, int shift) {
    for (int i = 0; i < data.length; ++i) {
      target[i] = (byte)(data[i] >> shift);
    }
  }

この2の補数演算をSWARでエミュレートするのは非常に難しいですが、特に0x80と0x00を等価と考えれば、似たようなことが可能です(例えば算術計算の場合)。

  1. まず、符号ビット(8ビットごと)をキャプチャして保存する
  2. 続いて、符号ビットをオフにして符号ビットが右シフトしないようにする
  3. シフト
  4. その後、各バイトの上位ビットにシフトされた任意のビットをマスクする
  5. 最後に、符号ビットを戻す

実際のところ、これではbyteをゼロにシフトした場合の正しいビット単位の結果は得られませんが、符号付き算術の場合は問題ありません。

  @Benchmark
  public void shiftArithmeticUnsafe(ByteShiftState state, Blackhole bh) {
    byte[] data = state.data;
    byte[] target = state.target;
    int shift = state.shift;
    shiftArithmeticUnsafe(data, target, shift);
    bh.consume(target);
  }

  void shiftArithmeticUnsafe(byte[] data, byte[] target, int shift) {
    long mask = MASKS[shift];
    int i = 0;
    for (; i  + 7 < data.length; i += 8) {
      long word = UNSAFE.getLong(data, BYTE_ARRAY_OFFSET + i);
      long signs = word & SIGN_BITS;
      word &= ~SIGN_BITS;
      word >>>= shift;
      word &= mask;
      word |= signs;
      UNSAFE.putLong(target, BYTE_ARRAY_OFFSET + i, word);
    }
    for (; i < data.length; ++i) {
      target[i] = (byte)(data[i] >> shift);
    }
  }

これはかなり複雑かつスループットに影響を与えますが、JDK11では間違いなく価値があります。幸いなことに、単純なコードはJDK13でより高速なので、試してみる必要はありません。

繰り返しになりますが、下の赤色の系列は、各JDKバージョンと配列サイズに対するスループットの測定値(高いほど良い)で、青色の系列は、それぞれのケースでUnsafeを使用することで得られる利点です。グラフの下に生データが表示されています。

Arithmetic Right Shift Chart

以下は前のグラフと同じ幅で取得したデータを使って、shiftArithmeticをJDK11とJDK13で比較した棒グラフです。

Arithmetic Right Shift Comparison
JDKBenchmarkModeThreadsSamplesScoreScore Error (99.9%)UnitParam: shiftParam: size
11shiftArithmeticthrpt157.5578230.065235ops/us0250
11shiftArithmeticthrpt157.2566370.981208ops/us0256
11shiftArithmeticthrpt157.4765200.035784ops/us0262
11shiftArithmeticthrpt151.9763030.026156ops/us01018
11shiftArithmeticthrpt151.9584430.023188ops/us01024
11shiftArithmeticthrpt151.9660610.026168ops/us01030
11shiftArithmeticthrpt157.5438300.109140ops/us1250
11shiftArithmeticthrpt157.3662260.046778ops/us1256
11shiftArithmeticthrpt157.6919540.380654ops/us1262
11shiftArithmeticthrpt151.9704810.042620ops/us11018
11shiftArithmeticthrpt152.0398900.120633ops/us11024
11shiftArithmeticthrpt151.9653480.010959ops/us11030
11shiftArithmeticthrpt157.5257000.216891ops/us7250
11shiftArithmeticthrpt157.3479150.071271ops/us7256
11shiftArithmeticthrpt157.4882010.037903ops/us7262
11shiftArithmeticthrpt152.0099000.032639ops/us71018
11shiftArithmeticthrpt151.9583730.044689ops/us71024
11shiftArithmeticthrpt152.0444590.216456ops/us71030
11shiftArithmeticthrpt157.5369480.124611ops/us8250
11shiftArithmeticthrpt157.3364820.059378ops/us8256
11shiftArithmeticthrpt157.4707580.151656ops/us8262
11shiftArithmeticthrpt151.9723280.026727ops/us81018
11shiftArithmeticthrpt152.0279250.170155ops/us81024
11shiftArithmeticthrpt151.9672950.025890ops/us81030
13shiftArithmeticthrpt1518.2477870.177523ops/us0250
13shiftArithmeticthrpt1525.1892870.083362ops/us0256
13shiftArithmeticthrpt1523.8781281.486587ops/us0262
13shiftArithmeticthrpt159.2867760.169307ops/us01018
13shiftArithmeticthrpt1510.9140470.060050ops/us01024
13shiftArithmeticthrpt1510.5647640.303730ops/us01030
13shiftArithmeticthrpt1518.1260120.497112ops/us1250
13shiftArithmeticthrpt1525.0927440.685261ops/us1256
13shiftArithmeticthrpt1522.9993890.303475ops/us1262
13shiftArithmeticthrpt159.3087940.242943ops/us11018
13shiftArithmeticthrpt1510.8899870.201891ops/us11024
13shiftArithmeticthrpt1510.3548300.204797ops/us11030
13shiftArithmeticthrpt1518.1049290.833391ops/us7250
13shiftArithmeticthrpt1525.5252251.058005ops/us7256
13shiftArithmeticthrpt1522.8901700.457192ops/us7262
13shiftArithmeticthrpt159.3242880.196076ops/us71018
13shiftArithmeticthrpt1510.8915330.082364ops/us71024
13shiftArithmeticthrpt1510.5711870.222624ops/us71030
13shiftArithmeticthrpt1518.1758080.452371ops/us8250
13shiftArithmeticthrpt1525.2454520.396196ops/us8256
13shiftArithmeticthrpt1523.1090970.061468ops/us8262
13shiftArithmeticthrpt159.2847110.256823ops/us81018
13shiftArithmeticthrpt1510.8778130.105014ops/us81024
13shiftArithmeticthrpt1510.3583050.292978ops/us81030
13shiftArithmeticUnsafethrpt1515.6287980.415542ops/us0250
13shiftArithmeticUnsafethrpt1517.2724560.631146ops/us0256
13shiftArithmeticUnsafethrpt1514.4383530.315382ops/us0262
13shiftArithmeticUnsafethrpt154.4157690.079505ops/us01018
13shiftArithmeticUnsafethrpt154.4613730.080921ops/us01024
13shiftArithmeticUnsafethrpt154.1320340.250692ops/us01030
13shiftArithmeticUnsafethrpt1516.9927970.253043ops/us1250
13shiftArithmeticUnsafethrpt1517.3429520.238273ops/us1256
13shiftArithmeticUnsafethrpt1514.6272870.552194ops/us1262
13shiftArithmeticUnsafethrpt154.5174350.151964ops/us11018
13shiftArithmeticUnsafethrpt154.4766160.054379ops/us11024
13shiftArithmeticUnsafethrpt154.1537280.068590ops/us11030
13shiftArithmeticUnsafethrpt1516.9356700.515578ops/us7250
13shiftArithmeticUnsafethrpt1517.6686350.343247ops/us7256
13shiftArithmeticUnsafethrpt1514.4082050.368361ops/us7262
13shiftArithmeticUnsafethrpt154.4366540.020834ops/us71018
13shiftArithmeticUnsafethrpt154.4764750.039526ops/us71024
13shiftArithmeticUnsafethrpt154.1726090.061469ops/us71030
13shiftArithmeticUnsafethrpt1516.9874660.202447ops/us8250
13shiftArithmeticUnsafethrpt1517.4034200.208813ops/us8256
13shiftArithmeticUnsafethrpt1514.4642750.160839ops/us8262
13shiftArithmeticUnsafethrpt154.4437080.070989ops/us81018
13shiftArithmeticUnsafethrpt154.7206260.171716ops/us81024
13shiftArithmeticUnsafethrpt154.2530400.088258ops/us81030

SWARはJavaではあまり利用されていない技術です。Unsafeを使わず、様々なコンパイラの最適化を放棄することなく、SWARを活用できるといいのですが。Project PanamaのVector APIで実験したとき、最も興味深かった機能は、異なる幅の整数型間で簡単に変換できる機能です。これは特に8ビットの論理右シフトに関連しています。なぜならこの機能はAVX2には存在せず、このエントリの序盤のperfasmの出力で見られるように、いくつかの演算から組み上げる必要があるからです。時間が経てばAVX2はだんだん関連性が薄れていくでしょうし、ベンチマークで使っているコンピュータでそれにアクセスしても、AVX2が重要になることはありませんが、AVX-512はまだそれほど普及しておらず、AMD のサポートもありません。直近でVector APIと戯れていたとき、Wojciech Mula によって考案されたvector bit count algorithmで論理右シフトする場合に、SWAR実行機能があるとパフォーマンス上有益であることがわかりました。

[vector] AVX2 ByteVector.shiftR performance and semantics
https://mail.openjdk.java.net/pipermail/panama-dev/2019-January/004042.html
Faster Population Counts Using AVX2 Instructions
https://arxiv.org/pdf/1611.07612.pdf
Wojciech Mula
https://twitter.com/pshufb

再解釈は最新バージョンのAPIで第1級の概念としてを表現されています。最新バージョンのAPIではSWARのトリックをshiftRightIntで確認できますが、より簡単なshiftRIghtByteでは確認できません。ちなみに、shiftRightByteはJDK13 の自動ベクトル化された符号なしシフトと同様のコードにコンパイルされます。

もちろん、一般性の損失という犠牲はありますが、32バイトでの演算とより高速な8個のint配列に対する演算の間で、2019年1月に遡って10倍のパフォーマンス差がありました。

  @Benchmark
  public int shiftRightByte() {
    return LongVector.fromArray(L256, data, 0)
            .reinterpretAsBytes()
            .lanewise(LSHR, 4)
            .and((byte)0x0F)
            .lane(0);
  }

  @Benchmark
  public int shiftRightInt() {
    return LongVector.fromArray(L256, data, 0)
            .reinterpretAsInts()
            .lanewise(LSHR, 4)
            .and(0x0F0F0F0F)
            .reinterpretAsBytes()
            .lane(0);
  }

Vector APIが利用可能になる前に、汎用的な方法があるといいですね。

コードはgithubにあります。

JDK13 benchmark
https://github.com/richardstartin/simdbenchmarks/blob/master/src/main/java/com/openkappa/simd/byteshift/ByteShiftBenchmark.java
Vector API benchmark
https://github.com/richardstartin/vectorbenchmarks

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中