Przyspieszenie if/else, gdy warunek jest nieprzewidywalny

Question

Mam taką funkcję:

uint64_t funct()
{
    if(x >> 63)
    {
        x = x * a + b;
    }
    else
    {
        x = (x >> 1) * c + d;
    }
    return x;

x,a,b,c,d to liczby 64-bitowe. x jest liczbą pseudo-losową (generowaną za pomocą generatora PRNG), a zatem nie jesteśmy w stanie przewidzieć jej ostatniego bitu obliczanego w warunku x >> 63.

Czy to da się zaprogramować szybciej? Próbowałem kilku najprostszych rozwiązań, np. zapisania tego tak:

x = ((x >> 63) * (x * key[0] + key[1])) + ((1^(x >> 63)) * ((x >> 1) * key[2] + key[3]));

Próbowałem też usunąć else. Wszystko to działa nawet wolniej niż proste if/else. Czytałem trochę o branching i powoli tracę nadzieję, że da się to przyspieszyć. Jeżeli w warunku znajdzie się z np. k & 1, gdzie k zmienia się od 0 do 3: 0,1,2,3,0,1,2,3,... to kod przyspiesza znacząco. A zatem samo mnożenie z dodawaniem zajmuje tylko połowę tego co instrukcja if/else - tak kosztowna jest ona w tym przypadku.

Ponoć takie problemy można przyspieszyć w ramach mikro-optymalizacji, ale jak dokładnie się to robi? To jest wąskie gardło programu i ta funkcja jest wykonywana bez przerwy, jeżeli jej nie przyspieszę, to niewiele jest do optymalizacji w reszcie kodu.

Comments

Przede wszystkim... ta funkcja nie bierze w ogóle argumentów? `x, a, b, c, d` to jest stan globalny w pamięci?

---

Bo to co napisałeś oryginalnie to przepięknie się kompiluje z normalnymi argumentami:

https://godbolt.org/z/79caebnje

---

Tak, można równie dobrze podawać x,a,b,c,d jako argumenty. Ja akurat używam x,a,b,c,d jako zmiennych globalnych.

---

Tamtą schowałeś więc tutaj:

Nie kompiluję z optymalizacjami

To... nie ma sensu mówić o przyśpieszaniu, porównywaniu lub mierzeniu czegokolwiek. Włącz optymalizacje (profil release w C::B) i dopiero wtedy na to patrz.

Answer 1

Ja akurat używam x,a,b,c,d jako zmiennych globalnych.

To przestań :) To prawdopodobnie jedna z większych barier optymalizacji. Bez tego Twoja oryginalna funkcja jest na tyle prosta, że kompilator bez problemu ją elegancko zoptymalizuje.

Możesz pokazać, co testujesz, że wg Ciebie to jest bottleneck?

(sanity check: kompilujesz z optymalizacjami, nie? :))

Comments

Ale wynikowe xsl jest 64-bitowe. Nie mogę zrobić przesunięcia o 32 bity, skoro high32 jest 32 bitowe? Powinno być 64-bitowe?

Tak, musisz zrobić cast na uint64_t przed <<, nie po. (nie musisz na to osobnej zmiennej robić, może być wszystko w jednej linii)

Próbowałem to zmienić, ale return key nie działa, return key[] też nie działa. W każdym razie jak rozumiem funkcja może zwracać po prosu 0?

...nic nie zwracać. Dosłownie.

void funkcja() {
    cout << "nic nie zwracam!";
}

z kolei zrobienie pętli w pętli znów z jakichś tajemniczych powodów nie zmienia wyników:

Jeśli wszystkie couty masz zakomentowane, to możliwe że kompilator podczas optymalizowania że wyniki nie są do niczego nie używane i kompletnie wyrzuca pętle. Spróbuj wrzucić cout wyniku po wszystkich pętlach.

(Ale to tylko mój strzał, co się może dziać. )

---

Wypisuje liczby, ale nie mierzy czasu poprawnie:

#include <iostream>
#include <cmath>
#include <stdio.h>

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    return LCG_state;
}

int main()
{
    uint64_t LCG_state = 333;
    uint32_t wynik;

    for(int i=0; i<50; i++)
    {
    for(int i=0; i<640000000; i++)
    {
        LCG_state = LCG(LCG_state);
        wynik = LCG_state >> 32;
        //std::cout << wynik << "\n";
    }
    std::cout << wynik << "\n";
    }
}

