java - TODO-FIXME : In Java 8's Integer class?

Question

在阅读 Java 8 的 Integer 时类，我遇到了以下 FIX-ME:(第 379 行)

// TODO-FIXME: convert (x * 52429) into the equiv shift-add
// sequence.

评论全文如下:

// I use the "[invariant division by multiplication][2]" trick to
// accelerate Integer.toString.  In particular we want to
// avoid division by 10.
//
// The "trick" has roughly the same performance characteristics
// as the "classic" Integer.toString code on a non-JIT VM.
// The trick avoids .rem and .div calls but has a longer code
// path and is thus dominated by dispatch overhead.  In the
// JIT case the dispatch overhead doesn't exist and the
// "trick" is considerably faster than the classic code.
//
// TODO-FIXME: convert (x * 52429) into the equiv shift-add
// sequence.
//
// RE:  Division by Invariant Integers using Multiplication
//      T Gralund, P Montgomery
//      ACM PLDI 1994
//

我无法想象我应该为此担心，因为这已经存在了很长一段时间。

但是，有人可以阐明这个 FIX-ME 的含义以及是否有任何副作用吗？

---

边注:

• 我看到它已从 JDK 10 中删除
• paper链接中引用的地址似乎没有直接解决问题。

Answer 1

52429 是最接近 (2 ^ 19)/10 的整数，因此除以 10 可以通过 乘以 52429，然后除以 2 ^ 19 来实现，其中后者是微不足道的位移位操作而不需要完全除法。

代码作者似乎建议使用移位/加法运算可以更优化地完成乘法，根据这个(C 语言)片段:

uint32_t div10(uint16_t in)
{
    // divides by multiplying by 52429 / (2 ^ 16)
    // 52429 = 0xcccd
    uint32_t x = in << 2;    // multiply by 4   : total = 0x0004
    x += (x << 1);           // multiply by 3   : total = 0x000c
    x += (x << 4);           // multiply by 17  : total = 0x00cc
    x += (x << 8);           // multiply by 257 : total = 0xcccc
    x += in;                 // one more makes  : total = 0xcccd

    return x >> 19;
}

我无法回答的是，为什么他们显然认为这可能比 Java 环境中的直接乘法更优化。

在机器代码级别，它只会在没有硬件乘法器的(现在很少见的)CPU 上更优化，其中最简单(尽管可能是幼稚的)乘法函数需要 16 次移位/加法运算才能将两个 16 位数字相乘。

另一方面，像上面这样的手工函数可以通过利用常量的数字属性以更少的步骤执行与常量的乘法运算，在本例中将其减少到 4 次移位/加法运算而不是 16 次。

FWIW(有点令人印象深刻)macOS 上的 clang 编译器即使只有 -O1 优化标志实际上也会将上面的代码转换回单个乘法:

_div10:                             ## @div10
    pushq   %rbp
    movq    %rsp, %rbp
    imull   $52429, %edi, %eax      ## imm = 0xCCCD
    shrl    $19, %eax
    popq    %rbp
    retq

它还转:

uint32_t div10(uint16_t in) {
   return in / 10;
}

进入完全相同的汇编代码，这只是表明现代编译器确实最了解。