Забыть все
Есть множество маленьких хитростей, с помощью которых можно добиться быстрой работы с 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 раз меньше, чем остальных).
Заметки не окончены. Буду вспоминать еще.