Niezależnie ile się wpisze powtórzeń do pierwszej pętli, zawsze jest to około 0,028 s. Takiego problemu nie ma w moim kodzie:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>

uint64_t XSLRRRR(uint64_t xsl)
{
    uint8_t count1;
    uint8_t count2;
    uint32_t low32;
    uint32_t high32;
    uint32_t x1;
    uint32_t x2;

    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = ((uint64_t)high32 << 32) | low32;
    return xsl;
}

uint64_t funct(uint64_t x, uint64_t key[])
{
    if(x >> 63)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    return x;
}

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

void keymix(uint64_t x, uint64_t key[], uint64_t coefficients[], int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
}

int main()
{
    uint64_t LCG_state = 999111;

    uint64_t coefficients[4] = {3,5,7,9};
    uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint64_t x;
    int k = 0;
    uint32_t result;

    for(int i=0; i<50; i++)
    {
    for(int i=0; i<10000000; i++)
    {
    LCG_state = LCG(LCG_state);
    x = LCG_state;

    keymix(x,key,coefficients,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x,key);
        result = x >> 32;
        //std::cout << result << "\n";
        }
    }
    }
}

 

---

A jednak wygląda na to, że te wyniki mogą być niepoprawne i nie można im ufać. Można w różny sposób zmodyfikować kod, powtórzyć niektóre operacje, a czas i tak się nie zmieni. Co więcej sposób mierzenia czasu za pomocą chrono daje 0 sekund:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <chrono>

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    return LCG_state;
}

int main()
{
auto begin = std::chrono::high_resolution_clock::now();
    uint64_t LCG_state = 333;
    uint32_t wynik;

    for(int i=0; i<640000000; i++)
    {
        LCG_state = LCG(LCG_state);
        wynik = LCG_state >> 32;
        //std::cout << wynik << "\n";
    }

auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.3f seconds.\n", elapsed.count() * 1e-9);
}

Więc właściwie nie da się porównać obu kodów, skoro jeden wykonuje się ciągle w 0 sekund.

---

Kod z __asm__ volatile("" : "+g" (result) : :); mierzy czas poprawnie:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>
#include <chrono>

uint64_t XSLRRRR(uint64_t xsl)
{
    uint8_t count1;
    uint8_t count2;
    uint32_t low32;
    uint32_t high32;
    uint32_t x1;
    uint32_t x2;

    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = ((uint64_t)high32 << 32) | low32;
    return xsl;
}

uint64_t funct(uint64_t x, uint64_t key[])
{
    if(x >> 63)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    //x = (x >> 63) * (x * key[0] + key[1]) + ((~x >> 63) * ((x >> 1) * key[2] + key[3]));
    return x;
}

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

void keymix(uint64_t x, uint64_t key[], uint64_t coefficients[], int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
}

int main()
{
auto begin = std::chrono::high_resolution_clock::now();

    uint64_t LCG_state = 999111;

    uint64_t coefficients[4] = {3,5,7,9};
    uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint64_t x;
    int k = 0;
    uint32_t result;

    for(int i=0; i<10000000; i++)
    {
    LCG_state = LCG(LCG_state);
    x = LCG_state;

    keymix(x,key,coefficients,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x,key);
        result = x >> 32;
        __asm__ volatile("" : "+g" (result) : :);
        //std::cout << result << "\n";
        }
    }
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.3f seconds.\n", elapsed.count() * 1e-9);
}

Niestety ten branching jest bardzo kosztowny. Czasy, które uzyskuję to ok. 3,382 sekund. Natomiast dla LCG:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <chrono>

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    //if (LCG_state >> 63)
    //{
    //    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    //}
    //else
    //{
    //    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    //}
    //LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841) * (LCG_state >> 63) + (LCG_state * 2862933555777941757 + 1422359891750319841) * (~LCG_state >> 63);
    return LCG_state;
}

int main()
{
auto begin = std::chrono::high_resolution_clock::now();

    uint64_t LCG_state = 333;
    uint32_t wynik;
    int r;

    //for(int i=0; i<10; i++)
    //{
    for(int i=0; i<640000000; i++)
    {
        LCG_state = LCG(LCG_state);
        wynik = LCG_state >> 32;
        __asm__ volatile("" : "+g" (wynik) : :);
        //std::cout << wynik << "\n";
    }
    //}

auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.3f seconds.\n", elapsed.count() * 1e-9);
//std::cout << wynik << "\n";
}

