W moim programie przetwarzam miliony ciągów znaków specjalnych, np. „|” rozdzielić żetony w ramach każdego ciągu. Mam funkcję zwracającą n-ty token i to jest to:

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 }

Funkcję tę rozwinąłem, gdy korzystałem z Delphi 4. Wywołuje bardzo wydajną procedurę PosEx, która została pierwotnie opracowana przez Fastcode i jest teraz zawarta w bibliotece StrUtils w Delphi.

Ostatnio zaktualizowałem do Delphi 2009, a wszystkie moje ciągi znaków to Unicode. Ta funkcja GetTok nadal działa i nadal działa dobrze.

Przejrzałem nowe biblioteki w Delphi 2009 i istnieje wiele nowych funkcji i dodatków do niego.

Ale nie widziałem funkcji GetToken, jakiej potrzebuję w żadnej z nowych bibliotek Delphi, w różnych projektach fastcode i nie mogę znaleźć niczego z wyszukiwarką Google inną niżZarko Gajic: Funkcje Delphi Split / Tokenizer, który nie jest tak zoptymalizowany, jak to, co już mam.

Jakakolwiek poprawa, nawet 10%, byłaby zauważalna w moim programie. Wiem, że alternatywą jest StringLists i zawsze utrzymywać tokeny osobno, ale ma to duży nadmiar pamięci i nie jestem pewien, czy zrobiłem to wszystko, aby przekonwertować, czy będzie szybszy.

Whew. Więc po całej tej długiej rozmowie naprawdę moje pytanie brzmi:

Czy znasz jakieś szybkie implementacje procedury GetToken? Zoptymalizowana wersja asemblera byłaby idealna?

Jeśli nie, czy są jakieś optymalizacje, które można zobaczyć w moim kodzie powyżej, które mogą poprawić?

Followup: Barry Kelly wspomniał o pytaniu, które zadałem rok temu na temat optymalizacji parsowania linii w pliku. W tamtym czasie nawet nie pomyślałem o mojej procedurze GetTok, która nie była używana do tego odczytu lub parsowania. Dopiero teraz zobaczyłem koszty mojej procedury GetTok, która doprowadziła mnie do zadawania tego pytania. Do czasu odpowiedzi Carla Smotricza i Barry'ego nigdy nie myślałem o połączeniu obu. Tak oczywiste, ale po prostu się nie zarejestrowało. Dzięki za wskazanie tego.

Tak, mój Delim jest pojedynczym znakiem, więc oczywiście mam kilka dużych możliwości optymalizacji. Moje użycie Pos i PosEx w procedurze GetTok (powyżej) oślepiło mnie na myśl, że mogę to zrobić szybciej dzięki wyszukiwaniu znaków po znaku, z bitami kodu takimi jak:

      while (cp^ > #0) and (cp^ <= Delim) do    
        Inc(cp);

Przejdę przez wszystkie odpowiedzi i wypróbuję różne sugestie i porówna je. Potem opublikuję wyniki.

Zamieszanie: Dobra, teraz jestem naprawdę zakłopotany.

Wziąłem zalecenie Carla i Barry'ego, aby pójść z PCharsami i oto moja implementacja:

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 }

Na papierze nie sądzę, żebyś mógł zrobić o wiele lepiej.

Więc umieściłem obie procedury w zadaniu i wykorzystałem AQTime, aby zobaczyć, co się dzieje. Bieg, w którym brałem udział 1 108 514 połączeń do GetTok.

AQTime odmierzył pierwotną procedurę po 0,40 sekundy. Miliony połączeń do Pos zajęło 0,10 sekundy. Pół miliona TokenNum = 1 kopii zajęło 0,10 sekundy. 600 000 połączeń PosEx zajęło tylko 0,03 sekundy.

