11

CPU の初期から、整数除算命令が高価であることは一般的な知識でした。何十億ものトランジスタを贅沢に搭載した CPU で、今日がどれほど悪いかを見に行きました。ハードウェアidiv命令は、命令を含まない JIT コンパイラが発行できるコードよりも、定数除数に対して依然として大幅にパフォーマンスが悪いことがわかりましたidiv。

これを専用のマイクロベンチマークで明らかにするために、次のように記述しました。

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@OperationsPerInvocation(MeasureDiv.ARRAY_SIZE)
@Warmup(iterations = 8, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@State(Scope.Thread)
@Fork(1)
public class MeasureDiv
{
  public static final int ARRAY_SIZE = 128;
  public static final long DIVIDEND_BASE = 239520948509234807L;
  static final int DIVISOR = 10;
  final long[] input = new long[ARRAY_SIZE];

  @Setup(Level.Iteration) public void setup() {
    for (int i = 0; i < input.length; i++) {
      input[i] = DIVISOR;
    }
  }

  @Benchmark public long divVar() {
    long sum = 0;
    for (int i = 0; i < ARRAY_SIZE; i++) {
      final long in = input[i];
      final long dividend = DIVIDEND_BASE + i;
      final long divisor = in;
      final long quotient = dividend / divisor;
      sum += quotient;
    }
    return sum;
  }

  @Benchmark public long divConst() {
    long sum = 0;
    for (int i = 0; i < ARRAY_SIZE; i++) {
      final long in = input[i];
      final long dividend = DIVIDEND_BASE + in;
      final int divisor = DIVISOR;
      final long quotient = dividend / divisor;
      sum += quotient;
    }
    return sum;
  }
}

divVar簡単に言えば、1 つの ( ) が配列から読み取った数値で除算を実行し、もう 1 つはコンパイル時の定数で除算することを除いて、すべての点で同一の 2 つのメソッドがあります。結果は次のとおりです。

Benchmark            Mode  Cnt  Score   Error  Units
MeasureDiv.divConst  avgt    5  1.228 ± 0.032  ns/op
MeasureDiv.divVar    avgt    5  8.913 ± 0.192  ns/op

パフォーマンスの比率は非常に異常です。私の予想では、最新の Intel プロセッサには十分なスペースがあり、そのエンジニアは、複雑ではあるがパフォーマンスの高い除算アルゴリズムをハードウェアに実装するのに十分な関心を持っています。それでも、JIT コンパイラーは、同じジョブを実行する他の命令のストリームをインテルに送信するという点でインテルに勝っていますが、その速度はわずか 7 倍です。どちらかといえば、専用のマイクロコードは、アセンブリ命令のパブリック API を介して JIT が実行できるものよりも CPU を有効に活用できるはずです。

idivなぜまだこんなに遅いのか、根本的な制限は何ですか?

頭に浮かぶ説明の 1 つは、プロセスの非常に遅い段階で初めて被除数を含む除算アルゴリズムが存在するという仮説です。JIT コンパイラは、コンパイル時に除数のみを含む最初の部分を評価し、アルゴリズムの 2 番目の部分のみをランタイム コードとして出力するため、有利なスタートを切ることができます。その仮説は本当ですか？

4

1 に答える 1

1

ユーザーpvgがコメントを通じて説明したように、仮説アルゴリズムは実際に存在し、現在知られている最高のものです。このアルゴリズムは、準備段階で同じ約数による除算を含むため、全体として基本的に既約です。これは、古典的な出版物Hacker's Delight の第 10 章で取り上げられています。

于 2015-07-13T08:14:46.560 に答える