Проблема второго прохода
Для достижения приемлемой точности измерений профилируемое приложение следует прогнать по крайней мере 9– 12 раз (см. "Непостоянства времени выполнения. Обработка результатов измерений"), причем каждый прогон должен осуществляться в идентичных условиях окружения. Увы! Без написания полноценного эмулятора всей системы это требование практически невыполнимо. Дисковый кэш, сверхоперативная память обоих уровней, буфера физических страниц и история переходов чрезвычайно затрудняют профилировку программ, поскольку при повторных прогонах время ее выполнения значительно сокращается.
Если мы профилируем многократно выполняемый цикл, то этим обстоятельством можно и пренебречь, поскольку время загрузка данных и/или кода в кэш практически не сказывается на общем времени выполнения цикла. К сожалению, так бывает далеко не всегда (такой случай как раз и был разобран в главе "Цели и задачи профилировки. Информация о пенальти").
Да и можем же мы наконец захотеть оптимизировать именно инициализацию приложения?! Пускай, она выполняется всего лишь один раз за сеанс, но какому пользователю приятно, если запуск вашей программы растягивается на минуты и то и десятки минут? Конечно, можно просто перезагрузить систему, но… сколько же тогда профилировка займет времени!
Хорошо. Очистить кэш данных – это вообще раз плюнуть. Достаточно считать очень большой блок памяти, намного превышающий его (кэша) емкость. Не лишнем будет и записать большой блок для выгрузки всех буферов записи (см. "Часть II. Кэш"). Это же, кстати, очистит и TLB (Translate Look aside Buffer) – буфер, хранящий атрибуты страниц памяти для быстрого обращения к ним (см. "предвыборка?"). Аналогичным образом очищается и кэш/TLB кода. Достаточно сгенерировать очень большую функцию, имеющую размер порядка 1 – 4 Мб, и при этом ничего не делающую (для определенности забьем ее NOP'ами – машинными командами "нет операции"). Всем этим мы уменьшим пагубное влияние всех, перечисленных выше эффектов, хотя и не устраним его полностью.
Увы! В этом мире есть вещи, не подвластные ни прямому, ни косвенному контролю (во всяком случае на прикладном уровне).
С другой стороны, если мы оптимизируем одну, отдельно взятую функцию, (для определенности остановимся на функции реверса строк), то как раз таки ее первый прогон нам ничего не даст, поскольку в данном случае основным фактором, определяющим производительность, окажется не эффективность кода/алгоритма самой функции, а накладные расходы на загрузку машинных инструкций в кэш, выделение и проецирование страниц операционной системой, загрузку обрабатываемых функцией данных в сверхоперативную память… В реальной же программе эти накладные расходы как правило уже устранены (даже если эта функция вызывается однократно).
Давайте проведем следующий эксперимент. Возьмем следующую функцию и десять раз подряд запустим ее на выполнение, замеряя время каждого прогона.
#define a (int *)((int)p + x)
A_BEGIN(0)
#define b (int *)((int)p + BLOCK_SIZE - x - sizeof(int))
for (x = 0; x < BLOCK_SIZE/2; x+=sizeof(int))
{
#ifdef __OVER_BRANCH__
if (x & 1)
#endif
*a = *a^*b; *b = *b^*a; *a = *a^*b;
}
A_END(0)
Листинг 9 Пример функции, однократно обращающийся к каждой загруженной в кэш ячейке
Для блоков памяти, полностью умещающихся в кэш-памяти первого уровня, на P-III 733/133/100/I815EP мы получим следующий ряд замеров:
__OVER_BRANCH__ not define __OVER_BRANCH__ is define
68586 63788
17629 18507
17573 18488
17573 18488
17573 18488
17573 18488
17573 18488
17573 18488
Обратите внимание: время выполнения первого прогона функции (не путать с первой итерации цикла!) практически вчетверо превосходит все последующие! Причем, результаты замеров непредсказуемым образом колеблются от 62.190 до 91.873 тактов, что соответствует погрешности ~50%.
Означает ли это, что если данный цикл в реальной программе исполняется всего один раз, то оптимизировать его бессмысленно? Конечно же нет! Давайте, для примера избавимся от этого чудачества с XOR и как нормальные люди обменяем два элемента массива через временную переменную. Оказывается, это сократит время первого прогона до 47.603 – 65.577 тактов, т.е. увеличит эффективность его выполнения на 20% – 40%!
Тем не менее, устойчивая повторяемость результатов начинается лишь с третьего прогона! Почему так медленно выполняется первый прогон – это понятно (загрузка данных в кэш и все такое), но вот что не дает второму показать себя во всю мощь? Оказывается – ветвления. За первый прогон алгоритм динамического предсказания ветвлений еще не накопил достаточное количество информации и потому во втором прогоне еще давал ошибки, но начиная с третьего наконец-то "въехал" в ситуацию и понял, что от него ходят.
Убедиться, что виноваты именно ветвления, а ни кто ни будь другой, позволяет следующий эксперимент: давайте определим __OVER_BRANCH__ и посмотрим как это скажется на результат. Ага! Разница между вторым и третьим проходом сократилась с 0,3% до 0,1%. Естественно, будь наш алгоритм малость поразлапистее (в смысле – "содержи побольше ветвлений"), и всех трех прогонов могло бы не хватить для накопления надежного статистического результата. С другой стороны, погрешность, вносимая переходами, крайне невелика и потому ей можно пренебречь. Кстати, обратите внимание, что постоянство времени выполнения функции на всех последних проходах соблюдается с точностью до одного такта!
Таким образом, при профилировании многократно выполняющихся функций, результаты первых двух – трех прогонов стоит вообще откинуть, и категорически не следует их арифметически усреднять.
Напротив, при профилировании функций, исполняющихся в реальной программе всего один раз, следует обращать внимание лишь на время первого прогона и отбрасывать все остальные, причем, при последующих запусках программы необходимо каким либо образом очистить все кэши и все буфера, искажающие реальную производительность.
