Является ли дополнительный ход как-то быстрее при делении на умножение? - PullRequest
Новая
       33

Является ли дополнительный ход как-то быстрее при делении на умножение?

7 голосов
/ 28 апреля 2020

Рассмотрим эту функцию: 

unsigned long f(unsigned long x) {
    return x / 7;
}

При -O3 Clang превращает деление в умножение , как и ожидалось: 

f:                                      # @f
        movabs  rcx, 2635249153387078803
        mov     rax, rdi
        mul     rcx
        sub     rdi, rdx
        shr     rdi
        lea     rax, [rdi + rdx]
        shr     rax, 2
        ret

G CC делает в основном то же самое, за исключением использования rdx, где Clang использует rcx. Но они оба, кажется, делают дополнительный ход. Почему бы не сделать это вместо этого? 

f:
        movabs  rax, 2635249153387078803
        mul     rdi
        sub     rdi, rdx
        shr     rdi
        lea     rax, [rdi + rdx]
        shr     rax, 2
        ret

В частности, они оба поместили числитель в rax, но вместо этого, поместив туда число волхвов c, вы вообще не будете перемещать числитель. Если это на самом деле лучше, я удивляюсь, что ни G CC, ни Clang не делают этого так, поскольку это кажется таким очевидным. Есть ли какая-то микроархитектурная причина, по которой их путь на самом деле быстрее моего?

Godbolt link .

Ответы [ 3 ]

4 голосов
/ 28 апреля 2020

Это очень похоже на пропущенную оптимизацию как g cc, так и clang; бесполезно для этого дополнительного движения.

Если об этом еще не сообщается, G CC и LLVM принимают отчеты об ошибках пропущенной оптимизации: https://bugs.llvm.org/ и https://gcc.gnu.org/bugzilla/. Для G CC есть даже тег ошибки «Пропущенная оптимизация».

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

Zero-latency mov (mov-elission) помогает снизить стоимость таких пропущенных оптимизаций (а также случаев, когда mov невозможно избежать), но все равно требуется входной uop так что это намного хуже. (За исключением случая, когда это помогает выровнять что-то позже, но если бы это было причиной, тогда nop был бы таким же хорошим).

И это занимает место в ROB, уменьшая, насколько далеко вперед - exe-порядка exe c можно увидеть мимо пропущенного кэша или другого киоска. mov никогда не бывает по-настоящему свободным, исключается только часть исполнительного модуля и задержки - Может ли MOV x86 действительно быть "свободным"? Почему я вообще не могу воспроизвести это?

Мое общее предположение о внутренностях компилятора:

Вероятно, внутреннему механизму gcc / clang нужно понять, что этот шаблон деления коммутативный и может взять входное значение в каком-то другом регистре и поместить константу в RAX.

В al oop они хотели бы получить константу в каком-то другом регистре, чтобы они могли использовать ее повторно, но, надеюсь, компилятор все еще мог понять это в тех случаях, когда это полезно.

2 голосов
/ 28 апреля 2020

Visual Studio 2015 генерирует код, который вы ожидали, rcx = входное деление: 

        mov     rax, 2635249153387078803
        mul     rcx
        sub     rcx, rdx
        shr     rcx, 1
        lea     rax, QWORD PTR [rdx+rcx]
        shr     rax, 2

Для получения правильной точности делителю 7 требуется множитель 65 бит. 

floor((2^(64+ceil(log2(7))))/7)+1 = floor((2^67)/7)+1 = 21081993227096630419

Удаление старшего значащего бита, 2 ^ 64, приводит к 21081993227096630419 - 2 ^ 64 = 2635249153387078803, который является множителем, фактически используемым в коде.

Сгенерированный код компенсирует отсутствующий бит 2 ^ 64, который объясняется на рисунке 4.1 и уравнении 4.5 в этом файле PDF:

https://gmplib.org/~tege/divcnst-pldi94.pdf

Дальнейшее объяснение можно увидеть в этом предыдущем ответ:

Почему G CC использует умножение на странное число при реализации целочисленного деления?

Если 65-битный множитель имеет завершающий 0 бит, то он можно сдвинуть вправо на 1 бит, чтобы получить 64-битный множитель, уменьшая количество команд. Например, если делить на 5: 

floor((2^(64+ceil(log2(5))))/5)+1 = floor((2^67)/5)+1 = 29514790517935282586
29514790517935282586 >> 1 = 14757395258967641293

        mov     rax, -3689348814741910323 ; == 14757395258967641293 ==  0cccccccccccccccdH
        mul     rcx
        shr     rdx, 2
        mov     rax, rdx
0 голосов
/ 28 апреля 2020

Ваша версия не выглядит быстрее.

