Dlaczego kompilatory C optymalizują przełącznik, a jeśli inaczej

9

Ostatnio pracowałem nad osobistym projektem, kiedy natknąłem się na dziwny problem.

W bardzo ciasnej pętli mam liczbę całkowitą o wartości od 0 do 15. Muszę uzyskać -1 dla wartości 0, 1, 8 oraz 9 i 1 dla wartości 4, 5, 12 i 13.

Zwróciłem się do Godbolta, aby sprawdzić kilka opcji i byłem zaskoczony, że wydawało się, że kompilator nie może zoptymalizować instrukcji switch w taki sam sposób jak łańcuch if.

Link jest tutaj: https://godbolt.org/z/WYVBFl

Kod to:

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}

int b(int num) {
    num &= 0xF;

    if (num == 0 || num == 1 || num == 8 || num == 9) 
        return -1;

    if (num == 4 || num == 5 || num == 12 || num == 13)
        return 1;

    return 0;
}

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
        default:
            return 0;
    }
}

Myślałem, że b i c przyniosą takie same wyniki, i miałem nadzieję, że sam potrafię odczytać hacki bitów, aby samemu wymyślić wydajną implementację, ponieważ moje rozwiązanie (instrukcja switch - w innej formie) było dość wolne.

Dziwnie, bskompilowany do hacków bitowych, podczas gdy cbył albo prawie niezoptymalizowany, albo zredukowany do innego przypadku auzależnienia od docelowego sprzętu.

Czy ktoś może wyjaśnić, dlaczego istnieje taka rozbieżność? Jaki jest „prawidłowy” sposób optymalizacji tego zapytania?

EDYTOWAĆ:

Wyjaśnienie

Chcę, aby rozwiązanie przełącznika było najszybsze lub podobnie „czyste”. Jednak po skompilowaniu z optymalizacjami na moim komputerze rozwiązanie jest znacznie szybsze.

Napisałem szybki program do zademonstrowania, a TIO ma takie same wyniki, jak znajduję lokalnie: Wypróbuj online!

Dzięki static inlinetablicy odnośników trochę przyspieszysz: wypróbuj online!

LambdaBeta
źródło
4
Podejrzewam, że odpowiedź brzmi: „Kompilatory nie zawsze dokonują rozsądnych wyborów”. Właśnie skompilowałem twój kod do obiektu z GCC 8.3.0 -O3i skompilowałem go cdo czegoś prawdopodobnie gorszego niż alub b( cmiał dwa skoki warunkowe plus kilka bitowych manipulacji, w porównaniu do tylko jednego skoku warunkowego i prostszego manipulowania bitami b), ale nadal lepszy niż naiwny przedmiot według testów przedmiotów. Nie jestem pewien, o co tak naprawdę tutaj prosisz; prosty fakt jest taki, że kompilator optymalizacyjny może zmienić dowolne z nich w dowolne inne, jeśli tak zdecyduje, i nie ma twardych i szybkich reguł dotyczących tego, co zrobi lub nie zrobi.
ShadowRanger,
Moim problemem jest to, że muszę być szybki, ale jeśli rozwiązanie nie jest zbyt łatwe do utrzymania. Czy jest jakiś sposób na to, aby kompilator wystarczająco zoptymalizował czystsze rozwiązanie? Czy ktoś może wyjaśnić, dlaczego nie może tego zrobić w tym przypadku?
LambdaBeta
Zacznę od zdefiniowania przynajmniej funkcji jako statycznych lub - nawet lepiej - ich wstawienia.
wildplasser,
@wildplasser przyspiesza, ale ifwciąż bije switch(dziwne wyszukiwanie staje się jeszcze szybsze) [TIO do śledzenia]
LambdaBeta 10.10.19
@LambdaBeta Nie można powiedzieć kompilatorowi, aby zoptymalizował się w określony sposób. Zauważysz, że clang i msvc generują dla nich zupełnie inny kod. Jeśli nie zależy ci na tym i chcesz tylko tego, co działa najlepiej na gcc, wybierz to. Optymalizacje kompilatora oparte są na heurystyce, która nie zapewnia optymalnego rozwiązania we wszystkich przypadkach; Starają się być dobrzy w przeciętnym przypadku, a nie optymalni we wszystkich przypadkach.
Cubic

Odpowiedzi:

6

Jeśli jawnie wyliczysz wszystkie przypadki, gcc jest bardzo wydajny:

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
            case 2: case 3: case 6: case 7: case 10: case 11: case 14: case 15: 
        //default:
            return 0;
    }
}

jest po prostu skompilowany w prostej gałęzi indeksowanej:

c:
        and     edi, 15
        jmp     [QWORD PTR .L10[0+rdi*8]]
.L10:
        .quad   .L12
        .quad   .L12
        .quad   .L9
        .quad   .L9
        .quad   .L11
        .quad   .L11
        .quad   .L9
        .quad   .L9
        .quad   .L12
etc...

Zauważ, że jeśli nie default:ma komentarza, gcc wraca do swojej zagnieżdżonej wersji gałęzi.

Alain Merigot
źródło
1
@LambdaBeta Powinieneś rozważyć nieakceptowanie mojej odpowiedzi i zaakceptowanie tej, ponieważ współczesne procesory Intel mogą wykonywać dwa równoległe odczyty pamięci indeksowanej / cykl, podczas gdy przepustowość mojej sztuczki to prawdopodobnie 1 wyszukiwanie / cykl. Z drugiej strony, być może mój hack jest bardziej podatny na 4- drożną wektoryzację za pomocą SSE2 pslld/ psradlub ich 8-drożnych odpowiedników AVX2. Wiele zależy od innych cech Twojego kodu.
Iwillnotexist Idonotexist
4

