Содержание материала

 

Программа измерения строит тестовый массив из 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;

 

Добавить комментарий

Не использовать не нормативную лексику.

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

ВСЕ КОММЕНТАРИИ МОДЕРИРУЮТСЯ ВРУЧНУЮ, ТАК ЧТО СПАМИТЬ БЕСПОЛЕЗНО!


Защитный код
Обновить