Зачастую оптимизация противоречит интуиции

Это перевод Optimization is often counter-intuitive. Автор: Реймонд Чен.

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

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

function GetCurrentAddress: Pointer;
asm
  mov eax, [esp]
end;

// ...

var
  CurrentInstruction: Pointer;
begin
  // ...
  CurrentInstruction := GetCurrentAddress;

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

GetCurrentAddress:
    mov eax, [esp]
    ret

...
    call GetCurrentAddress
    mov [CurrentInstruction], eax

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

var
  CurrentInstruction: Pointer;
label
  L1;
begin
  // ...
  asm
       call L1
   L1: pop CurrentInstruction
  end;

"Тут вдвое меньше инструкций, чем в вашем раздутом girly-code!"

Но если вы сядете и запустите оба фрагмента, вы можете обнаружить, что первый вариант с вызовом функций быстрее в два раза! Как такое может быть?

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

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

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

Вот почему наша "оптимизация" стала работать ещё медленнее. Предположим, что в момент выполнения инструкции CALL L1 стек адресов возврата предсказателя переходов выглядел так:

Адрес возврата Стек предсказателя:		caller1	->	caller2	->	caller3	->	...
Действительный стек:		caller1	->	caller2	->	caller3	->	...

Тут, caller1 - вызывающий функции, caller2 - вызывающий вызывающего функцию и т.д. Пока стек предсказателя переходов соответствует действительности (я нарисовал действующий стек под стеком предсказателя переходов, чтобы вы могли увидеть, что они соответствуют друг другу).

Теперь вы выполняете инструкцию CALL. Стек предсказателя переходов и программный стек теперь выглядят вот так:

Адрес возврата Стек предсказателя:		L1	->	caller1	->	caller2	->	caller3	->	...
Действительный стек:		L1	->	caller1	->	caller2	->	caller3	->	...

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

Адрес возврата Стек предсказателя:		L1	->	caller1	->	caller2	->	caller3	->	...
Действительный стек:		caller1	->	caller2	->	caller3	->	caller4	->	...

Думаю вы видите, к чему я клоню.

Потом ваша функция возвращает управление. Процессор декодирует вашу команду RET, он смотрит на адрес в стеке предсказателя переходов и говорит: "что-то подсказывает мне, что эта команда RET вернёт управление на L1. Я начну предварительное выполнение команд оттуда".

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

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

Адрес возврата Стек предсказателя:		caller1	->	caller2	->	caller3	->	...
Действительный стек:		caller2	->	caller3	->	caller4	->	...

Затем ваш вызывающий вернёт управление. И снова, процессор проконсультируется со стеком предсказателя переходов и начнёт спекулятивное выполнение инструкций по адресу caller1. Но вы возвращаетесь не туда - на самом деле вы вернётесь к caller2.

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

Ваша оптимизация "через щель" оказалась недальновидной.

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

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