Mediumbranch-prediction
Что такое branch prediction и как влияет на производительность?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Branch prediction — CPU спекулятивно выполняет ветвь if до разрешения условия. Угадал — без задержки; ошибся — pipeline flush (10–20 тактов). Предикторы точны (>95%), но плохо предсказуемые ветви (if (arr[i] < t) по случайным данным) дороги.
// Ветвление: при случайных данных много mispredictions
for (int x : data)
if (x < threshold) ++count;
// Branchless: cmov, нет ветви вообще
count += (x < threshold); // bool → 0/1
// Сортировка делает ветвь предсказуемой (all true, потом all false)
std::sort(data.begin(), data.end());Branchless-приёмы: тернар x = cond ? a : b; → cmov, bit-tricks (cond != 0) * value. Профайлеры perf, VTune показывают branch-miss rate.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.