Редактировать: ROB (буфер переупорядочения) может переименовать регистр, поэтому дополнительные mov делают не на самом деле должны перемещать любые данные. Он может просто настроить индекс в PRF [файл физического регистра] для сгенерированного мопа. Итак, mov возможно слиты.

Я закодировал обе ваши версии asm:

Вот orig.s: 

    .file   "orig.c"
    .text
    .p2align 4,,15
    .globl  orig
    .type   orig, @function
orig:
.LFB0:
    .cfi_startproc
    movabsq $2635249153387078803, %rdx
    movq    %rdi, %rax
    mulq    %rdx
    subq    %rdx, %rdi
    shrq    %rdi
    leaq    (%rdx,%rdi), %rax
    shrq    $2, %rax
    ret
    .cfi_endproc
.LFE0:
    .size   orig, .-orig
    .ident  "GCC: (GNU) 8.3.1 20190223 (Red Hat 8.3.1-2)"
    .section    .note.GNU-stack,"",@progbits

И, fix1.s: 

    .file   "fix1.c"
    .text
    .p2align 4,,15
    .globl  fix1
    .type   fix1, @function
fix1:
.LFB0:
    .cfi_startproc
    movabsq $2635249153387078803, %rax
    mulq    %rdi
    subq    %rdx, %rdi
    shrq    %rdi
    leaq    (%rdx,%rdi), %rax
    shrq    $2, %rax
    ret
    .cfi_endproc
.LFE0:
    .size   fix1, .-fix1
    .ident  "GCC: (GNU) 8.3.1 20190223 (Red Hat 8.3.1-2)"
    .section    .note.GNU-stack,"",@progbits

Вот тестовая программа, main.c. (Вам может потребоваться изменить постоянную итерации в test): 

#include <stdio.h>
#include <time.h>

typedef unsigned long ulong;

ulong orig(ulong);
ulong fix1(ulong);

typedef ulong (*fnc_p)(ulong);

typedef long long tsc_t;

static inline tsc_t
tscget(void)
{
    struct timespec ts;
    tsc_t tsc;

    clock_gettime(CLOCK_MONOTONIC,&ts);

    tsc = ts.tv_sec;
    tsc *= 1000000000;
    tsc += ts.tv_nsec;

    return tsc;
}

tsc_t
test(fnc_p fnc)
{
    tsc_t beg;
    tsc_t end;
    ulong tot = 0;

    beg = tscget();

    for (ulong cnt = 10000000;  cnt > 0;  --cnt)
        tot += fnc(cnt);

    end = tscget();

    end -= beg;

    return end;
}

int
main(void)
{

    tsc_t odif = test(orig);
    tsc_t fdif = test(fix1);

    printf("odif=%lld fdif=%lld (%lld)\n",odif,fdif,odif - fdif);

    return 0;
}

Сборка с: 

gcc -O3 -o main main.c orig.s fix1.s

Вот результаты тестовых испытаний 20 прогонов : 

odif=43937784 fdif=34104334 (9833450)
odif=39791246 fdif=42641752 (-2850506)
odif=25818191 fdif=25586750 (231441)
odif=35056015 fdif=25276729 (9779286)
odif=43955175 fdif=31112246 (12842929)
odif=25731472 fdif=25493826 (237646)
odif=25627395 fdif=26202191 (-574796)
odif=28029957 fdif=25627366 (2402591)
odif=25828608 fdif=26291294 (-462686)
odif=25690703 fdif=25703610 (-12907)
odif=25908418 fdif=26411828 (-503410)
odif=25690776 fdif=25673766 (17010)
odif=25992890 fdif=25982718 (10172)
odif=25693459 fdif=25636974 (56485)
odif=26572724 fdif=25870050 (702674)
odif=25627334 fdif=25621802 (5532)
odif=27760054 fdif=27382748 (377306)
odif=26343245 fdif=26195134 (148111)
odif=27289865 fdif=25840818 (1449047)
odif=25985794 fdif=25721351 (264443)

ОБНОВЛЕНИЕ:

Ваши данные не подтверждают ваше заключение, если я что-то не так понимаю.

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

Вы должны заметить, что современные модели x86 (например, Sandy Bridge или более поздние), делают массивную суперскалярную и переупорядочение команд, а также слияние мопов так что я бы не стал рассчитывать на буквальный перевод. Например, см .: https://www.realworldtech.com/sandy-bridge/

Вот лучшая (?) Версия, но она все равно показывает то же самое . А именно, что иногда оригинал быстрее, а иногда «улучшенный» быстрее 

#include <stdio.h>
#include <time.h>

typedef unsigned long ulong;

ulong orig(ulong);
ulong fix1(ulong);

typedef ulong (*fnc_p)(ulong);

typedef long long tsc_t;

