TODO-FIXME:在Java 8的Integer类中？

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中删除了
• 链接中引用的文件似乎没有解决直接解决问题的方法.

Answer 1

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

根据这个(C语言)片段,代码作者似乎建议使用shift/add操作更好地完成乘法:

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位数字才能更加优化.

另一方面,像上面这样的手工制作的函数可以通过利用该常量的数字属性以较少的步长执行乘法,在这种情况下将其减少到四个移位/加法操作而不是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;
}

到恰好相同的汇编代码,这只是表明,现代编译器真的知道最好的.