Podczas pisania zoptymalizowanej ftolfunkcji znalazłem bardzo dziwne zachowanie GCC 4.6.1. Pokażę najpierw kod (dla jasności zaznaczyłem różnice):

fast_trunc_one, C:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;                       /* diff */
    } else {
        r = mantissa >> exponent;                        /* diff */
    }

    return (r ^ -sign) + sign;                           /* diff */
}

fast_trunc_two, C:

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent) ^ -sign;             /* diff */
    } else {
        r = (mantissa >> exponent) ^ -sign;              /* diff */
    }

    return r + sign;                                     /* diff */
}

Wydaje się to samo, prawda? Cóż, GCC się nie zgadza. Po skompilowaniu z gcc -O3 -S -Wall -o test.s test.ctym jest wyjście asemblera:

fast_trunc_one, wygenerowano:

_fast_trunc_one:
LFB0:
    .cfi_startproc
    movl    4(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %edx
    andl    $8388607, %edx
    sarl    $23, %eax
    orl $8388608, %edx
    andl    $255, %eax
    subl    %eax, %ecx
    movl    %edx, %eax
    sarl    %cl, %eax
    testl   %ecx, %ecx
    js  L5
    rep
    ret
    .p2align 4,,7
L5:
    negl    %ecx
    movl    %edx, %eax
    sall    %cl, %eax
    ret
    .cfi_endproc

fast_trunc_two, wygenerowano:

_fast_trunc_two:
LFB1:
    .cfi_startproc
    pushl   %ebx
    .cfi_def_cfa_offset 8
    .cfi_offset 3, -8
    movl    8(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %ebx
    movl    %eax, %edx
    sarl    $23, %ebx
    andl    $8388607, %edx
    andl    $255, %ebx
    orl $8388608, %edx
    andl    $-2147483648, %eax
    subl    %ebx, %ecx
    js  L9
    sarl    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_remember_state
    .cfi_def_cfa_offset 4
    .cfi_restore 3
    ret
    .p2align 4,,7
L9:
    .cfi_restore_state
    negl    %ecx
    sall    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_restore 3
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc

To ekstremalna różnica. To faktycznie pokazuje się również w profilu, fast_trunc_onejest około 30% szybsze niż fast_trunc_two. Teraz moje pytanie: co to powoduje?

Zaktualizowano, aby zsynchronizować z edycją PO

Dzięki majstrowaniu przy kodzie udało mi się zobaczyć, jak GCC optymalizuje pierwszy przypadek.

Zanim zrozumiemy, dlaczego są tak różne, najpierw musimy zrozumieć, w jaki sposób GCC optymalizuje fast_trunc_one().

Wierzcie lub nie, fast_trunc_one()jest do tego optymalizowany:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

Daje to dokładnie taki sam zestaw jak oryginał fast_trunc_one()- rejestruj nazwy i wszystko.

Zauważ, że xorw zestawie nie ma żadnych fast_trunc_one(). To mi to dało.

Jak to?

Krok 1: sign = -sign

Najpierw spójrzmy na signzmienną. Ponieważ sign = i & 0x80000000;możliwe są tylko dwie możliwe wartości sign:

• sign = 0
• sign = 0x80000000

Teraz sobie sprawę, że w obu przypadkach sign == -sign. Dlatego po zmianie oryginalnego kodu na ten:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;
    } else {
        r = mantissa >> exponent;
    }

    return (r ^ sign) + sign;
}

Tworzy dokładnie taki sam zespół jak oryginał fast_trunc_one(). Oszczędzę ci zgromadzenia, ale jest identyczne - zarejestruj nazwy i wszystko.

Krok 2: Redukcja matematyczna:x + (y ^ x) = y

signmoże przyjąć tylko jedną z dwóch wartości 0lub 0x80000000.

