Тактическая оптимизация или результаты одного тестирования

Как-то в одном ЖЖ возникло обсуждение работы транслятора IBM для Windows с языка PL/1. Для алгоритмически довольно простого решения стационарного уравнения теплопроводности методом Либмана ответ вообще не удавалось получить, поскольку быстро возникало исключение типа «исчезновение порядка» («антипереполнение»). Мне предложили попробовать решить задачу своим транслятором, изначально разработанным для x86.

Поясню саму эту несложную задачу: матрица T (в примере 5000х5000) значений float первоначально заполняется вся нулями и единицами «по краям» - верхняя строка и левый столбец. Затем начинается длительный итерационный процесс изменения этой матрицы (N=5000):

DO L=1 TO 10000;
   DTM=0;
   DO I=2 TO N-1;
      DO J=2 TO N-1;
         T1=(T(I-1,J)+T(I+1,J)+T(I,J+1)+T(I,J-1))/4;
         DTM=MAX(ABS(T1-T(I,J)),DTM);
         T(I,J)=T1;
      END J;
   END I;
END L;

Пока я разбирался с задачей, ее заказчик сам нашел простой выход: первоначально заполнять матрицу не нулями, а некоторым исчезающе малым значением 1E-30, тогда «антипереполнение» пропадает.

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

В результате, и программа, оттранслированная компилятором IBM, и программа, оттранслированная PL/1-KT начали работать.

Задача решилась, но при этом наглядно проявилось отсутствие оптимизации в PL/1-KT. Если результат компилятора IBM позволял проводить одну итерацию в среднем за 227 мс (Intel core i5-3210M 2.50 GHz), то у компилятора PL/1-KT – лишь за 624 мс, почти втрое медленнее.

При этом все-таки, небольшая «тактическая» оптимизация в PL/1-KT имелась. Этот термин я придумал сам, увидев некоторую аналогию с терминами военного дела, где принято различать стратегический, оперативный и тактический уровни.

На мой взгляд, «стратегическая» оптимизация – нахождение лучшего решения в целом (включая и ответ на вопрос, нужно ли вообще искать решение) лежит полностью в компетенции человека. Компилятор не может понять смысл и цель решения. Может быть, когда-нибудь ИИ облегчит и эту область, но пока компиляторам остается только оперативный и тактический уровни.

«Оперативная» оптимизация – это улучшения в терминах программы, а не конкретных команд. Типичный пример – вынос общих выражений за пределы цикла.

И, наконец, нижний уровень – это «тактическая» оптимизация в пределах нескольких команд, обычно уже предварительно сгенерированных. Такая оптимизация в большинстве случаев проще «оперативной».

Разумеется, имея две небольших программы, выполняющих одни и те же действия, захотелось посмотреть, какая именно оптимизация дает наибольший вклад в быстродействие. Ведь в данном случае для оценки все эти оптимизации легко можно было повторить поэтапно «вручную» (на ассемблере).

Оптимизатор IBM превратил двумерный массив в одномерный, заменил деление на 4 умножением на 0.25, выровнял данные и подпрограммы на 16, вынес все повторяющиеся действия из циклов. Переменные I и J компилятор IBM вообще не стал заводить, поскольку кроме цикла, они нигде не использовались. В результате в основном цикле работы у него получилось 39 команд, а в случае моего транслятора - 104.

Казалось бы, дальше анализ можно и не проводить, замедление понятно. Но не все оказалось так просто, когда я начал повторять приемы оптимизации.

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

А вот выравнивание данных на 16 привело не к ускорению, а к замедлению работы. Выравнивание данных здесь вообще выглядит не очень. Я как программист рассчитываю, что для матрицы будет использовано 5000х5000х4=100 000 000 байт, а транслятор IBM реально использовал 400 Мбайт. Для 32-х разрядной Windows это значительная разница.

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

Нашлось и место, где оптимизация не сработала. «Главное» присвоение в программе:

T(I,J)=T1;

транслятором IBM превратилось в:

fld     tbyte ptr [ebp-50h]
fstp    tbyte ptr [edx-13890h]

а PL/1-KT в громоздкие:

MOV    EDI,[0040B428] .P
IMUL   EAX,[0040B440],00004E20 .I
ADD    EDI,EAX
MOV    EAX,[0040B444] .J
LEA    EDI,[EDI+EAX*4]+FFFFB1DC
MOV    ESI,0040B42C
MOVSD

которые, тем не менее, работают не медленнее, так как не задействуют FPU, а загрузка ESI может выполняться параллельно с EDI.

Но главный вклад в замедление внесли вовсе не такие действия, а то самое включение режима FPU с превращением «антипереполнения» в чистый ноль. После заполнения матрицы малым значением 1E-30 вместо нулей, одна итерация стала выполняться уже за 343 мс, а не за 624 мс как ранее. Вероятно, сброшенный бит UM слова управления не дает исключению выйти за пределы FPU, но все сопутствующие тормозящие действия остаются и замедляют работу.

Попутно подтвердилось ожидаемое, но печальное обстоятельство. 64-х разрядная кухня работает медленнее 32-х разрядной, чтобы там не писали разработчики этой архитектуры. В данном случае на 10% (365 мс против 343 мс). Я допускаю, что 64-х разрядные команды работают так же быстро, но поскольку часть команд стала длиннее, код получается менее плотным и кэш менее эффективен. Правда, кроме снятия барьера в 4 Гбайт (ради чего и затевалась эта архитектура), тест в 64-х разрядном виде продемонстрировал и дополнительный бонус: работа с double идет так же быстро, как с float, а в 32-х разрядной среде — заметно медленнее, хотя бы из-за того, что невозможно одной командой MOVSQ пересылать по 8 байт данных.

Совсем другие результаты показали те же тесты на процессоре AMD A6-9220 RADEON R4 2,50 GHz:

IBM транслятор - 597 мс

PL/1-KT 32 разряда - 616 мс

PL/1-KT 64 разряда - 636 мс

Разница стала незначительной. Но при этом заполнение 1E-30 для ускорения уже не требуется! И без этого заполнения работа получается даже чуть быстрее — 610 мс. Таким результатам уже подходит девиз: «если результат одинаков, зачем платить больше?».

Возможное объяснение такому времени работы заключается в том, что в AMD FPU-команды выполняются медленнее, чем в Intel по сравнению с остальными командами. Поэтому пока выполняется долгая обработка float, исполнение команд расчета индексов (даже с не вынесенной за цикл частью) успевает закончиться. А может быть, и тип памяти также играет заметную роль.

Подведем некоторые итоги этого тестирования.

1. Небольшая, но все-таки реальная задача показала, что значение «оперативной» оптимизации снижается. Даже «честное» вычисление индексов без выноса общих действий за пределы цикла замедлило работу лишь на 50% (343 мс против 227 мс), а для некоторых процессоров и этого нет (в AMD всего на 2%: 610 мс против 597 мс). Отчасти это связано и с тем, что после оптимизации осталось мало независимых команд, которые могут выполняться в параллель, а при отсутствии оптимизации часть независимых команд выполняется процессором параллельно.

2. К сожалению, оптимизация начинает превращаться в некую «угадайку» и иногда невозможно понять, как реально сработает тот или иной прием, особенно для разных архитектур. Например, в документации Intel я не нашел описания поведения процессора при сброшенном бите UM в слове управления FPU и искренне считал, что никаких дополнительных действий при этом не будет.

3. Даже простая «тактическая» оптимизация все же тоже дает эффект, например, при использовании SIB-адресации, поскольку части этой адресации декодируются параллельно.