Методы оптимизации для С++

В своем разговоре несколько дней назад в Facebook - slides, видео, переговоры Андрея Александреску об общих интуициях, которые могут оказаться неправильными. Для меня очень интересный момент появился на Слайде 7, где он утверждает, что предположение "Меньше инструкций = более быстрый код" неверно, и больше инструкций не обязательно означает более медленный код.

Вот моя проблема: качество звука в его разговоре (около 6: 20 минут) не так уж хорошо, и я не очень хорошо понимаю это объяснение, но из того, что я получаю, заключается в том, что он сравнивает устаревшие инструкции с оптимальностью алгоритм на уровне производительности.

Однако, по моему мнению, это невозможно сделать, потому что это два независимых структурных уровня. Инструкции (особенно на самом деле отставные инструкции) являются одной очень важной мерой и в основном дают вам представление о производительности для достижения цели. Если мы откажемся от латентности инструкции, мы можем обобщить, что меньше выбывших команд = более быстрый код. Теперь, конечно, бывают случаи, когда алгоритм, выполняющий сложные вычисления внутри цикла, даст лучшую производительность, даже если он выполняется внутри цикла, потому что он рано сломает цикл (подумайте об обходе графика). Но разве было бы более полезно сравнивать с алгоритмами на уровне сложности, а не говорить, что этот цикл содержит больше инструкций и лучше другого? С моей точки зрения, лучший алгоритм в конце концов будет иметь меньше отставших команд.

Может кто-нибудь, пожалуйста, помогите мне понять, куда он идет с его примером, и как может быть случай, когда (значительно) более отставные инструкции приводят к лучшей производительности?

Ответ 1

Качество действительно плохое, но я думаю, что он приводит к тому, что процессоры хороши для вычислений, но страдают от плохой производительности для поиска в памяти (оперативная память намного медленнее CPU) и ветвей (потому что CPU работает как конвейер, и ветки могут привести к разрыву трубопровода).

Вот некоторые случаи, когда более быстрые инструкции:

Прогнозирование ветвей - даже если нам нужно сделать больше инструкций, но это вызывает лучшее предсказание отрасли, конвейер процессора будет больше времени, и меньше оптов будет "выброшено" из него, что в конечном итоге приведет к повышению производительности. Этот поток, например, показывает, как делать то же самое, но сначала сортировка - улучшает выполнение.
Кэш ЦП - если ваш код оптимизирован с учетом кеша и следует за принцип локальности - он скорее будет быстрее, чем код, который этого не делает, даже если код, который не выполняет половину объема инструкций, Этот поток дает пример для небольшой оптимизации кеша - то же количество инструкций может привести к значительно более медленному коду, если он не оптимизирован для кеширования.
Также важно, какие инструкции выполняются. Иногда - некоторые инструкции могут выполняться медленнее, чем другие, например - divide может быть медленнее, чем целое дополнение.

Примечание: все вышеперечисленное зависит от машины и как/если они действительно изменяют производительность, может отличаться от одной архитектуры к другой.

Ответ 2

Количество инструкций не является хорошей мерой.

Меньше отставших команд (потому что больше нечего делать) = более быстрый код.

Меньше отставных инструкций (потому что они должны ждать зависимостей) = более медленный код.

Иногда бывает, что больше инструкций в коде также означает больше отставших команд, потому что они могут использовать слоты для выполнения, которые в противном случае были бы потрачены впустую в случае 2.