Kompilatory C mają specjalne przypadki switch, ponieważ oczekują od programistów zrozumienia idiomuswitch i go wykorzystają.

Kod jak:

if (num == 0 || num == 1 || num == 8 || num == 9) 
    return -1;

if (num == 4 || num == 5 || num == 12 || num == 13)
    return 1;

nie przejdzie przeglądu przez kompetentnych programistów C; trzech lub czterech recenzentów jednocześnie wykrzyknęłoby „powinno to byćswitch !”

Kompilatory C nie warto analizować struktury ifinstrukcji do konwersji do tabeli skoków. Warunki muszą być w sam raz, a ilość możliwych zmian w wielu ifstwierdzeniach jest astronomiczna. Analiza jest zarówno skomplikowana, jak i może okazać się negatywna (jak w: „nie, nie możemy przekonwertować tych ifs na switch”).

Kaz
źródło
Wiem, dlatego zacząłem od przełącznika. Jednak w moim przypadku rozwiązanie if jest znacznie szybsze. Zasadniczo pytam, czy istnieje sposób przekonania kompilatora do zastosowania lepszego rozwiązania dla przełącznika, ponieważ był on w stanie znaleźć wzorzec w ifs, ale nie przełącznik. (Nie podoba mi się ifs, ponieważ nie są tak jasne ani
łatwe w
Pozytywne, ale nieakceptowane, ponieważ sentyment jest właśnie powodem, dla którego zadałem to pytanie. I chcą , aby użyć przełącznika, ale jest zbyt powolne w moim przypadku, chcę uniknąć if, jeśli w ogóle możliwe.
LambdaBeta
@LambdaBeta: Czy istnieje jakiś powód, aby unikać tabeli odnośników? Zrób to statici skorzystaj z inicjalizatorów C99, jeśli chcesz, aby było trochę bardziej jasne, co przypisujesz, i jest to całkowicie w porządku.
ShadowRanger,
1
Zaczynam przynajmniej odrzucić niski bit, aby optymalizator musiał wykonać mniej pracy.
R .. GitHub ZATRZYMAJ LÓD
@ShadowRanger Niestety nadal jest wolniejszy niż if(patrz edycja). @R .. Opracowałem pełne rozwiązanie bitowe dla kompilatora, którego teraz używam. Niestety w moim przypadku są to enumwartości, a nie liczby całkowite, więc hacków bitowych nie da się łatwo utrzymać.
LambdaBeta
4

Poniższy kod obliczy Twoje wyszukiwanie bez gałęzi, bez LUT, w ~ 3 cyklach zegara, ~ 4 przydatnych instrukcjach i ~ 13 bajtach wysoce-inline kodu maszynowego x86.

To zależy od reprezentacji liczb całkowitych dopełniacza 2.

Musisz jednak upewnić się, że u32i i s32typedefs naprawdę wskazują 32-bitowe typy całkowite bez znaku i ze znakiem. stdint.htypy uint32_ti int32_tbyłyby odpowiednie, ale nie mam pojęcia, czy nagłówek jest dostępny.

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}


int d(int num){
    typedef unsigned int u32;
    typedef signed   int s32;

    // const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
    // 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
    // Hexadecimal:                   F     0     5     0     F     0     5     0
    const u32 K = 0xF050F050U;

    return (s32)(K<<(num+num)) >> 30;
}

int main(void){
    for(int i=0;i<16;i++){
        if(a(i) != d(i)){
            return !0;
        }
    }
    return 0;
}

Przekonaj się tutaj: https://godbolt.org/z/AcJWWf


Na wybór stałej

Twoje wyszukiwanie obejmuje 16 bardzo małych stałych od -1 do +1 włącznie. Każdy mieści się w obrębie 2 bitów, a jest ich 16, które możemy przedstawić następująco:

// const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
// 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
// Hexadecimal:                   F     0     5     0     F     0     5     0
u32 K = 0xF050F050U;

Umieszczając je z indeksem 0 najbliższym najbardziej znaczącym bitowi, pojedyncze przesunięcie 2*numspowoduje umieszczenie bitu znakowego twojej 2-bitowej liczby w bicie znakowym rejestru. Przesunięcie w prawo 2-bitowej liczby o 32-2 = 30 bitów - znak rozszerza ją do pełnego int, kończąc lewę.

Nie będę istniał Idonotexist
źródło
To może być najczystszy sposób na zrobienie tego z magickomentarzem wyjaśniającym, jak go zregenerować. Czy możesz wyjaśnić, jak to wymyśliłeś?
LambdaBeta,
Akceptowane, ponieważ można to uczynić „czystym”, a jednocześnie jest szybkie. (za pomocą jakiejś magii preprocesora :) < xkcd.com/541 >)
LambdaBeta
1
!!(12336 & (1<<x))-!!(771 & (1<<x));
Uderza w moją bezgałęziową
0

Możesz stworzyć ten sam efekt używając tylko arytmetyki:

// produces : -1 -1 0 0 1 1 0 0 -1 -1 0 0 1 1 0 0 ...
int foo ( int x )
{
    return 1 - ( 3 & ( 0x46 >> ( x & 6 ) ) );
}

Mimo to, technicznie rzecz biorąc, jest to nadal (bitowe) wyszukiwanie.

Jeśli powyższe wydaje się zbyt tajemnicze, możesz także:

int foo ( int x )
{
    int const y = x & 6;
    return (y == 4) - !y;
}
KevinZ
źródło