• Kiedy x = 0, a x + (y ^ x) = ynastępnie trywialne.
• Dodawanie i wstawianie 0x80000000jest takie samo. Odwraca bit znaku. Dlatego też obowiązuje x + (y ^ x) = yrównież, kiedy x = 0x80000000.

Dlatego x + (y ^ x)zmniejsza się do y. A kod upraszcza to:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent);
    } else {
        r = (mantissa >> exponent);
    }

    return r;
}

Ponownie, kompiluje się do dokładnie tego samego zestawu - rejestruj nazwy i wszystkie.

Ta powyższa wersja ostatecznie ogranicza się do tego:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

co jest właściwie dokładnie tym, co GCC generuje w zestawie.

Dlaczego więc kompilator nie optymalizuje fast_trunc_two()tego samego?

Kluczowym elementem fast_trunc_one()jest x + (y ^ x) = yoptymalizacja. W fast_trunc_two()tej x + (y ^ x)wypowiedzi jest podzielona całej branży.

Podejrzewam, że to może wystarczyć, aby pomylić GCC i nie przeprowadzić tej optymalizacji. (Musiałby ^ -signwyciągnąć gałąź z gałęzi i połączyć ją r + signna końcu.)

Na przykład tworzy to ten sam zestaw co fast_trunc_one():

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = ((mantissa << -exponent) ^ -sign) + sign;             /* diff */
    } else {
        r = ((mantissa >> exponent) ^ -sign) + sign;              /* diff */
    }

    return r;                                     /* diff */
}

Taka jest natura kompilatorów. Zakładanie, że pójdą najszybszą lub najlepszą ścieżką, jest dość fałszywe. Każdy, kto sugeruje, że nie trzeba nic robić w celu zoptymalizowania kodu, ponieważ „nowoczesne kompilatory” wypełniają puste pola, wykonują najlepszą pracę, robią najszybszy kod itp. W rzeczywistości widziałem, że gcc pogarsza się z wersji 3.x do 4.x przynajmniej ramię. 4.x mógł do tego czasu dogonić 3.x, ale na początku produkował wolniejszy kod. Ćwicząc, możesz nauczyć się pisać kod, aby kompilator nie musiał pracować tak ciężko, dzięki czemu zapewnia bardziej spójne i oczekiwane wyniki.

Błąd polega na twoich oczekiwaniach co do tego, co zostanie wyprodukowane, a nie co faktycznie zostało wyprodukowane. Jeśli chcesz, aby kompilator wygenerował to samo wyjście, podaj to samo wejście. Nie matematycznie to samo, nie trochę to samo, ale w rzeczywistości takie same, bez różnych ścieżek, bez operacji udostępniania lub dystrybucji z jednej wersji do drugiej. To dobre ćwiczenie na zrozumienie, jak napisać kod i zobaczenie, co z nim robią kompilatory. Nie popełnij błędu, zakładając, że ponieważ jedna wersja gcc dla jednego procesora docelowego jednego dnia dała pewien wynik, że jest to reguła dla wszystkich kompilatorów i całego kodu. Musisz użyć wielu kompilatorów i wielu celów, aby poczuć, co się dzieje.

gcc jest dość paskudne, zapraszam do spojrzenia za zasłonę, spojrzenia na wnętrzności gcc, próby dodania celu lub zmodyfikowania czegoś samemu. Z trudem utrzymuje się go za pomocą taśmy izolacyjnej i drutu ratunkowego. Dodatkowa linia kodu dodana lub usunięta w krytycznych miejscach i zawodzi. Fakt, że stworzył użyteczny kod, jest czymś, z czego można się cieszyć, zamiast martwić się, dlaczego nie spełnił on innych oczekiwań.

patrzyłeś na jakie różne wersje gcc produkują? 3.x i 4.x w szczególności 4.5 vs 4.6 vs 4.7 itd.? i dla różnych procesorów docelowych, x86, uzbrojenia, mipsa itp. lub różnych smaków x86, jeśli jest to natywny kompilator, którego używasz, 32-bitowy vs 64-bitowy itp? A potem lvv (clang) dla różnych celów?

