Так потрібно позбавлятися від розгалужень? — На прикладі sign, abs, min і max

Я б хотів запропонувати співтовариству взяти участь у пробному експерименті. Суть його полягає в тому, щоб прогнати на своєму комп'ютері програму, написану на C++, і поділитися результатом вимірювання часу, який вона видає, порівнюючи швидкість роботи функцій sign(x), abs(x), min(a,b) і max(a,b) у виконанні з розгалуженням і без нього. У статті я поясню свою мотивацію, покажу самі функції, а в кінці запропоную умови участі в експерименті та його (на жаль) обмеження.



Мотивація
Серед програмістів, особливо тих, хто навчався програмувати десь в кінці 90-х, досі жваво стійке переконання, що алгоритм без розгалужень краще, ніж алгоритм з ветвлениями. Я нерідко зустрічав надзвичайну фанатичність у спробах реалізувати ряд простих функцій без розгалужень тільки з-за того, що програмісту здається, ніби так буде ефективніше. Серед таких простих функцій я особливо виділив поки чотири: знак числа, абсолютне значення числа, мінімум і максимум (в двох варіантах: для чисел зі знаком і без знака). Якщо мій експеримент виявиться вдалим, я візьмуся й за багато інші алгоритми.

Правда, що без IF швидше?
Ні, це неправда. Якщо бути більш точним, то позбавлення від розгалужень може дати приріст швидкості, так і погіршити ситуацію в кілька разів. Все залежить від конкретної машини, на якій даний код буде виконуватися, і від компілятора. Наведу як приклад свій старий комп'ютер Core 2 Duo E8400 @3ГГц – на ньому всі запропоновані функції працюють швидше у варіанті з IF, коли дані подаються впорядковано і ситуація може стати зворотного хаотичної подачі (подробиці нижче). Компілятор у мене VC++ 2015, опція компіляції /Ox.

Давайте розглянемо трохи докладніше ті функції, що я пропоную протестувати. Кожна із чотирьох функцій може бути написана півдюжиною варіантів, які Ви можете вивчити самостійно по посиланнях [1-7] у кінці статті. Всі ці варіанти я вже тестував і вибрав для кожної функції два: класичний і який-небудь без розгалужень (найкращий за моїми вимірами). Якщо, знову ж таки, мій експеримент виявиться вдалим, я проведу схоже порівняння взагалі всіх відомих мені варіантів [4-7].

Для початку я вводжу свої псевдоніми для типів даних і константу для зсуву:

typedef int32_t i32;
typedef uint32_t u32;
typedef int8_t sign_t;
const u32 SHIFT = 31;


Знак числа – sign
Класичний варіант реалізується нескладною схемою з умов:
sign_t sign0 (i32 a) {
if (a>0) return +1;
if (a<0) return -1;
return 0;
}

Найкращий варіант без розгалужень виглядає наступним чином:
sign_t sign1 (i32 a) {
return (a >> SHIFT) | ((u32)(-a) >> SHIFT);
}

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

На моєму процесорі різниця між цими двома функціями досить помітна. Я прогнав їх на всіх можливих числах з робочого діапазону і перша спрацювала за 2,87 секунди, а друга тільки за 3,97 при впорядкованої подання чисел та 13,02 vs 1,26 при хаотичною.

Абсолютне значення – abs
Тут ситуація дещо краща. Перша функція IF, може виглядати, наприклад, так:
u32 abs0 (i32 a) {
if (a<0) return -a;
return a;
}

А без розгалуження самий кращий (на мій погляд) варіант має вигляд:
u32 abs1 (i32 a) {
const i32 b = a >> SHIFT; 
return (a+b) ^ b;
}


Час роботи першої 2,29, а другий — 2,33 при впорядкованої подачі і 12,01 vs 0,81 при хаотичною. Прошу звернути увагу: програміст часто не знає, що компілятор може сам зробити код без розгалужень для abs, який буде за логікою повністю збігатися з другим варіантом [3]. Таким чином, якщо в програмі є IF, це не означає, що після компіляції розгалуження залишиться. Мій компілятор генерує код з розгалуженням.

Мінімум і максимум зі знаком — mini і maxi
Комусь може здатися, що класичний варіант таких функції буде виглядати ось так:
i32 mini0 (i32 a, i32 b) {
return a<b ? a:b;
}
i32 maxi0 (i32 a, i32 b) {
return a>b ? a:b;
}

Насправді (і для мене це абсолютно незрозуміло) ось такий варіант в півтора рази швидше:
i32 mini0 (i32 a, i32 b) {
return a>b ? b:a;
}
i32 maxi0 (i32 a, i32 b) {
return a<b ? b:a;
}


