Dlaczego kompilator nie może (lub nie może) zoptymalizować przewidywalnej pętli dodawania do mnożenia?

To pytanie, które przyszło mi do głowy, czytając genialną odpowiedź Mysticial na pytanie: dlaczego szybciej jest przetwarzać posortowaną tablicę niż nieposortowaną ?

Kontekst dla zaangażowanych typów:

const unsigned arraySize = 32768;
int data[arraySize];
long long sum = 0;

W swojej odpowiedzi wyjaśnia, że ​​kompilator Intel (ICC) optymalizuje to:

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            sum += data[c];

... w coś równoważnego z tym:

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

Optymalizator rozpoznaje, że są one równoważne i dlatego wymienia pętle , przesuwając gałąź poza pętlę wewnętrzną. Bardzo mądry!

Ale dlaczego tego nie robi?

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

Miejmy nadzieję, że Mysticial (lub ktokolwiek inny) może udzielić równie genialnej odpowiedzi. Nigdy wcześniej nie dowiedziałem się o optymalizacjach omówionych w tym drugim pytaniu, więc jestem za to naprawdę wdzięczny.

Kompilator nie może generalnie przekształcić

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

w

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

ponieważ ta ostatnia może prowadzić do przepełnienia liczb całkowitych ze znakiem, podczas gdy pierwsza nie. Nawet przy gwarantowanym zachowaniu zawijania dla przepełnienia liczb całkowitych dopełniających do dwóch ze znakiem, zmieniłoby to wynik (jeśli data[c]wynosi 30000, produkt stałby się -1294967296dla typowych 32-bitowych ints z zawijaniem, a 100000 razy dodając 30000 do sum, jeśli to nie przepełnia, należy zwiększyć sumo 3000000000). Należy zauważyć, że to samo dotyczy wielkości bez znaku, z różnymi liczbami, przepełnienie 100000 * data[c]zwykle wprowadzałoby modulo redukcyjne, 2^32które nie może pojawić się w wyniku końcowym.

Może to przekształcić w

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000LL * data[c];  // resp. 100000ull

chociaż, jak zwykle, long longjest wystarczająco większy niż int.

Dlaczego tego nie robi, nie potrafię powiedzieć, myślę, że to właśnie powiedział Mysticial , „najwyraźniej nie wykonuje przejścia z zapadaniem pętli po wymianie pętli”.

Zauważ, że sama wymiana pętli nie jest ogólnie poprawna (dla liczb całkowitych ze znakiem), ponieważ

for (int c = 0; c < arraySize; ++c)
    if (condition(data[c]))
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

może prowadzić do przepełnienia

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (condition(data[c]))
            sum += data[c];

nie. Jest tutaj koszerny, ponieważ warunek zapewnia, data[c]że wszystkie dodane elementy mają ten sam znak, więc jeśli jeden się przepełni, oba mają ten sam znak.

Nie byłbym jednak zbyt pewien, czy kompilator wziął to pod uwagę (@Mysticial, czy mógłbyś spróbować z warunkiem takim data[c] & 0x80lub takim, który może być prawdziwy dla wartości dodatnich i ujemnych?). Miałem kompilatory, które dokonywały nieprawidłowych optymalizacji (na przykład kilka lat temu miałem ICC (11.0, iirc) używające konwersji ze znakiem 32-bitowym int-to-double, 1.0/ngdzie nbył an unsigned int. Był około dwa razy szybszy niż gcc Ale źle, wiele wartości było większych niż 2^31, ups.).

Ta odpowiedź nie dotyczy konkretnego przypadku, do którego prowadzi łącze, ale dotyczy tytułu pytania i może zainteresować przyszłych czytelników:

Ze względu na skończoną precyzję powtarzane dodawanie zmiennoprzecinkowe nie jest równoznaczne z mnożeniem . Rozważać:

float const step = 1e-15;
float const init = 1;
long int const count = 1000000000;

float result1 = init;
for( int i = 0; i < count; ++i ) result1 += step;

float result2 = init;
result2 += step * count;

cout << (result1 - result2);

Próbny

Kompilator zawiera różne przebiegi, które dokonują optymalizacji. Zwykle w każdym przebiegu przeprowadzana jest optymalizacja instrukcji lub optymalizacja pętli. Obecnie nie ma modelu, który dokonuje optymalizacji treści pętli na podstawie nagłówków pętli. Jest to trudne do wykrycia i mniej powszechne.

