Выбор ответа Senior Производительность и кеш обновлено
Отсортированный массив быстрее
Вопрос
Цикл for (int x : v) if (x >= 128) sum += x; по vector<int> со значениями 0..255 работает в несколько раз быстрее, если v предварительно отсортировать. Почему?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Условие стало предсказуемым, ошибок предсказания почти нет. Объём и порядок обращений к памяти одинаковы, отличается только последовательность исходов условия.
Варианты ответа
- Отсортированный массив лучше ложится в кеш процессора
- Условие стало предсказуемым, ошибок предсказания почти нетправильный ответ
- После сортировки компилятор видит порядок и убирает условие
- Отсортированный массив занимает меньше памяти после сжатия
Разбор
Объём и порядок обращений к памяти одинаковы, отличается только последовательность исходов условия. На случайных данных предсказатель ошибается в половине случаев, каждая ошибка сбрасывает конвейер. На отсортированных сначала всегда «нет», потом всегда «да». (Иногда компилятор сам делает код безветвленным через cmov или векторизацию, и разница пропадает.)
- Кешу всё равно: данные читаются подряд в обоих случаях.
- Условие остаётся, оно просто хорошо предсказывается.
- Размер не меняется.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.