Jest to około 0,967 sekund. Nieco lepiej jest po usunięciu warunków i zastosowaniu wzoru:

x = (x >> 63) * (x * key[0] + key[1]) + ((~x >> 63) * ((x >> 1) * key[2] + key[3]));

Ale niewiele lepiej. Kosztowny nie jest sam warunek, bo, gdy w LCG użyjemy:

if (LCG_state >> 63)
    {
        LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    }
    else
    {
        LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    }

Czas niemal się nie zmienia. Ale w tym przykładzie, co nie będzie wynikiem warunku, program w każdym przypadku liczy to samo. Jednak, gdy zmienimy jedną z instrukcji tak, aby nie były identyczne:

if (LCG_state >> 63)
    {
        LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    }
    else
    {
        LCG_state = (LCG_state * 2862933555777941757 + 555);
    }

To staje się to ok. 2,5-krotnie wolniejsze. Przy czym ostatni bit, który jest w warunku LCG_state >> 63 zmienia się praktycznie losowo. I ta nieprzewidywalność chyba ma znaczenie. Bo na przykład użycie bitu liczby k, która zmienia się regularnie od 0 do 3, znacznie przyspiesza program:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>
#include <chrono>

uint64_t XSLRRRR(uint64_t xsl)
{
    uint8_t count1;
    uint8_t count2;
    uint32_t low32;
    uint32_t high32;
    uint32_t x1;
    uint32_t x2;

    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = ((uint64_t)high32 << 32) | low32;
    return xsl;
}
uint64_t funct(uint64_t x, uint64_t key[], int k)
{
    if(k & 1)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    //x = (x >> 63) * (x * key[0] + key[1]) + ((~x >> 63) * ((x >> 1) * key[2] + key[3]));
    return x;
}

//x = (x >> 63) * (x * key[0] + key[1]) + ((~x >> 63) * ((x >> 1) * key[2] + key[3]));

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

void keymix(uint64_t x, uint64_t key[], uint64_t coefficients[], int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
}

int main()
{
auto begin = std::chrono::high_resolution_clock::now();

    uint64_t LCG_state = 999111;

    uint64_t coefficients[4] = {3,5,7,9};
    uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint64_t x;
    int k = 0;
    uint32_t result;

    for(int i=0; i<10000000; i++)
    {
    LCG_state = LCG(LCG_state);
    x = LCG_state;

    keymix(x,key,coefficients,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x,key,k);
        result = x >> 32;
        __asm__ volatile("" : "+g" (result) : :);
        //std::cout << result << "\n";
        }
    }
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.3f seconds.\n", elapsed.count() * 1e-9);
}

Więc na tę chwilę istnienie warunku if/else znacznie spowalnia kod w porównaniu do prostego LCG. I wydaje się tak być nie z powodu samego if/else, tylko dlatego, że musi być testowany bit, który zmienia się praktycznie losowo (tak jak pisałem, to są generatory liczb pseudolosowych, są zaprojektowane, by generować liczby właśnie w taki sposób, by symulować losowość), dopóki nie obliczymy liczby x, nie wiemy jaki bit się tam pojawi (0, czy 1).

Wydaje się, że w przypadku normalnych programów, czy nawet zwykłego generatora LCG, pewne instrukcje są wykonywane z wyprzedzeniem, podobnie jak w przypadku:

https://en.wikipedia.org/wiki/Branch_predictor

The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. As a result, making a pipeline longer increases the need for a more advanced branch predictor.

Natomiast w przypadku mojego kodu to po prostu jest niemożliwe. Oczywiście kod można bardzo łatwo zwektoryzować/zrównoleglić, czego nie można zrobić z LCG. Wystarczy w moim kodzie z wyprzedzeniem obliczyć kilka:

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;

A później dla każdego LCG_state równolegle pętle:

for(int j=0; j<64; j++)
        {
        x=funct(x,key,k);
        result = x >> 32;
        }

Ale w normalnym kodzie raczej nie da się wykorzystać tego podejścia.

---

Kosztowny nie jest sam warunek, bo, gdy w LCG użyjemy:

if (LCG_state >> 63) {

    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);

} else {

    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);

}

Tu akurat wytłumaczenie jest proste - kompilator zauważa że oba wyrażenia są identyczne i wyrzuca ifa - więc procesor w ogóle nie widzi warunku.

I nie rób tego black boxa na wartość w środku ciasnej pętli, wystarczy ją uzyć raz na końcu pętli.