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

132

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.

c  performance  compiler-optimization 
— jhabbott
źródło
14
To jest coś, co prawdopodobnie wie tylko Intel. Nie wiem, w jakiej kolejności przeprowadza optymalizację. I najwyraźniej po wymianie pętli nie uruchamia przebiegu z zapadaniem pętli.
— Mysticial
7
Ta optymalizacja jest prawidłowa tylko wtedy, gdy wartości zawarte w tablicy danych są niezmienne. Na przykład, jeśli pamięć are mapowana jest na urządzenie wejścia / wyjścia za każdym razem, gdy odczytujesz dane [0], wygeneruje inną wartość ...
— Thomas CG de Vilhena
2
Jaki to typ danych, liczba całkowita czy zmiennoprzecinkowa? Wielokrotne dodawanie liczb zmiennoprzecinkowych daje bardzo różne wyniki z mnożenia.
— Ben Voigt
6
@ Thomas: Gdyby dane były volatile, wymiana pętli również byłaby nieprawidłową optymalizacją.
— Ben Voigt,
3
GNAT (kompilator Ada z GCC 4.6) nie przełączy pętli na O3, ale jeśli pętle zostaną przełączone, zamieni je na mnożenie.
— prosfilaes

Odpowiedzi:

105

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

— Daniel Fischer
źródło
4
Pamiętam wersję kompilatora MPW, która dodała opcję zezwalającą na ramki stosu większe niż 32K [wcześniejsze wersje były ograniczone przy użyciu adresowania @ A7 + int16 dla zmiennych lokalnych]. Wszystko było w porządku dla ramek stosu poniżej 32K lub powyżej 64K, ale dla ramki stosu 40K użyłby ADD.W A6,$A000, zapominając, że operacje na słowach z rejestrami adresowymi rozszerzają słowo do 32 bitów przed dodaniem. Zajęło trochę czasu, aby rozwiązać problem, ponieważ jedyną rzeczą, którą kod zrobił między tym ADDa następnym razem, gdy zdjął A6 ze stosu, było przywrócenie rejestrów dzwoniącego, które zapisał w tej ramce ...
— supercat
3
... a jedynym rejestrem, o który zdarzyło się zwracać wywołującemu, był adres [stała czasu ładowania] tablicy statycznej. Kompilator wiedział, że adres tablicy został zapisany w rejestrze, aby mógł na tej podstawie zoptymalizować, ale debugger po prostu znał adres stałej. Zatem przed instrukcją MyArray[0] = 4;mogłem sprawdzić adres MyArrayi przyjrzeć się tej lokalizacji przed i po wykonaniu instrukcji; to się nie zmieni. Kod był podobny move.B @A3,#4i A3 miał zawsze wskazywać na MyArraywykonanie instrukcji, ale tak się nie stało. Zabawa.
— supercat
dlaczego więc clang przeprowadza tego rodzaju optymalizację?
— Jason S
Kompilator mógłby wykonać to przepisanie w swoich wewnętrznych reprezentacjach pośrednich, ponieważ pozwala na mniej niezdefiniowane zachowanie w swoich wewnętrznych reprezentacjach pośrednich.
— user253751
48

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

— Ben Voigt
źródło
10
To nie jest odpowiedź na zadane pytanie. Pomimo interesujących informacji (które muszą znać każdy programista C / C ++), to nie jest forum i nie należy tutaj.
— orlp
30
@nightcracker: Deklarowanym celem StackOverflow jest zbudowanie przeszukiwalnej biblioteki odpowiedzi przydatnych dla przyszłych użytkowników. I to jest odpowiedź na zadane pytanie ... tak się składa, że ​​jest jakaś nieokreślona informacja, która sprawia, że ​​ta odpowiedź nie dotyczy oryginalnego plakatu. Może nadal dotyczyć innych z tym samym pytaniem.
— Ben Voigt,
12
To mogłaby być odpowiedź na tytuł pytania , ale nie pytanie, nie.
— orlp
7
Jak powiedziałem, to ciekawa informacja. Jednak nadal wydaje mi się niewłaściwe, że nota bene najlepsza odpowiedź na to pytanie nie odpowiada na to pytanie w obecnej postaci . Po prostu nie jest to powód, dla którego kompilator Intel zdecydował się nie optymalizować, basta.
— orlp
4
@nightcracker: Wydaje mi się, że to jest najlepsza odpowiedź. Mam nadzieję, że ktoś opublikuje naprawdę dobrą odpowiedź na przypadek liczby całkowitej, który przewyższa ten pod względem wyniku. Niestety, nie sądzę, aby istniała odpowiedź na „nie można” dla przypadku liczby całkowitej, ponieważ transformacja byłaby legalna, więc pozostaje nam „dlaczego nie”, co w rzeczywistości jest niezgodne z zasadą „ zbyt zlokalizowany „bliski powód, ponieważ jest charakterystyczny dla określonej wersji kompilatora. Pytanie, na które odpowiedziałem, jest ważniejsze, IMO.
— Ben Voigt
6

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.

— knightrider
źródło
4

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.

— Mrówka
źródło
Wolałbym wiedzieć, czy przypadkowo polegam na niezdefiniowanym zachowaniu, ale wydaje mi się, że kompilator nie ma możliwości tego wiedzieć, ponieważ przepełnienie byłoby problemem w czasie wykonywania: /
— jhabbott
2
@jhabbott: jeśli wystąpi przepełnienie, zachowanie jest niezdefiniowane. To, czy zachowanie jest zdefiniowane, jest nieznane do czasu wykonania (zakładając, że liczby są wprowadzane w czasie wykonywania): P.
— orlp
3

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
— Jason S.
źródło
2

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.

— zwol
źródło
3
Zastąpienie pętli obliczeniem w formie zamkniętej to także redukcja wytrzymałości, prawda?
— Ben Voigt,
Formalnie tak, tak, ale nigdy nie słyszałem, żeby ktokolwiek mówił o tym w ten sposób. (Jestem trochę przestarzały jeśli chodzi o literaturę.)
— zwol
1

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,

— dfeuer
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.