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

integer java

2022-09-03 06:49:46

在阅读Java 8的整数类时，我遇到了以下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中删除了
链接中引用的论文似乎没有直接解决该问题。

答案 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位数字。

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

进入完全相同的汇编代码，这恰恰表明现代编译器确实知道得最好。

答案 2