Następnie zmierzyłem mój nowy program z AQTime na ten sam przebieg i dokładnie te same połączenia. AQTime informuje, że moja nowa „szybka” procedura zajęła 3,65 sekundy, czyli 9 razy dłużej. Sprawcą według AQTime była pierwsza pętla:

     while (PLine^ <> #0) and (PLine^ <> Delim) do
       inc(PLine);

Linia while, która została wykonana 18 milionów razy, została zgłoszona po 2,66 sekundy. Linia inc, wykonana 16 milionów razy, miała zająć 0,47 sekundy.

Teraz myślałem, że wiem, co się tutaj dzieje. Miałem podobny problem z AQTime w pytaniu, które zadałem w zeszłym roku:Dlaczego CharInSet jest szybszy niż opis przypadku?

Znowu to Barry Kelly mnie przykuł. Zasadniczo, profiler narzędziowy, taki jak AQTime, niekoniecznie wykonuje zadanie dla mikrooptymalizacji. Dodaje nadwyżkę do każdej linii, która może zalewać wyniki, które są wyraźnie widoczne w tych liczbach. 34 miliony linii wykonanych w moim nowym „zoptymalizowanym kodzie” przytłoczy kilka milionów linii mojego oryginalnego kodu, z pozornie niewielkim lub zerowym obciążeniem z procedur Pos i PosEx.

Barry dał mi próbkę kodu za pomocą QueryPerformanceCounter, aby sprawdzić, czy ma rację, iw tym przypadku był.

Dobrze, więc zróbmy to samo teraz z QueryPerformanceCounter, aby udowodnić, że moja nowa procedura jest szybsza i nie 9 razy wolniejsza, jak mówi AQTime. Więc idę:

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;

Przetestuje to 1.000.000 wywołań GetTok.

Moja stara procedura z połączeniami Poz i PosEx trwała 0,29 sekundy. Nowa z PCharami zajęła 2,07 sekundy.

Teraz jestem całkowicie oszołomiony! Czy ktoś może mi powiedzieć, dlaczego procedura PChar jest nie tylko wolniejsza, ale jest od 8 do 9 razy wolniejsza !?

Zagadka rozwiązana! Andreas powiedział w odpowiedzi, aby zmienić parametr Delim z ciągu znaków na znak Char. Zawsze będę używał tylko znaku Char, więc przynajmniej dla mojej implementacji jest to bardzo możliwe. Byłem zdumiony tym, co się stało.

Czas na milion połączeń zmalał z 1,88 sekundy do 0,22 sekundy.

Co zaskakujące, czas na moją oryginalną procedurę Pos / PosEx podniósł się z 0,29 do 0,44 sekundy, kiedy zmieniłem jej parametr Delim na Char.

Szczerze mówiąc, jestem rozczarowany optymalizatorem Delphi. To Delim jest stałym parametrem. Optymalizator powinien zauważyć, że ta sama konwersja zachodzi w pętli i powinna była zostać przeniesiona, aby można było ją wykonać tylko raz.

Podwójne sprawdzanie parametrów generowania kodu, tak.

Najważniejsze jest to, że nowa procedura PChar z poprawką Andrei jest o 25% szybsza niż moja oryginalna (0,22 w porównaniu z 0,29).

Nadal chcę śledzić inne komentarze tutaj i przetestować je.

Wyłączenie optymalizacji i włączenie sprawdzania formatu String tylko wydłuża czas z .22 do .30. Dodaje to mniej więcej do oryginału.

Zaletą używania kodu asemblera lub wywoływania procedur zapisanych w asemblerze, takich jak Pos lub PosEx, jest to, że NIE podlegają one ustawionym opcjom generowania kodu. Będą zawsze działać w ten sam sposób, w sposób zoptymalizowany i nie nadęty.

W ciągu ostatnich kilku dni potwierdziłem, że najlepszym sposobem porównania kodu do mikrooptymalizacji jest sprawdzenie i porównanie kodu Assemblera w oknie CPU. Byłoby miło, gdyby Embarcadero mógł uczynić to okno nieco wygodniejszym i umożliwić nam kopiowanie części do schowka lub drukowanie jego części.

Ponadto niesprawiedliwie zatrzasnąłem AQTime wcześniej w tym poście, myśląc, że dodatkowy czas dodany do mojej nowej procedury był wyłącznie z powodu dodanego oprzyrządowania. Teraz, gdy wracam i sprawdzam za pomocą parametru Char zamiast String, pętla while spada do 0,30 sekundy (z 2,66), a linia inc jest zmniejszona do 0,14 sekundy (z 0,47). Dziwne, że spadnie również linia inc. Ale jestem już zmęczony tymi wszystkimi testami.

Wziąłem pomysł Carla na zapętlenie postaci i przepisałem ten kod za pomocą tego pomysłu. Powoduje to kolejne ulepszenie, do 0,19 sekundy z 0,22. Więc teraz jest najlepszy jak dotąd:

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;

Nadal mogą istnieć pewne niewielkie optymalizacje, takie jak porównanie CurToken = Tokennum, które powinno być tego samego typu, Integer lub Byte, w zależności od tego, co jest szybsze.

Ale powiedzmy, że teraz jestem szczęśliwy.

Jeszcze raz dziękuję społeczności StackOverflow Delphi.