Один и тот же фильтр втрое быстрее на отсортированных данных
int64_t sum = 0;
for (uint8_t v : samples) // 100 млн значений 0..255
if (v >= 128) sum += v;
На случайных данных цикл выполняется 0,9 с, а после std::sort(samples) — 0,3 с, хотя сама сортировка в замер не входит и работы для цикла столько же. perf stat на случайных данных показывает около 25% branch-misses. Почему так и как убрать зависимость?
- Промахи предсказателя; переписать без ветвления
- Отсортированные данные сжимаются процессором
- После сортировки компилятор пропускает половину
- Случайные данные не помещаются в кэш L1