Инструкции CPU и продолжительность
У меня есть две разные программы для решения математической задачи, написанные на C ++ (программа A а также B).
A работает примерно в 10 раз лучше (по продолжительности), чем B, Теперь я посчитал выполненные инструкции процессора с помощью инструмента valgrind callgrind и понял, что программа A требуется всего 1/3 инструкций, выполняемых программой B, Я бы ожидал, что коэффициент будет около 1/10.
Я знаю, что есть инструкции процессора, которые занимают больше тактов процессора (например, доступ к памяти), но по своей конструкции A должен включать в себя кучу больше этих дорогих инструкций, чем B,
Также я не знаю, как callgrind считает такие инструкции (не смог найти ничего об этом в документации).
Кто-нибудь может дать правдоподобное объяснение этому поведению? ТИА
РЕДАКТИРОВАТЬ: (из-за комментария)
К сожалению, этот код является всеобъемлющим, чтобы разместить его здесь … обе программы выполняются на одной машине. Оба полностью распараллелены (каждый поток запускает независимую копию программы, просто должен сообщить другим потокам, когда он нашел решение). Но подсчет инструкций выполняется в одном потоке, потому что callgrind все равно выполняет последовательность программ. Как уже упоминалось A нужно гораздо больше памяти, чем B,
Я не ожидаю ответа, который был бы правильным на деньги, просто дать мне несколько советов, что может вызвать эту проблему, было бы хорошо.
Решение
Вы также не указываете платформу, на которой вы его используете, каждый ЦП имеет свой набор действий, которые нужно делать / не делать.
Например, на x86 очень мало корреляции между количеством команд и общим временем выполнения, как:
- Сначала x86 переводит инструкции во внутренние микрооперационные коды (uops) и затем запускает их, поэтому в основном выполняет код, отличный от машинного кода, видимого человеку в исполняемом файле. Это также переупорядочивает мопы, поэтому даже если вы имитируете трансляцию, вы не можете быть уверены в том, в каком порядке они выполнялись (если вы не имитируете всю архитектуру ЦП, кэшей и памяти).
- несколько мопов могут быть выполнены за один такт, или другим способом, одиночный моп может блокировать ЦП на несколько тактов, поэтому время выполнения любых двух команд x86 может отличаться в 100 раз (даже одна и та же команда в двух запусках может имеют сильно различающееся (~ 100x) время выполнения, если оно зависает при отсутствии кэша).
- доступ к памяти. Память намного медленнее, чем центральный процессор, поэтому последовательное чтение памяти в предсказуемом виде и максимально компактный объем данных (для полного повторного использования кэшей) более важны для скорости кода, чем для количества команд (алгоритма). В некоторых крайних случаях хорошо спроектированная структура данных может превзойти даже намного лучший алгоритм, такой как
std::vector<int>для ~ 100 тыс. элементов намного быстрее при случайной вставке / удалении, чем в списке, хотя вектор вставки / удаления равен O (n ^ 2), а список — только O (n). Единственная память, доступная для процессора, — это кэш L0, L1 — как на улице, L2 — как путешествие в другой город, L3 — в другую страну. Сама память почти как на луне. - другой доступ к входам / выходам … если память медленная, то доступ к диску подобен солнечному излучению (SSD) или за пределами солнечной системы (HDD).
Итак, как вы можете видеть, в крайнем случае процессор x86 может выполнять даже код, который содержит ~ 200 инструкций + обрабатывает в 30 раз больше памяти, чем обычная процедура с ~ 10 инструкциями. Различия могут быть действительно крайними в угловых случаях, которые трудно представить человеку, прочитав источник. Вот почему на x86 единственный верный способ оправдать ваши оптимизации в коде — это профилировать код с данными, достаточно близкими к реальным данным. «Оптимизация» только теоретически, биг-нотация и «интуитивное чувство» могут легко привести к обратному эффекту, что было действительно 10-20 лет назад, и даже тогда мы профилировали результат с помощью инструментов для проверки выигрышей.
Конечно, большее количество инструкций само по себе может легче выпасть из кэша, что приведет к задержке чтения инструкций, но если вы сможете создать гораздо лучшие структуры данных, тогда даже 30 кБ против 1 кБ кода могут быть оправданы (хотя это может привести к большим потерям кеша) пока прерывается ОС).
Сеть Callgrind говорит: «Опционально, симуляция кэша и / или прогноз ветвления (аналогично Cachegrind) могут дать дополнительную информацию о поведении приложения во время выполнения»., таким образом, вы можете получить даже более точные данные, чем количество команд, и посмотреть, есть ли какое-то узкое место, где реорганизация кода / данных сделает его остановленным.
Другие решения
Других решений пока нет …