Как это быстрее? 52-битное умножение по модулю с использованием «трюка FPU» быстрее, чем встроенный ASM на x64 - PullRequest
Новая
       4

Как это быстрее? 52-битное умножение по модулю с использованием «трюка FPU» быстрее, чем встроенный ASM на x64

1 голос
/ 27 февраля 2020

Я обнаружил, что это: 

#define mulmod52(a,b,m) (((a * b) - (((uint64_t)(((double)a * (double)b) / (double)m) - 1ULL) * m)) % m)

... быстрее, чем: 

static inline uint64_t _mulmod(uint64_t a, uint64_t b, uint64_t n) {
    uint64_t d, dummy;                    /* d will get a*b mod c */
    asm ("mulq %3\n\t"              /* mul a*b -> rdx:rax */
         "divq %4\n\t"              /* (a*b)/c -> quot in rax remainder in rdx */
         :"=a"(dummy), "=&d"(d)     /* output */
         :"a"(a), "rm"(b), "rm"(n)  /* input */
         :"cc"                      /* mulq and divq can set conditions */
        );
    return d;
}

Первый способ - использовать FPU для вычисления модульного умножения двух до до 52 битных чисел. Последний простой X64 ASM для вычисления модульного умножения двух 64-разрядных чисел, и, конечно, он также отлично работает только для 52 битов.

Первый быстрее, чем последний примерно на 5-15% в зависимости от где я проверяю это.

Как это возможно, учитывая, что трюк FPU также включает в себя одно целочисленное умножение и одно целочисленное деление (модуль) плюс дополнительную работу FPU? Есть кое-что, чего я не понимаю здесь. Является ли это каким-то странным артефактом компилятора, таким как asm проходы оптимизации встроенного разрушающего компилятора?

1 Ответ

6 голосов
/ 27 февраля 2020

На процессорах до Icelake, таких как Skylake , существует большая разница между «полным» 128-битным делением и «половинным» 64-битным делением (где верхнее qword ноль). Полный может занять до почти 100 циклов (немного варьируется в зависимости от значения в rdx, но возникает внезапный «обрыв», когда rdx даже установлен на 1), половина больше около 30 до 40-я sh циклов в зависимости от µarch.

64-битное деление с плавающей запятой (для деления) является относительно быстрым, приблизительно от 14 до 20 циклов в зависимости от µarch, так что даже с этим и некоторыми другими даже - без значительных накладных расходов, этого недостаточно, чтобы потратить преимущество 60 циклов, которое разделило «половину» по сравнению с «полным» делением. Таким образом, сложная версия с плавающей запятой может выйти вперед.

Icelake , очевидно, имеет удивительный делитель, который может сделать полное деление за 18 циклов (и «половинное» деление не быстрее) , встроенный ассм должен быть хорошим на Icelake.

На AMD Ryzen, деления с ненулевым верхним словом кажутся медленнее, постепенно, когда rdx становится выше (меньше «перфорации»).

...