Прискорення циклів із залежностями вчетверо за допомогою прогнозування розгалужень
Класичний цикл із залежностями між ітераціями (pointer chasing) часто впирається в затримки пам'яті. Додавши семантично марну умову if разом із приведенням до volatile, розробники можуть змусити блок прогнозування розгалужень процесора виконувати спекулятивні обчислення, що дає прискорення до 4 разів.
Вплив: Середній
Чому це важливо
Ви можете застосувати прогнозування розгалужень та volatile-приведення для обходу затримок пам'яті у критично важливих залежних циклах.
TL;DR
- 01Послідовний перехід за вказівниками або індексами у циклах створює залежність за даними, що обмежує продуктивність затримками пам'яті.
- 02Впровадження умовного перевірочного блоку та використання приведення volatile заважає оптимізації компілятора та запускає спекулятивне виконання інструкцій CPU.
- 03Дана техніка забезпечила 4-кратне прискорення в синтетичних тестах та 2-кратне прискорення при реальній компіляції через LLVM.
Ключові факти
- Синтетичне прискорення
- 4x (з 320 мкс до 80 мкс)
- Прискорення при компіляції LLVM
- 2x
Вузьке місце залежностей інструкцій
При низькорівневій оптимізації алгоритмів цикли, які виконують послідовний перехід за вказівниками або індексами (наприклад, j = next_j[i][j]), страждають від неможливості паралельного виконання інструкцій. Оскільки значення j для наступної ітерації повністю залежить від результату поточної, процесор змушений чекати завершення затримки читання з пам'яті. Це обмежує швидкість CPU затримками звернення, а не обчислювальною пропускною здатністю.
Використання прогнозування розгалужень
Щоб обійти затримки пам'яті, можна ввести умовне розгалуження, яке перевіряє, чи дійсно змінюється j. Якщо змусити компілятор згенерувати розгалуження, апаратний блок прогнозування CPU вважатиме, що j залишається незмінним (що часто трапляється в алгоритмах стиснення або парсингу). Процесор почне спекулятивно виконувати наступні кроки наперед. У разі помилкового прогнозування CPU виконає відкат та застосує правильне значення.
Як перехитрити компілятор
Оскільки сучасні компілятори автоматично видаляють семантично зайві перевірки змінних у регістрах, звичайний код втратить це розгалуження. Автор обійшов це обмеження за допомогою приведення вказівника до типу volatile. Це змушує компілятор здійснити читання з пам'яті та заважає оптимізатору (CSE) видалити перевірку. У синтетичних тестах ця техніка скоротила час виконання з 320 мкс до 80 мкс (прискорення у 4 рази).
Спробуй за 2 хвилини
// Speed up dependency-bound memory loops via branch prediction simulation
for (int i = 0; i < n; i++) {
if (j != next_j[i][j]) {
j = *(uint8_t volatile *)&next_j[i][j];
}
}cpp
✓ Коли використовувати
- При оптимізації вузьких циклів із залежностями, де індекс з високою ймовірністю залишається незмінним між ітераціями.
- Коли оптимізатор компілятора автоматично видаляє звичайні розгалуження, і потрібне примусове читання через volatile.
✕ Коли НЕ варто
- Коли індекс пошуку змінюється майже кожну ітерацію, оскільки часті помилки прогнозування розгалужень лише сповільнять код.
- У високорівневих мовах програмування (наприклад, Python або JavaScript), де низькорівневі маніпуляції з регістрами є недоступними.
Що зробити сьогодні
- Знайдіть у вашому критичному за продуктивністю C/C++ коді цикли, які виконують залежний пошук за індексами.
- Оновіть алгоритми пошуку за допомогою приведення типів до volatile для збереження розгалуження при оптимізації компілятором.
- Проведіть профілювання циклу за допомогою інструментів типу perf для верифікації реального приросту швидкості.
Що каже спільнота
“Brilliant! Hadn't seen this technique before.”
Джерела