Я виявив це, коли порівнював різні варіанти реалізації, але конкретної відповіді так і не знайшов. Коли дивився асемблерний лістинг, то виявив, що різниця тільки в порядку порівняння (a порівнюємо з b, або навпаки). Підозрюю, що справа в мікроархітектурі процесора. Аналогічно, я вже помічав, що команда inc ecx працює значно повільніше, ніж lea eax, [eax+1], що теж незрозуміло як можна пояснити, якщо не кривизною мікроархітектури.

Варіант без розгалужень для функцій мінімуму та максимуму в моєму репертуарі тільки один (який коректно працює для всіх можливих вхідних даних):

i32 mini1 (i32 a, i32 b) {
i32 d = a-b;
return a - (d&(~(d^((a^b)&(d^a))) >> SHIFT));
}
i32 maxi1 (i32 a, i32 b) {
i32 d = a-b;
return b + (d&(~(d^((a^b)&(d^a))) >> SHIFT));
}


Тут різниця колосальна. Перша серія функцій працює близько 3,5 секунд, друга – близько 9 на послідовних даних і 2 секунди vs 6 секунд на хаотичних. Різниця майже втричі в обох випадках.

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

Мінімум і максимум без знака — minu і maxu
Класичний варіант не змінюється, крім заміни i32 на u32:
u32 minu0 (u32 a, u32 b) {
return a>b ? b:a;
}
u32 maxu0 (u32 a, u32 b) {
return a<b ? b:a;
}

Варіант без розгалужень буде заснований на інший страшної формулою:
u32 minu1 (u32 a, u32 b) {
u32 d = a-b;
return a - (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT));
}
u32 maxu1 (u32 a, u32 b) {
u32 d = a-b;
return b + (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT));
}


Різниця в швидкості ще більше: якщо перший варіант працює все так само 3,5 секунд, то другий вже 9,5 на послідовних даних і приблизно 2 секунди проти 6 на хаотичних.

Суть і правила експерименту
Я пропоную читачам самі перевірити на своїх машинах те, яким буде результат порівняння. З цією метою була написана телепрограма (GitHub) (з урахуванням зауважень meduzik і ivas, даю виправлену програму — тестуємо обидві. В одній дані подаються послідовно, у другій — хаотично). Її потрібно скомпілювати і запустити. Працювати вона може довго, можливо, кілька хвилин, майте терпіння. Прошу обов'язково відключити інші ресурсомісткі програми на комп'ютері, коли запускаєте цю програму.

Відпрацювавши, вона видасть в STDOUT таблицю (послідовна подача даних)

sign: 2.87 vs 3.97
abs: 2.29 vs 2.33
mini: 3.46 vs 8.93
maxi: 3.45 vs 9.10
minu: 3.45 vs 9.46
maxu: 3.45 vs 9.81

У першій колонці час роботи функцій з IF, а в другій – без розгалужень. У STDERR буде виведено число, не звертайте на нього уваги, воно для правильного розуміння компілятором циклів в програмі.

Аналогічна таблиця для хаотичної подачі:

sign: 13.02 vs 1.26
abs: 12.01 vs 0.81
mini: 1.89 vs 5.97
maxi: 1.93 vs 6.31
minu: 1.89 vs 6.44
maxu: 1.92 vs 6.70

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

Відразу хочу попередити про можливі невдачі Вашого експерименту, за які я прошу мене вибачити, але я нічого не можу з цим вдіяти, як не старався.
  1. Програма не відбудеться створення. Це можливо, так як не всі компілятори розуміють std::chrono. Ще, можливо, я десь вийшов за межі Стандарту мови С++. Гарантую тільки, що код компілюється в Visual C++ 2015 і GCC 4.8.1 (з MinGW) в OS Windows 7 (64). Компилировал я саме 32-бітовий код. Я намагався спросить у грамотних людей на SO, як зробити програму краще, але поки не отримав відповіді.
  2. У Вас на машині немає знакового зсуву або від'ємні числа мають уявлення не в додатковому коді — тоді всі функції будуть працювати неправильно.
  3. Програма буде працювати не так, як повинна. Це можливо. Я вперше використовую chrono і міг помилитися. До цього завжди вимірював час через утиліту runexe, а в цій програмі мені потрібен універсальний спосіб, який працював би у більшості користувачів.
Отже, давайте разом з'ясуємо, що в якихось випадках краще і на якому процесорі.

Список джерел
  1. hacker's Delight
  2. Bit Склавши Hacks
  3. Optimized abs function
  4. Функція sign(x) — визначення знака змінної
  5. Функція abs(x) — абсолютне значення числа
  6. Функції min(a,b) і max(a,b) для чисел зі знаком
  7. Функції min(a,b) і max(a,b) для чисел без знака


Подяки
Дякую meduzik і ivas, за те, що нагадали мені про хаотичну подачу даних, про яку я випадково забув.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.