Существует ли быстрая процедура GetToken для Delphi?
В моей программе я обрабатываю миллионы строк, которые имеют специальный символ, например, "|" разделять токены внутри каждой строки. У меня есть функция для возврата n-го токена, и вот оно:
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
var
I, P, P2: integer;
begin
P2 := Pos(Delim, Line);
if TokenNum = 1 then begin
if P2 = 0 then
Result := Line
else
Result := copy(Line, 1, P2-1);
end
else begin
P := 0; { To prevent warnings }
for I := 2 to TokenNum do begin
P := P2;
if P = 0 then break;
P2 := PosEx(Delim, Line, P+1);
end;
if P = 0 then
Result := ''
else if P2 = 0 then
Result := copy(Line, P+1, MaxInt)
else
Result := copy(Line, P+1, P2-P-1);
end;
end; { GetTok }
Я разработал эту функцию еще тогда, когда использовал Delphi 4. Она вызывает очень эффективную процедуру PosEx, которая была первоначально разработана Fastcode и теперь включена в библиотеку StrUtils Delphi.
Я недавно обновился до Delphi 2009, и все мои строки - Unicode. Эта функция GetTok все еще работает и работает хорошо.
Я ознакомился с новыми библиотеками в Delphi 2009, и в нем много новых функций и дополнений.
Но я не видел такой функции GetToken, которая мне нужна, ни в одной из новых библиотек Delphi, в различных проектах fastcode, и я не могу найти ничего с помощью поиска Google, кроме функций Zarko Gajic: Delphi Split / Tokenizer Functions, которая не является так же оптимизирован, как и то, что у меня уже есть.
Любое улучшение, даже 10%, было бы заметно в моей программе. Я знаю, что альтернативой является StringLists и всегда держать токены отдельно, но это имеет большие накладные расходы памяти, и я не уверен, что сделал всю эту работу, чтобы преобразовать, будет ли это быстрее.
Уф. Так что после всего этого многословного разговора мой вопрос на самом деле таков:
Знаете ли вы какие-либо очень быстрые реализации подпрограммы GetToken? Оптимизированная версия на ассемблере была бы идеальной?
Если нет, есть ли какие-либо оптимизации, которые вы можете увидеть в моем коде выше, которые могут улучшить ситуацию?
Продолжение: Барри Келли упомянул вопрос, который я задал год назад об оптимизации разбора строк в файле. В то время я даже не думал о своей подпрограмме GetTok, которая не использовалась для чтения или анализа. Только теперь я увидел накладные расходы на мою процедуру GetTok, которая заставила меня задать этот вопрос. До того, как Карл Смотриц и Барри ответили, я никогда не думал о том, чтобы соединить их. Так очевидно, но это просто не зарегистрировано. Спасибо что подметил это.
Да, мой Delim представляет собой один символ, поэтому, очевидно, у меня есть несколько важных возможностей для оптимизации. Мое использование Pos и PosEx в подпрограмме GetTok (см. Выше) ослепило меня тем, что я могу сделать это быстрее с посимвольным поиском вместо символов, например, с кусочками кода:
while (cp^ > #0) and (cp^ <= Delim) do
Inc(cp);
Я собираюсь просмотреть ответы каждого, попробовать различные предложения и сравнить их. Тогда я опубликую результаты.
Путаница: Хорошо, теперь я действительно озадачен.
Я принял рекомендацию Карла и Барри пойти с PChars, и вот моя реализация:
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackru.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
I: integer;
PLine, PStart: PChar;
begin
PLine := PChar(Line);
PStart := PLine;
inc(PLine);
for I := 1 to TokenNum do begin
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
if I = TokenNum then begin
SetString(Result, PStart, PLine - PStart);
break;
end;
if PLine^ = #0 then begin
Result := '';
break;
end;
inc(PLine);
PStart := PLine;
end;
end; { GetTok }
На бумаге, я не думаю, что вы можете сделать намного лучше, чем это.
Поэтому я поставил обе процедуры в задачу и использовал AQTime, чтобы увидеть, что происходит. Пробежка включала 1 108 514 звонков в GetTok.
AQTime рассчитал время исходной процедуры на 0,40 секунды. Миллион звонков в Pos занял 0,10 секунды. Полмиллиона копий TokenNum = 1 заняли 0,10 секунды. 600000 вызовов PosEx заняли всего 0,03 секунды.
Затем я рассчитал мою новую подпрограмму с AQTime для того же запуска и точно таких же вызовов. AQTime сообщает, что моя новая "быстрая" процедура заняла 3,65 секунды, что в 9 раз больше. Виновником по версии AQTime стала первая петля:
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
Время выполнения, которое было выполнено 18 миллионов раз, было сообщено за 2,66 секунды. Говорят, что линия inc, выполненная 16 миллионов раз, заняла 0,47 секунды.
Теперь я думал, что знаю, что здесь происходит. У меня была похожая проблема с AQTime в вопросе, который я задал в прошлом году: почему CharInSet быстрее, чем оператор Case?
Опять же, Барри Келли рассказал мне об этом. По сути, инструментальный профилировщик, такой как AQTime, не обязательно выполняет работу по микрооптимизации. Это добавляет накладные расходы к каждой строке, которая может затмить результаты, которые четко показаны в этих числах. 34 миллиона строк, выполненных в моем новом "оптимизированном коде", переполняют несколько миллионов строк моего исходного кода, по-видимому, с минимальными или отсутствующими издержками от процедур Pos и PosEx.
Барри дал мне пример кода, используя QueryPerformanceCounter, чтобы проверить, что он был прав, и в этом случае он был прав.
Хорошо, давайте теперь сделаем то же самое с QueryPerformanceCounter, чтобы доказать, что моя новая подпрограмма работает быстрее, а не в 9 раз медленнее, чем говорит AQTime. Итак, я иду:
function TimeIt(const Title: string): double;
var i: Integer;
start, finish, freq: Int64;
Seconds: double;
begin
QueryPerformanceCounter(start);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 1);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 2);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 3);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 4);
QueryPerformanceCounter(finish);
QueryPerformanceFrequency(freq);
Seconds := (finish - start) / freq;
Result := Seconds;
end;
Так что это будет проверять 1 000000 звонков в GetTok.
Моя старая процедура с вызовами Pos и PosEx заняла 0,29 секунды. Новый с PChars занял 2,07 секунды.
Теперь я совершенно сбит с толку! Может кто-нибудь сказать мне, почему процедура PChar не только медленнее, но и в 8-9 раз медленнее!?
Тайна разгадана! Андреас сказал в своем ответе изменить параметр Delim со строки на Char. Я всегда буду использовать только Char, так что по крайней мере для моей реализации это очень возможно. Я был поражен тем, что случилось.
Время для 1 миллиона звонков сократилось с 1,88 до 22 секунд.
И что удивительно, время для моей первоначальной процедуры Pos / PosEx увеличилось с.29 до.44 секунд, когда я изменил параметр Delim на Char.
Честно говоря, я разочарован оптимизатором Delphi. Этот Delim является постоянным параметром. Оптимизатор должен был заметить, что такое же преобразование происходит внутри цикла, и должен был его переместить, чтобы это было сделано только один раз.
Двойная проверка моих параметров генерации кода, да, у меня есть Оптимизация True и проверка формата String Выкл.
Суть в том, что новая процедура PChar с исправлением Андреа примерно на 25% быстрее, чем моя оригинальная (.22 против.29).
Я все еще хочу прокомментировать другие комментарии здесь и проверить их.
Отключение оптимизации и включение проверки формата строки только увеличивает время с.22 до.30. Это добавляет примерно то же самое к оригиналу.
Преимущество использования кода на ассемблере или вызова подпрограмм, написанных на ассемблере, таких как Pos или PosEx, состоит в том, что они НЕ зависят от того, какие параметры генерации кода вы установили. Они всегда будут работать одинаково, предварительно оптимизированным и не раздутым способом.
В последние пару дней я подтвердил, что лучший способ сравнить код для микрооптимизации - это посмотреть и сравнить код Ассемблера в окне ЦП. Было бы неплохо, если бы Embarcadero мог сделать это окно более удобным и позволить нам копировать части в буфер обмена или распечатывать его части.
Кроме того, я несправедливо критиковал AQTime ранее в этом посте, думая, что дополнительное время, добавленное для моей новой рутины, было исключительно из-за инструментов, которые он добавил. Теперь, когда я возвращаюсь и проверяю параметр Char вместо String, цикл while уменьшается до 0,30 секунд (с 2,66), а линия inc уменьшается до 0,14 секунд (с.47). Странно, что линия inc тоже пойдет вниз. Но я уже устал от всех этих испытаний.
Я взял идею Карла про цикл по символам и переписал этот код с этой идеей. Это делает еще одно улучшение, до.19 секунд с.22. Итак, вот теперь самое лучшее на данный момент:
function GetTok(const Line: string; const Delim: Char; const TokenNum: Byte): string;
{ LK Nov 8, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackru.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
I, CurToken: Integer;
PLine, PStart: PChar;
begin
CurToken := 1;
PLine := PChar(Line);
PStart := PLine;
for I := 1 to length(Line) do begin
if PLine^ = Delim then begin
if CurToken = TokenNum then
break
else begin
CurToken := CurToken + 1;
inc(PLine);
PStart := PLine;
end;
end
else
inc(PLine);
end;
if CurToken = TokenNum then
SetString(Result, PStart, PLine - PStart)
else
Result := '';
end;
Для этого все еще могут быть некоторые незначительные оптимизации, такие как сравнение CurToken = Tokennum, которое должно быть того же типа, Integer или Byte, в зависимости от того, что быстрее.
Но скажем, я счастлив сейчас.
Еще раз спасибо сообществу Stackru Delphi.
7 ответов
Ваша новая функция (та, что с PChar) должна объявить Delim как Char, а не как String. В вашей текущей реализации компилятор должен преобразовать символ PLine^ в строку, чтобы сравнить его с "Delim". И это происходит в тесном цикле, в результате чего огромный удар по производительности.
function GetTok(const Line: string; const Delim: Char{<<==}; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; http://stackru.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
I: integer;
PLine, PStart: PChar;
begin
PLine := PChar(Line);
PStart := PLine;
inc(PLine);
for I := 1 to TokenNum do begin
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
if I = TokenNum then begin
SetString(Result, PStart, PLine - PStart);
break;
end;
if PLine^ = #0 then begin
Result := '';
break;
end;
inc(PLine);
PStart := PLine;
end;
end; { GetTok }
Это имеет большое значение, какой "Delim" ожидается. Если ожидается, что это будет один символ, вам гораздо лучше пройти через строку символ за символом, в идеале через PChar, и провести специальное тестирование.
Если это длинная строка, у Бойера-Мура и аналогичных поисков есть фаза настройки для пропускаемых таблиц, и лучшим способом было бы создать таблицы один раз и повторно использовать их для каждого последующего поиска. Это означает, что вам нужно состояние между вызовами, и вместо этой функции лучше использовать ее как метод объекта.
Возможно, вас заинтересует ответ, который я задал на вопрос о быстрейшем способе анализа строки в Delphi. (Но я вижу, что именно вы задали вопрос! Тем не менее, решая вашу проблему, я бы понял, как я описал синтаксический анализ, а не использование PosEx, как вы используете, в зависимости от того, как обычно выглядит Delim.)
ОБНОВЛЕНИЕ: хорошо, я потратил около 40 минут, глядя на это. Если вы знаете, что разделитель будет символом, вам в большинстве случаев лучше со второй версией (то есть сканированием PChar), но вы должны пройти Delim как персонаж. На момент написания вы конвертируете PLine^ выражение - типа Char - в строку для сравнения с Delim. Это будет очень медленно; даже индексирование в строку, с Delim[1] также будет несколько медленным.
Однако, в зависимости от размера ваших линий и количества частей с разделителями, которые вы хотите вытащить, вам может быть лучше использовать возобновляемый подход, а не пропускать нежелательные элементы с разделителями в процедуре токенизации. Если вы вызываете GetTok с последовательно увеличивающимися индексами, как вы это делаете в своем мини-тесте, вы получите производительность O(n*n), где n - количество разделенных разделителей. Это можно превратить в O(n), если вы сохраните состояние сканирования и восстановите его для следующей итерации или упакуете все извлеченные элементы в массив.
Вот версия, которая выполняет всю токенизацию один раз и возвращает массив. Тем не менее, он должен быть дважды разбит на токены, чтобы узнать, насколько велик массив. С другой стороны, только вторая токенизация должна извлечь строки:
// Do all tokenization up front.
function GetTok4(const Line: string; const Delim: Char): TArray<string>;
var
cp, start: PChar;
count: Integer;
begin
// Count sections
count := 1;
cp := PChar(Line);
start := cp;
while True do
begin
if cp^ <> #0 then
begin
if cp^ <> Delim then
Inc(cp)
else
begin
Inc(cp);
Inc(count);
end;
end
else
begin
Inc(count);
Break;
end;
end;
SetLength(Result, count);
cp := start;
count := 0;
while True do
begin
if cp^ <> #0 then
begin
if cp^ <> Delim then
Inc(cp)
else
begin
SetString(Result[count], start, cp - start);
Inc(cp);
Inc(count);
end;
end
else
begin
SetString(Result[count], start, cp - start);
Break;
end;
end;
end;
Вот возобновляемый подход. Загрузка и хранение текущей позиции и символа разделителя имеют свою стоимость, хотя:
type
TTokenizer = record
private
FSource: string;
FCurrPos: PChar;
FDelim: Char;
public
procedure Reset(const ASource: string; ADelim: Char); inline;
function GetToken(out AResult: string): Boolean; inline;
end;
procedure TTokenizer.Reset(const ASource: string; ADelim: Char);
begin
FSource := ASource; // keep reference alive
FCurrPos := PChar(FSource);
FDelim := ADelim;
end;
function TTokenizer.GetToken(out AResult: string): Boolean;
var
cp, start: PChar;
delim: Char;
begin
// copy members to locals for better optimization
cp := FCurrPos;
delim := FDelim;
if cp^ = #0 then
begin
AResult := '';
Exit(False);
end;
start := cp;
while (cp^ <> #0) and (cp^ <> Delim) do
Inc(cp);
SetString(AResult, start, cp - start);
if cp^ = Delim then
Inc(cp);
FCurrPos := cp;
Result := True;
end;
Вот полная программа, которую я использовал для бенчмаркинга.
Вот результаты:
*** count=3, Length(src)=200
GetTok1: 595 ms
GetTok2: 547 ms
GetTok3: 2366 ms
GetTok4: 407 ms
GetTokBK: 226 ms
*** count=6, Length(src)=350
GetTok1: 1587 ms
GetTok2: 1502 ms
GetTok3: 6890 ms
GetTok4: 679 ms
GetTokBK: 334 ms
*** count=9, Length(src)=500
GetTok1: 3055 ms
GetTok2: 2912 ms
GetTok3: 13766 ms
GetTok4: 947 ms
GetTokBK: 446 ms
*** count=12, Length(src)=650
GetTok1: 4997 ms
GetTok2: 4803 ms
GetTok3: 23021 ms
GetTok4: 1213 ms
GetTokBK: 543 ms
*** count=15, Length(src)=800
GetTok1: 7417 ms
GetTok2: 7173 ms
GetTok3: 34644 ms
GetTok4: 1480 ms
GetTokBK: 653 ms
В зависимости от характеристик ваших данных, от того, может ли разделитель быть символом или нет, и от того, как вы с ним работаете, разные подходы могут быть быстрее.
(Я допустил ошибку в своей предыдущей программе, я не измерял одни и те же операции для каждого стиля рутины. Я обновил ссылку на pastebin и результаты тестов.)
Delphi компилируется в ОЧЕНЬ эффективный код; по моему опыту, это было очень трудно сделать лучше на ассемблере.
Я думаю, что вы должны просто указать PChar (они все еще существуют, не так ли? Я расстался с Delphi около 4.0) в начале строки и увеличивать его, считая "|", пока не найдете n-1 из них. Я подозреваю, что это будет быстрее, чем повторный вызов PosEx.
Запомните эту позицию, затем увеличивайте указатель еще немного, пока не дойдете до следующей трубы. Вытащите свою подстроку. Готово.
Я только догадываюсь, но я не удивлюсь, если это будет как можно быстрее, эта проблема может быть решена.
РЕДАКТИРОВАТЬ: Вот что я имел в виду. Этот код, увы, не скомпилирован и не проверен, но он должен продемонстрировать, что я имел в виду.
В частности, Delim рассматривается как один символ, который, как мне кажется, имеет большое значение, если он будет соответствовать требованиям, а персонаж в PLine тестируется только один раз. Наконец, больше нет сравнения с TokenNum; Я считаю, что быстрее подсчитать счетчик до 0 для подсчета разделителей.
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
var
Del: Char;
PLine, PStart: PChar;
Nth, I, P0, P9: Integer;
begin
Del := Delim[1];
Nth := TokenNum + 1;
P0 := 1;
P9 := Line.length + 1;
PLine := PChar(line);
for I := 1 to P9 do begin
if PLine^ = Del then begin
if Nth = 0 then begin
P9 := I;
break;
end;
Dec(Nth);
if Nth = 0 then P0 := I + 1
end;
Inc(PLine);
end;
if (Nth <= 1) or (TokenNum = 1) then
Result := Copy(Line, P0, P9 - P0);
else
Result := ''
end;
Использование ассемблера было бы микрооптимизацией. Оптимизация алгоритма дает гораздо большую выгоду. Невыполнение работы превосходит выполнение работы самым быстрым способом, каждый раз.
Например, если в вашей программе есть места, где вам нужно несколько токенов одной строки. Другая процедура, которая возвращает массив токенов, которые вы можете затем проиндексировать, должна выполняться быстрее, чем вызывать вашу функцию более одного раза, особенно если вы разрешаете процедуре возвращать не все токены, а только столько, сколько вам нужно.
Но в целом я согласен с ответом Карла (+1), используя PChar для сканирования, вероятно, будет быстрее, чем ваш текущий код.
Это функция, которой я пользовался в своей личной библиотеке в течение достаточно долгого времени и которой я часто пользуюсь. Я считаю, что это самая актуальная версия. В прошлом у меня было несколько версий, оптимизированных по разным причинам. Этот пытается учесть строки в кавычках, но если этот код будет удален, это сделает функцию немного быстрее.
У меня на самом деле есть ряд других подпрограмм, CountSections и ParseSectionPOS, являющихся парой примеров.
К сожалению, эта процедура основана только на ANSI / PCHAR. Хотя я не думаю, что было бы трудно перевести его в Unicode. Может быть, я уже сделал это... Я должен проверить это.
Примечание. Эта подпрограмма равна 1 в индексировании ParseNum.
function ParseSection(ParseLine: string; ParseNum: Integer; ParseSep: Char; QuotedStrChar:char = #0) : string;
var
wStart, wEnd : integer;
wIndex : integer;
wLen : integer;
wQuotedString : boolean;
begin
result := '';
wQuotedString := false;
if not (ParseLine = '') then
begin
wIndex := 1;
wStart := 1;
wEnd := 1;
wLen := Length(ParseLine);
while wEnd <= wLen do
begin
if (QuotedStrChar <> #0) and (ParseLine[wEnd] = QuotedStrChar) then
wQuotedString := not wQuotedString;
if not wQuotedString and (ParseLine[wEnd] = ParseSep) then
begin
if wIndex=ParseNum then
break
else
begin
inc(wIndex);
wStart := wEnd+1;
end;
end;
inc(wEnd);
end;
result := copy(ParseLine, wStart, wEnd-wStart);
if (length(result) > 0) and (QuotedStrChar <> #0) and (result[1] = QuotedStrChar) then
result := AnsiDequotedStr(result, QuotedStrChar);
end;
end; { ParseSection }
Я не тот человек, который всегда обвиняет алгоритм, но если я посмотрю на первый фрагмент исходного кода, проблема в том, что для строки N вы также делаете POS/posexes для строки 1..n-1.
Это означает, что для N предметов вы суммируете (n, n-1,n-2...1) POS (=+/- 0,5*N^2), в то время как требуется только N.
Если вы просто кешируете позицию последнего найденного результата, например, в записи, которая передается параметром VAR, вы можете получить много.
тип
TLastPosition = record
elementnr: integer; // последний номер токена elementpos: integer; // индекс символа последнего совпадения end;
а потом что-то
если tokennum=(lastposition.elementnr+1), тогда начинайте newpos:=posex(delim,line,lastposition.elementpos); конец;
К сожалению, у меня нет времени, чтобы написать это, но я надеюсь, что вы поняли идею
В вашем коде, я думаю, это единственная строка, которая может быть оптимизирована:
Result := copy(Line, P+1, MaxInt)
Если вы вычислите новую длину там, она может стать немного быстрее, но не на 10%, которые вы ищете.
Ваш алгоритм токенизации выглядит довольно хорошо. Для его оптимизации я бы запустил его через профилировщик (например, AQTime из AutomatedQA) с репрезентативным подмножеством ваших производственных данных. Это укажет вам на самое слабое место.
Единственная функция RTL, которая подходит близко, это в модуле Classes:
procedure TStrings.SetDelimitedText(const Value: string);
Он маркирует, но использует и QuoteChar, и Delimiter, но вы используете только разделитель.
Он использует функцию SetString в системном блоке, которая является довольно быстрым способом установки содержимого строки на основе PChar/PAnsiChar/PUnicodeChar и длины.
Это может дать вам некоторое улучшение; с другой стороны, копирование тоже очень быстро.