Код без розгалужень у

Про концепцію Код без розгалужень

Концепція умовних конструкцій знайомить із jcc, родиною інструкцій для розгалужень за умовою. jcc передає керування в іншу точку програми лише тоді, коли виконується її умова.

Однак сучасні процесори швидкі й здатні виконувати багато інструкцій паралельно. Було б надто дорого зупиняти всю роботу, поки процесор чекає на перевірку умови під час виконання.

Саме тому всередині процесор не чекає. Він використовує передбачувач розгалужень, щоб угадати результат умови, і починає спекулятивно виконувати передбачений шлях.

Якщо передбачення правильне, виконання триває так, ніби розгалуження не було. Якщо ж передбачення хибне, процесор мусить відкинути виконану роботу на передбаченому шляху й почати заново на правильному.

Це називають помилкою передбачення розгалуження, і вона дорого коштує, спричиняючи затримку.

Коли розгалуження важко передбачити, ці помилки накопичуються. У таких випадках іноді краще взагалі обійтися без розгалуження, щоб ті самі інструкції виконувалися незалежно від умови. Код, який вибирає між значеннями без jcc, називають кодом без розгалужень.

Є кілька способів побудувати код так, щоб він розгалужувався рідше, або щоб наявні розгалуження були передбачуванішими. Зокрема, x86-64 надає дві родини інструкцій, які часто використовують для написання коду без розгалужень.

Умовні переміщення

Родина інструкцій cmovcc копіює операнд-джерело в операнд призначення лише тоді, коли виконується певна умова. Інакше операнд призначення залишається без змін.

Суфікс cc має ті самі назви, що й у jcc, з тим самим значенням:

Правила подібні до jcc:

1. l і g використовують для порівнянь зі знаком, а b і a - для порівнянь без знаку.
2. Додавання e до суфікса включає рівність.
3. Додавання n заперечує умову.
4. Є також варіанти, що посилаються на встановлений прапорець. Наприклад, cmovz і cmovc.

Розглянемо абсолютне значення цілого числа зі знаком у rdi, яке повертається в rax. Записана через jcc, функція вибирає один із двох шляхів:

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

Записана через cmovcc, вона обчислює обидва можливі значення безумовно, а умовне переміщення вибирає одне з них:

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; if rdi >= 0, rax = rdi
                       ; otherwise rax stays = -rdi
    ; now rax = abs(rdi)
    ret

Версія без розгалужень завжди виконує ті самі інструкції. Тут немає jcc, яке мав би вгадувати передбачувач.

Операнд призначення cmovcc мусить бути регістром. Операнд-джерело може бути регістром або коміркою памʼяті, але не безпосереднім значенням.

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF = 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

Умовне встановлення

Родина інструкцій setcc встановлює операнд призначення в 1, якщо виконується певна умова, і в 0 в іншому разі. Призначення завжди є 8-бітним операндом.

Суфікс cc має ті самі назви, що й у jcc та cmovcc. Наприклад, setz встановлює призначення в 1, якщо ZF == 1, і в 0 в іншому разі.

Оскільки призначення має 8 бітів, після setcc часто ставлять movzx, коли потрібне ширше значення:

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

Це поширений прийом, щоб перетворити результат порівняння на ціле число 0 або 1.

Коли використовувати код без розгалужень

Код без розгалужень не завжди швидший за код із розгалуженнями. Коли розгалуження добре передбачуване, передбачувач майже завжди має рацію, і jcc фактично нічого не коштує. Код без розгалужень, який замінює таке розгалуження, повільніший, бо він завжди виконує обидва можливі обчислення.

Канонічний приклад - лічильник циклу. Розглянемо функцію, яка додає rsi 64-бітних цілих чисел, починаючи з rdi:

sum_array:
    xor rax, rax
.loop:
    add rax, [rdi]
    add rdi, 8
    dec rsi
    jnz .loop          ; taken on every iteration except the last
    ret

Це саме той різновид закономірності, з яким передбачувачі розгалужень добре дають раду, тож розгалуження фактично безкоштовне, незалежно від того, скільки елементів опрацьовує sum_array.

Код без розгалужень себе виправдовує, коли розгалуження важко передбачити або коли потрібна стабільна тривалість виконання незалежно від вхідних даних.