BASM - Уроки для начинающих

 Previous  Top  Next

    
 

BASM

Уроки для начинающих

Денис Христенсен

Из news://forums.borland.com

borland.public.Delphi.languages.basm

 

© Dennis Chistensen, 2003

© Anatoly Podgoretsky, 2003, Russian translations

Vit - Печатается в DRKB с сокращениями

©Drkb::00301

 

Введение

Серия статей, названная “BASM for beginners” (BASM уроки для начинающих) в данный момент состоит из 7 статей, статьи 8 и 9 находятся в стадии подготовки. Общее для этих статей и для тех, что в процессе подготовки то, что они объясняют некоторые вопросы использования BASM на примерах функций. Большинство из этих функций сначала реализуются на Паскале, затем сгенерированный компилятором ассемблерный код, копируется из окна CPU view в Delphi, затем анализируется и оптимизируется. Иногда оптимизация включает в себя и использование инструкций MMX, SSE или SSE2.

В самом начале рассматривается код сделанный компилятором, в котором использует только наиболее используемые инструкции из огромного набора инструкций 32-битной архитектуры Intel. Просматривая, сгенерированный компилятором код, мы получаем представление и об эффективности компилятора, в общем, и о компиляторе Delphi в целом.

Когда применимо, то приводятся обобщения по оптимизации ассемблерного кода. Эта общая оптимизация применима к компиляторам и большинство компиляторов, включая Delphi, ее имеют. Когда ни будь, в будущем будет разработан инструмент по автоматической оптимизации ассемблерного кода.

Знание об используемом процессоре очень необходимы при оптимизации кода и поэтому также разъясняются множество подробностей о CPU, таких как например конвейеры.

Насколько Я знаю, имеется очень мало литературы, в которой объясняются все эти особенности, на уровне, который был бы понятен начинающим. Я надеюсь, что эта серия статей сможет помочь им в этом.

 

С уважением,

Денис Христенсен
Dennis Kjaer Christensen.

 

Lesson 1

Начнем с небольшого примера. Это простая функция Паскаля по умножению целого на константу 2.

Code:

function MulInt2(I : Integer) : Integer;

begin

Result := I * 2;

end;

 

Посмотрим сгенерированный код в окне CPU view. Я компилировал с включенной оптимизацией.

Code:

function MulInt2_BASM(I : Integer) : Integer;

begin

Result := I * 2;

{

add eax,eax

ret

}

end;

 

Здесь мы видим, что параметр передается в функцию в регистре EAX и результат возвращается в том же регистре. Это соглашение по передаче параметров через регистры (register calling convention), которое является соглашением по умолчанию в Delphi. Актуальный код очень простой, умножение на 2 заменяется сложением операнда с самим собой, I + I = 2I. Инструкция RET возвращает управление в строку, следующую за вызовом функции.

Сделаем тот же код, как чистую asm функцию.

Code:

function MulInt2_BASM2(I : Integer) : Integer;

asm

//Result := I * 2;

add eax,eax

//ret

end;

 

Заметим, что возврат из функции обеспечивается встроенным ассемблером.

Теперь посмотрит на код вызова функции.

Вот Паскаль код:

Code:

procedure TForm1.Button1Click(Sender: TObject);

var

I, J : Integer;

 

begin

I := StrToInt(IEdit.Text);

J := MulInt2_BASM2(I);

JEdit.Text := IntToStr(J);

end;

Важная для нас строка следующая

J := MulInt2_BASM2(I);

В окне CPU мы видим

Code:

call StrToInt

call MulInt2_BASM2

mov esi,eax

После вызова StrToInt из строки выше вызова нашей функции, I находится в регистре EAX. (StrToInt также следует соглашению о передаче параметров через регистры). Функция MulInt2_BASM2 вызывается, и возвращает свой результат в регистре EAX, который в следующей строке копируется в регистр ESI.

Замечание об оптимизации: Умножение на два может быть сделано двумя различными путями. С помощью инструкции MUL или сдвигом влево на один разряд. Инструкция MUL описана в руководстве разработчика (Intel IA32 SW developers manual 2) на странице 536. Данная инструкция умножает значение в регистре EAX на другой регистр, результат помещается в регистровую пару EDX:EAX. Регистровая пара необходима, потому что в результате умножения двух 32-битных регистров получается 64-бита, подобно 9*9=81 – два однозначных числа дают результат из двух цифр.

Это совпадает с соглашение об использовании регистров, которые должны быть сохранены во время работы функции, и какие можно свободно изменять. Это описано в справочной системе Дельфи.

"Выражения asm должны сохранять регистры EDI, ESI, ESP, EBP и EBX, но могут свободно изменять регистры EAX, ECX и EDX."

Отсюда мы делаем вывод, что у нас не будет проблем с изменением регистра EDX в инструкции MUL и наша функция может быть реализована следующим образом.

Code:

function MulInt2_BASM3(I : Integer) : Integer;

asm

//Result := I * 2;

mov ecx, 2

mul ecx

end;

Также используется регистр ECX, но  с этим тоже все в порядке. Так как результат меньше, чем диапазон для integer, то это также корректно возвращается в EAX. Но если I больше половины диапазона integer, то произойдет переполнение и результат будет неверным.

Реализация с помощью сдвига влево на один разряд

Code:

function MulInt2_BASM4(I : Integer) : Integer;

asm

//Result := I * 2;

shl eax,1

end;

 

 

Время выполнения в данном случае меньше. Мы можем также проконсультироваться с документацией Intel или AMD по таблицам латентности (latency) и по пропускной способности (throughput). От переводчика: в дальнейшем в документе будут использоваться термины - latency и throughput без перевода или латентность, поскольку нет хорошего эквивалента этим терминам или же будет использоваться термин пенальти. Смысл этих терминов следующий, команда может быть выполнена без пенальти (throughput). За минимальное время и с пенальти (latency) за полное, это особенность работы с конвейерами, на мой взгляд, автору стоило заострить эту особенность в данном месте, возможно, это будет сделано позже. Инструкции ADD и MOV выполняются за 0.5 цикла в обоих случаях, Инструкции MUL за 14-18 циклов (latency) и 5 циклов (throughput). Инструкции SHL за 4 цикла (latency) и 1 цикл (throughput). Версия, выбранная в Delphi наиболее эффективна для процессоров P4 и вероятно также для Athlon и P3.

 

Не рассматриваются: версия MUL против IMUL, контроль диапазона, другие соглашения о вызове, измерение производительности, подсчет тактов для других процессоров, подсчет тактов для CALL + RET, расположение адреса возврата и другое.

Урок 2

Это вторая глава введения в программирование с помощью BASM в Delphi. В первой главе было короткое введение в целочисленный код, а в этой главе введение в код с плавающей запятой. В нашем примере мы рассчитаем полином второго порядка. Параметры A, B и C, которые определяют полином, закодированы как локальные константы. В функцию передается переменная X типа double и результат также типа double. Функция выглядит так.

Code:

function SecondOrderPolynomial1(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

begin

Result := A*X*X + B*X + C;

end;

 

Просмотр кода в окне CPU показывает следующее.

Code:

function SecondOrderPolynomial2(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

 

begin

{

push  ebp

mov   ebp,esp

add   esp,-$08

}

Result := A*X*X + B*X + C;

{

fld   qword ptr [A]

fmul  qword ptr [ebp+$08]

fmul  qword ptr [ebp+$08]

fld   qword ptr [B]

fmul  qword ptr [ebp+$08]

faddp st(1)

fadd  qword ptr [C]

fstp  qword ptr [ebp-$08]

wait

fld   qword ptr [ebp-$08]

}

{

pop   ecx

pop   ecx

pop   ebp

}

end;

 

Попробую объяснить ассемблерный код, строка за строкой. Код begin выглядит в коде так.

Code:

begin

{

push  ebp

mov   ebp,esp

add   esp,-$08

}

 

 

Здесь устанавливается фрейм стека для функции. Фрейм стека просто часть памяти, которая выделена в стеке. Фрейм стека доступен через два указателя, указатель базы и указатель стека. Указатель базы это регистр EBP и указатель стека это регистр ESP. Эти два регистра резервированы только для использования в качестве этих указателей. Первая инструкция PUSH EBP сохраняет указатель базы. В строке MOV EBP, ESP устанавливается новая база для адресации по стеку. В строке ADD ESP, -$08 указатель стека смещается на 8 вниз. Как курьез, стек увеличивается вниз, и более понятной командой было бы его установка с помощью инструкции SUB ESP, 8. Новый фрейм стека устанавливается с помощью этих трех строк, поверх старого фрейма,  который был размещен функцией, которая вызвала нашу функцию SecondOrderPolynomial.

Следующая строка Паскаля компилируется в 9 строк на ассемблере.

Code:

Result := A*X*X + B*X + C;

{

fld   qword ptr [A]

fmul  qword ptr [ebp+$08]

fmul  qword ptr [ebp+$08]

fld   qword ptr [B]

fmul  qword ptr [ebp+$08]

faddp st(1)

fadd  qword ptr [C]

fstp  qword ptr [ebp-$08]

wait

fld   qword ptr [ebp-$08]

}

 

 

Для тех, кто использует калькуляторы HP для расчетов с плавающей запятой, данный код очень прост для понимания. В первой строке, FLD QWORD PTR [A], загружается константа A в регистр стека с плавающей запятой. Строка, FMUL QWORD PTR [EBP+$08], умножает A на X. Это понятно при просмотре Паскаль кода, но что означает "QWORD PTR [EBP+$08]". QWORD PTR означает "указатель на двойное слово, которое размером с double (64 бита). Значение указателя между квадратными скобками [EBP+$08]. Регистр EBP это указатель базы и $08 это – да просто 8. Поскольку стек при увеличении движется вниз, то это смещение на 8 байт вверх относительно указателя базы в текущем фрейме. Здесь находится переданный параметр X, помещенный сюда вызывающей функцией. При соглашение о регистром вызове, значение не помещается в 32-разрядный регистр, но оно хорошо помещается в регистр с плавающей запятой. Borland решил передавать параметры с плавающей запятой двойной точности через стек, но передача через регистры с плавающей запятой, была бы более эффективной. Следующие три строки не требуют специального пояснения, but the line, но инструкция FADDP ST(1), нуждается в объяснении. Все инструкции с плавающей запятой начинаются с префикса f. add это сложение. ST(1) это название регистра с плавающей запятой номер 1, который является вторым, поскольку первый регистр это ST(0)! Регистры с плавающей запятой скомпонованы в стек и инструкции по умолчанию работаю с верхушкой стека, которая равна ST(0). FADDP ST(1) идентична инструкции FADDP ST(0), ST(1) - складывает содержимое регистров ST(0) и ST(1), результат помещается в регистр ST(1). P в FADDP означает POP ST(0) из стека. Таким путем результат помещается в ST(0). Строка FADD QWORD PTR [C] заканчивает вычисление, и единственная вещь, которая осталась, это помещения результата в  ST(0). Результат и так уже там, поэтому две следующие строки кода излишни.

fstp  qword ptr [ebp-$08]

fld   qword ptr [ebp-$08]

Они просто копируют результат на стек и обратно. Такая затрата времени и энергии :-). Инструкция WAIT обеспечивает обработку возможных исключений при выполнении операций с плавающей запятой. Смотри руководство Intel SW Developers Manual Volume 2, страницу 822 для полного понимания этого.

Осталось объяснить еще три строки кода.

Code:

{

pop   ecx

pop   ecx

pop   ebp

}

end;

 

 

Они возвращают фрейм стека, путем восстановления старого содержимого регистров ESP и EBP. Понятнее был бы следующий код.

add esp, 4

pop ebp

это также было бы более эффективным, и я не понимаю, почему компилятор увеличивает указатель стека таким странным методом. Вспоминаем, что регистр ECX можно использоваться свободно, назначать ему любые значения, поскольку они все равно не будет использовано далее.

Осталось также объяснить, что скрывается за [A] в строке fld qword ptr [A]. Мы знаем, что A должен быть указателем на место, где хранится само A в памяти. Адрес A закодирован в инструкции. Вот полная строка из окна CPU.

00451E40 DD05803C4500     fld qword ptr [B]

00451E40 это адрес инструкции в exe файле. DD05803C4500 это машинный код строки FLD QWORD PTR [B], которая более понятна для человеческого разума. При просмотре руководства Intel SW Developers Manual Volume 2, страница 280, мы увидим, что код команды для FLD равен D9, DD, DB или D9C0, в зависимости от типа данных. Мы узнаем, что DD это код для FLD DOUBLE. Остается еще 05803C4500. 05 это (Не знаю, может быть, кто-то поможет мне!), а 803C4500 это 32-битный адрес константы A.

Попробуем теперь преобразовать эту функцию в чистый ассемблерный код.

Code:

function SecondOrderPolynomial3(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

 

asm

push  ebp

mov   ebp,esp

add   esp,-$08

//Result := A*X*X + B*X + C;

fld   qword ptr [A]

fmul  qword ptr [ebp+$08]

fmul  qword ptr [ebp+$08]

fld   qword ptr [B]

fmul  qword ptr [ebp+$08]

faddp //st(1)

fadd  qword ptr [C]

fstp  qword ptr [ebp-$08]

wait

fld   qword ptr [ebp-$08]

pop   ecx

pop   ecx

pop   ebp

end;

 

Но мы теперь получили несколько сюрпризов. Во-первых, функция не компилируется. FADDP ST(1) не распознается, как допустимая комбинация команды и операндов. Снова консультируемся с руководством от Интел, мы узнаем, что  FADDP существует только в одной версии. Она работает с ST(0), ST(1) и нет необходимости писать FADDP ST(0), ST(1) и только краткая форма FADDP единственно допустимая. После маскирования ST(1) наконец стало компилироваться.

Второй сюрприз. Вызов функции с X = 2 должен рассчитать Y = 2^2+2*2+3 = 11. Но SecondOrderPolynomial3 возвращает 3! Снова открываем окно просмотра FPU, так как окно CPU и трассируем код, наблюдая, что происходит. Видно, что A=1 корректно загружается в ST(0) в строке 4, но в строке 5, которая производит умножение A на X, 1 на 2, результат в ST(0) что-то очень маленький, в действительности 0. Это означает, что X близок к 0 вместо 2. Могут быть неверным две вещи. Вызывающий код передает неверное значение X или мы неправильно адресуем X. Сравнивая код вызова функций SecondOrderPolynomial3 и SecondOrderPolynomial1, мы видим, что он одинаков и поэтому не может быть причиной ошибки. Было бы большим сюрпризом, если бы Delphi делала это неверно! Пробуем опять  трассировать код вызова, наблюдая за окном просмотра памяти в окне просмотра CPU. Зеленая стрелочка показывает позицию стека. Код вызова выглядит так:

Code:

push dword ptr [ebp-$0c]

push dword ptr [ebp-$10]

call SecondOrderPolynomial1

 

Два указателя помещаются на стек. Один из них это указатель на X. Но что за второй указатель. Просматриваем окно памяти и видим, что первый указатель это указатель на X, а второй нулевой указатель. При трассировке внутрь функции мы видим, что первые две строки повторяются. Компилятор автоматически вставляет инструкции PUSH EBP и MOV EBP, ESP. Поскольку инструкция PUSH уменьшает указатель стека на 4, то ссылка на X оказывается неверной. После того, как были убраны две первые строки, все пришло в норму.

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

Для начала уберем два строки FSTP/FLD поскольку они лишние.

Code:

function SecondOrderPolynomial4(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

 

asm

//push  ebp

//mov   ebp,esp

add   esp,-$08

//Result := A*X*X + B*X + C;

fld   qword ptr [A]

fmul  qword ptr [ebp+$08]

fmul  qword ptr [ebp+$08]

fld   qword ptr [B]

fmul  qword ptr [ebp+$08]

faddp //st(1)

fadd  qword ptr [C]

//fstp  qword ptr [ebp-$08]

wait

//fld   qword ptr [ebp-$08]

pop   ecx

pop   ecx

pop   ebp

end;

 

Есть также одна ссылка на фрейм стека, которая не нужна.

Code:

function SecondOrderPolynomial5(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

 

asm

//push  ebp

//mov   ebp,esp

//add   esp,-$08

//Result := A*X*X + B*X + C;

fld   qword ptr [A]

fmul  qword ptr [ebp+$08]

fmul  qword ptr [ebp+$08]

fld   qword ptr [B]

fmul  qword ptr [ebp+$08]

faddp //st(1)

fadd  qword ptr [C]

 

wait

 

//pop   ecx

//pop   ecx

//pop   ebp

end;

 

После удаления этих шести строк, наша функция уменьшилась до следующего:

Code:

function SecondOrderPolynomial6(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

 

asm

//Result := A*X*X + B*X + C;

fld   qword ptr [A]

fmul  qword ptr [ebp+$08]

fmul  qword ptr [ebp+$08]

fld   qword ptr [B]

fmul  qword ptr [ebp+$08]

faddp

fadd  qword ptr [C]

wait

end;

 

X загружается из памяти в FPU три раза. Было бы более эффективным загрузить его один раз и повторно использовать.

Code:

function SecondOrderPolynomial7(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

 

asm

//Result := A*X*X + B*X + C;

fld   qword ptr [ebp+$08]

fld   qword ptr [A]

fmul  st(0), st(1)

fmul  st(0), st(1)

fld   qword ptr [B]

fmul  st(0), st(2)

ffree st(2)

faddp

fadd  qword ptr [C]

wait

end;

 

Расскажем о магии данного кода. Во-первых, в первой строке загружаем X. Во второй строке загружаем A. В третьей строке умножаем A на X. В четвертой строке умножаем a*X, расположено в ST(0) на X. Так мы выполнили первое вычисление. Загружаем B и умножаем его на X, этим выполняем второе вычисление. Это последняя необходимость в X и мы освобождаем регистр ST(2), в котором оно хранится. Теперь складываем вычисления 1 и 2 и выкидываем вычисление 2 из стека. Единственно, что нам осталось, это прибавить C. Результат теперь в регистре ST(0) и все остальные регистры освобождены. Теперь мы проверяем на возможные ошибки вычислений и заканчиваем. Теперь кажется, что лишних операций нет и код вполне оптимальный.

Осталась еще инструкции для загрузки часто используемых констант в арифметический сопроцессор, одна из них это 1которая может быть загружена инструкцией fld1. Использование ее убирает одну загрузку из памяти, которая может привести к потерям тактов, если данные неверно выровнены.

Code:

function SecondOrderPolynomial8(X : Double) : Double;

const

//A : Double = 1;

B : Double = 2;

C : Double = 3;

 

asm

//Result := A*X*X + B*X + C;

fld   qword ptr [ebp+$08]

//fld   qword ptr [A]

fld1

fmul  st(0), st(1)

fmul  st(0), st(1)

fld   qword ptr [B]

fmul  st(0), st(2)

ffree st(2)

faddp

fadd  qword ptr [C]

wait

end;

 

Урок 3

Тема третьего урока MMX и SSE2, одновременно будет обсуждена 64-битная математика. И мы впервые обратим внимание на зависимость оптимизации оп процессорам.

Пример выглядит следующим образом.

Code:

function AddInt64_1(A, B : Int64) : Int64;

begin

Result := A + B;

end;

 

Посмотрим теперь ассемблерный код.

Code:

function AddInt64_2(A, B : Int64) : Int64;

begin

{

push ebp

mov ebp,esp

add esp,-$08

}

Result := A + B;

{

mov eax,[ebp+$10]

mov edx,[ebp+$14]

add eax,[ebp+$08]

adc edx,[ebp+$0c]

mov [ebp-$08],eax

mov [ebp-$04],edx

mov eax,[ebp-$08]

mov edx,[ebp-$04]

}

{

pop ecx

pop ecx

pop ebp

//ret

}

end;

 

Первые три строки устанавливают фрейм стека, так же как в предыдущих уроках. В данный момент мы уже знаем, что компилятор самостоятельно добавляет первые две строки. Последние три строки так же хорошо знакомы нам. Опять строку POP EBP компилятор добавляет сам. Теперь посмотри, что же это за восемь строк.

Code:

Result := A + B;

{

mov eax,[ebp+$10]

mov edx,[ebp+$14]

add eax,[ebp+$08]

adc edx,[ebp+$0c]

mov [ebp-$08],eax

mov [ebp-$04],edx

mov eax,[ebp-$08]

mov edx,[ebp-$04]

}

 

 

Анализ показывает, что они работают парами, осуществляя 64-битную математику на основе 32-битных регистров. Первые две строки загружают параметр A в регистровую пару EAX:EDX. Команды загружают непрерывный 64-битный блок данных из предыдущего стекового фрейма, показывая нам, что A был помещен на стек. Указатели отличаются на 4 байта. Первый из них указывает на младшую часть A и другой на старшую часть A. Затем производится два сложения. Первое это обычное сложение, а второе сложение с переносом. Указатели в данном случае относятся к параметру B по тем же правилам, как и параметр A. Первое сложение добавляет младшие 32 бита операнда B к младшим битам операнда A. При этом может возникнуть перенос, если результат больше, чем может поместиться в 32 битах. Это перенос включается в сложение старших 32 бит. Что бы сделать это окончательно понятным рассмотрим на простом примере для десятичных чисел. При сложении 1 + 2 = 3. Для наших воображаемых чисел, наш мозговой «CPU» будет двухразрядным процессором. Это означает, что сложение реально выглядит как 01 + 02 = 03. Пока еще нет переноса из младшей цифры в старшею, которая равная 0. Пример номер 2 для десятичных чисел. 13+38=?. Сначала мы складываем 3 + 8 = 11. Теперь результат имеет перенос и 1 в младшем разряде. Затем мы складываем Перенос + 1 + 3 = 1 + 1 + 3 = 5. Результат равен 51. В третьем примере мы рассмотрим случай с переполнением. 50 + 51 = 101. 101 слишком велик, что бы разместиться в двух разрядах и наш «CPU» не сможет выполнить расчет. Здесь также получился перенос при сложении двух старших цифр. Вернем в код. Могут произойти две вещи. Если мы компилировали без проверки диапазонов, то результат будет обрезан. При включенной проверке диапазонов будет возбуждено исключение. Мы не видим проверки на диапазон в нашем коде, и поэтому будет производиться усечение результата.

Следующие две строки помещают результат обратно на стек. А затем следующие две строки возвращают результат обратно в EAX и EDX, который и так уже здесь. Эти 4 строки абсолютно излишни. Они могут быть удалены и также не требуется и фрейм стека. Это так просто для оптимизатора ;-)

Code:

function AddInt64_6(A, B : Int64) : Int64;

asm

mov eax,[ebp+$10]

mov edx,[ebp+$14]

add eax,[ebp+$08]

adc edx,[ebp+$0c]

end;

 

 

Теперь это прекрасная маленькая функция. Компилятор сгенерировал код из 16 строк, а мы его уменьшили до 4. Сегодня Delphi реально слепая.

Теперь подумаем так: Если бы мы имели 64-битные регистры, то сложение могло бы быть выполнено с помощью двух строк кода. Но MMX регистры уже 64-битные и может быть, мы получим преимущества при их использовании. В руководстве Intel SW Developers Manual для инструкций не указана принадлежность к IA32, MMX, SSE или SSE2. Было бы превосходно иметь эту информацию, но мы должны искать ее где-то в другом месте. Я обычно использую три маленькие программы от Intel. Они называются «computer based tutorials on MMX, SSE & SSE2». Я не знаю где их можно найти на Интеловском Веб сайте, но Вы можете написать мне, если они очень вам нужны. Они простые и удобные – очень иллюстративные. В них я нашел, что инструкция MOV для 64-битных операндов из памяти в MMX регистр, называется MOVQ. Символ Q означает QUAD WORD (четыре слова). MMX именуются, как MM0, MM1...MM7. В отличие от регистров FPU они не организованы в стек, и вы можете их использовать их как вам угодно. Попробуем загрузить регистр MM0. Инструкция выглядит так:

movq    mm0, [ebp+$10]

Есть два пути. Мы можем загрузить операнд B также в регистр. Очень просто посмотреть, как это происходит при помощи окна просмотра FPU. Регистры MMX сделаны псевдонимами к FP регистрам и окно FPU может показывать оба набора. Переключение между просмотром FP и MMX делается выбором "Display as words/Display as extendeds" в меню. Второй путь использовать шаблоны из «IA32 implementation» и выполнить сложение с ячейкой памяти B как источник. Два решения идентичны, поскольку CPU должен загрузить операнд B в регистр до выполнения операции сложения и сделать это явно с помощью инструкции MOV или неявно с помощью инструкции ADD, количество выполненных микроинструкций будет одинаковым. Мы используем более наглядный первый путь. Поэтому следующая строка снова MOVQ

movq    mm1, [ebp+$08]

Затем взглянем на инструкцию сложения, которая выглядит так: PADDQ. P означает MMX, ADD означает сложение, а Q означает QUAD WORD. И снова мы в недоумении, поскольку здесь нет таких MMX инструкций. А что насчет SSE. Опять разочарование. В конце концов, SSE2 имеет это и мы счастливы или нет? Да если мы используем это на P4 и не запускаем на P3 или на Athlon. Так как мы почитатели P4 мы продолжаем все равно.

paddq   mm0, mm1

Это строка очень понятна. Сложить MM1 с MM0.

Последнее действие это скопировать результат из MM0 в EAX:EDX. Для выполнения этого нам нужно инструкция пересылки двойного слова из MMX регистра, как источника, в регистр IA32, как приемник.

movd    eax, mm0

Данная MMX инструкция выполняет эту работу. Она копирует младшие 32 бита регистра MM0 в EAX. Затем мы должны скопировать старшие 32 бита результата в регистр EDX. Я не нашел инструкции, которая могла бы сделать это и взамен этого воспользовался сдвигом старших 32 бит в младшие, с помощью 64-битной MMX инструкции сдвига.

psrlq   mm0, 32

Затем копируя в регистр

movd    edx, mm0

Что же мы сделали? В действительности мы использовали расширенные EMMS инструкции, поскольку нам нужны были MMX инструкции. Это очистило FP стек и оставило его в определенном чистом состоянии. EMMS на выполнение затрачивает 23 такта на процессоре P4. Совместно со сдвигом, который также не эффективен (2 цикла для throughput и latency) на P4. Наше решение не особенно быстро и работает только на P4, а на AMD этих вещей пока нет :-(

На этом мы заканчиваем третий урок. Мы оставили мяч повисшим в воздухе. Можем мы прийти к более эффективному решению? Передача данных между MMX регистрами и IA32 регистрами очень накладна. Соглашение о вызове не очень подходящее, поскольку данные перемещаются на стек, а не в регистры. EAX->MM0 занимает 2 такта. Другой путь занимает 5 циклов. EMMS требует 23 такта. Сложение только 2 cycles. Перегрузка налицо.

 

Урок 4

В данном уроке мы посмотрим насчет ветвления, рассматривая это на примере конструкции IF-ELSE. Условное перемещение для плавающей запятой также будет рассмотрено.

Примером для данного урока будет функция Min из модуля Delphi Math.

Code:

function Min1(const A, B: Single) : Single;

begin

if A < B then

Result := A

else

Result := B;

end;

 

 

Компилятор генерирует следующий ассемблерный код.

Code:

function Min2(const A, B: Single) : Single;

begin

{

00452458 55               push ebp

00452459 8BEC             mov ebp,esp

0045245B 51               push ecx

}

if A < B then

{

0045245C D9450C           fld dword ptr [ebp+$0c]

0045245F D85D08           fcomp dword ptr [ebp+$08]

00452462 DFE0             fstsw ax

00452464 9E               sahf

00452465 7308             jnb +$08

}

Result := A

{

00452467 8B450C           mov eax,[ebp+$0c]

0045246A 8945FC           mov [ebp-$04],eax

0045246D EB06             jmp +$06

}

else

Result := B;

{

0045246F 8B4508           mov eax,[ebp+$08]

00452472 8945FC           mov [ebp-$04],eax

}

{

00452475 D945FC           fld dword ptr [ebp-$04]

00452478 59               pop ecx

00452479 5D               pop ebp

}

end;

 

 

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

Code:

function Min3(const A, B: Single) : Single;

begin

{

push ebp                     // Save ebp on stack

mov ebp,esp                  // New basepointer is the old stackpointer  

push ecx                     // subtract 4 from esp  

}

if A < B then

{

fld dword ptr [ebp+$0c]      // Load A on FP stack

fcomp dword ptr [ebp+$08]    // FP compare A to B and pop A from stack

fstsw ax                     // Store FP statusword in ax

sahf                         // Store ah into EFlags register

jnb +$08                     // If not below jump 8 bytes forward

}

Result := A

{

mov eax,[ebp+$0c]           // Copy A into eax

mov [ebp-$04],eax           // Copy A into stackframe

jmp +$06                    // Jmp 6 bytes forward

}

else

Result := B;

{

mov eax,[ebp+$08]           // Copy B into eax

mov [ebp-$04],eax           // Copy B into stackframe

}

{

fld dword ptr [ebp-$04]     // Load A or B from stackframe onto FP stack

pop ecx                     // Add 4 to esp  

pop ebp                     // Restore ebp

}

end;

 

Я сделал комментарии для каждой строки кода. Детали немного ниже. Первая новая инструкция, обсуждаемая здесь это инструкция FCOMP. F как всегда означает инструкции с плавающей запятой. СOM означает сравнение и P означает  POP из стека FP. FCOM сравнивает два операнда с плавающей запятой и устанавливает флаги по результату сравнения, именуемые как C0, C1, C2 и C3. Эти флаги эквивалентны регистру EFlags CPU. Данные флаги проверяются инструкциями условного перехода, в зависимости от их состояния производится или не производится переход. Инструкции условного перехода проверяют флаги CPU, а не FPU и поэтому необходимо копировать эти влаги из FPU в CPU. Это делается с помощью двух следующих инструкции. FSTSW записывает флаги FP в регистр AX и SAHF копирует 8-бит из регистра AH в регистр EFlags. Это длинный путь для флагов, перед тем как они смогут быть использованы в инструкции JNB. JNB означает JUMP NOT BELOW (переход если не меньше). В руководстве «Intel SW Developers Manual Vol 2» на странице 394 есть таблица, в которой описаны все инструкции переходов с объяснением используемых ими флагов. Здесь мы видим, что инструкция JNB делает переход, если установлен флаг переноса (CF=1) и флаг нуля (ZF=1). Попробуйте протрассировать код в просмотром в окне FPU и в окне CPU. Смотрите, как устанавливаются флаги FPU, затем их значения копируются в регистр CPU EFlags.

Если по инструкции JNB переход не выполняется, то выполнение продолжается на следующей за ней строке. Это часть конструкции IF-ELSE. Если же переход происходит, то выполнение будет продолжено по адресу на 8 далее. В этой точке начинается часть ELSE. Части IF и ELSE очень похожи. Как видно в Паскаль коде, A или B копируется в переменную RESULT, в зависимости от условия IF. Вместо копирования A или B напрямую на верхушку FP стека, который является местом для результата функции, в соответствии с соглашением о вызове, компилятор Delphi помещает его на стек как временное хранилище. Инструкция FLD DWORD PTR [EBP-$04] затем копирует результат в правильное место.

Добавим, что в конце блока IF требуется инструкция безусловного перехода, чтобы выполнение не распространилось на блок ELSE. Это делается вне зависимости, от того какой переход избран. Несколько слов о предсказании переходов. Предсказание переходов бывает статическое и динамическое. При первом выполнении перехода в CPU отсутствуют знания насчет вероятности, будет совершен переход или нет. В данной ситуации используется статическое предсказание, которое гласит, что прямой переход не будет выполнен, а обратный будет. В нашем примере прямой переход не предсказан при первом выполнении. Если бы мы имели знания насчет значений A и B, мы могли бы использовать это в конструкции IF-ELSE так, что бы IF часть была бы наиболее часто исполнимой, и статическое предсказание было бы оптимизировано. Безусловный переход не требует предсказания – это всегда имеет место быть ;-). Обратный переход часто используется в циклах, и большинство циклов исполняются более одного раза. Это объясняет, почему для статического предсказания выбран именно этот путь. При динамическом предсказании накапливаются знания насчет вероятности, того какой переход более вероятен, и сделать предсказание наиболее корректным.

Теперь пришло время преобразовать данную функцию в чистую ассемблерную.

Code:

function Min4(const A, B: Single) : Single;

asm

//push  ebp

//mov   ebp,esp

push  ecx

//if A < B then

fld   dword ptr [ebp+$0c]

fcomp dword ptr [ebp+$08]

fstsw ax

sahf

jnb   @ElseBegin

//Result := A

mov   eax,[ebp+$0c]

mov   [ebp-$04],eax

jmp   @ElseEnd

//else

//Result := B;

@ElseBegin :

mov   eax,[ebp+$08]

mov   [ebp-$04],eax

@ElseEnd :

fld   dword ptr [ebp-$04]

pop   ecx

//pop   ebp

end;

 

 

Мы видим две новых вещи – это метки. Наш анализ функции делает более понятным, куда мы переходим при переходе. В действительности это хорошая вещь, использовать метки, это делает более понятной структуру кода. Вы можете открыть окно FPU и просто пройтись по коду, наблюдая, когда происходит переход или нет. Если вы устанавливать адрес перехода без меток, то используйте математику. Пример ниже.

Здесь у нас переход

00452465 7308             jnb +$08

Это следующая за ним строка

00452467 8B450C           mov eax,[ebp+$0c]

А это строка на 8 байт далее ее

0045246F 8B4508           mov eax,[ebp+$08]

Возьмите адрес в строке после строки с переходом и добавьте к ней смещение до строки, в которую осуществляется переход. Математически это: 00452467 + 8 = 0045246F.

Почему мы должны добавлять смещение к адресу после команды перехода, а не к адресу с инструкцией?

Теперь приступаем к оптимизации.

Code:

function Min5(const A, B: Single) : Single;

asm

push  ecx

//if A < B then

fld   dword ptr [ebp+$0c]

fcomp dword ptr [ebp+$08]

fstsw ax

sahf

jnb   @ElseBegin

//Result := A

mov   eax,[ebp+$0c]

mov   [ebp-$04],eax

jmp   @ElseEnd

//else

//Result := B;

@ElseBegin :

mov   eax,[ebp+$08]

mov   [ebp-$04],eax

@ElseEnd :

fld   dword ptr [ebp-$04]

pop   ecx

end;

 

 

Это улучшенная версия функции. Изменены инструкции PUSH ECX, POP ECX для манипуляции регистром ESP напрямую и не нужно перемещать данные между ECX и стеком.

Code:

function Min6(const A, B: Single) : Single;

asm

//push  ecx

sub   esp, 4

//if A < B then

fld   dword ptr [ebp+$0c]

fcomp dword ptr [ebp+$08]

fstsw ax

sahf

jnb   @ElseBegin

//Result := A

mov   eax,[ebp+$0c]

mov   [ebp-$04],eax

jmp   @ElseEnd

//else

//Result := B;

@ElseBegin :

mov   eax,[ebp+$08]

mov   [ebp-$04],eax

@ElseEnd :

fld   dword ptr [ebp-$04]

//pop   ecx

add esp, 4

end;

 

 

При анализе кода мы заметили, что флаги перемещаются длинным путем и требуется для выполнения два цикла. Как насчет инструкций сравнения для плавающей запятой, которые бы напрямую устанавливали регистр EFlags? Такая инструкция есть, это FCOMI, которая описана в архитектуре P6. Попробуем использовать ее, но выбросим эти старые CPU, более старые, чем Pro. Эти строки

fcomp dword ptr [ebp+$08]

fstsw ax

sahf

должно быть заменены на следующую

fcomip dword ptr [ebp+$08]

Инструкция FCOMI не воспринимает указатели на операнд в памяти. Поэтому необходимо загрузить данные до ее использования.

fld    dword ptr [ebp+$0c]

fcomip st(0), st(1)

Поскольку мы загрузили данные, то мы и должны их удалить, с помощью FFREE инструкции. Хотелось бы иметь инструкцию fcomipp.

fld    dword ptr [ebp+$0c]

fcomip st(0), st(1)

ffree  st(0)

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

Code:

function Min7(const A, B: Single) : Single;

asm

  sub    esp, 4

  //if A < B then

  fld    dword ptr [ebp+$08]

  fld    dword ptr [ebp+$0c]

  fcomip st(0), st(1)

  ffree  st(0)

  //fstsw ax

  //sahf

  jnb    @ElseBegin

  //Result := A

  mov    eax,[ebp+$0c]

  mov    [ebp-$04],eax

  jmp    @ElseEnd

  //else

  //Result := B;

@ElseBegin :

  mov    eax,[ebp+$08]

  mov    [ebp-$04],eax

@ElseEnd :

  fld    dword ptr [ebp-$04]

  add    esp, 4

end;

 

 

Теперь можно и подумать. Зачем нам копировать результат? Оба A и B уже на стеке для использования в сравнении с помощью FCOM и результат также должен остаться на стеке. Единственно, что нужно, так это удалить или A или B и оставить наименьшее из них на стеке.

Code:

function Min8(const A, B: Single) : Single;

asm

  sub    esp, 4

  //if A < B then

  fld    dword ptr [ebp+$08]

  fld    dword ptr [ebp+$0c]

  //fcomip  st(0), st(1)

  fcomi  st(0), st(1)

  //ffree  st(0)

  jnb    @ElseBegin

  //Result := A

  //mov    eax,[ebp+$0c]

  //mov    [ebp-$04],eax

  ffree st(1)

  jmp    @ElseEnd

  //else

  //Result := B;

@ElseBegin :

  //mov    eax,[ebp+$08]

  //mov    [ebp-$04],eax

  fxch

  ffree st(1)

@ElseEnd :

  //fld    dword ptr [ebp-$04]

  add    esp, 4

end;

 

 

Инструкция FCOMIP заменяется инструкцией FCOMI, поскольку мы не хотим, удалять B со стека в данный момент. FFREE поскольку она удаляет A. Затем удалены все строки, которые копируют результат туда/обратно. В блоке IF A является результатом и B должно быть удалено. B находится в ST(1) и FFREE ST(1) сделает эту работу. В блоке ELSE мы должны удалить A и поставить B в ST(0). Обмениваем местами A и B, с помощью инструкции FXCH и затем удаляем A в ST(1) с помощью FFREE. FXCH ничего не стоит (занимает 0 циклов), поскольку вместо реальной пересылки данных используется переименование регистров.

Code:

function Min9(const A, B: Single) : Single;

asm

  //sub    esp, 4

  //if A < B then

  fld    dword ptr [ebp+$08]

  fld    dword ptr [ebp+$0c]

  fcomi  st(0), st(1)

  jnb    @ElseBegin

  //Result := A

  ffree st(1)

  jmp    @ElseEnd

  //else

  //Result := B;

@ElseBegin :

  fxch

  ffree st(1)

@ElseEnd :

  //add    esp, 4

end;

 

Теперь фрейм стека более не нужен и мы удалим код его установки.

Code:

function Min10(const A, B: Single) : Single;

asm

  //if A < B then

  fld    dword ptr [ebp+$08]

  fld    dword ptr [ebp+$0c]

  fcomi  st(0), st(1)

  jnb    @ElseBegin

  //Result := A

  ffree st(1)

  jmp    @ElseEnd

  //else

  //Result := B;

@ElseBegin :

  fxch

  ffree st(1)

@ElseEnd :

end;

 

Это достаточно прекрасная функция, но кто-то в группе новостей говорил об условных пересылках. FCMOVNB именно такая функция - floating point conditional move not below. Она пересылает данные из ST(1)-ST(7) в ST(0) если выполняется условие. Для проверки условия проверяются флаги Eflags. FCMOV приводится в архитектуре P6 наряду с FCOMI.

Code:

function Min11(const A, B: Single) : Single;

asm

  fld     dword ptr [ebp+$08]

  fld     dword ptr [ebp+$0c]

  fcomi   st(0), st(1)

  fcmovnb st(0), st(1)

  ffree   st(1)

end;

 

 

Вместо всех переходов и пересылок мы копируем A на верхушку стека, где сейчас находится B, но только если A меньше B. Удаляем B и заканчиваем.

Это почти отличная функция, кроме того, что компилятор все равно создает пролог и эпилог функции, копируя и восстанавливая регистр EBP, даже если он не модифицируется внутри функции.

Урок 5

Добро пожаловать на пятый урок. Его тема циклы. Мы увидим, как компилятор реализует циклы, и какую оптимизацию мы можем сделать в них. Мы также проверим эффективность этой оптимизации. 

Code:

function ForLoop(Start, Stop : Integer) : Integer;

var

I : Integer;

 

begin

Result := 0;

for I := Start to Stop do

begin

   Result := Result + I;

end;

end;

 

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

Code:

function ForLoopNonOpt(Start, Stop : Integer) : Integer;

var

I : Integer;

 

begin

{

push ebp

mov ebp,esp

add esp,-$14

mov [ebp-$08],edx

mov [ebp-$04],eax

}

Result := 0;

{

xor eax,eax

mov [ebp-$0c],eax

}

for I := Start to Stop do

{

mov eax,[ebp-$04]

mov edx,[ebp-$08]

sub edx,eax

jl +$15

inc edx

mov [ebp-$14],edx

mov [ebp-$10],eax

}

begin

   Result := Result + I;

   {

   mov eax,[ebp-$10]

   add [ebp-$0c],eax

   inc dword ptr [ebp-$10]

   }

end;

{

dec dword ptr [ebp-$14]

jnz -$0e

mov eax,[ebp-$0c]

}

{

mov esp,ebp

pop ebp

ret

}

end;

 

Как мы видим, компилятор сгенерировал кучу кода, где или совсем нет оптимизации или ее мало. Как обычно первые три строки это установка стекового фрейма. В данном примере он на 20 байт больше (16 hex). Две следующие строки копируют переменные Start и Stop на стек. Start передается в EAX и Stop передается в EDX, в соответствии с соглашением об вызове. Следующие две строки создают значение 0 и копируют его на стек [EBP-$0C], это место для хранения переменной Result. Теперь мы готовы к выполнению тела цикла. Перед началом цикла необходимо убедиться, что цикл действительно должен выполняться. Если Stop больше чем Start, то это как раз тот случай. Start и Stop извлекаются из стека в регистры EAX и EDX. Мы вычисляем выражение Stop-Start и если результат отрицательный, то цикл не выполняется и управление передается в конец цикла инструкцией JL (jump low). В следующей строке увеличивается значение Stop, и оно копируется на стек [EBP-$14]. У нас нет имени для этой локальной переменной в данной точке. Данная особенность потребует дополнительных объяснений. Эта переменная (NoName) введена компилятором для оптимизации и это немного странно, поскольку мы отключили оптимизацию. Доступ до этой неименованной переменной есть в строке DEC DWORD PTR [EBP-$14]. Эта строка уменьшает ее значение на единицу, в конце каждой итерации и проверяется, что она не достигла нуля. Инструкция DEC устанавливает флаги, и инструкция JNZ делает переход на начало цикла, при условии, что NoName <> 0. Мы должны считать, что это используется как счетчик цикла и что она бежит от Start до Stop. Это действительно делается так, но это не используется для управления циклом. Преимущество в том, что это сохраняет инструкции при сравнении I со Stop. Но это также и увеличивает стоимость инструкции DEC NoName. На P4 latency/throughput инструкции CMP составляет 0.5/0.5 цикла, а для DEC оно 1/0.5. Поэтому это можно считать «де оптимизацией». Значения latency и throughput для P4 можно найти в «Intel Pentium 4 and Xeon Processor Optimization» руководстве от Intel.

Вернемся к строке MOV [EBP-$10], EAX. Она копирует переменную I на стек. Тело цикла состоит из одной строки Паскаля Result := Result + I. Она транслируется в три строки на ассемблере. Первые две строки загружают переменную I в регистр EAX и затем прибавляют ее к переменной Result на стеке [EBP-$0C]. Третья строка увеличивает переменную I. На этом мы заканчиваем объяснения кода цикла и у нас остались только две вещи. Переменная Result должна быть скопирована в регистр EAX, который используется для возврата результата из функции, в соответствии с соглашением о вызове. Последние три строки восстанавливают фрейм стека и возвращают управление обратно в программу.

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

Code:

function ForLoopBASM1(Start, Stop : Integer) : Integer;

asm

push ebp

mov ebp,esp

add esp,-$14

mov [ebp-$08],edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,[ebp-$08]

sub edx,eax

jl @LoopEnd

inc edx

mov [ebp-$14],edx

mov [ebp-$10],eax

  //begin

  @LoopStart :

    //Result := Result + I;

    mov eax,[ebp-$10]

    add [ebp-$0c],eax

    inc dword ptr [ebp-$10]

  //end;

  dec dword ptr [ebp-$14]

  jnz @LoopStart

@LoopEnd :

  mov eax,[ebp-$0c]

mov esp,ebp

pop ebp

//ret

end;

 

первое, что мы сделаем, так это удалим локальную переменную NoName.

Code:

function ForLoopBASM2(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx                      //New

mov ebp,esp

add esp,-$14

mov [ebp-$08],edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,[ebp-$08]

sub edx,eax

jl @LoopEnd

//inc edx                    //NoName intialize

//mov [ebp-$14],edx          //NoName intialize

mov [ebp-$10],eax

  //begin

  @LoopStart :

    //Result := Result + I;

    mov eax,[ebp-$10]

    add [ebp-$0c],eax

    inc dword ptr [ebp-$10]

  //end;

  //dec dword ptr [ebp-$14]  //NoName decrement

  mov ebx, [ebp-$10]         //New

  mov ecx, [ebp-$08]         //New

  cmp ebx, ecx               //New

  //jnz @LoopStart

  jbe @LoopStart             //New

@LoopEnd :

  mov eax,[ebp-$0c]

mov esp,ebp

pop ebx                     //New

pop ebp

//ret

end;

 

Строка, помеченная как "New" введена, для создания переменной цикла I. Строка MOV EBX, [EBP-$10] копирует переменную I в регистр EBX. Следующая строка копирует переменную Stop в регистр ECX. Затем в строке CMP EBX, ECX они сравниваются, и инструкцией JBE @LOOPSTART управление передается в начало цикла, если I меньше или равно Stop. Поскольку мы используем регистр EBX и он не разрешен для свободного использования, поэтому мы его сохраняем его в стеке.

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

Code:

function ForLoopBASM4(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

mov [ebp-$08],edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,[ebp-$08]

//sub edx,eax

//jl @LoopEnd

mov [ebp-$10],eax

  //begin

  @LoopStart :

    mov ebx, [ebp-$10]

    mov ecx, [ebp-$08]

    cmp ebx, ecx

    ja  @LoopEnd

    //Result := Result + I;

    mov eax,[ebp-$10]

    add [ebp-$0c],eax

    inc dword ptr [ebp-$10]

  //end;

  //mov ebx, [ebp-$10]

  //mov ecx, [ebp-$08]

  //cmp ebx, ecx

  //jbe @LoopStart

  jmp @LoopStart

@LoopEnd :

  mov eax,[ebp-$0c]

mov esp,ebp

pop ebx

pop ebp

end;

 

 

Проверка на окончания цикла была перемещена в начало и тест был инвертирован. На месте старой проверки теперь находится безусловный переход. Этот переход единственное, что сделано по отношению к инверсной оптимизации. В не оптимизированном цикле было два  перехода,  оптимизированным один. Проверка вверху, то что проверяется всегда. Start был на Stop и теперь лишнее и поэтому удалено. Перед проведением измерений по эффекту от двух оптимизаций, хорошей идеей будет оптимизировать часть или все, что возможно, стек в регистры, регистры в стек. Данный процесс называется – размещение в регистрах и это одна из самых важных оптимизаций на всех архитектурах, но это особенно важно для архитектуры Intel, поскольку в ней малое количество доступных регистров. Если нет места для всех переменных в регистрах, то важно определить какие переменные поместить в регистры. Инструкции MOV в теле цикла наиболее важные кандидаты на это. Они выполняются большое количество раз. Инструкции за пределами цикла выполняются только раз. Переменные внутри цикла первыми должны быть размещены в регистрах. Это переменные I, Stop и Result. Теперь рассмотрим использование регистров для временных переменных. Если переменная всегда копируется в тот же самый временный регистр, то ее желательно разместить в этом регистре. Переменная Stop в регистре EDX при входе в функцию и также используется как временный регистр, во всех строках, кроме двух строк. Здесь есть две строки в цикле, которые мы добавили, изменим их

mov ecx, [ebp-$08]

cmp ebx, ecx

на

mov edx, [ebp-$08]

cmp ebx, edx

Регистр EAX используется для Start вверху функции и как Result в остальной части функции. Если нет перекрытия по использованию, то мы можем использовать EAX для Result, как только Start прекратит его использования. После того, как Start назначен переменной I (MOV [EBP-$10], EAX), он больше нигде не используется и регистр EAX свободен для использования для Result, кроме тех строк, где EAX используется как временное хранилище для I.

mov eax,[ebp-$10]

add [ebp-$0c],eax

inc dword ptr [ebp-$10]

после того, как ECX прекращает использоваться, мы можем его использовать как временное хранилище для I, вместо EAX.

mov ecx,[ebp-$10]

add [ebp-$0c],ecx

inc dword ptr [ebp-$10]

Подведем итог по первой части оптимизации по использованию регистров: Result в EAX, I в ECX и Stop в EDX.

В начале заменим все строки со Stop. [EBP-$08] на использование EDX.

Code:

function ForLoopBASM6(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

//mov [ebp-$08],edx

mov edx,edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

//mov edx,[ebp-$08]

mov edx,edx

mov [ebp-$10],eax

  //begin

  @LoopStart :

    mov ebx, [ebp-$10]

    //mov edx, [ebp-$08]

    mov edx, edx

    cmp ebx, edx

    ja  @LoopEnd

    //Result := Result + I;

    mov ecx,[ebp-$10]

    add [ebp-$0c],ecx

    inc dword ptr [ebp-$10]

  //end;

  jmp @LoopStart

@LoopEnd :

  mov eax,[ebp-$0c]

mov esp,ebp

pop ebx

pop ebp

end;

 

Затем распределим ECX для I, заменив  [EBP-$10] на ECX.

Code:

function ForLoopBASM7(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

mov edx,edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,edx

//mov [ebp-$10],eax

mov ecx,eax

  //begin

  @LoopStart :

    //mov ebx, [ebp-$10]

    mov ebx, ecx

    mov edx, edx

    cmp ebx, edx

    ja  @LoopEnd

    //Result := Result + I;

    //mov ecx,[ebp-$10]

    mov ecx,ecx

    add [ebp-$0c],ecx

    //inc dword ptr [ebp-$10]

    inc ecx

  //end;

  jmp @LoopStart

@LoopEnd :

  mov eax,[ebp-$0c]

mov esp,ebp

pop ebx

pop ebp

end;

 

И на конец используем EAX для Result. Поскольку EAX также используется вверху функции для Start и как временный регистр для инициализации Result нулем, то мы должны добавить несколько строк для копирования Result в EAX после как EAX более нигде не будет использоваться для других целей.

Code:

function ForLoopBASM8(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

mov edx,edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,edx

mov ecx,eax

mov eax, [ebp-$0c]                //New

  //begin

  @LoopStart :

    mov ebx, ecx

    mov edx, edx

    cmp ebx, edx

    ja  @LoopEnd

    //Result := Result + I;

    mov ecx,ecx

    //add [ebp-$0c],ecx

    add eax,ecx

    inc ecx

  //end;

  jmp @LoopStart

@LoopEnd :

  //mov eax,[ebp-$0c]

  mov eax,eax

mov esp,ebp

pop ebx

pop ebp

end;

 

 

поскольку мы особо не обращали внимания при конвертировании на другие вещи, то у нас образовалось много строк типа MOV EAX, EAX. Сразу видно они излишни ;-). Просто удалим их.

Code:

function ForLoopBASM9(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

//mov edx,edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

//mov edx,edx

mov ecx,eax

mov eax, [ebp-$0c]               

  //begin

  @LoopStart :

    mov ebx, ecx

    //mov edx, edx

    cmp ebx, edx

    ja  @LoopEnd

    //Result := Result + I;

    //mov ecx,ecx

    add eax,ecx

    inc ecx

  //end;

  jmp @LoopStart

@LoopEnd :

  //mov eax,eax

mov esp,ebp

pop ebx

pop ebp

end;

 

При оптимизации ассемблерного кода есть две линии поведения, которым мы можем следовать. Мы можем думать как человек, пытаясь проявлять сообразительность, используя информацию из кода. Мы поступили так, когда распределяли регистры. Другой путь – это пытаться использовать системный подход, так как поступает компилятор/оптимизатор. Это путь разработки алгоритмов. Данный подход позже даст многое для оптимизации, так мы поступали много раз выше. Удаление лишних строк кода, MOV EAX, EAX, был примером удаления мертвого кода, что является базисом для любых оптимизаторов.

Вверху функции мы еще имеем некоторые ссылки на стек. Для их удаления мы должны разместить эти переменные также в регистрах. В данное время мы выберем регистры EDI и ESI, поскольку они ни где не используются. Используем ESI для [EBP-$04] и EDI для [EBP-$0C]. Поскольку регистры ESI и EDI должны быть сохранены, мы поместим их в стек и потом восстановим.

Code:

function ForLoopBASM10(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

push esi

push edi

mov ebp,esp

add esp,-$14

//mov [ebp-$04],eax

mov esi,eax

//Result := 0;

xor eax,eax

//mov [ebp-$0c],eax

mov edi,eax

//for I := Start to Stop do

//mov eax,[ebp-$04]

mov eax,esi

mov ecx,eax

//mov eax, [ebp-$0c]

mov eax, edi

  //begin

  @LoopStart :

    mov ebx, ecx

    cmp ebx, edx

    ja  @LoopEnd

    //Result := Result + I;

    add eax,ecx

    inc ecx

  //end;

  jmp @LoopStart

@LoopEnd :

mov esp,ebp

pop edi

pop esi

pop ebx

pop ebp

end;

 

 

Фрейм стека больше нигде не используется и поэтому нет нужды его настраивать, это также сохранит 4 инструкции. Затем заметим, что две строки

mov eax,esi

mov ecx,eax

могут быть заменены одной.

mov ecx, esi

Это пример упрощения копирования с дальнейшим удалением мертвого кода. Любые другие строки не используют значения в EAX далее следующей строки, которая копирует обратно в ECX. Фактически это сразу переписывается строкой MOV EAX, EDI. Поэтому мы можем заменить вторую строку, на строку MOV ECX, ESI и удалить первую, которая становится мертвым кодом.

Code:

function ForLoopBASM11(Start, Stop : Integer) : Integer;

asm

//push ebp

push ebx

push esi

push edi

//mov ebp,esp

//add esp,-$14

mov esi,eax

//Result := 0;

xor eax,eax

mov edi,eax

//for I := Start to Stop do

//mov eax,esi

//mov ecx,eax

mov ecx, esi

mov eax, edi

  //begin

@LoopStart :

//mov ebx, ecx

//cmp ebx, edx

cmp ecx, edx

ja  @LoopEnd

  //Result := Result + I;

add eax,ecx

inc ecx

  //end;

jmp @LoopStart

@LoopEnd :

//mov esp,ebp

pop edi

pop esi

pop ebx

//pop ebp

end;

 

Строка XOR EAX, EAX присваивает начальное значение переменной Result в 0 и может быть перемещена на несколько строк ниже в место, где EAX будет использован в первый раз. Зато она никогда не должна быть помещена в тело цикла, что изменит логику функции, но может быть перед loopStart. Это убирает необходимость в копировании EAX в EDI и обратно в EAX в строке перед строкой комментария //FOR I := START TO STOP DO.

Code:

function ForLoopBASM12(Start, Stop : Integer) : Integer;

asm

push ebx

push esi

push edi

mov esi,eax

//for I := Start to Stop do

mov ecx, esi

//Result := 0;

xor eax,eax

//mov edi,eax

//mov eax, edi

  //begin

  @LoopStart :

    cmp ecx, edx

    ja  @LoopEnd

    //Result := Result + I;

    add eax,ecx

    inc ecx

  //end;

  jmp @LoopStart

@LoopEnd :

pop edi

pop esi

pop ebx

end;

 

После всего этого мы видим две строки MOV, которые копируют EAX в ECX через ESI. Это оставляет копию EAX в ESI, которая не используется. Поэтому одна пересылка EAX directly into ECX может заменить эти две строки. Это также уменьшение копирования и удаление мертвого кода.

Code:

function ForLoopBASM13(Start, Stop : Integer) : Integer;

asm

push ebx

//push esi

push edi

//mov esi,eax

//for I := Start to Stop do

//mov ecx, esi

mov ecx, eax

//Result := 0;

xor eax,eax

  //begin

  @LoopStart :

    cmp ecx, edx

    ja  @LoopEnd

    //Result := Result + I;

    add eax,ecx

    inc ecx

  //end;

  jmp @LoopStart

@LoopEnd :

pop edi

//pop esi

pop ebx

end;

После удаления использования ESI, теперь нет необходимости в его сохранении и восстановлении.

Code:

function ForLoopBASM14(Start, Stop : Integer) : Integer;

asm

//push ebx

//push edi

//for I := Start to Stop do

mov ecx, eax

//Result := 0;

xor eax,eax

  //begin

  @LoopStart :

    cmp ecx, edx

    ja  @LoopEnd

    //Result := Result + I;

    add eax,ecx

    inc ecx

  //end;

  jmp @LoopStart

@LoopEnd :

//pop edi

//pop ebx

end;

 

Также, хоть и немного поздно мы видим, что EBX и EDI нигде не используются. После их удаления и удаления комментариев, в результате получилась следующая красивая функция.

Code:

function ForLoopBASM15(Start, Stop : Integer) : Integer;

asm

mov ecx, eax

//Result := 0;

xor eax,eax

//for I := Start to Stop do

@LoopStart :

cmp ecx, edx

ja  @LoopEnd

//Result := Result + I;

add eax,ecx

inc ecx

jmp @LoopStart

@LoopEnd :

end;

 

Это потребовало много времени и усилий по оптимизации, поскольку мы начали с не оптимизированной версии компилятора. Данный длинный процесс послужил для иллюстрации количества работы оставленной компилятором для оптимизации. Иногда мы не используем должные алгоритмы для оптимизации, но мы можем получить тот же самый результат, используя их.

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

Code:

function ForLoopOpt(Start, Stop : Integer) : Integer;

var

I : Integer;

 

begin

{

}

Result := 0;

{

xor ecx,ecx

}

for I := Start to Stop do

{

sub edx,eax

jl +$08

inc edx

xchg eax,edx

}

begin

  Result := Result + I;

  {

  add ecx,edx

  inc edx

  }

end;

{

dec eax

jnz -$06

}

{

mov eax,ecx

}

end;

 

 

В данном случае Delphi действительно сделало прекрасную работу. Только две строки режут наши глаза. XCHG EAX, EDX простой обмен значениями в EAX и EDX, и MOV EAX, ECX копирует результат в EAX. Обе строки находятся за пределами цикла и не отнимают много времени. Теперь мы имеем две функции – одна без оптимизации цикла и одна с двумя. Для полного комплекта нам нужно еще две функции, одна с обратным циклом и одна с переменной NoName, только с оптимизацией. В начале урока мы видели, как удалить две оптимизации и это я сделал в двух оставшихся функциях. В Delphi оптимизированной выше функции, я оптимизировал инструкцию XCHG для обмена значений двух регистров.

Поскольку мы хотим увидеть максимальный эффект только от оптимизации циклов, я удалил тело цикла Result := Result + I;

Здесь четыре последние функции.

Code:

function ForLoopNoLoopInverNoNoName(Start, Stop : Integer) : Integer;

asm

mov ecx, eax

//Result := 0;

xor eax,eax

//for I := Start to Stop do

@LoopStart :

cmp ecx, edx

ja  @LoopEnd

inc ecx

jmp @LoopStart

@LoopEnd :

end;

 

 

Цикл состоит их 4 инструкции. 1 CMP, 1 JA, 1 INC и 1 JMP. Latency и throughput для этих двух инструкции на P4 следующие: CMP 0.5/0.5, JA X/0.5, INC 0.5/1 и JMP X/0.5. X означает, что "latency is not applicable to this instruction" «Латентность не применима к данной инструкции». Дополнительная латентность, которую мы имеет: 0.5 + X + 0.5 + X = ? циклов.

Code:

function ForLoopLoopInverNoNoName(Start, Stop : Integer) : Integer;

asm

mov ecx, eax

//Result := 0;

xor eax,eax

//for I := Start to Stop do

cmp ecx, edx

ja  @LoopEnd

@LoopStart :

inc ecx

cmp ecx, edx

jbe @LoopStart

@LoopEnd :

end;

 

Данный цикл состоит из 3 инструкций, также с неизвестной суммой латентности.

Code:

function ForLoopNoLoopInverNoName(Start, Stop : Integer) : Integer;

asm

//Result := 0;

xor ecx,ecx

//for I := Start to Stop do

sub edx,eax

cmp edx, 0

@LoopStart :

jz  @LoopEnd

inc eax

dec edx

jmp @LoopStart

@LoopEnd :

mov eax,ecx

end;

 

 

Данный цикл состоит из 4 инструкций, также с неизвестной суммой латентности. Заметим, что две инструкции INC/DEC имеют возможность выполняться параллельно. Поскольку за DEC NoName инструкцией не следует условный переход JMP, это выглядит как преимущество, в отсутствии необходимости использования инструкций CMP или TEST для установки флагов, но инструкция JMP не изменяет значения флагов и они доступны, когда мы попадаем на инструкцию JZ в начале цикла. Только в первой итерации инструкция CMP EDX,0 необходима для этого.

Code:

function ForLoopLoopInverNoName(Start, Stop : Integer) : Integer;

asm

//Result := 0;

xor ecx,ecx

//for I := Start to Stop do

sub edx,eax

jl @LoopEnd

inc edx

@LoopStart :

inc eax

dec edx

jnz @LoopStart

@LoopEnd :

mov eax,ecx

end;

 

 

Данный цикл состоит из 3 инструкций, также с неизвестной суммой латентности. Здесь также есть независимая пара INC/DEC.

Это очень простая измерительная программа (benchmark), которую я использую для проверки производительности этих четырех функций.

Code:

var

Starttime, Endtime, Runtime : TDateTime;

I, LoopResult : Integer;

RunTimeSec, NoOfLoopsPerSec, NoOfLoops, ClockCount, LoopEnd2Float,

LoopEndFloat, LoopStartFloat : Double;

 

begin

Starttime := Time;

for I := 1 to LOOPEND2 do

begin

  LoopResult := ForLoopNoLoopInverNoName(LOOPSTART, LOOPEND);

end;

Endtime := Time;

Runtime := Endtime - Starttime;

CEdit.Text := IntToStr(LoopResult);

RuntimeEdit4.Text := TimeToStr(Runtime);

RunTimeSec := RunTime*24*60*60;

LoopEnd2Float := LOOPEND2;

LoopEndFloat := LOOPEND;

LoopStartFloat := LOOPSTART;

NoOfLoops := LoopEnd2Float * (LoopEndFloat - LoopStartFloat);

NoOfLoopsPerSec := NoOfLoops / RunTimeSec;

ClockCount := CLOCK / NoOfLoopsPerSec;

ClockCountEdit4.Text := FloatToStrf(ClockCount, ffFixed, 9, 1);

end;

 

результаты на P4 1920 следующие:

No Loop Inversion and No NoName variable    00:00:55  (2.7 Clock cycles)

Loop Inversion but No NoName variable       00:00:39  (1.9 Clock cycles)

No Loop Inversion but NoName variable       00:01:02  (3.0 Clock cycles)

Loop Inversion + NoName                     00:00:41  (2.0 Clock cycles)

результаты на P3 1400 следующие:

No Loop Inversion and No NoName variable    00:01:26  (3.0 Clock cycles)

Loop Inversion but No NoName variable       00:01:26  (3.0 Clock cycles)

No Loop Inversion but NoName variable       00:01:55  (4.0 Clock cycles)

Loop Inversion + NoName                     00:01:26  (3.0 Clock cycles)

Конечно, clock count числа должны быть целыми. На P4 возможны пол цикла, в связи с double-clocked ALU. Наши измерения не так хороши, как хотелось бы, но для сравнения производительности циклов они достаточны.

Заключение для P4. Используйте только No Loop Inversion или loop inversion with NoName variable оптимизацией.

Заключение для P3. Не используйте No Loop Inversion but NoName variable оптимизацию.

Заключение для обеих платформ. Используйте обе оптимизации как делает Delphi.

Также обратите внимание насколько эффективен P4 на этом коде.

 

Урок 6

Это урок 6 и его тема CharPos. Данная функция ищет первое вхождение символа в строке, и возвращает его позицию когда найдет. Если ничего не найдено, то возвращается 0. функция из Delphi делает тоже самое, но с различием, что ищется вхождение подстроки в строке. Передача символа в Pos как подстроки возможна и это путь использования Pos как CharPos. В данном уроке мы разработаем CharPos, которая будет примерно в 4 раза быстрее, чем Pos.

Как обычно мы начнем с Паскаль реализации алгоритма.

Code:

function CharPos2(Chr : Char; const Str : AnsiString) : Cardinal;

var

I : Integer;

begin

if (Str <> '') then

begin

   I := 0;

   repeat

     Inc(I);

   until((Str[I] = Chr) or (Str[I] = #0));

   if (Str[I] <> #0) then

     Result := I

   else

     Result := 0;

end

else

   Result := 0;

end;

 

 

В функцию предаются два параметры типа Char и string. Параметр string передается как константа. Результат работы функции типа Cardinal. В начале в функции проверяется, что входная строка не пустая и если пустая, то возвращается 0. Если строка есть, то проходим по ней пока не найдем в цикле repeat until до тех пор пока не встретим совпадение с входным символом. Если встретился символ 0, он также является признаком окончания строки и цикла. Поскольку цикл может завершиться в случае нахождения символа и в случае достижения конца строки мы должны знать причину, что бы вернуть правильный результат. Если цикл закончился нахождением символа, то мы вернем переменную счетчика, а иначе вернем 0.

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

Code:

function CharPos1(Chr : Char; const Str : AnsiString) : Cardinal;

var

StrLenght, I : Integer;

begin

StrLenght := Length(Str);

if StrLenght > 0 then

begin

   I := 0;

   repeat

     Inc(I);

   until((Str[I] = Chr) or (I > StrLenght));

   if I <= StrLenght then

     Result := I

   else

     Result := 0;

end

else

   Result := 0;

end;

 

 

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

Code:

const

NOOFLOOPS : Cardinal = 200000;

SCALE : Cardinal = 1000;

 

procedure Benchmark;

var

lpPerformanceCount, StartCount, EndCount : TLargeInteger;

Succes : Boolean;

Str, Str1, FunctionName : AnsiString;

Chr1, Chr2 : Char;

I, CharPos, J, K, Bench, SumBench : Cardinal;

StringArray : array[1..255] of AnsiString;

 

begin

Series1.Clear;

Str1 := 'T';

for J := 1 to 255 do

begin

   StringArray[J] := Str1;

   Str1 := 'A' + Str1;

end;

SumBench := 0;

Chr1 := 'T';

Chr2 := 'X';

for K := 1 to 255 do

begin

   Str := StringArray[K];

   Succes := QueryPerformanceCounter(lpPerformanceCount);

   if Succes then

     StartCount := lpPerformanceCount

   else

     raise Exception.Create('QueryPerformanceCounter failed');

   for I := 1 to NOOFLOOPS dиo

   begin

     CharPos := CharPosFunction(Chr1, Str);

   end;

   for I := 1 to NOOFLOOPS do

   begin

     CharPos := CharPosFunction(Chr2, Str);

   end;

   Succes := QueryPerformanceCounter(lpPerformanceCount);

   if Succes then

     EndCount := lpPerformanceCount

   else

     raise Exception.Create('QueryPerformanceCounter failed');

   Bench := Round((EndCount - StartCount) / SCALE);

   Series1.AddXY(K, Bench, '', clBlue);

   Bench := Round(Bench / K);

   SumBench := SumBench + Bench;

   Update;

end;

FunctionName :=

   FunctionSelectRadioGroup.Items[FunctionSelectRadioGroup.ItemIndex];

ReportRichEdit.Lines.Add(FunctionName + #9 + IntToStr(SumBench));

end;

 

 

Программа измерения строит тестовый массив из 255 AnsiStrings. Первая строка 'T'. 'T' также символ для поиска. Поэтому строка номер 1 наиболее короткая для успешного поиска. Следующие строки равны 'AT', 'AAT' и 'AAAT'. Я надеюсь, что этот шаблон прост и понятен. Также важно провести измерение и для неуспешного поиска. В этом случае для поиска мы используем символ 'X'. Программа измерения делает некоторое количество (NOOFLOOPS) поисков по каждой строке и измеряет время на каждой строке. Поскольку мы хотим, что бы результат был аппроксимирован независимо от длины строки, то полученное время делится на длину строки.

В данном тесте CharPos1 получил результат 767 на P4 1600A, разогнанный до 1920 и CharPos2 получил результат 791. Для сравнения Delphi Pos получил результат всего 2637.

Поскольку CharPos1 незначительно лучше, чем CharPos2, то мы выбрали его для дальнейшей оптимизации. Это ассемблерный код на Delphi 6 откомпилированный с включенной оптимизацией.

Code:

function CharPos14(Chr : Char; const Str : AnsiString) : Cardinal;

var

StrLenght, I : Integer;

begin

{

push ebx

push esi

mov  esi,edx

mov  ebx,eax

}

StrLenght := Length(Str);

{

mov  eax,esi

call @LStrLen

mov  edx,eax

}

if StrLenght > 0 then

{

test edx,edx

jle  @Else1Begin

}

begin

  I := 0;

  {

  xor eax,eax

  }

  repeat

   {

   @RepeatBegin :

   }

   Inc(I);

   {

   inc eax

   }

  until((Str[I] = Chr) or (I > StrLenght));

  {

  cmp bl,[esi+eax-$01]

  jz  @If2

  cmp edx,eax

  jnl @RepeatBegin :

  }

  if I <= StrLenght then

  {

  @If2 :

  cmp edx,eax

  jnl @Exit

  }

   Result := I

   {

   }

  else

   Result := 0;

   {

   xor eax,eax

   pop esi

   pop ebx

   ret

   }

end

else

Result := 0;

{

@Else1Begin :

xor eax,eax

}

{

@Exit :

pop esi

pop ebx

}

end;

 

 

В данный момент здесь нет фрейма стека. Регистры EBX и ESI используются, и поэтому требуется их сохранения и восстановление при выходе из функции. Поскольку функция не имеет своего собственно фрейма стека, то они просто помещаются на верхушку стека текущего фрейма. Входные параметры принимаются в регистрах EAX и EDX и они первым делом копируются в регистры ESI и EBX. Функция Length имеет внутренне секретное имя, которое LStrLen. В данную функцию передается параметр  Str, который передается через регистр EAX. Отсюда мы видим, что функция LStrLen также следует регистровому соглашению о вызове. Str был получен через регистр EDX, затем был скопирован в регистр ESI и затем в EAX. LStrLen возвращает свой результат также в регистре EAX. Этот результат копируется в EDX и сравнивается с 0. TEST EDX, EDX, тоже самое, что и CMP EDX,0 и устанавливает флаги. Инструкция JLE проверяет флаги и передает управление в часть ELSE блока IF-ELSE, если StrLenght меньше или равен нулю. В части ELSE мы видим только одну Паскаль строку, которая Result := 0;. Поскольку наша функция должна вернуть результат в EAX мы создаем значение 0 как XOR EAX с самим собой. Если длина строки больше нуля, то управление продолжается в части блока IF. Первая строка этого блока устанавливает начальное значение счетчика I в ноль. Для этого снова используется инструкция XOR. Тело цикла имеет только одну строку, очень простую для понимания  INC(I); = INC EAX. И ассемблерный, и Паскаль код делают одинаково ;-)

Реализация проверки цикла, это то место где проводится реальная работа. Это сделано с помощью четырех строк на ассемблере.

Code:

cmp bl,[esi+eax-$01]

jz  @If2

cmp edx,eax

jnl @RepeatBegin :

 

Мы видим здесь две инструкции перехода. Последняя начинает цикла, а первая выходит из цикла. Здесь также две инструкции сравнения CMP для установки флагов. Вторая очень простая для понимания. Она сравнивает EAX с EDX. Быстрый взгляд на Паскаль код, показывает, что здесь StrLenght и I в этих регистрах. В действительности мы видим, что в eax находится I, а вверху функции мы видим, что StrLenght находится в EDX.

В строке 4 параметр Chr бил скопирован в регистр EBX, но char размером только в один байт. Поэтому первая инструкция CMP сравнивает, что с в BL, который содержит младший байт EBX. Мы предполагаем, что символ поиска - Chr – сравнивается с символом 1, 2, 3… входной строки. Поэтому выражение [ESI+EAX-$01] должно быть указателем на эту строку. EAX это счетчик цикла I, который имеет значение 1, при первой итерации. Регистр ESI должен быть адресом параметра Str, который был принят через регистр EDX, и сразу был скопирован в регистр ESI. -$01 это константа смещения, которая необходима, поскольку первый символ в AnsiString расположен по смещению 0. Это позиция, на которую указывает Str.

А куда же пропал OR из кода Паскаля? Для понимания этого мы должны поговорить насчет оптимизации, называемой частичное выполнение логических выражений. Эта оптимизация применяется к логическому оператору AND, и к логическому оператору OR.

Посмотрим это на примере таблицы истинности для AND.

false and false is false

false and true  is false

true  and false is false

true  and true  is true

Оператор AND возвращает значение TRUE только если оба операнда TRUE. В этом и содержится преимущество при оптимизации при частичном выполнении логических выражений. Если один из операндов FALSE, то нет необходимости проверять другой, поскольку результат все равно FALSE, вне зависимости от его значения.

Таблица истинности для оператора OR:

false or false is false

false or true  is true

true  or false is true

true  or true  is true

Результат для OR истинен, если хотя бы один из операндов или оба операнда также истинны. Если один из операндов истинен, то также нет нужды проверять другой.

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

Если бы мы знали, что ни будь о строках и символах переданных нашей функции до вызова, то мы могли бы получить преимущества, просто сменив порядок тестов, так что бы получить значение TRUE первым.

Попробуйте сменить параметр компилятора "complete Boolean evaluation", в свойствах проекта, и посмотрите какой код будет сгенерировать.

Остаток кода уже разобран в более ранних уроках, и мы пропустим его объяснение, лучше сходите и выпейте взамен чашечку кофе ;-)

Теперь можно выполнить некоторую оптимизацию. В начале превратим функцию в чисто ассемблерную. Метки были объяснены в листинге предыдущего кода. Здесь видно, что они следуют Паскаль коду интуитивным образом.

Code:

function CharPos15(Chr : Char; const Str : AnsiString) : Cardinal;

//var

//StrLenght, I : Integer;

 

asm

push ebx

push esi

mov  esi,edx

mov  ebx,eax

//StrLenght := Length(Str);

mov  eax,esi

call System.@LStrLen

mov  edx,eax

//if StrLenght > 0 then

test edx,edx

jle  @Else1Begin

//I := 0;

xor eax,eax

//repeat

@RepeatBegin :

//Inc(I);

inc  eax

//until((Str[I] = Chr) or (I > StrLenght));

cmp  bl,[esi+eax-$01]

jz   @If2

cmp  edx,eax

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

cmp  edx,eax

jnl  @Exit

//Result := I

//else

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//else

//Result := 0;

@Else1Begin :

xor eax,eax

@Exit :

pop  esi

pop  ebx

end;

 

 

Вызов функции LStrLen сделан с префиксом System, иначе компилятор не сможет распознать ее. LStrLen реализована в модуле System.

Секция VAR удалена, поскольку мы не ссылаемся ни к каким переменным по имени.

Code:

function CharPos16(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

push esi

mov  esi,edx

mov  ebx,eax

//StrLenght := Length(Str);

mov  eax,esi

//call System.@LStrLen

//*************

test eax,eax

jz  @LStrLenExit

mov eax,[eax-$04]

@LStrLenExit :

//*************

mov  edx,eax

//if StrLenght > 0 then

test edx,edx

jle @Else1Begin

//I := 0;

xor eax,eax

//repeat

@RepeatBegin :

//Inc(I);

inc  eax

//until((Str[I] = Chr) or (I > StrLenght));

cmp  bl,[esi+eax-$01]

jz   @If2

cmp  edx,eax

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

cmp  edx,eax

jnl  @Exit

//Result := I

//else

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//else

//Result := 0;

@Else1Begin :

xor eax,eax

@Exit :

pop  esi

pop  ebx

end;

 

 

Первая вещь, которую мы сделаем, это сделаем функцию LstrLen inline. Сделаем это путем трассировки и копированием ее тела из окна CPU view. Она состоит из четырех строк.

Code:

test eax,eax

jz +$03

mov eax,[eax-$04]

ret

 

Если указатель, переданный через EAX, в функцию LStrLen имеет nil, то ничего не делается, а просто производится возврат из функции. Если же указатель действительный, то длина строки расположена, в 4 предшествующих строке байтах. Эти 4 байта возвращаются, через регистр EAX. Для превращения этой функции в inline функцию, мы заменим вызов этой функции этими четырьмя строками. Инструкция JZ передает управление на инструкцию RET. Взамен инструкции RET мы передадим управление на метку LStrLenExit. Инструкция RET осуществляет возврат из функции. Данная инструкция RET должна быть удалена, иначе она вернет управление в CharPos, это не то, что мы хотим. А вот так наша встроенная (inline) функция должна выглядеть.

Code:

test eax,eax

jz  @LStrLenExit

mov eax,[eax-$04]

@LStrLenExit :

 

function CharPos17(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

push esi

mov  esi,edx

mov  ebx,eax

//StrLenght := Length(Str);

mov  eax,esi

//*************

test eax,eax

//jz  @LStrLenExit

jz  @Else1Begin

mov eax,[eax-$04]

//@LStrLenExit :

//*************

mov  edx,eax

//if StrLenght > 0 then

//test edx,edx

//jle @Else1Begin

//I := 0;

xor eax,eax

//repeat

@RepeatBegin :

//Inc(I);

inc  eax

//until((Str[I] = Chr) or (I > StrLenght));

cmp  bl,[esi+eax-$01]

jz   @If2

cmp  edx,eax

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

cmp  edx,eax

jnl  @Exit

//Result := I

//else

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//else

//Result := 0;

@Else1Begin :

xor eax,eax

@Exit :

pop  esi

pop  ebx

end;

 

 

Теперь мы видим, что Паскаль строка; IF STRLENGHT > 0 THEN, проверяет длину точно также, как первая строка во встроенной LStrLen. Проверка Str на nil вполне достаточно ;-). Вторая строка удалена и первая изменена, чтобы переход был на @Else1Begin вместо простого выхода из встроенной StrLen функции, если Str равен nil. Теперь нет надобности в метке LStrLenExit.

Code:

function CharPos18(Chr: Char; const Str: AnsiString) : Cardinal;

asm

push ebx

push esi

mov  esi,edx

mov  ebx,eax

//StrLenght := Length(Str);

//mov  eax,esi

//if StrLenght > 0 then

//test eax,eax

test esi,esi

jz  @Else1Begin

//mov eax,[eax-$04]

mov eax,[esi-$04]

mov  edx,eax

//I := 0;

xor eax,eax

//repeat

@RepeatBegin :

//Inc(I);

inc  eax

//until((Str[I] = Chr) or (I > StrLenght));

cmp  bl,[esi+eax-$01]

jz   @If2

cmp  edx,eax

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

cmp  edx,eax

jnl  @Exit

//Result := I

//else

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//else

//Result := 0;

@Else1Begin :

xor eax,eax

@Exit :

pop  esi

pop  ebx

end;

 

 

Мы переместили проверку STRLENGHT = 0 и комментарий //IF STRLENGHT > 0 также должен быть перемещен. После встраивания функции стало возможным избавиться от копирования ESI в этих строках.

mov  eax,esi

//*************

test eax,eax

jz  @Else1Begin

mov eax,[eax-$04]

Последние строки переписывают EAX и последнее использованное значение в EAX, которое было скопировано из ESI.

mov  eax,esi

//*************

//test eax,eax

test esi,esi

jz  @Else1Begin

//mov eax,[eax-$04]

mov eax,[esi-$04]

В действительности мы должны также посмотреть в точку возможного перехода Else1Begin и увидим, что значение из EAX также используется здесь. Мы видим, что значение в EAX сразу обнуляется в следующей за меткой строке и поэтому не используется. Так что первая строка кажется лишняя и должна быть удалена.

 

Code:

//mov  eax,esi

test esi,esi

jz  @Else1Begin

mov eax,[esi-$04]

 

function CharPos19(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

push esi

mov  esi,edx

mov  ebx,eax

//if StrLenght > 0 then

test esi,esi

jz  @Else1Begin

//StrLenght := Length(Str);

//mov eax,[esi-$04]

mov edx,[esi-$04]

//mov  edx,eax

//I := 0;

xor eax,eax

//repeat

@RepeatBegin :

//Inc(I);

inc  eax

//until((Str[I] = Chr) or (I > StrLenght));

cmp  bl,[esi+eax-$01]

jz   @If2

cmp  edx,eax

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

cmp  edx,eax

jnl  @Exit

//Result := I

//else

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//else

//Result := 0;

@Else1Begin :

xor eax,eax

@Exit :

pop  esi

pop  ebx

end;

 

 

Как результат встраивания функции LStrLen мы можем также удалить одну инструкцию. Функция LStrLen возвращает свой результат в EAX, затем он копируется в EDX. MOV EAX, [ESI-$04]. Это можно изменить на MOV EDX, [ESI-$04], а инструкцию MOV EDX, EAX можно удалить.

После этого изменения сменим наш фокус на цикл. Это особенно важно, поскольку это выполняется множество раз, в зависимости от длины строки и позиции, в которой произойдет сравнение.

Code:

function CharPos20(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

push esi

mov  esi,edx

mov  ebx,eax

//if StrLenght > 0 then

test esi,esi

jz  @Else1Begin

//StrLenght := Length(Str);

mov edx,[esi-$04]

//I := 0;

xor eax,eax

dec  esi

@RepeatBegin :

//Inc(I);

inc  eax

//until((Str[I] = Chr) or (I > StrLenght));

//cmp  bl,[esi+eax-$01]

cmp  bl,[esi+eax]

jz   @If2

cmp  edx,eax

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

cmp  edx,eax

jnl  @Exit

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//Result := 0;

@Else1Begin :

xor eax,eax

@Exit :

pop  esi

pop  ebx

end;

 

Когда мы проанализируем код, то мы увидим, что здесь есть смещение -1 при адресации строки. Нет необходимости вычитать это смещение при каждой итерации. Будет хорошо, если мы один раз уменьшим указатель на Str в ESI до начала цикла. Мы также можем уменьшить счетчик цикла в EAX, но затем мы должны будем увеличить его на единицу при возврате результата.

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

Code:

function CharPos22(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

push esi

mov  esi,edx

mov  ebx,eax

//if StrLenght > 0 then

test esi,esi

jz  @Else1Begin

//StrLenght := Length(Str);

mov edx,[esi-$04]

//I := 0;

//xor  eax,eax

xor ecx,ecx

dec  esi

@RepeatBegin :

//Inc(I);

//inc  eax

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

//cmp  bl,[esi+eax]

cmp  bl,[esi+ecx]

jz   @If2

//cmp  edx,eax

cmp  edx,ecx

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

//cmp  edx,eax

cmp  edx,ecx

jnl  @Exit

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//Result := 0;

@Else1Begin :

xor eax,eax

pop  esi      //New

pop  ebx      //New

ret           //New

@Exit :

mov  eax, ecx

pop  esi

pop  ebx

end;

 

 

Во всех строках, в которых EAX использовался как I, EAX изменен на ECX. Поскольку I это возвращаемое значение функции при нахождении позиции и возвращаться должно через EAX, мы должны скопировать ECX в EAX до перехода на метку @Exit. Это приводит нас к небольшой проблеме, поскольку переход Else1Begin также осуществляется сюда, и в этой ситуации мы скопируем значение из ECX в EAX, которое мы только что очистили. Это исправляется строками помеченными как «new».

Теперь мы готовы к удалению лишнего копирования EAX. Регистр EBX используется только в одной строке. Это строка CMP BL, [ESI+ECX], которую изменим на CMP AL, [ESI+ECX]. Затем удалим ненужное теперь MOV EBX, EAX. Это устранение лишнего копирования и удаление мертвого кода и мы можем приступить к наиболее важной части оптимизации.

Code:

function CharPos23(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

push esi

mov  esi,edx

//mov  ebx,eax

//if StrLenght > 0 then

test esi,esi

jz  @Else1Begin

//StrLenght := Length(Str);

mov edx,[esi-$04]

//I := 0;

xor ecx,ecx

dec  esi

@RepeatBegin :

//Inc(I);

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

//cmp  bl,[esi+ecx]

cmp  al,[esi+ecx]

jz   @If2

cmp  edx,ecx

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

cmp  edx,ecx

jnl  @Exit

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//Result := 0;

@Else1Begin :

xor eax,eax

pop  esi     

pop  ebx     

ret

@Exit :

mov  eax, ecx

pop  esi

pop  ebx

end;

 

 

Для удаления лишнего копирования EDX (хранит указатель на Str), мы должны освободиться от использования EDX в других местах. Он используется в StrLenght, и мы разместим его в EBX вместо EDX.

Code:

function CharPos24(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

push esi

mov  esi,edx

//if StrLenght > 0 then

test esi,esi

jz  @Else1Begin

//StrLenght := Length(Str);

//mov edx,[esi-$04]

mov ebx,[esi-$04]

//I := 0;

xor ecx,ecx

dec  esi

@RepeatBegin :

//Inc(I);

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

cmp  al,[esi+ecx]

jz   @If2

//cmp  edx,ecx

cmp  ebx,ecx

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

//cmp  edx,ecx

cmp  ebx,ecx

jnl  @Exit

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//Result := 0;

@Else1Begin :

xor eax,eax

pop  esi     

pop  ebx     

ret

@Exit :

mov  eax, ecx

pop  esi

pop  ebx

end;

 

После этого лишнее копирование EDX и MOV ESI, EDX становятся лишними.

Code:

function CharPos25(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

push esi

//mov  esi,edx

//if StrLenght > 0 then

//test esi,esi

test edx,edx

jz  @Else1Begin

//StrLenght := Length(Str);

//mov ebx,[esi-$04]

mov ebx,[edx-$04]

//I := 0;

xor ecx,ecx

//dec  esi

dec  edx

@RepeatBegin :

//Inc(I);

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

//cmp  al,[esi+ecx]

cmp  al,[edx+ecx]

jz   @If2

cmp  ebx,ecx

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

cmp  ebx,ecx

jnl  @Exit

//Result := 0;

xor eax,eax

pop  esi

pop  ebx

ret

//Result := 0;

@Else1Begin :

xor eax,eax

pop  esi     

pop  ebx     

ret

@Exit :

mov  eax, ecx

pop  esi

pop  ebx

end;

 

Так мы удалили использование ESI и избавились от сохранения и его восстановления. При удалении POP ESI, вспомним, что было три выхода и каждый со своим собственным POP ESI.

Code:

function CharPos26(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

//push esi

//if StrLenght > 0 then

test edx,edx

jz  @Else1Begin

//StrLenght := Length(Str);

mov ebx,[edx-$04]

//I := 0;

xor ecx,ecx

dec  edx

@RepeatBegin :

//Inc(I);

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

cmp  al,[edx+ecx]

jz   @If2

cmp  ebx,ecx

jnl  @RepeatBegin

//if I <= StrLenght then

@If2 :

cmp  ebx,ecx

jnl  @Exit

//Result := 0;

xor eax,eax

//pop  esi

pop  ebx

ret

//Result := 0;

@Else1Begin :

xor eax,eax

//pop  esi     

pop  ebx     

ret

@Exit :

mov  eax, ecx

//pop  esi

pop  ebx

end;

 

В строке после метки If2 есть строка, которая идентична второму сравнению для окончания цикла. В Паскаль эта строка была необходимой, поскольку IF I <= STRLENGHT после цикла, поскольку не было ясно, как закончился цикл. Данная строка порождала лишнею инструкцию CMP EBX, ECX, которая теперь явно не нужна. На самом деле это не так, поскольку есть два перехода на метку If2 и только в одном из них есть проверка. Если мы изменим, эти два перехода так, чтобы только один из них шел на to If2, то мы сможем удалить лишнею проверку. Вместо перехода на If2 при сравнении мы можем сделать переход напрямую на метку Exit.

Code:

function CharPos27(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

//if StrLenght > 0 then

test edx,edx

jz  @Else1Begin

//StrLenght := Length(Str);

mov ebx,[edx-$04]

//I := 0;

xor ecx,ecx

dec  edx

@RepeatBegin :

//Inc(I);

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

cmp  al,[edx+ecx]

//jz   @If2

jz   @Exit

cmp  ebx,ecx

jnl  @RepeatBegin

//if I <= StrLenght then

//@If2 :

//cmp  ebx,ecx

//jnl  @Exit

//Result := 0;

xor eax,eax

pop  ebx

ret

//Result := 0;

@Else1Begin :

xor eax,eax

pop  ebx

ret

@Exit :

mov  eax,ecx

pop  ebx

end;

 

Метка If2 становится лишней и когда мы доходим до этой позиции, то мы знаем, что достигнут конец строки (ограничитель #0) и поэтому на не надо повторно тестировать условие.

Также здесь есть два идентичных куска кода, перед меткой Else1Begin и после ее. Удалим верхний кусок.

Code:

function CharPos28(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

//if StrLenght > 0 then

test edx,edx

jz   @Else1Begin

//StrLenght := Length(Str);

mov  ebx,[edx-$04]

//I := 0;

xor ecx,ecx

dec  edx

@RepeatBegin :

//Inc(I);

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

cmp  al,[edx+ecx]

jz   @Exit

cmp  ebx,ecx

jnl  @RepeatBegin

//Result := 0;

//xor  eax,eax

//pop  ebx

//ret

//Result := 0;

@Else1Begin :

xor eax,eax

pop  ebx

ret

@Exit :

mov  eax,ecx

pop  ebx

end;

На этом наш поиск по удалению лишнего кода закончен. Чистая версия кода выглядит так:

Code:

function CharPos29(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

//if StrLenght > 0 then

test edx,edx

jz   @Else1Begin

//StrLenght := Length(Str);

mov  ebx,[edx-$04]

//I := 0;

xor ecx,ecx

dec  edx

@RepeatBegin :

//Inc(I);

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

cmp  al,[edx+ecx]

jz   @Exit

cmp  ebx,ecx

jnl  @RepeatBegin

@Else1Begin :

//Result := 0;

xor eax,eax

pop  ebx

ret

@Exit :

mov  eax,ecx

pop  ebx

end;

 

При итерации в поиске для нахождения позиции или конца строки, данные строки кода повторяются снова и снова.

inc  ecx

cmp  al,[edx+ecx]

jz   @Exit

cmp  ebx,ecx

jnl  @RepeatBegin

Попробуем некоторые варианты и посмотрим, как они исполняются. Наиболее существенно является строка:

cmp  al,[edx+ecx]

Она генерирует две микроинструкции. Одна для загрузки байта по адресу [EDX+ECX] и вторая для сравнения его со значением в AL. Данная строка может быть закодирована также как:

mov ah, byte ptr [edx+ecx]

cmp al, ah

Данный вариант также генерирует две микроинструкции, но это также требует и дополнительный регистр (AH).

Если мы готовы выделить лишний регистр, то это также можно сделать также как:

movzx efx, byte ptr [edx+ecx]

cmp   al, fh

Инструкция MOVZX это пересылка с расширением нуля. Она загружает один байт в младшую часть регистра EFX и заполняет отставшие биты нулями. Конечно, нет такой вещи как регистр efx, но два неиспользуемых регистра ESI и EDI не могут быть доступны на байтовой основе. Поэтому если есть свободный регистр EAX, EBX, ECX или EDX, подставьте это место EDI или ESI и используйте подстановку EBX вместо "EFX".

Данная функция демонстрирует первый вариант.

Code:

function CharPos30(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

//if StrLenght > 0 then

test edx,edx

jz   @Else1Begin

//StrLenght := Length(Str);

mov  ebx,[edx-$04]

//I := 0;

xor ecx,ecx

dec  edx

@RepeatBegin :

//Inc(I);

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

mov  ah, [edx+ecx]

//cmp  al,[edx+ecx]

cmp  al,ah

jz   @Exit

cmp  ebx,ecx

jnl  @RepeatBegin

@Else1Begin :

//Result := 0;

xor eax,eax

pop  ebx

ret

@Exit :

mov  eax,ecx

pop  ebx

end;

 

А эта функция демонстрирует второй вариант.

Code:

function CharPos31(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push ebx

push edi

//if StrLenght > 0 then

test edx,edx

jz   @Else1Begin

//StrLenght := Length(Str);

mov  edi,[edx-$04]

//I := 0;

xor ecx,ecx

dec  edx

@RepeatBegin :

//Inc(I);

inc  ecx

//until((Str[I] = Chr) or (I > StrLenght));

movzx ebx, byte ptr [edx+ecx]

//cmp  al,[edx+ecx]

cmp  al, bl

jz   @Exit

cmp  edi,ecx

jnl  @RepeatBegin

@Else1Begin :

//Result := 0;

xor eax,eax

pop  edi

pop  ebx

ret

@Exit :

mov  eax,ecx

pop  edi

pop  ebx

end;

 

 

Вместо сложения EDX и ECX при расчете адреса в каждой итерации, мы можем их сложить до цикла. Затем если необходимо вычитать их друг из друга для получения счетчика цикла при возврате результата. Это выполняется с помощью инструкции SUB во второй строке поле метки Exit.

Code:

function CharPos32(Chr : Char; const Str : AnsiString) : Cardinal;

asm

push  ebx

push  edi

//if StrLenght > 0 then

test  edx,edx

jz    @Else1Begin

//StrLenght := Length(Str);

mov   edi,[edx-$04]

//I := 0;

xor   ecx,ecx

//dec  edx

add   ecx,edx

@RepeatBegin :

//Inc(I);

//until((Str[I] = Chr) or (I > StrLenght));

movzx ebx, byte ptr [ecx]

inc   ecx

cmp   al, bl

jz    @Exit

//cmp  edi,ecx

test  bl, bl

jnz   @RepeatBegin

@Else1Begin :

//Result := 0;

xor   eax,eax

pop   edi

pop   ebx

ret

@Exit :

mov   eax,ecx

sub   eax,edx

pop   edi

pop   ebx

end;

 

Теперь у нас есть четыре функции для сравнения производительности: CharPos29, CharPos30, CharPos31 и CharPos32.

Результаты на P4 1920 следующие:

CharPos29 716

CharPos30 973

CharPos31 710

CharPos32 702

Победитель функция CharPos32

Результаты на P3 1400 следующие:

CharPos29  949

CharPos30  921

CharPos31  950

CharPos32 1403

Победитель функция CharPos30

Суммарное время

CharPos29 716 + 949  = 1665

CharPos30 973 + 921  = 1894

CharPos31 710 + 950  = 1660

CharPos32 702 + 1403 = 2105

Winner is CharPos31

На P4 выигрышный цикл следующий:

@RepeatBegin :

movzx ebx, byte ptr [ecx]

inc   ecx

cmp   al, bl

jz    @Exit

test  bl, bl

jnz   @RepeatBegin

На P3 выигрышный цикл следующий:

@RepeatBegin :

inc  ecx

mov  ah, [edx+ecx]

cmp  al,ah

jz   @Exit

cmp  ebx,ecx

jnl  @RepeatBegin

При работе на обеих платформах выигрышный цикл следующий:

@RepeatBegin :

inc   ecx

movzx ebx, byte ptr [edx+ecx]

cmp   al, bl

jz    @Exit

cmp   edi,ecx

jnl   @RepeatBegin

Победитель на P4 очень плох на P3 и не может быть использован в библиотеках на других платформах, кроме P4, таких как Delphi RTL. Победитель на P3 выполняется очень отвратительно на P4 и поэтому не должен быть использован в библиотеках для обеих платформ. Победитель для обеих платформ, это функция CharPos31, которая имеет результаты близкие к оптимальным для P4 и также достаточно оптимальные и для P3. Данная функция подходящий выбор для библиотек класса Delphi RTL. Это показывает, что можно оптимизировать функцию для обоих типов процессоров, без потери производительности не более, чем на несколько процентов.

Сравнение производительности P3 и P4 на основе такт-такт всегда немного спектакль. Появляется необоснованная тенденция думать, что P4 имеет as having an inferior design, но это не подтверждается нашим кодом. Взяв победителя для смешанной платформы и сделав приведение результата к 1400 MHz процессору, то мы получим 950 для P3 и 710 * (1920/1400) = 973 для P4. Производительность процессоров почти одинаковая при одинаковой частоте.

 

Урок 7

Добро пожаловать на урок номер 7. Темой сегодняшнего урока является плавающая запятая в BASM. Это уже было темой в более раннем уроке, но этот урок даст дополнительную информацию. Мы посмотрим, как кодировать скаляры на SSE2 и как инструкции обслуживаются в конвейерах FP. Сегодняшний пример это расчет полинома третьего порядка.

Code:

function ArcSinApprox1a(X, A, B, C, D : Double) : Double;

begin

Result := A*X*X*X + B*X*X + C*X + D;

end;

 

 

Вместо анализа и оптимизации этой функции мы посмотрим, как реально мы можем ее использовать. Полином третьего порядка может аппроксимировать функцию в ее интервале, [-1;1], с максимальной абсолютной ошибкой 0.086. Это не очень высокая точность, но то что мы разработаем в данном уроке можно будет расширить до более высоких порядков, в той же манере для получения большей точности.

Параметры A, B, C и D определяют форму кривой для функции и значения для аппроксимации в ArcSin с минимальной ошибкой. Для этой цели мы разработаем оптимизатор, который будет использоваться для измерения производительности. Поскольку ARCSIN(0) = 0 мы непосредственно видим, что D=0 и D можно вывести из оптимизации. Мы также знаем, что ArcSin это нечетная функция и поэтому выражение второго порядка B*X*X не используется в аппроксимации. Это поскольку выражение второго порядка  четное и симметрично относительно оси Y. Функции нечетных порядков имеют анти симметрию вокруг оси Y с F(X) = -F(-X). Все это означает, что наша функция может быть уменьшена до

Result := A*X*X*X + C*X;

Тем не менее, мы не поступим так, поскольку это будет более наглядно с полной функцией. ArcSin это особый случай, и мы хотим сделать его обычным, насколько это возможно.

В функции номер 1a имеется 6 умножений и три сложения. Напишем ее в виде формы Хорнера (Horner form). 

Result := ((A*X + B)*X + C)*X + D;

Уменьшив этим до трех умножений и сложений.

Другая форма такая

Result := (A*X + B)*(X*X)+(C*X + D);

Здесь четыре умножения и три сложения.

На современных процессорах очень важно распараллеливания можно извлечь из формулы и как много умножений и сложений она имеет. Современные процессоры, такие как AMD Athlon, Intel P4 и P3 имеют конвейеры. Конвейеры необходимы на процессорах, работающих на высокой частоте, поскольку основные операции сложения, вычитания, умножения или деления не могут быть выполнены за один такт частоты. На P4 есть конвейер называемый FP_ADD, который предназначен для операций сложения и вычитания. Этот конвейер имеет 5 состояний, это означает, что процесс сложения или вычитания может быть разбит на 5 подзадач. Следовательно, сложение и вычитание выполняются за 5 тактов. Преимущество конвейера состоит в том, что хотя операция требует 5 тактов, но зато каждая новая операция может начинаться в каждом такте. Это потому что первое сложение покидает первую подзадачу при втором такте и эта подзадача может начинать сложение для второго числа. Если мы имеем серию сложений, то первое сложение покидает конвейер на такте 5, второе на такте 6 и так далее. Производительность Throughput получается всего в один такт. Параллельность составляет до 5 сложений или вычитаний в конвейере одновременно. Проблема в том, что если второе или следующие сложения связаны с первым сложением, то придется ожидать, когда закончится первое сложение. Мы можем сказать, что здесь есть зависимость данных между двумя инструкциями, и мы видим, что полная латентность для сложения составляет 2 раза по 5 тактов.

Посмотрим на основе нашей функции работу конвейера.

Result := A*X*X*X + B*X*X + C*X + D;

Также видно, что четвертое выражение может выполняться параллельно, и затем сложено в конце действия. A*X это первая инструкция, готовая для обработки в конвейере F_MUL. Латентность для FMUL на P4 составляет 7 тактов и выражение A*X будет готово через 7 тактов. FMUL имеет максимальную пропускную способность (throughput) в 2 такта. Отсюда ясно, что FMUL не полностью конвейеризирован. Конвейер принимает новую инструкцию на такте три, а не на втором. B*X это вторая инструкция, готовая к выполнению и процессор начнет ее выполнение на такте 3. В такте 5 конвейер снова готов к принятию новой инструкции и это будет инструкция C*X. В такте 7 выполнение инструкции A*X будет закончено и выражение (A*X)*X можно будет начать вычислять в такте 8. В такте 10 вычисление выражения B*X будет закончено и процессор начнет выполнению выражения (B*X)*X. В такте 12 также будет закончено выполнение C*X и конвейер F_ADD прибавит значение D. В такте 15 будет закончено вычисление (A*X)*X и можно будет начинать выражение (A*X*X)*X. В такте 17 выражения (B*X)*X и (C*X) + D будут закончены и можно начать работу с конвейером F_ADD. Данное сложение будет закончено на такте 21, где выражение (A*X*X)*X также будет готово. Последнее сложение можно будет начать на такте 22. Осталась только одна операция в действии, и мы должны подождать до полной латентности FADD, которая составляет 5 тактов. На такте 27 последнее сложение будет закончено и работа будет выполнена.

Данные таблицы покажут это в деталях. Левая колонка символизирует конвейер F_MUL , с 7 состояниями 7, а правая конвейер F_ADD на 5 состояний.

F_MUL

F_ADD

A*X

 

 

 

 

 

 

 

 

 

 

 

Такт 1

F_MUL

F_ADD

 

 

A*X

 

 

 

 

 

 

 

 

 

Такт 2

F_MUL

F_ADD

B*X

 

 

 

A*X

 

 

 

 

 

 

 

Такт 3

F_MUL

F_ADD

 

 

B*X

 

 

 

A*X

 

 

 

 

 

Такт 4

F_MUL

F_ADD

C*X

 

 

 

B*X

 

 

 

A*X

 

 

 

Такт 5

F_MUL

F_ADD

 

 

C*X

 

 

 

B*X

 

 

 

A*X

 

Такт 6

F_MUL

F_ADD

 

 

 

 

C*X

 

 

 

B*X

 

 

A*X

Такт 7

F_MUL

F_ADD

(A*X)*X

 

 

 

 

 

C*X

 

 

 

B*X

 

Такт 8

F_MUL

F_ADD

 

 

(A*X)*X

 

 

 

 

 

C*X

 

 

B*X

Такт 9

F_MUL

F_ADD

(B*X)*X

 

 

 

(A*X)*X

 

 

 

 

 

C*X

 

Такт 10

F_MUL

F_ADD

 

 

(B*X)*X

 

 

 

(A*X)*X

 

 

 

 

C*X

Такт 11

F_MUL

F_ADD

 

(C*X)+D

 

 

(B*X)*X

 

 

 

(A*X)*X

 

 

 

Такт 12

F_MUL

F_ADD

 

 

 

(C*X)+D

 

 

(B*X)*X

 

 

 

(A*X)*X

 

Такт 13

F_MUL

F_ADD

 

 

 

 

 

(C*X)+D

 

 

(B*X)*X

 

 

(A*X)*X

Такт 14

F_MUL

F_ADD

(A*X*X)*X

 

 

 

 

 

 

(C*X)+D

 

 

(B*X)*X

 

Такт 15

F_MUL

F_ADD

 

 

(A*X*X)*X

 

 

 

 

 

 

(C*X)+D

 

(B*X)*X

Такт 16

F_MUL

F_ADD

 

(B*X*X)+(C*X+D)

 

 

(A*X*X)*X

 

 

 

 

 

 

 

Такт 17

F_MUL

F_ADD

 

 

 

(B*X*X)+(C*X+D)

 

 

(A*X*X)*X

 

 

 

 

 

Такт 18

F_MUL

F_ADD

 

 

 

 

 

(B*X*X)+(C*X+D)

 

 

(A*X*X)*X

 

 

 

Такт 19

F_MUL

F_ADD

 

 

 

 

 

 

 

(B*X*X)+(C*X+D)

 

 

(A*X*X)*X

 

Такт 20

F_MUL

F_ADD

 

 

 

 

 

 

 

 

 

(B*X*X)+(C*X+D)

 

(A*X*X)*X

Такт 21

F_MUL

F_ADD

 

(A*X*X*X)+ (B*X*X+C*X+D)

 

 

 

 

 

 

 

 

 

 

Такт 22

F_MUL

F_ADD

 

 

 

(A*X*X*X)+ (B*X*X+C*X+D)

 

 

 

 

 

 

 

 

Такт 23

F_MUL

F_ADD

 

 

 

 

 

(A*X*X*X)+ (B*X*X+C*X+D)

 

 

 

 

 

 

Такт 24

F_MUL

F_ADD

 

 

 

 

 

 

 

(A*X*X*X)+ (B*X*X+C*X+D)

 

 

 

 

Такт 25

F_MUL

F_ADD

 

 

 

 

 

 

 

 

 

(A*X*X*X)+ (B*X*X+C*X+D)

 

 

Такт 26

F_MUL

F_ADD

 

 

 

 

 

 

 

 

 

Finished

 

 

Такт 27

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

После того, как мы посмотрели, как обслуживаются инструкции в конвейерах P4, мы приступим к измерению. Оптимизатор измерения ищет наилучшую возможность для нашего полинома ArcSin. Он базируется на наиболее простом алгоритме оптимизации, это исчерпывающий поиск. Мы просто пробуем множество комбинаций параметров и запоминаем каждый набор параметров, который дает наилучший результат. A и C начинаются в интервалах [AStart; AEnd] и [CStart; CEnd], а размер шага AStepSize и CStepsize. Это делается с помощью двух вложенных циклов.

Code:

StartA    := 0;

StartC    := -1;

EndA      := 1;

EndC      := 1;

AStepSize := 1E-2;

CStepSize := 1E-3;

OptA      := 9999;

OptC      := 9999;

A         := StartA;

while A <= EndA do

begin

C := StartC;

while C <= EndC do

begin

   Inc(NoOfIterations);

   MaxAbsError := CalculateMaxAbsError(A,C, ArcSinArray);

   if MaxAbsError <= MinMaxAbsError then

   begin

     MinMaxAbsError := MaxAbsError;

     OptA := A;

     OptC := C;

   end;

   C := C + CStepSize;

end;

A := A + AStepSize;

end;

 

Функция CalculateMaxAbsError рассчитывает количество точек X на интервале [-1;1], который определяет интервал функции ArcSin .

Code:

TMainForm.CalculateMaxAbsError(A, C : Double; ArcSinArray : TArcSinArray) : Double;

var

X, Y, D, B, Yref, Error, AbsError, MaxAbsError : Double;

 

begin

B := 0;

D := 0;

MaxAbsError := 0;

X := -1;

repeat

   Yref := ArcSin (X);

   Y := ArcSinApproxFunction(X, A, B, C, D);

   Error := Yref-Y;

   AbsError := Abs(Error);

   MaxAbsError := Max(MaxAbsError, AbsError);

   X := X + XSTEPSIZE;

until(X > 1);

Result := MaxAbsError;

end;

 

 

в каждой точке мы рассчитываем ошибку, вычитая значение Y из нашей функции аппроксимации из ссылки значения Y, полученное из  Delphi RTL функции ArcSin. Ошибка может быть положительной или отрицательной, нас же интересует абсолютное значение. Мы помним, что наибольшее абсолютное значение ошибки получается из двух значений MaxAbsError и AbsError, назначая из MaxAbsError. MaxAbsError инициализируется нулем, и в первом вычисление принимает значение первой ошибки (если она больше нуля). MaxAbsError возвращает результат из функции, после окончания полного цикла. В функции оптимизатора, два значения A и C, которые дают наименьшую максимальную ошибку, запоминаются вместе с действительным значением MinMaxAbsError.

Все, что делается в оптимизаторе это возможность расчета максимально количества комбинаций. По этой причине мы должны оптимизировать оптимизатор ;-), и функцию расчета. В этом уроке наши цели немного отличаются, поскольку все, что мы хотим, это получение правильных измерений для функций, которые мы хотим оптимизировать. Это все равно означает, что код оптимизатора должен занимать как можно меньше тактов, так как используемые в функциях большая часть общего количества использованных тактов. Первая оптимизация оптимизатора, которую мы сделаем, состоит в том, что не надо рассчитывать ссылки функции снова и снова. При возврате, нам не важно, какие значения имели A и C. Сделаем ссылку один раз и запишем значение Yref в массив.

Следующей оптимизации подвержены строки, которые рассчитывают MaxAbsError.

Длинная версия

Yref := ArcSinArray[I];

Error := Yref-Y;

AbsError := Abs(Error);

Короткая версия

AbsError := Abs(ArcSinArray[I]-Y);

Это поможет, поскольку Delphi создает множество лишнего кода, при компиляции FP кода.

Длинная версия компилируется в следующее

Code:

Yref := ArcSinArray[I];

 

mov eax,[ebp-$14]

mov edx,[eax+ebx*8]

mov [ebp-$48],edx

mov edx,[eax+ebx*8+$04]

mov [ebp-$44],edx

 

Error := Yref-Y;

 

fld   qword ptr [ebp-$48]

fsub qword ptr [ebp-$30]

fstp  qword ptr [ebp-$50]

wait

 

AbsError := Abs(Error);

 

fld qword ptr [ebp-$50]

fabs

fstp qword ptr [ebp-$10]

wait

 

 

Здесь множество излишеств в данном коде и мы должны заключить, что Delphi сделала плохую работу по оптимизации кода с плавающей запятой. Попробую дать несколько разъяснений этого кода. В начале Паскаль назначает одну переменную типа double другой. Делается это с помощью пар инструкций MOV, одна для младших четырех байт переменной, а вторая для старшей части. Первая строка ассемблерного кода загружает адрес массива в регистр EAX, который используется как база для адресации в массиве. В EBX находится I, и он умножается на 8, поскольку элемент массива занимает 8 байт. Смещение на 4 байта, в последней из двух строк (в строке это скрыто!), это смещение до старшей части элемента.

Yref размещен во фрейме стека [EBP-$48] и загружается в первой строке FP кода. Y размещен во фрейме стека [EBP -$30] и он вычитается из Yref инструкцией FSUB. Результат Error и он записывается во фрейме стека [EBP-$50].

Последняя строка Паскаль кода компилируется в четыре строки ассемблерного кода, в котором сначала загружается Error. Сохранение и загрузка Error излишне и оптимизатор должен удалить это. FABS это функция ABS и вероятно одна из наиболее коротких реализации функций ;-). Компилятор Delphi не имеет inline оптимизации, но применяет это, как «компьютерную магию» к небольшому количеству функций, одна из которых ABS. Последняя строка записывает AbsError на стек.

Короткая версия компилируется в следующее

Code:

mov eax,[ebp-$14]

fld qword ptr [eax+ebx*8]

fsub qword ptr [ebp-$30]

fabs

fstp qword ptr [ebp-$10]

wait

 

 

В данной версии нет лишнего кода, и компилятор должен был сделать такой же код и для длинной версии. Все строки кода присутствуют и в длинной версии, но весь лишний код удален. Первая строка загружает базовый адрес массива в EAX. Вторая строка загружает элемент I, который находится в регистре EBX, на верхушку стека FP. Третья строка вычитает Y из Yref. Четвертая строка это функция Abs. Пятая строка записывает результат в переменную AbsError.

Имеются странности с измерения, которые я не могу объяснить. Результаты измерений сильно изменяются при выполнении. Если клавиатура используется, то при нажатии клавиши, мы получаем различные очки, чем при нажатии мышкой! Единственный кто наверно сможет это объяснить, это Нобель Прайз (Nobel Prize) из Delphi ;-)

Другой иррациональной вещью, является то, что Delphi не выравнивает переменные с двойной точностью должным образом. Они должны быть выровнены по границе 8 байт, а Delphi их выравнивает на границу 4 байта. Пенальти, которое мы можем получить, придет из кэш памяти первого уровня, в отличие от кэш памяти второго уровня она не разделена. При загрузке переменной, она может оказаться разделенной между двумя строка кэш памяти, что потребует двойного времени на ее загрузку. Поскольку переменные двойной точности имеют размер в 8 байт, а строка кэш L1 на P4 размером в 64 байта, то одна из восьми переменных может оказаться разнесенной по разным строкам. На P3 ширина кэш L1 составляет 32 байта, и это может произойти для одного из четырех чисел.

Идеально когда переменные длиной в 4 байта выравнивались бы на границу в 4 байта и восьми байтные на границу в восемь байт соответственно. Что бы сделать это понятным представим себе первую строку в кэш памяти первого уровня, куда будут загружены наши переменные. Первая строка начинается по адресу 0, так, что память из адреса 0 будет загружена в нее. Наша первая переменная выровнена и занимает первые 8 байт в строке 1. переменная номер два занимает байты 9-16 ..., переменная номер восемь байты 57-64 и не пересекает границы строки. Если переменная выровнена на границу 4 байт, то первая переменная размещается в строке по байту 4, а восьмая по байту 61. Первые 4 байта ее находятся в строке 1, но следующие 4 байта уже в строке 2. Процессор загружает младшие 4 байта, затем загружает старшие 4 байта, вместо того, чтобы загрузить все это за один раз.

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

 

Code:

function ArcSinApprox1a(X, A, B, C, D : Double) : Double;

begin

Result := A*X*X*X + B*X*X + C*X + D;

end;

 

Данная функция получила 43243 пункта при измерении на моем P4 1600 MHz (разогнанным до 1920 MHz).

Дельфи от компилировало это так

Code:

function ArcSinApprox1b(X, A, B, C, D : Double) : Double;

begin

{

push  ebp

mov   ebp,esp

add   esp,-$08

}

Result := A*X*X*X + B*X*X + C*X + D;

{

fld   qword ptr [ebp+$20]

fmul  qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

fld   qword ptr [ebp+$18]

fmul  qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

faddp st(1)

fld   qword ptr [ebp+$10]

fmul  qword ptr [ebp+$28]

faddp st(1)

fadd  qword ptr [ebp+$08]

fstp  qword ptr [ebp-$08]

wait

fld   qword ptr [ebp-$08]

}

{

pop   ecx

pop   ecx

pop   ebp

}

end;

 

 

Код из окна CPU view не откомпилируется, поскольку здесь есть инструкция FADDP ST(1), но мы удалим ST(1). По умолчанию инструкция FADDP оперирует с ST(0), ST(1) и поэтому нет необходимости писать это.

Code:

function ArcSinApprox1c(X, A, B, C, D : Double) : Double;

asm

//push  ebp       //Added by compiler

//mov   ebp,esp   //Added by compiler

add   esp,-$08

//Result := A*X*X*X + B*X*X + C*X + D;

fld   qword ptr [ebp+$20]

fmul  qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

fld   qword ptr [ebp+$18]

fmul  qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

faddp //st(1)

fld   qword ptr [ebp+$10]

fmul  qword ptr [ebp+$28]

faddp //st(1)

fadd  qword ptr [ebp+$08]

fstp  qword ptr [ebp-$08]

wait

fld   qword ptr [ebp-$08]

pop   ecx

pop   ecx

//pop   ebp //Added by compiler

end;

 

 

Во-первых, мы видим, что не надо устанавливать фрейм стека. Стек в действительности используется для записи временной переменной для результата и переписывается снов в строках

fstp  qword ptr [ebp-$08]

wait

fld   qword ptr [ebp-$08]

но для этого используется указатель базы, а не указатель стека. Строки, в которых используется EBP + смещение до параметров, которые расположены относительно указателя базы, и который равен фрейму стека вызывающей функции. Указатель стека не используется нигде в функции и изменение его не имеет значение. Инструкция MOV EBP, ESP, добавленная компилятором вместе со строкой ADD ESP, -$08 создает восьмибайтный фрейм. Поскольку эти строки изменяют регистр EBP, то его необходимо сохранить в стеке. В действительности мы можем удалить только строку ADD ESP, 8 и две строки POP ECX, назначение которых вычесть число 8 из ESP.

Code:

function ArcSinApprox1d(X, A, B, C, D : Double) : Double;

asm

//add   esp,-$08

//Result := A*X*X*X + B*X*X + C*X + D;

fld   qword ptr [ebp+$20]

fmul  qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

fld   qword ptr [ebp+$18]

fmul  qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

faddp

fld   qword ptr [ebp+$10]

fmul  qword ptr [ebp+$28]

faddp

fadd  qword ptr [ebp+$08]

fstp  qword ptr [ebp-$08]

wait

fld   qword ptr [ebp-$08]

//pop   ecx

//pop   ecx

end;

 

 

Данная реализация функции получила 42391 пункта (ранее 43243) и немного улучшила производительность.

Компилятор вставил строку MOV EBP, ESP и мы может уменьшить избыточность, используя Esp вместо EBP.

Code:

function ArcSinApprox1e(X, A, B, C, D : Double) : Double;

asm

//Result := A*X*X*X + B*X*X + C*X + D;

//fld   qword ptr [ebp+$20]

fld   qword ptr [esp+$20]

//fmul  qword ptr [ebp+$28]

fmul  qword ptr [esp+$28]

//fmul  qword ptr [ebp+$28]

fmul  qword ptr [esp+$28]

//fmul  qword ptr [ebp+$28]

fmul  qword ptr [esp+$28]

//fld   qword ptr [ebp+$18]

fld   qword ptr [esp+$18]

//fmul  qword ptr [ebp+$28]

fmul  qword ptr [esp+$28]

//fmul  qword ptr [ebp+$28]

fmul  qword ptr [esp+$28]

faddp

//fld   qword ptr [ebp+$10]

fld   qword ptr [esp+$10]

//fmul  qword ptr [ebp+$28]

fmul  qword ptr [esp+$28]

faddp

//fadd  qword ptr [ebp+$08]

fadd  qword ptr [esp+$08]

//fstp  qword ptr [ebp-$08]

fstp  qword ptr [esp-$08]

wait

//fld   qword ptr [ebp-$08]

fld   qword ptr [esp-$08]

end;

 

 

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

При понимании, где результат записывается в стек, мы сможем оптимизировать строки копирования и перезагрузки их. Результат состоит в том, что здесь уже есть копия переменной Result в стеке. Это уменьшает необходимость извлечения результат из стека FP и загрузки Result из стека. Эта одиночная строка имеет тоже действие, но избыточность удалена.

fst   qword ptr [ebp-$08]

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

Code:

function ArcSinApprox1f(X, A, B, C, D : Double) : Double;

asm

//Result := A*X*X*X + B*X*X + C*X + D;

fld   qword ptr [esp+$20]

fmul  qword ptr [esp+$28]

fmul  qword ptr [esp+$28]

fmul  qword ptr [esp+$28]

fld   qword ptr [esp+$18]

fmul  qword ptr [esp+$28]

fmul  qword ptr [esp+$28]

faddp

fld   qword ptr [esp+$10]

fmul  qword ptr [esp+$28]

faddp

fadd  qword ptr [esp+$08]

//fstp  qword ptr [esp-$08]

fst  qword ptr [esp-$08]

wait

//fld   qword ptr [esp-$08]

end;

 

 

Данная реализация получила 47939 пункта, и это улучшило результат на 11%.

Следующий вопрос, который мы должны задать себе: А копия Result на стеке используется? Для ответа мы должны проинспектировать код в месте вызова функции.

Y := ArcSinApproxFunction(X, A, B, C, D);

 

call dword ptr [ArcSinApproxFunction]

fstp qword ptr [ebp-$30]

wait

Первая строка после вызова, записывает результат в Y и извлекает из стека. Видя это, мы можем сделать вывод, что результат на стеке не используется, но чтобы быть уверенным мы должны просмотреть также и остаток кода. Если правило для соглашения по регистровому вызову гласит, что результат с плавающей запятой (FP) возвращается в стеке процессора с плавающей запятой, то несколько странно хранить еще и его копию в стеке. Заключаем, что это избыточно копировать Result на стек и затем извлекать его из стека и удали строку, которая делает это.

Code:

function ArcSinApprox1g(X, A, B, C, D : Double) : Double;

asm

//Result := A*X*X*X + B*X*X + C*X + D;

fld   qword ptr [esp+$20]

fmul  qword ptr [esp+$28]

fmul  qword ptr [esp+$28]

fmul  qword ptr [esp+$28]

fld   qword ptr [esp+$18]

fmul  qword ptr [esp+$28]

fmul  qword ptr [esp+$28]

faddp

fld   qword ptr [esp+$10]

fmul  qword ptr [esp+$28]

faddp

fadd  qword ptr [esp+$08]

//fst  qword ptr [esp-$08]

wait

end;

 

Данная функция получила 47405 пункта

Вместо написания всех QWORD PTR [ESP+$XX] строк мы можем писать имена переменных и позволить компилятору рассчитать за нас адреса. Это делает код более безопасным. Если положение переменной будет изменено, то код будет неработоспособным, при использовании жесткой адресации. Это может произойти при смене соглашения по вызову, что конечно бывает редко.

Code:

function ArcSinApprox1g_2(X, A, B, C, D : Double) : Double;

asm

//Result := A*X*X*X + B*X*X + C*X + D;

//fld   qword ptr [esp+$20]

fld   A

//fmul  qword ptr [esp+$28]

fmul  X

//fmul  qword ptr [esp+$28]

fmul  X

//fmul  qword ptr [esp+$28]

fmul  X

//fld   qword ptr [esp+$18]

fld   B

//fmul  qword ptr [esp+$28]

fmul  X

//fmul  qword ptr [esp+$28]

fmul  X

faddp

//fld   qword ptr [esp+$10]

fld   C

//fmul  qword ptr [esp+$28]

fmul  X

faddp

//fadd  qword ptr [esp+$08]

fadd  D

wait

end;

 

Попробуй оба типа строк

fld   qword ptr [esp+$20]

fld   A

и посмотрите в окне CPU view, что компилятор сгенерировал абсолютно идентичный код для обеих версий.

X используется во многих строках и ссылается не стек. И поэтому загружается со стека во внутренние регистры процессора с плавающей запятой каждый раз. Будет быстрее загрузить X один раз в регистровый стек процессора и изменить все ссылки на него.

Code:

function ArcSinApprox1h(X, A, B, C, D : Double) : Double;

asm

//Result := A*X*X*X + B*X*X + C*X + D;

fld   qword ptr [esp+$20]

fld   qword ptr [esp+$28] //New

fxch

//fmul qword ptr [esp+$28]

fmul  st(0),st(1)

//fmul qword ptr [esp+$28]

fmul  st(0),st(1)

//fmul qword ptr [esp+$28]

fmul  st(0),st(1)

fld   qword ptr [esp+$18]

//fmul qword ptr [esp+$28]

fmul  st(0),st(2)

//fmul qword ptr [esp+$28]

fmul  st(0),st(2)

faddp

fld   qword ptr [esp+$10]

//fmul qword ptr [esp+$28]

fmul  st(0),st(2)

ffree st(2)

faddp

fadd  qword ptr [esp+$08]

fst   qword ptr [esp-$08]

wait

end;

 

 

Добавленная, вторая строка загружает X один раз, для всех операция. Поскольку она загружает X на верхушку стека ST(0), а эта позиция нужна как временная переменная, то мы обменяем регистр ST(0) с ST(1), с помозью инструкции FXCH. Мы также можем поменять местами строки 1 и 2 и получить тот же эффект. Все строки умножения st(0) на X

fmul qword ptr [esp+$28]

мы заменим на

fmul  st(0),st(1)

после последнего использования копии X, мы удалим ее инструкцией FFREE.

Данная реализация получила уже 46882 пункта и ухудшила производительность на 1%. Это стало сюрпризом. Инструкция FXCH объявлена Intel, как не занимающая времени, поскольку используется переименование внутренних регистров. Попробуем проверить это, просто удалив ее.

Code:

function ArcSinApprox1i(X, A, B, C, D : Double) : Double;

asm

//Result := A*X*X*X + B*X*X + C*X + D;

fld   qword ptr [esp+$28]

fld   qword ptr [esp+$20]

//fld   qword ptr [esp+$28]

//fxch

fmul  st(0),st(1)

fmul  st(0),st(1)

fmul  st(0),st(1)

fld   qword ptr [esp+$18]

fmul  st(0),st(2)

fmul  st(0),st(2)

faddp

fld   qword ptr [esp+$10]

fmul  st(0),st(2)

ffree st(2)

faddp

fadd  qword ptr [esp+$08]

wait

end;

 

 

Теперь функция получила 45393 пункта, и производительность изменилась на 3%. FXCH действительно ни причем, поскольку производительность опять ушла вниз. В чем же дело?

Инструкция WAIT была рассмотрена в более раннем уроке, и в данный момент мы просто удалим ее.

Code:

function ArcSinApprox1j(X, A, B, C, D : Double) : Double;

asm

//Result := A*X*X*X + B*X*X + C*X + D;

fld   qword ptr [esp+$28]

fld   qword ptr [esp+$20]

fmul  st(0),st(1)

fmul  st(0),st(1)

fmul  st(0),st(1)

fld   qword ptr [esp+$18]

fmul  st(0),st(2)

fmul  st(0),st(2)

faddp

fld   qword ptr [esp+$10]

fmul  st(0),st(2)

ffree st(2)

faddp

fadd  qword ptr [esp+$08]

//wait

end;

 

Производительно упала до 44140.

Посмотрим эти удивляющие нас результаты на процессоре P3.

ArcSinApprox1a         63613

ArcSinApprox1b         64412

ArcSinApprox1c         64433

ArcSinApprox1d         65062

ArcSinApprox1e         64830

ArcSinApprox1f         62598

ArcSinApprox1g         79586

ArcSinApprox1h         85361

ArcSinApprox1i         80515

ArcSinApprox1j         80192

Во-первых, видим, что вариант ArcSinApprox1h самый быстрый на P3. Поэтому видно, что загрузка данных из кэш памяти L1 более ощутима на P3, чем на P4, поскольку изменение кода, такое как одноразовая загрузка X дало существенное улучшение производительности на P3, и почти нет на P4. С другой стороны мы можем также сказать, что получение данных из кэш памяти всегда медленнее, чем получение из внутренних регистров. P4 имеет быструю кэш память уровня L1, которая читается только за 2 такта, но внутренние регистры еще быстрее, только один такт. Мы также видим, что P3 на частоте 1400 примерно на 80% быстрее, чем P4 на частоте 1920 в данном коде. Мы знаем, что латентность на P3 короче, но этого недостаточно для объяснения такой большой разницы.

Латентность и ускорение (throughput) по использованным регистрам на P3

FADD latency is 3 clock cycles and throughput is 1

FMUL latency is 5 clock cycles and throughput is 1

На P4

FADD latency is 5 clock cycles and throughput is 1

FMUL latency is 7 clock cycles and throughput is 2

Я не смог найти данных для FLD

Объяснение плохой производительности P4 в данном коде состоит в 2-тактном сквозном проходе по конвейеру (throughput) для FMUL, совместно с медленным доступом до FP регистров процессора. Конвейер FMUL получает доступ до следующей инструкции только за два такта, тогда как P3 за один такт.

Нормализованный к частоте результат

47939 / 1920 = 25

85361 / 1400 = 61

разоблачает, что при приведении частот процессор P3 примерно в 2.5 раза быстрее P4. Это вызывает подлинное удивление. Чтобы P4 имел некоторые шансы, по отношению к P 3, нам мы должны убрать некоторые умножения. Это получается в функции по версии Хорнера.

Code:

function ArcSinApprox3a(X, A, B, C, D : Double) : Double;

begin

Result := ((A*X + B)*X + C)*X + D;

end;

 

 

Это компилируется в

Code:

function ArcSinApprox3b(X, A, B, C, D : Double) : Double;

begin

{

push ebp

mov  ebp,esp

add  esp,-$08

}

Result := ((A*X + B)*X + C)*X + D;

{

fld  qword ptr [ebp+$20]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$18]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$10]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$08]

fstp qword ptr [ebp-$08]

wait

fld  qword ptr [ebp-$08]

}

{

pop  ecx

pop  ecx

pop  ebp

}

end;

 

 

Первые три версии этой функции идентичны и они получают свои очки без сюрпризов. Наша методика измерения не совсем хороша, но дает достаточную точность в текущий момент ;-)

ArcSinApprox3a        45076

ArcSinApprox3b        45076

ArcSinApprox3c        45076

Оптимизация следует по тому же шаблону, как и в первой функции. Вот первая BASM версия без оптимизации. Закомментирован код добавленный компилятором.

Code:

function ArcSinApprox3c(X, A, B, C, D : Double) : Double;

asm

//push ebp

//mov ebp,esp

add  esp,-$08

//Result := ((A*X + B)*X + C)*X + D;

fld  qword ptr [ebp+$20]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$18]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$10]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$08]

fstp qword ptr [ebp-$08]

wait

fld  qword ptr [ebp-$08]

pop  ecx

pop  ecx

//pop ebp

end;

 

Первым делом удаляем строку ADD ESP, -$08 и две строки POP ECX. Они устанавливают фрейм стека, но ничего не делают кроме манипулирования указателем стека, который нигде не используется.

Code:

function ArcSinApprox3d(X, A, B, C, D : Double) : Double;

asm

//add  esp,-$08

//Result := ((A*X + B)*X + C)*X + D;

fld  qword ptr [ebp+$20]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$18]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$10]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$08]

fstp qword ptr [ebp-$08]

wait

fld  qword ptr [ebp-$08]

//pop  ecx

//pop  ecx

end;

 

Данная функция получила 43535 пункта.

Обе лишние строки, копирующие результат на стек и обратно, удалены одновременно.

Code:

function ArcSinApprox3e(X, A, B, C, D : Double) : Double;

asm

//Result := ((A*X + B)*X + C)*X + D;

fld  qword ptr [ebp+$20]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$18]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$10]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$08]

//fstp qword ptr [ebp-$08]

wait

//fld  qword ptr [ebp-$08]

end;

Этот вариант получил 47237 пункта, и улучшение составило 8.5%

Затем изменим код, таким образом, чтобы X загружался только один раз.

Code:

function ArcSinApprox3f(X, A, B, C, D : Double) : Double;

asm

//Result := ((A*X + B)*X + C)*X + D;

fld   qword ptr [ebp+$20]

fld   qword ptr [ebp+$28]

fxch

//fmul qword ptr [ebp+$28]

fmul  st(0),st(1)

fadd  qword ptr [ebp+$18]

//fmul qword ptr [ebp+$28]

fmul  st(0),st(1)

fadd  qword ptr [ebp+$10]

//fmul qword ptr [ebp+$28]

fmul  st(0),st(1)

ffree st(1)

fadd qword ptr [ebp+$08]

wait

end;

 

Данная функция получила 47226 пункта и без изменения производительности.

Инструкция FFREE может быть удалена, за счет использования инструкции FMULP вместо FMUL, но для этого мы должны сменить два используемых регистра. Только эти два регистра используются и A*B = B*A, так что нет проблем сделать это. Этим мы не удаляем некоторую избыточность, и оба пути дают одинаковый результат.

Code:

function ArcSinApprox3g(X, A, B, C, D : Double) : Double;

asm

//Result := ((A*X + B)*X + C)*X + D;

fld   qword ptr [ebp+$20]

fld   qword ptr [ebp+$28]

fxch  st(1)

fmul  st(0),st(1)

fadd  qword ptr [ebp+$18]

fmul  st(0),st(1)

fadd  qword ptr [ebp+$10]

//fmul  st(0),st(1)

fmulp st(1),st(0)

//ffree st(1)

fadd qword ptr [ebp+$08]

wait

end;

 

Данная реализация получила 47416 пункта.

Затем мы удалим инструкцию WAIT.

Code:

function ArcSinApprox3h(X, A, B, C, D : Double) : Double;

asm

//Result := ((A*X + B)*X + C)*X + D;

fld   qword ptr [ebp+$20]

fld   qword ptr [ebp+$28]

fxch  st(1)

fmul  st(0),st(1)

fadd  qword ptr [ebp+$18]

fmul  st(0),st(1)

fadd  qword ptr [ebp+$10]

fmulp st(1),st(0)

fadd qword ptr [ebp+$08]

//wait

end;

 

Теперь функция получила 47059 пункта.

Последняя вещь, которую мы сделаем, это строки, производящие загрузку X и A, и удалим инструкцию FXCH.

Code:

function ArcSinApprox3i(X, A, B, C, D : Double) : Double;

asm

//Result := ((A*X + B)*X + C)*X + D;

fld   qword ptr [ebp+$28]

fld   qword ptr [ebp+$20]

//fld   qword ptr [ebp+$28]

//fxch  st(1)

fmul  st(0),st(1)

fadd  qword ptr [ebp+$18]

fmul  st(0),st(1)

fadd  qword ptr [ebp+$10]

fmulp st(1),st(0)

fadd qword ptr [ebp+$08]

end;

 

 

Эта реализация функции получила 46544 и производительность упала!

Теперь сравним производительность по версии Хорнера с функцией, получившей наибольшую производительность на P4.

ArcSinApprox1g 47939

ArcSinApprox3g         47416

На P3

ArcSinApprox1h         85361

ArcSinApprox3h 87604

Различие не большое, но обычная функция немного быстрее на P4 и медленнее на P3. Обычная функция имеет больше вычисление, но параллелизм это сгладил. Вариант Хорнера имеющий маленький параллелизм и латентность проявляется в полной мере. Это особо плохо на P4.

Держим это в уме и продолжаем с третьим решением, которое выглядит так.

Code:

function ArcSinApprox4b(X, A, B, C, D : Double) : Double;

begin

{

push  ebp

mov  ebp,esp

add   esp,-$08

}

Result := (A*X + B)*(X*X)+(C*X + D);

{

fld     qword ptr [ebp+$20]

fmul  qword ptr [ebp+$28]

fadd  qword ptr [ebp+$18]

fld     qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

fmulp st(1)

fld     qword ptr [ebp+$10]

fmul  qword ptr [ebp+$28]

fadd   qword ptr [ebp+$08]

faddp st(1)

fstp   qword ptr [ebp-$08]

wait

fld   qword ptr [ebp-$08]

}

{

pop ecx

pop ecx

pop ebp

}

end;

 

 

Опыт уже позволяет нам сделать это просто и быстро ;-)

Данная версия сделана так, как это сделала Delphi

Code:

function ArcSinApprox4c(X, A, B, C, D : Double) : Double;

asm

//push ebp

//mov ebp,esp

add   esp,-$08

//Result := (A*X + B)*(X*X)+(C*X + D);

fld     qword ptr [ebp+$20]

fmul  qword ptr [ebp+$28]

fadd  qword ptr [ebp+$18]

fld     qword ptr [ebp+$28]

fmul  qword ptr [ebp+$28]

fmulp //st(1)

fld     qword ptr [ebp+$10]

fmul  qword ptr [ebp+$28]

fadd  qword ptr [ebp+$08]

faddp //st(1)

fstp   qword ptr [ebp-$08]

wait

fld   qword ptr [ebp-$08]

pop   ecx

pop   ecx

//pop  ebp

end;

 

Удаляем фрейм стека и две строки, которые пишут результат на стек

Code:

function ArcSinApprox4d(X, A, B, C, D : Double) : Double;

asm

//add  esp,-$08

//Result := (A*X + B)*(X*X)+(C*X + D);

fld  qword ptr [ebp+$20]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$18]

fld  qword ptr [ebp+$28]

fmul qword ptr [ebp+$28]

fmulp //st(1)

fld  qword ptr [ebp+$10]

fmul qword ptr [ebp+$28]

fadd qword ptr [ebp+$08]

faddp //st(1)

//fstp qword ptr [ebp-$08]

wait

//fld  qword ptr [ebp-$08]

//pop  ecx

//pop  ecx

end;

 

Загружаем X только раз

Code:

function ArcSinApprox4e(X, A, B, C, D : Double) : Double;

asm

//Result := (A*X + B)*(X*X)+(C*X + D);

fld   qword ptr [ebp+$20]

fld   qword ptr [ebp+$28]

//fmul qword ptr [ebp+$28]

fxch

fmul  st(0),st(1)

fadd  qword ptr [ebp+$18]

//fld  qword ptr [ebp+$28]

fld   st(1)

//fmul  qword ptr [ebp+$28]

fmul  st(0),st(2)

fmulp

fld   qword ptr [ebp+$10]

//fmul  qword ptr [ebp+$28]

fmul  st(0),st(2)

fadd  qword ptr [ebp+$08]

faddp

ffree st(1)

wait

end;

Удаляем FXCH и WAIT.

Code:

function ArcSinApprox4f(X, A, B, C, D : Double) : Double;

asm

//Result := (A*X + B)*(X*X)+(C*X + D);

fld   qword ptr [ebp+$28]

fld   qword ptr [ebp+$20]

//fxch

fmul  st(0),st(1)

fadd  qword ptr [ebp+$18]

fld   st(1)

fmul  st(0),st(2)

fmulp

fld   qword ptr [ebp+$10]

fmul  st(0),st(2)

fadd  qword ptr [ebp+$08]

faddp

ffree st(1)

//wait

end;

Переопределяем FFREE ST(1)

Code:

function ArcSinApprox4g(X, A, B, C, D : Double) : Double;

asm

//Result := (A*X + B)*(X*X)+(C*X + D);

fld   qword ptr [ebp+$28]

fld   qword ptr [ebp+$20]

fmul  st(0),st(1)

fadd  qword ptr [ebp+$18]

fld   st(1)

fmul  st(0),st(2)

fmulp

fld   qword ptr [ebp+$10]

fmul  st(0),st(2)

ffree st(2)

fadd  qword ptr [ebp+$08]

faddp

//ffree st(1)

end;

заменяем FMUL/FFREE на FMULP

Code:

function ArcSinApprox4h(X, A, B, C, D : Double) : Double;

asm

//Result := (A*X + B)*(X*X)+(C*X + D);

fld   qword ptr [ebp+$28]

fld   qword ptr [ebp+$20]

fmul  st(0),st(1)

fadd  qword ptr [ebp+$18]

fld   st(1)

fmul  st(0),st(2)

fmulp

fld   qword ptr [ebp+$10]

//fmul  st(0),st(2)

fmulp st(2),st(0)

//ffree st(2)

fadd  qword ptr [ebp+$08]

faddp

end;

Очищаем код и видим, что компилятор еще использует EBP и излишне модифицирует ESP.

Code:

function ArcSinApprox4i(X, A, B, C, D : Double) : Double;

asm

//Result := (A*X + B)*(X*X)+(C*X + D);

fld   qword ptr [ebp+$28]

fld   qword ptr [ebp+$20]

fmul  st(0),st(1)

fadd  qword ptr [ebp+$18]

fld   st(1)

fmul  st(0),st(2)

fmulp

fld   qword ptr [ebp+$10]

fmulp st(2),st(0)

fadd  qword ptr [ebp+$08]

faddp

end;

 

 

Теперь большой вопрос, насколько хорошо эта функция работает.

ArcSinApprox4a        45228

ArcSinApprox4b        45239

ArcSinApprox4c        45228

ArcSinApprox4d        51813

ArcSinApprox4e        49044

ArcSinApprox4f        48674

ArcSinApprox4g        48852

ArcSinApprox4h        44914

ArcSinApprox4i        44914

Мы видим, что в результате «optimizations» на шагах от d до i мы получили «оптимизацию наоборот» на P4, исключая шаг g.

На P3

ArcSinApprox4a        68871

ArcSinApprox4b        68871

ArcSinApprox4c        68634

ArcSinApprox4d        86806

ArcSinApprox4e        85727

ArcSinApprox4f        83542

ArcSinApprox4g        80548

ArcSinApprox4h        88378

ArcSinApprox4i        85324

Мы видим, что оптимизационные шаги d и h очень хороши, а шаги e, f g и I плохие. Вполне возможно, что оптимальной реализации нет. Мы можем выбрать вариант h и удалить оставшиеся и просто сделать несколько вариантов и это путь к быстрой оптимизации.

Так какая же функция победитель? Чтобы найти его мы выберем самую быструю реализацию по каждому решению

На P4

ArcSinApprox1f        47939

ArcSinApprox3g        47416

ArcSinApprox4d        51813

Последняя версия самая быстрая. Параллелизм очень важен на современных процессорах и версия 4 бьет остальных на 9%.

На P3

ArcSinApprox1h        85361

ArcSinApprox3h        87604

ArcSinApprox4h        88378

Версия 4 победитель на P3, но с меньшим преимуществом.

Процессор P4 имеет набор инструкций SSE2, который содержит инструкции для точных расчетов с плавающей запятой. Главная идея этих инструкций The в данном наборе – это использование SIMD расчетов. SIMD - это аббревиатура для Single Instruction Multiple Data. «множество данных» (Multiple data) здесь это переменные двойной точности с плавающей запятой (64 bit) и две переменные этих данных могут быть сложены, вычтены, умножены или поделены одной инструкцией. В SSE2 также есть несколько инструкций для скалярных вычислений, которые вычисляют пару этих данных, подобно обычным данным с плавающей запятой на FPU. Наибольшая разница между обычной математикой с плавающей запятой и SSE2 скалярной математикой, в том, что математика с плавающей запятой выполняется на расширенной точности и результат округляется до двойной точности, при копировании в переменную двойной точности в RAM/кэш. Математика SSE2 двойной точности и регистры также двойной точности. Код примеров в данном уроке выполняет несколько вычислений и точность FPU двойная. Если мы загрузим данные, выполним все вычисления и запишем результат, то результат будет только немного меньше, чем при расширенной точности, пока он еще на стеке FPU, и будет округлен до двойной точности, при копировании в переменную. SSE2 вычисления с другой стороны менее точные, в регистре результат также менее точный. При одном вычислении результат будет двойной точности, но когда мы выполним серию вычислений, то накопленная ошибка будет значительно больше. Поскольку FPU выполняет все вычисления с расширенной точностью и хранит промежуточные результаты в регистрах, то можно выполнить много вычислений, прежде чем ошибка станет значимой, ниже двойной точности.

Мы видим, что точность SSE2 равная двойной или менее точности двойной точности для IA32 плавающей запятой. В чем же преимущество? Есть два преимущества. Регистры не размещаются на стеке, что делает более простым управление кодом и второе то, что вычисления с двойной точностью быстрее, чем с расширенной точностью. Мы должны выбрать скалярные инструкции SSE2, чтобы иметь меньшую латентность, чем для IA32.

Fadd latency is 5

Fsub latency is 5

Fmul latency is 7

Fdiv latency is 38

 

Addsd latency is 4

Subsd latency is 4

Mulsd

Divsd latency is 35

Руководство по оптимизации P4 не имеет данных по латентности и по throughput для инструкции MULSD!

Мы видим, что латентность меньше на один такт для скаляров SSE2 в основном, и на 3 такта для деления.

Показатели для Throughput (в случае срабатывания конвейера) следующие

Fadd throughput is 1

Fsub throughput is 1

Fmul throughput is 2

Fdiv throughput is 38

 

Addsd throughput is 2

Subsd throughput is 2

Mulsd

Divsd latency is 35

Здесь мы видим сюрприз для ADDSD и SUBSD, результат в два раза хуже, по сравнению с FADD и Fsub.

Все, что можно подумать про SSE2, это то, что оно для встраиваемого оборудования, и то, что SIMD вычисления двух наборов данных в параллель просто удлиняет ваши руки!

Из руководства “Optimizations for Intel P4 and Intel Xeon” таблицы латентности и throughput на странице C-1 показывают, что все инструкции с плавающей запятой SSE2 выполняются на том же конвейере, что и старые инструкции с плавающей запятой. Это означает, что SIMD сложение из примера генерирует две микроинструкции, которые выполняются в конвейере  F_ADD. На первом такте число номер 1 вводится в конвейер, а на втором такте вводится число номер 2. поскольку латентность составляет 4 такта первое число покидает конвейер на такте 3, а второе число на такте 4. Это заставляет нас считать, что скалярное сложение SSE2 должно генерировать латентность в 3 такта и throughput в 1 такт. Из этих таблиц кажется, что SIMD версия ADD, ADDPD, имеет туже самую латентность и throughput, как и скалярная версия ADDSD. Или же здесь ошибка в таблицах, или скалярные инструкции также генерируют две микроинструкции, одна из которых «скрытая», и не имеет эффекта. Обращайтесь к Интел!

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

Code:

procedure TMainForm.BenchmarkADDSDLatency;

var

RunNo, ClockFrequency : Cardinal;

StartTime, EndTime, RunTime : TDateTime;

NoOfClocksPerRun, RunTimeSec : Double;

const

ONE : Double = 1;

NOOFINSTRUCTIONS : Cardinal = 895;

 

begin

ADDSDThroughputEdit.Text := 'Running';

ADDSDThroughputEdit.Color := clBlue;

Update;

StartTime := Time;

for RunNo := 1 to MAXNOOFRUNS do

begin

   asm

   movsd xmm0, ONE

   movsd xmm1, xmm0

   movsd xmm2, xmm0

   movsd xmm3, xmm0

   movsd xmm4, xmm0

   movsd xmm5, xmm0

   movsd xmm6, xmm0

   movsd xmm7, xmm0

 

   addsd xmm0, xmm1

   addsd xmm0, xmm1

   addsd xmm0, xmm1

   addsd xmm0, xmm1

   addsd xmm0, xmm1

   addsd xmm0, xmm1

   addsd xmm0, xmm1

 

   //Repeat the addsd block of code such that there are 128 blocks

 

   end;

end;

EndTime := Time;

RunTime := EndTime - StartTime;

RunTimeSec := (24 * 60 *60 * RunTime);

ClockFrequency := StrToInt(ClockFrequencyEdit.Text);

NoOfClocksPerRun := (RunTimeSec / MaxNoOfRuns) * ClockFrequency * 1000000 /

   NOOFINSTRUCTIONS;

ADDSDThroughputEdit.Text := FloatToStrF(NoOfClocksPerRun, ffFixed, 9, 1);

ADDSDThroughputEdit.Color := clLime;

Update;

end;

 

 

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

Для измерения производительности throughput вставим данный блок 128 раз

addsd xmm1, xmm0

addsd xmm2, xmm0

addsd xmm3, xmm0

addsd xmm4, xmm0

addsd xmm5, xmm0

addsd xmm6, xmm0

addsd xmm7, xmm0

здесь нет зависимости от данных, и они могут быть выполнены параллельно. Xmm0 используется как источник данных в каждой строке, но это строка не создает зависимости данных.

Результаты прогона данного кода показывают, что латентность равна 4 тактам, а throughput равна двум тактам. Это соответствует цифрам из таблицы.

Закодируем три функции для скаляров SSE2 и выполним измерения. Восемь регистров SSE2 называются как XMM0-XMM7, и Delphi не имеет возможности показать их в окне просмотра регистров. Поэтому мы должны создать свой собственный просмотр, созданием глобальной (или локальной) переменной для каждого регистра, поместить его в окно просмотра (watch window) и добавить функцию для копирования содержимого в переменные. Это несколько неудобно и я с надеждой смотрю в сторону Борланд, по созданию окна просмотр XMM регистров. Данный код показывает, как Я сделал это.

Code:

var

XMM0reg, XMM1reg, XMM2reg, XMM3reg, XMM4reg : Double;

 

function ArcSinApprox3i(X, A, B, C, D : Double) : Double;

asm

//Result := ((A*X + B)*X + C)*X + D;

 

fld   qword ptr [ebp+$20]

movsd xmm0,qword ptr [ebp+$20]

 

movsd XMM0reg,xmm0

movsd XMM1reg,xmm1

movsd XMM2reg,xmm2

movsd XMM3reg,xmm3

 

fld   qword ptr [ebp+$28]

movsd xmm1,qword ptr [ebp+$28]

 

movsd XMM0reg,xmm0

movsd XMM1reg,xmm1

movsd XMM2reg,xmm2

movsd XMM3reg,xmm3

 

fxch  st(1)

fmul  st(0),st(1)

mulsd xmm0,xmm1

 

movsd XMM0reg,xmm0

movsd XMM1reg,xmm1

movsd XMM2reg,xmm2

movsd XMM3reg,xmm3

 

fadd  qword ptr [ebp+$18]

addsd xmm0,qword ptr [ebp+$18]

 

movsd XMM0reg,xmm0

movsd XMM1reg,xmm1

movsd XMM2reg,xmm2

movsd XMM3reg,xmm3

 

fmul  st(0),st(1)

mulsd xmm0,xmm1

 

movsd XMM0reg,xmm0

movsd XMM1reg,xmm1

movsd XMM2reg,xmm2

movsd XMM3reg,xmm3

 

fadd  qword ptr [ebp+$10]

addsd xmm0,qword ptr [ebp+$10]

 

movsd XMM0reg,xmm0

movsd XMM1reg,xmm1

movsd XMM2reg,xmm2

movsd XMM3reg,xmm3

 

fmulp st(1),st(0)

mulsd xmm0,xmm1

 

movsd XMM0reg,xmm0

movsd XMM1reg,xmm1

movsd XMM2reg,xmm2

movsd XMM3reg,xmm3

 

fadd  qword ptr [ebp+$08]

addsd xmm0,qword ptr [ebp+$08]

 

movsd XMM0reg,xmm0

movsd XMM1reg,xmm1

movsd XMM2reg,xmm2

movsd XMM3reg,xmm3

 

movsd [esp-8],xmm0

fld   qword ptr [esp-8]

 

movsd XMM0reg,xmm0

movsd XMM1reg,xmm1

movsd XMM2reg,xmm2

movsd XMM3reg,xmm3

 

wait

end;

 

 

Код не использует регистры XMM4-XMM7, и поэтому не было нужды создавать их просмотр. Код просмотра XMM располагается после каждых двух строк SSE2 кода. Все строки, кроме двух последних – это код с плавающей запятой, и SSE2 код, добавлен так, что бы каждая операция выполнялась как операция с плавающей запятой, так и как SSE2. данный путь делает возможным трассировать код и проверять, что делает SSE2 версия, сравнительно классической версии. Откройте окно FPU view, и смотрите, как изменяется стек FP, и одновременно как изменяются регистры XMM. Я разработал SSE2 код, просто добавляя SSE2 инструкции сразу после каждой строки FP кода.

fld   qword ptr [ebp+$20]

movsd xmm0,qword ptr [ebp+$20]

MOVSD копирует одну переменную двойной точности, из памяти по адресу [EBP+$20], в регистр XMM. “qword ptr” не требуется, но я сохранил это, что бы снять различие между SSE2 и FP кодом.

Наибольшая разница между FP кодом и скалярным SSE2 кодом, состоит в том, что регистры FP организованы в виде стека, а регистры SSE2 нет. В первое время, при кодировании SSE2 кода, я просто игнорировал это, и затем после того, как я сделал все необходимые SSE2 строки, я вернулся назад, прошелся по всем строкам, строка за строкой и откорректировал их так, что бы они работали с корректным парой переменная/регистр. Активируя функции, определенными значениями, следуя двум следующим видам (например: X=2, A=3, B=4, C=5, D=6), и мы увидим, что сначала загружается “2”, затем “3”, затем 2 умножается на “3” и “2” переписывается “6” и так далее.

Скалярным SSE2 соответствием для FMUL является MULSD. Суффикс SD означает Scalar – Double (Скаляр – Двойная точность).

fxch  st(1)

fmul  st(0),st(1)

mulsd xmm0,xmm1

Скалярным SSE2 соответствием для FADD является ADDSD.

fadd  qword ptr [ebp+$18]

addsd xmm0,qword ptr [ebp+$18]

Продолжаем таким же образом, строка за строкой.

FP код оставляет результат в ST(0), а SSE2 код оставляет результат в регистре XMM. Затем результат копируется из регистра XMM в ST(0) через ячейку памяти на стек.

movsd [esp-8],xmm0

fld   qword ptr [esp-8]

Эти две строки выполняют именно это. В ESP-8, восемь байт находятся выше верхушки стека, есть также еще несколько мест, которые мы могли бы использовать, как временное место для хранения результата. Первая строка копирует XMM0 во временное место, и затем последняя строка загружает его в стек FP. Эти две строки дают перегрузку, что делает маленькие SSE2 функции менее эффективными, чем их FP аналоги.

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

Code:

function ArcSinApprox3j(X, A, B, C, D : Double) : Double;

asm

//Result := ((A*X + B)*X + C)*X + D;

movsd xmm0,qword ptr [ebp+$20]

movsd xmm1,qword ptr [ebp+$28]

mulsd xmm0,xmm1

addsd xmm0,qword ptr [ebp+$18]

mulsd xmm0,xmm1

addsd xmm0,qword ptr [ebp+$10]

mulsd xmm0,xmm1

addsd xmm0,qword ptr [ebp+$08]

movsd [esp-8],xmm0

fld   qword ptr [esp-8]

end;

Теперь это станет более красивым, после удаления не нужного подчеркивания “qword ptr”.

Code:

function ArcSinApprox3j(X, A, B, C, D : Double) : Double;

asm

//Result := ((A*X + B)*X + C)*X + D;

movsd xmm0, [ebp+$20]

movsd xmm1, [ebp+$28]

mulsd xmm0,xmm1

addsd xmm0, [ebp+$18]

mulsd xmm0,xmm1

addsd xmm0, [ebp+$10]

mulsd xmm0,xmm1

addsd xmm0, [ebp+$08]

movsd [esp-8],xmm0

fld   qword ptr [esp-8]

end;

Заменим указатели на имена параметров

Code:

function ArcSinApprox3j(X, A, B, C, D : Double) : Double;

asm

//Result := ((A*X + B)*X + C)*X + D;

movsd xmm0, A

movsd xmm1, X

mulsd xmm0,xmm1

addsd xmm0, B

mulsd xmm0,xmm1

addsd xmm0, C

mulsd xmm0,xmm1

addsd xmm0, D

movsd [esp-8],xmm0

fld   qword ptr [esp-8]

end;

И наконец, проверим, как работает данная версия?

Результат равен 45882 пунктам.

Данная версия немного медленнее, чем версия с плавающей запятой, которая получила 48292 пункта. Мы должны разобраться, в чем причина этого. Толи причина в перегрузки в двух последних строках, то ли в 2-тактном throughput инструкций ADDSD и MULSD? Перегрузка может быть удалена, путем передачи параметра как выходного (OUT параметр) или мы должны встроить (inline) в функцию. Было бы очень интересно для нас насколько велико преимущество от встраивания такой относительно маленькой функции. Во первых, мы избавляемся от передачи пяти параметров с двойной точностью, каждый из которых занимает восемь байт. Посмотрим насколько много кода используется для этого.

push dword ptr [ebp+$14]

push dword ptr [ebp+$10]

push dword ptr [ebp+$34]

push dword ptr [ebp+$30]

push dword ptr [ebp+$2c]

push dword ptr [ebp+$28]

push dword ptr [ebp+$24]

push dword ptr [ebp+$20]

push dword ptr [ebp+$1c]

push dword ptr [ebp+$18]

call dword ptr [ArcSinApproxFunction]

fstp qword ptr [ebp+$08]

Не менее десяти инструкций PUSH, каждая помещает в стек только четыре байта, половина от каждого параметра. Заметим, что регистровое соглашение о вызове, смотрит серьезно на их имена и передает параметры вместо использования FP стека. Затем мы должны иметь пять инструкций FLD, которые могли бы устранить ненужность загрузки параметров со стека в функцию. Это значит, что пять FLD инструкций в функции могли бы быть заменены пятью инструкциями FLD, в точке вызова и десять PUSH инструкции ушли бы в небытие. Это могло бы драматическим образом увеличить быстродействие. Встраивание функции вместо вызова, так же уменьшило перегрузку, за счет отсутствия пары инструкций CALL/RET, которая конечно меньше, чем перегрузка от такого количества PUSH, и это дало нам следующую производительность, на преобразованной в register2 соглашении об вызове ;-).

Inlined ArcSinApprox3i 156006

Inlined ArcSinApprox3j 160000

Улучшение составляет 400%.

Я подлинно желаю Борланду ввести истинное соглашение по вызову для параметров с плавающей запятой в самом ближайшем будущем.

SSE2 версия только на 3% быстрее, чем IA32 версия. Но это больше относится к должной реализации SSE2.

На этом урок 7 подошел к концу.

И теперь вы знаете почти все, о программировании с плавающей запятой ;-)