Mystical wykonał świetną robotę w procesie myślowym wymaganym do rozwiązania problemu analizy / optymalizacji kodu, oczekując, że kompilator wymyśli coś takiego, czego nie można się spodziewać po żadnym „nowoczesnym kompilatorze”.

Bez wchodzenia we właściwości matematyczne kod tego formularza

if (exponent < 0) {
  r = mantissa << -exponent;                       /* diff */
} else {
  r = mantissa >> exponent;                        /* diff */
}
return (r ^ -sign) + sign;                           /* diff */

poprowadzi kompilator do A: zaimplementuj go w tej formie, wykonaj if-then-else, a następnie zbierz wspólny kod, aby zakończyć i powrócić. lub B: zapisz gałąź, ponieważ jest to koniec funkcji. Nie przejmuj się także używaniem lub zapisywaniem r.

if (exponent < 0) {
  return((mantissa << -exponent)^-sign)+sign;
} else {
  return((mantissa << -exponent)^-sign)+sign;
}

Następnie możesz wejść w tryb, w którym Mystical wskazał, że zmienna znakowa znika razem dla kodu tak, jak napisano. Nie spodziewałbym się, że kompilator zobaczy, że zmienna znak odeszła, więc powinieneś to zrobić sam i nie zmuszać kompilatora do prób rozgryzienia.

To idealna okazja, aby zagłębić się w kod źródłowy gcc. Wygląda na to, że znalazłeś przypadek, w którym optymalizator widział jedną rzecz w jednej sprawie, a następnie inną rzecz w innej sprawie. Następnie zrób kolejny krok i sprawdź, czy nie możesz uzyskać gcc, aby zobaczyć tę sprawę. Każda optymalizacja istnieje, ponieważ jakaś osoba lub grupa rozpoznała optymalizację i celowo ją tam umieściła. Aby ta optymalizacja była dostępna i działała za każdym razem, gdy ktoś musi ją tam umieścić (a następnie przetestować, a następnie zachować w przyszłości).

Zdecydowanie nie zakładaj, że mniej kodu jest szybsze, a więcej kodu wolniejsze, bardzo łatwo jest stworzyć i znaleźć przykłady tego, że nie jest to prawda. Często może być tak, że mniej kodu jest szybszy niż więcej kodu. Jak pokazałem od samego początku, możesz stworzyć więcej kodu, aby zapisać rozgałęzienie w tym przypadku lub zapętlenie itp., A wynik netto będzie szybszy.

Najważniejsze jest to, że podałeś kompilatorowi inne źródło i oczekiwałeś tych samych rezultatów. Problemem nie są dane wyjściowe kompilatora, ale oczekiwania użytkownika. W przypadku konkretnego kompilatora i procesora dość łatwo jest zademonstrować dodanie jednego wiersza kodu, który znacznie spowalnia działanie całej funkcji. Na przykład dlaczego zmiana a = b + 2; do a = b + c + 2; Czy _fill_in_tank_compiler_name_ generuje radykalnie inny i wolniejszy kod? Odpowiedzią jest oczywiście, że kompilator otrzymał inny kod na wejściu, więc jest to całkowicie poprawne, aby kompilator generował różne dane wyjściowe. (jeszcze lepiej jest, gdy zamieniasz dwa niepowiązane wiersze kodu i powoduje to, że dane wyjściowe zmieniają się dramatycznie). Nie ma oczekiwanego związku między złożonością i rozmiarem danych wejściowych a złożonością i rozmiarem danych wyjściowych.

for(ra=0;ra<20;ra++) dummy(ra);

