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

Забыть все

Декабрь 25, 2011 — Шарахов А.П.

Есть множество маленьких хитростей, с помощью которых можно добиться быстрой работы с ANSI-строками в Delphi. Забавно, что большинство трюков основано на отказе от услуг, навязанных компилятором. Я тут кое-что записал, чтобы удержать в голове все способы заставить компилятор забыть, что мы работаем со строками.

Глаза печальные

Чтобы начать, давайте рассмотрим проблему одного посетителя форума. Он попросил увеличить в 100 раз скорость функции, удаляющей из строки все символы меньше пробела, кроме #9, #10, #13:

function RemoveLowAscii1(const s: AnsiString): AnsiString;
var
  i: integer;
begin;
  Result:='';
  for i:=1 to Length(s) do if not (s[i] in [#0..#8, #11..#12, #14..#31]) then Result:=Result+s[i];
  end;

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

function RemoveLowAscii2(const s: AnsiString): AnsiString;
var
  i, j, len: integer;
begin;
  len:=Length(s);
  SetLength(Result,len); 
  j:=0;
  for i:=1 to len do if not (s[i] in [#0..#8, #11..#12, #14..#31]) then begin;
    inc(j);
    Result[j]:=s[i];
    end;
  SetLength(Result,j); 
  end;

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

Натуральный блондин

В ассемблерном коде, который генерирует компилятор Delphi для пересылки одного символа из строки-параметра в строку-результат, присутствует вызов функции UniqueString. Это гарантия того, что изменение строки-результата не повлияет на значения других строк. Понятно, что достаточно потребовать уникальность результата один раз в самом начале программы. Более того, процедура SetLength уже делает это и поэтому все последующие проверки уникальности излишни. Чтобы от них избавиться, надо заставить Delphi забыть, что мы изменяем строку-результат:

function RemoveLowAscii3(const s: AnsiString): AnsiString;
var
  i, j, len: integer;
  p: pAnsiChar;
begin;
  len:=Length(s);
  SetLength(Result,len);
  p:=pointer(Result); 
  j:=0;
  for i:=1 to len do if not (s[i] in [#0..#8, #11..#12, #14..#31]) then begin;
    p[j]:=s[i];
    inc(j);
    end;
  SetLength(Result,j); 
  end;

Заметим, что мы приводим тип переменной Result к типу pointer, а не к типу pAnsiChar, чтобы лишний раз неявно не вызывать UniqueString. Кроме того, мы наращиваем смещение j очередного символа результата после выполнения присваивания. Вместо этого можно сразу вычислять его адрес, сократив тем самым количество используемых переменных:

function RemoveLowAscii4(const s: AnsiString): AnsiString;
var
  i, len: integer;
  p: pAnsiChar;
begin;
  len:=Length(s);
  SetLength(Result,len);
  p:=pointer(Result); 
  for i:=1 to len do if not (s[i] in [#0..#8, #11..#12, #14..#31]) then begin;
    p[0]:=s[i];
    inc(p);
    end;
  SetLength(Result,p-pointer(Result)); 
  end;

Не так сели

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

procedure RemoveLowAsciiProc(var s: AnsiString);
var
  i: integer;
  p: pAnsiChar;
begin;
  UniqueString(s);
  p:=pointer(s); 
  for i:=1 to len do if not (s[i] in [#0..#8, #11..#12, #14..#31]) then begin;
    p[0]:=s[i];
    inc(p);
    end;
  SetLength(s,p-pointer(s)); 
  end;

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

Еще раз заглянем в окно CPU и увидим, что самый длинный ассемблерный код соответствует проверке допустимости символа. Более того, в большинстве случаев, когда мы имеем дело с пробелами или символами больше пробела, все эти операторы действительно выполняются. Конечно, можно переписать код, чтобы проверки выполнялись в правильном порядне, но гораздо проще использовать таблицу:

function RemoveLowAscii5(const s: AnsiString): AnsiString;
var
  i, len: integer;
  p: pAnsiChar;
begin;
  len:=Length(s);
  SetLength(Result,len);
  p:=pointer(Result);
  for i:=1 to len do if ValidChars[s[i]] then begin;
    p[0]:=s[i];
    inc(p);
    end;
  SetLength(Result,p-pointer(Result));
  end;

Взгляд назад

Окно CPU демонстрирует также, что указатель на результат в ходе вычислений хранится на стеке. В заметке “О QuickSort не говори” мы нашли прием борьбы с этим на IA-32 – использование типа cardinal. Применим его к указателям на обе строки:

function RemoveLowAscii6(const s: AnsiString): AnsiString;
var
  cur, dst, len: cardinal;
  ch: AnsiChar;
begin;
  len:=Length(s);
  SetLength(Result,len);
  if len>0 then begin;
    cur:=cardinal(s);
    dst:=cardinal(Result);
    len:=len+cur;
    repeat;
      ch:=pAnsiChar(cur)^;
      inc(cur);
      if ValidChars[ch] then begin;
        pAnsiChar(dst)^:=ch;
        inc(dst);
        end;
      until cur>=len;
    SetLength(Result,dst-cardinal(Result));
    end;
  end;

Терминатор Тамара

Известно, что для непустой строки типа AnsiString в памяти после всех ее символов хранится терминатор – символ #0. Это позволяет нам без дополнительных проверок на выход за границу строки развернуть цикл. Ничего страшного не произойдет, если функция обработает терминальный символ как символ данных:

function RemoveLowAscii7(const s: AnsiString): AnsiString;
var
  cur, dst, len: cardinal;
  ch: integer;
begin;
  len:=Length(s);
  SetLength(Result,len);
  if len>0 then begin;
    cur:=cardinal(s);
    dst:=cardinal(Result);
    len:=len+cur;
    repeat;
      ch:=pShortInt(cur)^;
      inc(cur);
      if ValidChars[AnsiChar(ch)] then begin;
        pShortInt(dst)^:=ch;
        inc(dst);
        end;
      ch:=pShortInt(cur)^;
      inc(cur);
      if ValidChars[AnsiChar(ch)] then begin;
        pShortInt(dst)^:=ch;
        inc(dst);
        end;
      until cur>=len;
    SetLength(Result,dst-cardinal(Result));
    end;
  end;

Заметим, что при каждом проходе цикла мы всегда считываем из строки 2 символа. Этот факт можно использовать для дальнейшей оптимизации – те же 2 символа можно считывать и записывать при помощи одной операции:

function RemoveLowAscii8(const s: AnsiString): AnsiString;
const
  magic = $00640000; //0000 0000 0110 0100 0000 0000 0000 0000 = #9, #10, #13
var
  cur, dst, len: cardinal;
  mag, ch: integer;
begin;
  len:=Length(s);
  SetLength(Result,len);
  if len>0 then begin;
    cur:=cardinal(s);
    dst:=cardinal(Result);
    len:=len+cur;
    mag:=magic;
    dec(cur,2);
    while true do begin;
      inc(cur,2);
      if cur>=len then break;
      ch:=pSmallInt(cur)^;
      if (ch and $E0<>0) or (mag shl ch<0) then begin;
        pSmallInt(dst)^:=ch;
        inc(dst, 2);                                                   //count both
        if (ch and $E000=0) and (mag shl (ch shr 8)>=0) then dec(dst); //count first only
        end
      else begin;
        ch:=ch shr 8;
        if (ch and $E0<>0) or (mag shl ch<0) then begin;
          pShortInt(dst)^:=ch;
          inc(dst);                                                    //count second only
          end;
        end;
      end;
    SetLength(Result,dst-cardinal(Result));
    end;
  end;

Естественно, этот алгоритм работает только на little-endian машине.

Здесь также показано, как можно использовать двухступенчатую проверку символов, когда в тексте редко встречаются символы меньше пробела. В этом случае для большинства символов будет достаточно одного сравнения с пробелом – это несколько быстрее использования таблицы. Остальные символы (#0..#31) фильтруются при помощи 32-битной таблицы, которая хранится в целочисленной константе magic.

Глаза суровые

Когда символы меньше пробела в тексте крайне редки, можно копировать по 4 символа в группе (двойными словами). Если при этом встретится группа, которая содержит хотя бы один символ, не подлежащий копированию, то она обрабатывается одним из предыдущих способов:

function RemoveLowAscii9(const s: AnsiString): AnsiString;
const
  magic = $00640000; //0000 0000 0110 0100 0000 0000 0000 0000 = #9, #10, #13
var
  cur, dst, len: cardinal;
  ch, save: integer;
begin;
  len:=Length(s);
  SetLength(Result,len);
  if len>0 then begin;
    cur:=cardinal(s);
    dst:=cardinal(Result);
    len:=len+cur;
    repeat;
      ch:=pInteger(cur)^;
      inc(cur, 4);
      save:=ch;
      if cur>len then break;
      ch:=ch shr 1 and $7F7F7F7F - $10101010;      
      pInteger(dst)^:=save;
      inc(dst, 4);
      if ch and $80808080<>0 then begin;
        dec(dst, 4);
        ch:=magic;
        if (save and $E0<>0) or (ch shl save<0) then inc(dst);
        save:=save shr 8;
        if (save and $E0<>0) or (ch shl save<0) then begin; pShortInt(dst)^:=save; inc(dst); end;
        save:=save shr 8;
        if (save and $E0<>0) or (ch shl save<0) then begin; pShortInt(dst)^:=save; inc(dst); end;
        save:=save shr 8;
        if (save and $E0<>0) or (ch shl save<0) then begin; pShortInt(dst)^:=save; inc(dst); end;
        end;
      until false; //forever
    dec(cur, 4);
    ch:=magic;
    while cur<len do begin; //process tail
      if (save and $E0<>0) or (ch shl save<0) then begin; pShortInt(dst)^:=save; inc(dst); end;
      save:=save shr 8;
      inc(cur);
      end;
    SetLength(Result,dst-cardinal(Result));
    end;
  end;

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

Заметки не окончены. Буду вспоминать еще.

на главную

Ответить

  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Доступны HTML теги: <h1> <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Строки и параграфы переносятся автоматически.
  • You can enable syntax highlighting of source code with the following tags: <pre>, <code>, <asm>, <c>, <cpp>, <delphi>, <drupal5>, <drupal6>, <java>, <javascript>, <php>, <python>, <ruby>, <mytext>. Beside the tag style "<foo>" it is also possible to use "[foo]".

Подробнее о форматировании

CAPTCHA
Ведите текст с изображения. (вводить еще раз после предпросмотра а то не добавится комментарий)
Image CAPTCHA
Copy the characters (respecting upper/lower case) from the image.