В моей программе я обрабатываю миллионы строк, которые имеют специальный символ, например, "|" разделять токены внутри каждой строки. У меня есть функция для возврата 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 Функции, который не так оптимизирован, как у меня уже есть.

Любое улучшение, даже 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://stackoverflow.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 секунды. 600 000 вызовов 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 000 000 вызовов в 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://stackoverflow.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, в зависимости от того, что быстрее.

Но скажем, я счастлив сейчас.

Еще раз спасибо сообществу StackOverflow Delphi.