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

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!

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.

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”).

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ę.

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;
}