* При перепечатке материалов ссылка на www.SeoLiga.ru обязательна! RSS



CharPos
31 марта 2009

Это урок 6 и его тема CharPos. Данная функция ищет первое вхождение символа в строке, и возвращает его позицию когда найдет. Если ничего не найдено, то возвращается 0. функция из Delphi делает тоже самое, но с различием, что ищется вхождение подстроки в строке. Передача символа в Pos как подстроки возможна и это путь использования Pos как CharPos. В данном уроке мы разработаем CharPos, которая будет примерно в 4 раза быстрее, чем Pos.
Как обычно мы начнем с Паскаль реализации алгоритма.
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.
Также возможно использовать длину строки как условие для окончания цикла в случае неуспешного поиска. Этот код будет выглядеть так.
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;
Перед тем как перейти к ассемблерному коду, хорошо бы было посмотреть какая из Паскаль реализаций быстрее. Создадим тестовую программу для проведения измерений.
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 откомпилированный с включенной оптимизацией.
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. И ассемблерный, и Паскаль код делают одинаково ;-)
Реализация проверки цикла, это то место где проводится реальная работа. Это сделано с помощью четырех строк на ассемблере.
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", в свойствах проекта, и посмотрите какой код будет сгенерировать.
Остаток кода уже разобран в более ранних уроках, и мы пропустим его объяснение, лучше сходите и выпейте взамен чашечку кофе ;-)
Теперь можно выполнить некоторую оптимизацию. В начале превратим функцию в чисто ассемблерную. Метки были объяснены в листинге предыдущего кода. Здесь видно, что они следуют Паскаль коду интуитивным образом.
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 удалена, поскольку мы не ссылаемся ни к каким переменным по имени.
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. Она состоит из четырех строк.
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) функция должна выглядеть.
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.
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 сразу обнуляется в следующей за меткой строке и поэтому не используется. Так что первая строка кажется лишняя и должна быть удалена.
//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 можно удалить.
После этого изменения сменим наш фокус на цикл. Это особенно важно, поскольку это выполняется множество раз, в зависимости от длины строки и позиции, в которой произойдет сравнение.
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 как счетчик цикла и мы сначала должны найти другой регистр для этой цели.
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. Это устранение лишнего копирования и удаление мертвого кода и мы можем приступить к наиболее важной части оптимизации.
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.
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 становятся лишними.
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.
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.
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 и после ее. Удалим верхний кусок.
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;
На этом наш поиск по удалению лишнего кода закончен. Чистая версия кода выглядит так:
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".
Данная функция демонстрирует первый вариант.
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;
А эта функция демонстрирует второй вариант.
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.
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. Производительность процессоров почти одинаковая при одинаковой частоте.


Теги: практика программирования, курсы web программирования Borland Delphi

Статьи по теме:

Основные виды информационных технологий маркетинга
ExactRecordCount
Свойство AllDataSets
Основные принципы создания пользовательского интерфейса
Data Marts
Свойство LeftOffset
OnLocaleError
Свойство CurrentX
CopyFrom
Свойство ResetAfterPrint
Суперклассинг
Вопросы разработки информационных технологий обработки данных
OnCopyDateTimeAsString
Использование QRPrinter
Свойство AutoSize
| Borland Delphi | vitek |
 


Пн Вт Ср Чт Пт Сб Вс
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31


     



Rambler's Top100

Данный сайт или домен продается ICQ: 403-353-727

© 2009 Seoliga.ru | Borland Delphi | CharPos. Регион сайта: Москва и Санкт-Петербург