typedef struct {
    tsc_t orig;
    tsc_t fix1;
} bnc_t;

#define BNCMAX      100
bnc_t bnclist[BNCMAX];

static inline tsc_t
tscget(void)
{
    struct timespec ts;
    tsc_t tsc;

    clock_gettime(CLOCK_MONOTONIC,&ts);

    tsc = ts.tv_sec;
    tsc *= 1000000000;
    tsc += ts.tv_nsec;

    return tsc;
}

tsc_t
test(fnc_p fnc)
{
    tsc_t beg;
    tsc_t end;
    ulong tot = 0;

    beg = tscget();

    for (ulong cnt = 10000000;  cnt > 0;  --cnt)
        tot += fnc(cnt);

    end = tscget();

    end -= beg;

    return end;
}

void
run(bnc_t *bnc)
{
    tsc_t odif = test(orig);
    tsc_t fdif = test(fix1);

    bnc->orig = odif;
    bnc->fix1 = fdif;
}

int
main(void)
{
    bnc_t *bnc;

    for (int pass = 0;  pass < BNCMAX;  ++pass) {
        bnc = &bnclist[pass];
        run(bnc);
    }

    for (int pass = 0;  pass < BNCMAX;  ++pass) {
        bnc = &bnclist[pass];
        printf("orig=%lld fix1=%lld (%lld)\n",
            bnc->orig,bnc->fix1,bnc->orig - bnc->fix1);
    }

    return 0;
}

И вот что получилось (без реальных изменений): 

orig=31588215 fix1=26821473 (4766742)
orig=25748732 fix1=25917183 (-168451)
orig=25805426 fix1=25635759 (169667)
orig=25479642 fix1=26037620 (-557978)
orig=26668860 fix1=25959444 (709416)
orig=26047616 fix1=25540493 (507123)
orig=25772292 fix1=25460041 (312251)
orig=25709852 fix1=26172701 (-462849)
orig=26124151 fix1=25766472 (357679)
orig=25539018 fix1=26845018 (-1306000)
orig=26884105 fix1=26869566 (14539)
orig=26184938 fix1=27826408 (-1641470)
orig=25841934 fix1=25482603 (359331)
orig=25509107 fix1=25436511 (72596)
orig=25448812 fix1=25473302 (-24490)
orig=25433894 fix1=25812646 (-378752)
orig=25868190 fix1=26180032 (-311842)
orig=25451573 fix1=25503657 (-52084)
orig=25393540 fix1=25484952 (-91412)
orig=26032526 fix1=26825219 (-792693)
orig=25859126 fix1=25529430 (329696)
orig=25692214 fix1=25431668 (260546)
orig=25463849 fix1=25370236 (93613)
orig=25650185 fix1=25401441 (248744)
orig=25702951 fix1=26858126 (-1155175)
orig=26187072 fix1=25800102 (386970)
orig=26493916 fix1=25591639 (902277)
orig=26456983 fix1=25724181 (732802)
orig=25842746 fix1=26119019 (-276273)
orig=26654148 fix1=29452577 (-2798429)
orig=27936505 fix1=28494045 (-557540)
orig=30067162 fix1=27029523 (3037639)
orig=25785637 fix1=25856415 (-70778)
orig=25521760 fix1=25286859 (234901)
orig=25433035 fix1=25626380 (-193345)
orig=25373358 fix1=25541615 (-168257)
orig=25846496 fix1=25446494 (400002)
orig=25368198 fix1=25321934 (46264)
orig=25615453 fix1=28574223 (-2958770)
orig=26660896 fix1=25508745 (1152151)
orig=25891979 fix1=25546436 (345543)
orig=25296369 fix1=25382779 (-86410)
orig=25438794 fix1=25372736 (66058)
orig=25531652 fix1=25498422 (33230)
orig=25977272 fix1=25456931 (520341)
orig=25336327 fix1=25423638 (-87311)
orig=26037148 fix1=25313703 (723445)
orig=25314995 fix1=25538181 (-223186)
orig=26638367 fix1=26446762 (191605)
orig=25915537 fix1=25633327 (282210)
orig=25409105 fix1=25287069 (122036)
orig=25633931 fix1=26423463 (-789532)
orig=26074523 fix1=26524398 (-449875)
orig=25602157 fix1=25580893 (21264)
orig=25490481 fix1=25557287 (-66806)
orig=25666843 fix1=25496179 (170664)
orig=26573635 fix1=25796737 (776898)
orig=26133811 fix1=26226840 (-93029)
orig=28262664 fix1=26022265 (2240399)
orig=25336820 fix1=25683095 (-346275)
orig=25899602 fix1=25660778 (238824)
orig=25440453 fix1=25630320 (-189867)
orig=25356601 fix1=25422670 (-66069)
orig=25419887 fix1=25611533 (-191646)
orig=25766460 fix1=25596927 (169533)
orig=25619510 fix1=25449303 (170207)
orig=25359373 fix1=25380306 (-20933)
orig=25474687 fix1=27194210 (-1719523)
orig=26389253 fix1=26709738 (-320485)
orig=26132999 fix1=25671907 (461092)
orig=25416724 fix1=25540911 (-124187)
orig=25440277 fix1=25364387 (75890)
orig=25704885 fix1=25661456 (43429)
orig=25544376 fix1=25380520 (163856)
orig=25340926 fix1=25956342 (-615416)
orig=25383668 fix1=25397807 (-14139)
orig=25636178 fix1=25769479 (-133301)
orig=26237022 fix1=29897502 (-3660480)
orig=28235814 fix1=25475574 (2760240)
orig=25457466 fix1=25450557 (6909)
orig=25775658 fix1=25802380 (-26722)
orig=27577521 fix1=25444772 (2132749)
orig=25380927 fix1=25409250 (-28323)
orig=25417872 fix1=25336530 (81342)
orig=25995656 fix1=26338512 (-342856)
orig=25553088 fix1=25334495 (218593)
orig=25416197 fix1=25521031 (-104834)
orig=29150160 fix1=25717390 (3432770)
orig=26026892 fix1=26916678 (-889786)
orig=25694048 fix1=25496660 (197388)
orig=25576011 fix1=25676045 (-100034)
orig=25461907 fix1=25462593 (-686)
orig=25736879 fix1=27349093 (-1612214)
orig=25687558 fix1=25829963 (-142405)
orig=25492417 fix1=25752421 (-260004)
orig=25559702 fix1=25423874 (135828)
orig=25799145 fix1=28961932 (-3162787)
orig=25912111 fix1=26018163 (-106052)
orig=25725927 fix1=25794091 (-68164)
orig=25528795 fix1=25855893 (-327098)

