java - CPU 的 div 指令和 HotSpot 的 JIT 代码之间的性能差距很大

Question

自从 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) 执行除以从数组读取的数字而另一个除以编译时常量之外，我有两种在各个方面都相同的方法。这些是结果:

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

性能比相当不凡。我的期望是现代英特尔处理器有足够的空间，其工程师有足够的兴趣在硬件中实现复杂但高性能的除法算法。然而，JIT 编译器通过向英特尔发送一些执行相同工作的其他指令流来击败英特尔，速度只是快了七倍。如果有的话，专用微码应该能够比 JIT 通过汇编指令的公共(public) API 更好地利用 CPU。

为什么 idiv 还是那么慢，根本的限制是什么？

我想到的一个解释是假设存在一种除法算法，它在很晚的时候才第一次涉及除法。然后，JIT 编译器将抢先一步，因为它会在编译时评估仅涉及除数的第一部分，并仅将算法的第二部分作为运行时代码发出。这个假设是真的吗？

Answer 1

正如用户 pvg 在评论中所解释的那样，假设的算法确实存在，并且是目前已知的最好的算法。该算法在准备步骤中涉及用相同的除数进行除法，因此从根本上讲它作为一个整体是不可约的。它包含在经典出版物的第 10 章中 Hacker's Delight .