Оптимизация зачастую противоречит здравому смыслу.


Перевод с блога The Old New Thing. Оригинал здесь.

Всякий, кто занимался интенсивной оптимизацией знает, что оптимизация зачастую противоречит здравому смыслу. То, что казалось бы должно работать быстрее, на самом деле не дает ускорения.

Рассмотрим, к примеру, упражнение, где требуется получить указатель на текущую инструкцию. Вот очевидное решение:

__declspec(noinline)
void *GetCurrentAddress()
{
      return _ReturnAddress();
}


void *currentInstruction = GetCurrentAddress();

Если взглянуть на дизассемблированный код, то можно увидеть что-то вроде:

GetCurrentAddress:
      mov eax, [esp]
      ret 

      …
      call GetCurrentAddress
      mov [currentInstruction], eax

"Е-мое" — скажете вы про себя — "вы только посмотрите, насколько это неэффективно. Я могу реализовать это
всего двумя инструкциями. Смотрите:

void *currentInstruction;
__asm {
      call L1
L1: pop currentInstruction
}

В два раза меньше, чем в этой раздутой версии."

Однако если сесть и сравнить скорость работы этих двух вариантов, то вы обнаружите, что вариант с вызовом фукнции работает в два раза быстрее! Как такое может быть?

Причина кроется в так называемых "скрытых регистрах" внутри процессора. Все современные процессоры имеют намного больше регистров, чем это видно из последовательности инструкций. Существуют TLB, кеши первого и второго уровней и еще много чего, что вы не можете увидеть. В данном случае ключевую роль играет скрытый регистр под названием "предсказатель адреса возврата".

Последние модели Pentium (и я верю, что Athlon также) процессоров поддерживают внутренний стек, который
обновляется при каждой CALL и RET инструкции. Когда выполняется команда CALL, адрес возврата помещается в обычный стек (тот, на который указывает регистр ESP), а также во внутренний стек предсказания адресов возврата; команда RET извлекает адрес с вершины стека предсказания адресов и с обычного стека.

Стек предсказания адресов возврата используется в тот момент, когда процессор декодирует команду RET. Он смотрит на вершину этого стека и говорит: "Готов поспорить, что команда RET собирается вернуть управление вот на этот адрес." А затем, на основании этой информации, процессор начинает выполнять инструкции по этому адресу. Поскольку программы редко химичат с адресами возврата на стеке, то такое предсказание в подавляющем большинстве случаев оказывается верным.

Вот почему, та "оптимизация" привела к замедлению работы. Допустим, в точке команды CALL L1, стек предсказания возвратов выглядел так:

стек предсказаний: caller1 -> caller2 -> caller3 -> …
основной стек: caller1 -> caller2 -> caller3 -> …

Здесь, caller1 — это функция, вызвавшая текущую функцию, caller2 — функция, вызвавшая caller1 и так далее. Сейчас стек предсказаний отражает фактическую ситуацию. (Ниже для сравнения приведен основной стек и вы видите, что они совпадают.)

Теперь мы выполняем инструкцию CALL. После этого стеки будут выглядеть так:

стек предсказаний: L1 -> caller1 -> caller2 -> caller3 -> …
основной стек: L1 -> caller1 -> caller2 -> caller3 -> …

Но вместо выполнения инструкции RET, вы извлекаете адрес возврата из основного стека. Это удаляет его из основного стека, но не удаляет из стека предсказания возвратов.

стек предсказания возвратов: L1 -> caller1 -> caller2 -> caller3 -> …
основной стек: caller1 -> caller2 -> caller3 -> caller4 -> …

Я думаю, понятно к чему это приводит.

В конце концов, ваша функция завершается. Процессор декодирует вашу инструкцию RET и смотрит в стек предсказаний, и говорит: "Мой стек предсказаний говорит, что эта команда RET собирается передать управление функции L1. Я начинаю выполнять инструкции по тому адресу."

Но нет, значение на вершине основного стека не вовсе не L1. А caller1. Процессорный предсказатель предсказал неверно, и в результате время было потрачено на изучение неверного кода!

Эффекты от этой неверной догадки на этом не заканчитваются. После инструкции RET, стек предсказаний выгялдит так:

стек предсказаний: caller1 -> caller2 -> caller3 -> …
основной стек: caller2 -> caller3 -> caller4 -> …

Когда-нибудь завершится и caller1. И снова, процессор на основании данный из стека предсказаний начнет выполнять код функции caller1. Но теперь мы возвращается не в caller1, а в caller2.

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

Эта оптимизация оказалась близорукой.

Некоторые процессоры приокрывают свой предсказатель. Alpha AXP, к примеру, имеет несколько типов инструкций передачи управления, которые имеют один и тот же логический эффект, но по-разному работающие с внутренним стеком предсказаний процесора. Например, инструкция BR говорит: "Перейди к этому адресу, но не помещай старый адрес в стек предсказаний". С другой стороны, команда JSR говорит: "Перейди к этому адресу и помести старый адрес в стек предсказаний". Существует, также инструкция RET, говорящая: "Перейди к этому адресу и извлеки адрес из стека предсказаний" (Еще есть и четвертый тип, который редко используется.)

Мораль басни: Если что-то выглядит лучше, еще не означает, что оно лучше на самом деле.

Реклама
Запись опубликована в рубрике оптимизация. Добавьте в закладки постоянную ссылку.

Один комментарий на «Оптимизация зачастую противоречит здравому смыслу.»

  1. noop:

    А что тут необычного? Эта ситуация уже описана была не раз наравне с десятками прочих, по-моему даже в референсных мануалах, не говоря уж про неофициальные от Агнера Фога. Применению «здравого смысла» должно предшествовать ознакомление с документацией по теме, вот и все.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s