Optymalizacja, która została wykonana, była niezmiennym ruchem kodu w pętli. Można to zrobić za pomocą zestawu technik.

Cóż, przypuszczam, że niektóre kompilatory mogą dokonać tego rodzaju optymalizacji, zakładając, że mówimy o arytmetyce liczb całkowitych.

Jednocześnie niektóre kompilatory mogą odmówić zrobienia tego, ponieważ zastąpienie powtarzającego się dodawania mnożeniem może zmienić zachowanie kodu związane z przepełnieniem. W przypadku typów całkowitych bez znaku nie powinno to robić różnicy, ponieważ ich zachowanie związane z przepełnieniem jest w pełni określone przez język. Ale w przypadku podpisanych może (chociaż prawdopodobnie nie na platformie uzupełniającej 2). Prawdą jest, że przepełnienie ze znakiem faktycznie prowadzi do nieokreślonego zachowania w C, co oznacza, że ​​powinno być całkowicie w porządku zignorowanie tej semantyki przepełnienia, ale nie wszystkie kompilatory są wystarczająco odważne, aby to zrobić. Często przyciąga wiele krytyki ze strony tłumu "C to tylko język asemblera wyższego poziomu". (Pamiętasz, co się stało, gdy GCC wprowadziło optymalizacje oparte na semantyce ścisłego aliasingu?)

Historycznie rzecz biorąc, GCC pokazał się jako kompilator, który ma wszystko, czego potrzeba, aby podjąć tak drastyczne kroki, ale inne kompilatory mogą wolą trzymać się postrzeganego zachowania „zamierzonego przez użytkownika”, nawet jeśli nie jest ono zdefiniowane przez język.

Teraz tak - przynajmniej Clang :

long long add_100k_signed(int *data, int arraySize)
{
    long long sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

kompiluje się z -O1 do

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        movsxd  rdx, dword ptr [rdi + 4*rsi]
        imul    rcx, rdx, 100000
        cmp     rdx, 127
        cmovle  rcx, r8
        add     rax, rcx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

Przepełnienie liczby całkowitej nie ma z tym nic wspólnego; jeśli występuje przepełnienie całkowitoliczbowe, które powoduje niezdefiniowane zachowanie, może się to zdarzyć w obu przypadkach. Oto ten sam rodzaj funkcji używanej intzamiastlong :

int add_100k_signed(int *data, int arraySize)
{
    int sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

kompiluje się z -O1 do

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        mov     edx, dword ptr [rdi + 4*rsi]
        imul    ecx, edx, 100000
        cmp     edx, 127
        cmovle  ecx, r8d
        add     eax, ecx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

Istnieje koncepcyjna bariera dla tego rodzaju optymalizacji. Autorzy kompilatorów poświęcają wiele wysiłku na redukcję siły - na przykład zastępowanie mnożenia dodawaniem i przesunięciami. Przyzwyczajają się do myślenia, że ​​mnożenie jest złe. Tak więc przypadek, w którym należy pójść w drugą stronę, jest zaskakujący i sprzeczny z intuicją. Więc nikt nie myśli o wdrożeniu tego.

Ludzie, którzy rozwijają i utrzymują kompilatory, mają ograniczoną ilość czasu i energii, którą mogą poświęcić na swoją pracę, więc generalnie chcą skupić się na tym, co ich użytkownicy najbardziej interesują: przekształcaniu dobrze napisanego kodu w szybki kod. Nie chcą tracić czasu na szukanie sposobów na przekształcenie głupiego kodu w szybki kod - do tego służy przegląd kodu. W języku wysokiego poziomu może istnieć „głupi” kod, który wyraża ważną ideę, dzięki czemu warto poświęcić czas programistom, aby to przyspieszyć - na przykład wylesianie na skróty i fuzja strumieni pozwalają programom Haskella na leniwe tworzenie pewnych rodzajów stworzył struktury danych do kompilacji w ciasne pętle, które nie alokują pamięci. Ale tego rodzaju zachęta po prostu nie ma zastosowania do przekształcania zapętlonego dodawania w mnożenie. Jeśli chcesz, żeby było szybkie,