Jak mogę zrobić kod bez rozgałęzień?

Związane z tą odpowiedzią: https://stackoverflow.com/a/11227902/4714970

W powyższej odpowiedzi wspomniano, jak można uniknąć przewidywania gałęzi, unikając gałęzi.

Użytkownik demonstruje to zastępując: 

if (data[c] >= 128)
{
    sum += data[c];
}

Z: 

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

W Jaki Sposób te dwa równoważne (dla konkretnego zbioru danych, a nie ściśle równoważne)?

Jakie są ogólne sposoby, w jakie mogę robić podobne rzeczy w podobnych sytuacjach? Czy zawsze będzie to za pomocą >> i ~?

Author: Community, 2015-08-20
Source

3 answers

int t = (data[c] - 128) >> 31;

Sztuczka polega na tym, że jeśli data[c] >= 128, to data[c] - 128 jest nonnegatywne, w przeciwnym razie jest ujemne. Najwyższy bit int, bit znaku, wynosi 1 wtedy i tylko wtedy, gdy liczba ta jest ujemna. >> jest przesunięciem, które rozszerza bit znaku, więc przesunięcie w prawo o 31 sprawia, że cały daje 0, jeśli kiedyś był nieujemny, i wszystkie 1 bity (które reprezentują -1), jeśli kiedyś był ujemny. Więc t jest 0 Jeśli data[c] >= 128, i -1 w przeciwnym razie. ~t przełącza te możliwości, więc ~t jest -1 jeśli data[c] >= 128 i 0 inaczej.

x & (-1) jest zawsze równa x, a {[16] } jest zawsze równa 0. Więc sum += ~t & data[c] zwiększa sum o 0 jeśli data[c] < 128, I O data[c] w przeciwnym razie.

Wiele z tych sztuczek można zastosować gdzie indziej. Ta sztuczka z pewnością może być ogólnie zastosowana, aby liczba była 0 wtedy i tylko wtedy, gdy jedna wartość jest większa lub równa innej wartości, i -1 w przeciwnym razie, i można z nią bałagan więcej, aby uzyskać <=, <, i tak dalej. Trochę wijące się jak jest to powszechne podejście do tworzenia operacji matematycznych bez gałęzi, choć z pewnością nie zawsze będzie zbudowane z tych samych operacji; ^ (xor) i | (or) również wchodzą czasami w grę.
 27
Author: Louis Wasserman,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-08-20 08:28:56

Chociaż odpowiedź Louisa Wassermana jest prawidłowa, chcę pokazać ci bardziej ogólny (i dużo jaśniejszy) sposób pisania kodu bez rozgałęzień. Możesz po prostu użyć operatora ? :: 

    int t = data[c];
    sum += (t >= 128 ? t : 0);

JIT kompilator widzi z profilu wykonania, że warunek jest źle przewidywany tutaj. W takich przypadkach kompilator jest wystarczająco inteligentny, aby zastąpić warunkową gałąź instrukcją ruchu warunkowego: 

    mov    0x10(%r14,%rbp,4),%r9d  ; load R9d from array
    cmp    $0x80,%r9d              ; compare with 128
    cmovl  %r8d,%r9d               ; if less, move R8d (which is 0) to R9d

Możesz sprawdzić, czy ta wersja działa równie szybko zarówno dla sortowanych, jak i niesortowanych / align = "left" /

 15
Author: apangin,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-08-20 00:52:08

Kod Bezgałęziowy oznacza zazwyczaj ocenę wszystkich możliwych wyników instrukcji warunkowej z wagą ze zbioru [0, 1], tak aby suma{ weight_i } = 1. Większość obliczeń jest zasadniczo odrzucana. Pewna optymalizacja może wynikać z faktu, że E_i nie musi być poprawna, gdy Odpowiednia Waga w_i (lub maska m_i) wynosi zero.

  result = (w_0 * E_0) + (w_1 * E_1) + ... + (w_n * E_n)    ;; or
  result = (m_0 & E_0) | (m_1 & E_1) | ... | (m_n * E_n)

Gdzie m_i oznacza maskę bitową.

Prędkość można osiągnąć również poprzez równoległe przetwarzanie E_i z załamaniem poziomym.

Jest to sprzeczne z semantyką if (a) b; else c; lub jest to trójkowy Skrót a ? b : c, gdzie oceniane jest tylko jedno wyrażenie z [b, c].

Tak więc operacja trójwarstwowa nie jest magiczną kulą dla kodu bez rozgałęzień. Porządny kompilator wytwarza bezgałęziowy kod tak samo dla 

t = data[n];
if (t >= 128) sum+=t;

Vs. 

    movl    -4(%rdi,%rdx), %ecx
    leal    (%rax,%rcx), %esi
    addl    $-128, %ecx
    cmovge  %esi, %eax

Wariacje kodu bezgałęziowego obejmują przedstawienie problemu za pomocą innych bezgałęziowych funkcji nieliniowych, takich jak ABS, jeśli występują w maszyna celownicza.

Np. 

 2 * min(a,b) = a + b - ABS(a - b),
 2 * max(a,b) = a + b + ABS(a - b)

Lub nawet: 

 ABS(x) = sqrt(x*x)      ;; caveat -- this is "probably" not efficient

Oprócz << i ~ równie korzystne może być użycie bool i !bool zamiast (ewentualnie niezdefiniowanego) (int >> 31). Podobnie, jeśli warunek jest oceniany jako [0, 1] , można wygenerować działającą maskę z negacją: 

-[0, 1] = [0, 0xffffffff]  in 2's complement representation
 9
Author: Aki Suihkonen,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-08-20 11:26:12