В моей программе я обрабатываю миллионы строк, которые имеют специальный символ, например. "|" для разделения токенов в каждой строке. У меня есть функция, чтобы вернуть 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's: Delphi Split/Tokenizer Functions, который не так оптимизирован, как у меня уже есть.
Любое улучшение, даже 10% было бы заметно в моей программе. Я знаю, что альтернатива - это StringLists и всегда держать токены раздельными, но у этого есть большие накладные расходы памяти, и я не уверен, что я сделал все это, чтобы преобразовать, будет ли это быстрее.
Уф. Итак, после всего этого долгого разговора, мой вопрос на самом деле:
Знаете ли вы о каких-либо очень быстрых реализациях процедуры GetToken? Оптимизированная версия ассемблера была бы идеальной?
Если нет, есть ли какие-либо оптимизации, которые вы можете увидеть в моем коде выше, что может улучшить?
Followup: Барри Келли упомянул вопрос, который я задал год назад об оптимизации синтаксического анализа строк в файле. В то время я даже не думал о моей программе 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://stackoverflow.com/info/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 секунды. 600 000 звонков PosEx заняли всего 0,03 секунды.
Затем я приурочил свою новую процедуру с AQTime для одного и того же прогона и точно так же звонил. AQTime сообщает, что моя новая "быстрая" процедура заняла 3,65 секунды, что в 9 раз больше. Преступником по AQTime был первый цикл:
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
Линия while, выполненная 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,000,000 звонков в GetTok.
Моя старая процедура с вызовами Pos и PosEx заняла 0.29 секунды. Новый с PChars занял 2.07 секунды.
Теперь я полностью одурачен! Может ли кто-нибудь сказать мне, почему процедура PChar не только медленнее, но и в 8-9 раз медленнее!?
Тайна решена! Андреас сказал в своем ответе на изменение параметра Delim от строки до Char. Я всегда буду использовать только Char, поэтому, по крайней мере, для моей реализации это очень возможно. Я был поражен тем, что произошло.
Время для 1 миллиона вызовов снизилось с 1,88 секунды до 0,22 секунды.
И удивительно, что время для моей исходной процедуры Pos/PosEx увеличилось с 0,29 до 0,44 секунды, когда я изменил параметр Delim на Char.
Честно говоря, я разочарован оптимизатором Delphi. Этот разделитель является постоянным параметром. Оптимизатор должен был заметить, что одно и то же преобразование происходит в цикле и должно было переместить его так, чтобы он выполнялся только один раз.
Двойная проверка параметров генерации кода, да, у меня есть проверка оптимизации True и String.
Нижняя линия заключается в том, что новая процедура PChar с исправлением Andrea примерно на 25% быстрее, чем моя оригинальная (.22 против .29).
Я все еще хочу следить за другими комментариями здесь и тестировать их.
Отключение оптимизации и включение проверки формата String увеличивает время от 0,22 до 0,30. Он добавляет примерно то же самое к оригиналу.
Преимущество использования кода ассемблера или вызовов, написанных на ассемблере, таком как Pos или PosEx, заключается в том, что они НЕ подпадают под какие параметры генерации кода, которые вы установили. Они всегда будут работать одинаково, предварительно оптимизирован и не раздуты.
Я за последние пару дней подтвердил, что лучший способ сравнить код для микрооптимизации - это посмотреть и сравнить код Ассемблера в окне CPU. Было бы неплохо, если бы Embarcadero мог сделать это окно немного более удобным и позволить нам копировать фрагменты в буфер обмена или печатать его разделы.
Кроме того, я несправедливо захлопнул AQTime раньше в этом сообщении, думая, что дополнительное время, добавленное для моей новой процедуры, было исключительно из-за добавленной инструментализации. Теперь, когда я возвращаюсь и проверяю параметр Char вместо String, цикл while сокращается до 0,30 секунды (от 2,66), а строка inc - до 0,14 секунды (от .47). Странно, что линия inc также снизится. Но я уже устал от всего этого тестирования.
Я взял идею Карла о петлях персонажей и переписал этот код с этой идеей. Это делает еще одно улучшение, вплоть до 0,19 секунды с 0,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://stackoverflow.com/info/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, в зависимости от того, что быстрее.
Но позвольте сказать, теперь я счастлив.
Еще раз спасибо сообществу StackOverflow Delphi.
