Подтвердить что ты не робот

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

При чтении через класс 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
Документ, на который делается ссылка в ссылке, похоже, не касается прямого обращения к проблеме.

Ответ 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-разрядных чисел.

С другой стороны, обработанная вручную функция, подобная приведенной выше, может выполнять умножение на константу за меньшее количество шагов, используя числовые свойства этой константы, в этом случае уменьшая ее до четырех операций shift/add вместо 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;
}

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