Wyprodukował gdzieś pomiędzy 60-100 linii asemblera. Rozwinął pętlę. Nie policzyłem wierszy, jeśli się nad tym zastanowić, trzeba je dodać, skopiować wynik na wejście do wywołania funkcji, wykonać wywołanie funkcji, minimum trzy operacje. więc w zależności od celu, który prawdopodobnie wynosi co najmniej 60 instrukcji, 80 jeśli cztery na pętlę, 100 jeśli pięć na pętlę itp.

Mysticial podał już świetne wyjaśnienie, ale pomyślałem, że dodam, FWIW, że tak naprawdę nie ma nic fundamentalnego w tym, dlaczego kompilator dokonałby optymalizacji dla jednego, a nie drugiego.

clangNa przykład kompilator LLVM podaje ten sam kod dla obu funkcji (oprócz nazwy funkcji), dając:

_fast_trunc_two:                        ## @fast_trunc_one
        movl    %edi, %edx
        andl    $-2147483648, %edx      ## imm = 0xFFFFFFFF80000000
        movl    %edi, %esi
        andl    $8388607, %esi          ## imm = 0x7FFFFF
        orl     $8388608, %esi          ## imm = 0x800000
        shrl    $23, %edi
        movzbl  %dil, %eax
        movl    $150, %ecx
        subl    %eax, %ecx
        js      LBB0_1
        shrl    %cl, %esi
        jmp     LBB0_3
LBB0_1:                                 ## %if.then
        negl    %ecx
        shll    %cl, %esi
LBB0_3:                                 ## %if.end
        movl    %edx, %eax
        negl    %eax
        xorl    %esi, %eax
        addl    %edx, %eax
        ret

Ten kod nie jest tak krótki jak pierwsza wersja gcc z OP, ale nie tak długi jak druga.

Kod z innego kompilatora (którego nie wymienię), kompilującego dla x86_64, wytwarza to dla obu funkcji:

fast_trunc_one:
        movl      %edi, %ecx        
        shrl      $23, %ecx         
        movl      %edi, %eax        
        movzbl    %cl, %edx         
        andl      $8388607, %eax    
        negl      %edx              
        orl       $8388608, %eax    
        addl      $150, %edx        
        movl      %eax, %esi        
        movl      %edx, %ecx        
        andl      $-2147483648, %edi
        negl      %ecx              
        movl      %edi, %r8d        
        shll      %cl, %esi         
        negl      %r8d              
        movl      %edx, %ecx        
        shrl      %cl, %eax         
        testl     %edx, %edx        
        cmovl     %esi, %eax        
        xorl      %r8d, %eax        
        addl      %edi, %eax        
        ret                         

co jest fascynujące, ponieważ oblicza obie strony, ifa następnie wykorzystuje ruch warunkowy na końcu, aby wybrać właściwą.

Kompilator Open64 wytwarza:

fast_trunc_one: 
    movl %edi,%r9d                  
    sarl $23,%r9d                   
    movzbl %r9b,%r9d                
    addl $-150,%r9d                 
    movl %edi,%eax                  
    movl %r9d,%r8d                  
    andl $8388607,%eax              
    negl %r8d                       
    orl $8388608,%eax               
    testl %r8d,%r8d                 
    jl .LBB2_fast_trunc_one         
    movl %r8d,%ecx                  
    movl %eax,%edx                  
    sarl %cl,%edx                   
.Lt_0_1538:
    andl $-2147483648,%edi          
    movl %edi,%eax                  
    negl %eax                       
    xorl %edx,%eax                  
    addl %edi,%eax                  
    ret                             
    .p2align 5,,31
.LBB2_fast_trunc_one:
    movl %r9d,%ecx                  
    movl %eax,%edx                  
    shll %cl,%edx                   
    jmp .Lt_0_1538                  

i podobny, ale nie identyczny kod dla fast_trunc_two.

W każdym razie, jeśli chodzi o optymalizację, jest to loteria - taka jest ... Nie zawsze łatwo jest zrozumieć, dlaczego kod jest kompilowany w jakikolwiek sposób.