ОБНОВЛЕНИЕ # 2:

Вот моя последняя тестовая версия: 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef unsigned long ulong;

ulong orig(ulong);
ulong fix1(ulong);

typedef ulong (*fnc_p)(ulong);

typedef long long tsc_t;

typedef struct {
    tsc_t dif;
    ulong tot;
} test_t;

typedef struct {
    test_t orig;
    test_t fix1;
} bnc_t;

#define BNCMAX      100
bnc_t bnclist[BNCMAX];

ulong itermax;

static inline tsc_t
tscget(void)
{
    struct timespec ts;
    tsc_t tsc;

    clock_gettime(CLOCK_MONOTONIC,&ts);

    tsc = ts.tv_sec;
    tsc *= 1000000000;
    tsc += ts.tv_nsec;

    return tsc;
}

tsc_t
test(test_t *tst,fnc_p fnc)
{
    tsc_t beg;
    tsc_t end;
    ulong tot = 0;

    beg = tscget();

    for (ulong cnt = itermax;  cnt > 0;  --cnt)
        tot += fnc(cnt);

    end = tscget();
    end -= beg;

    tst->dif = end;
    tst->tot = tot;

    return end;
}

void
run(bnc_t *bnc)
{
    tsc_t odif = test(&bnc->orig,orig);
    tsc_t fdif = test(&bnc->fix1,fix1);
}

int
main(int argc,char **argv)
{
    bnc_t *bnc;
    test_t bestorig;
    test_t bestfix1;

    --argc;
    ++argv;

    if (argc > 0)
        itermax = atoll(*argv);
    else
        itermax = 10000000;

    for (int pass = 0;  pass < BNCMAX;  ++pass) {
        bnc = &bnclist[pass];
        run(bnc);
    }

    bnc = &bnclist[0];
    bestorig = bnc->orig;
    bestfix1 = bnc->orig;

    for (int pass = 0;  pass < BNCMAX;  ++pass) {
        bnc = &bnclist[pass];

        printf("orig=%lld fix1=%lld (%lld)\n",
            bnc->orig.dif,bnc->fix1.dif,bnc->orig.dif - bnc->fix1.dif);
        if (bnc->orig.tot != bnc->fix1.tot)
            printf("FAIL: orig=%ld fix1=%ld\n",bnc->orig.tot,bnc->fix1.tot);

        if (bnc->orig.dif < bestorig.dif)
            bestorig = bnc->orig;

        if (bnc->fix1.dif < bestfix1.dif)
            bestfix1 = bnc->fix1;
    }

    printf("\n");
    printf("itermax=%ld\n",itermax);
    printf("orig=%lld\n",bestorig.dif);
    printf("fix1=%lld\n",bestfix1.dif);

    return 0;
}
...