TODO-FIXME: В классе Integer в Java 8?

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, где последний является тривиальным битом сдвиг вместо полного деления.

Автор кода, кажется, предполагает, что умножение можно было бы сделать более оптимально, используя вместо этого операции shift / add, согласно этому фрагменту (язык 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.

На уровне машинного кода он был бы более оптимальным только на (в настоящее время редком) процессоре без аппаратного умножителя, где самой простой (хотя, возможно, наивной) функции умножения потребовалось бы 16 операций сдвига / сложения для умножения двух 16-разрядных чисел.

С другой стороны, созданная вручную функция, подобная описанной выше, может выполнять умножение на константу за меньшее количество шагов, используя числовые свойства этой константы, в этом случае уменьшая ее до четырех операций сдвига / сложения вместо 16.

FWIW (и несколько впечатляюще) компилятор clang в macOS, даже с одним лишь флагом оптимизации -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;
}

в в точности тот же код сборки, который показывает, что современные компиляторы действительно знают лучше.