Profilowanie wydajności PDFlibPas: indeksy hashowe w Delphi

PDFlibPas, biblioteka PDF losLab dla Delphi i C++Buildera, przyspiesza swoje ścieżki renderowania i generowania zawartości, zastępując cztery wzorce powtarzalnej pracy zamortyzowanymi: leniwym indeksem hashowym do wyszukiwania kluczy słownika, wstępnie obliczoną tabelą przeglądową gammy sRGB, koszykowaniem po pierwszym bajcie do dyspozycji operatorów strumienia zawartości oraz TStringBuilder w miejsce powtarzalnej konkatenacji łańcuchów. Żadne z tych czterech nie wzięło się z jednego dramatycznego odkrycia — wzięły się z tego samego mało efektownego wzorca w profilu: małej funkcji wywoływanej raz na operator, raz na piksel lub raz na znak, gdzie koszt liniowy wewnątrz wywołania staje się kwadratowy lub niemal kwadratowy na całym dokumencie. To jest przewodnia nić tutaj: cztery małe, pozornie niepowiązane poprawki, które atakują ten sam kształt problemu, plus uczciwe ograniczenia każdej z nich

Gdzie renderer strumienia zawartości faktycznie spędza swój czas

Renderer strumienia zawartości PDFlibPas przepuszcza niemal cały swój koszt na token przez cztery wąskie punkty: wyszukiwania w słowniku zasobów dla /Resources, /ColorSpace, /Font i /ExtGState; korekcję gammy na każdym zdekodowanym pikselu obrazu Lab, Indexed lub oznaczonego ICC; dopasowywanie nazw operatorów na każdym tokenie każdego strumienia zawartości; oraz budowanie łańcuchów znaków wszędzie tam, gdzie biblioteka generuje wyjście — ucieczkę literałów łańcuchowych przy zapisie, eksport XFDF, ekspansję tokenów pieczątek i zmiennych. Każda z tych czterech wykonuje niewielką ilość pracy sama w sobie, a każda uruchamia się tysiące lub miliony razy na realistycznym dokumencie, co jest dokładnie tym kształtem funkcji, gdzie szczegół implementacyjny O(n) lub O(n²) przestaje być niewidoczny i zaczyna być czołowym wpisem profilu

Dlaczego wyszukiwania w słowniku zasobów zwalniają w dużym PDF?

TPDFDictionary.FindIndexByKeyName to funkcja, którą renderer wywołuje, aby rozwiązać każde wyszukiwanie /Resources, /ColorSpace, /Font i /ExtGState, i dawniej przechodziła przez tablicę Entries od początku przy każdym wywołaniu — w porządku dla trzywpisowego słownika Resources, kosztowne dla Form XObject czy strony obfitującej w ExtGState, gdzie ten sam słownik jest sondowany przy każdym operatorze dotykającym koloru lub stanu grafiki. PDFlibPas teraz buduje leniwy indeks hashowy, gdy słownik przekroczy DICT_HASH_THRESHOLD (16) wpisów, i zostawia mniejsze słowniki na skanowaniu liniowym, ponieważ większość słowników PDF nigdy nie urośnie tak duża, a tabela hashowa dla trzech kluczy kosztowałaby więcej do zbudowania, niż oszczędza. Indeks to płaska tabela z otwartym adresowaniem, kluczowana przez PLAnsiStringHash, hash FNV-1a z kanoniczną bazą offsetu 2166136261 i liczbą pierwszą 16777619, wybrany, aby uniknąć dociągania System.Generics.Collections dla czegoś tak wrażliwego na rozmiar

Const
  DICT_HASH_THRESHOLD = 16;

Function TPDFDictionary.LookupKeyIndex(Const Key: AnsiString): Integer;
Var
  H, Probe: Integer;
Begin
  Result:= -1;
  If FKeyHashMask= 0 Then
  Begin
    // Not built yet; small dictionaries stay linear since the
    // build cost would not amortize over a handful of entries.
    If Length(Entries)> DICT_HASH_THRESHOLD Then
      BuildKeyHash
    Else
      Exit;
  End;
  H:= PLAnsiStringHash(Key) And FKeyHashMask;
  Probe:= 1;
  While FKeyHash[H]<> -1 Do
  Begin
    If Entries[FKeyHash[H]].Key.Name= Key Then
    Begin
      Result:= FKeyHash[H];
      Exit;
    End;
    H:= (H+ Probe) And FKeyHashMask;
    Inc(Probe);
  End;
End;

Indeks jest unieważniany, a nie utrzymywany przyrostowo: każde mutujące wywołanie — AddEntry, DeleteEntryByKeyName, Assign, AddDict — czyści hash i pozwala kolejnemu wyszukiwaniu przebudować go od zera. Wygląda to na marnotrawstwo, dopóki nie zauważysz, że klucz słownika to obiekt TPDFName, a TPDFName.SetTo może zmienić nazwę klucza już siedzącego w tablicy Entries słownika bez przechodzenia przez żadną z własnych metod słownika — indeks przyrostowy nie ma sposobu, by zaobserwować tę zmianę nazwy, podczas gdy leniwy po prostu się przebudowuje i pozostaje poprawny z konstrukcji. Cena tego bezpieczeństwa to przebudowa O(n) przy pierwszym zapytaniu do dużego słownika po zapisie, plus pamięć na samą tabelę hashową, mniej więcej jeden Integer na slot przy współczynniku wypełnienia dwie trzecie — błąd zaokrąglenia dla garstki nietypowo dużych słowników w typowym dokumencie, i prawdziwy koszt, którego PDFlibPas unika płacenia na każdym małym, utrzymując próg tam, gdzie jest

Wstępne obliczanie gammy sRGB zamiast wywoływania Power na piksel

TPDFSimpleColorManager.XYZ2RGB stosuje funkcję transferu sRGB do każdego zdekodowanego piksela obrazu Lab, Indexed lub opartego na ICC — 1.055 * Power(x, 1/2.4) - 0.055 powyżej progu segmentu liniowego — a Power(x, y) dla ułamkowego y nie ma taniej postaci zamkniętej w RTL Pascala: rozkłada się na Ln(x), a następnie Exp(y * Ln(x)), a ta para wywołań transcendentalnych, uruchamiana trzy razy na piksel dla kanałów czerwonego, zielonego i niebieskiego, jest dominującym kosztem dekodowania piksela obrazu Lab lub ICC piksel po pikselu. PDFlibPas zastępuje trzy wywołania Power na piksel jednym wyszukaniem w GSRGBGammaLUT, 4096-elementowej tablicy Double zbudowanej raz przez EnsureSRGBGammaLUT i indeksowanej przez zaokrąglenie ograniczonego wejścia do najbliższego slotu

Const
  SRGB_GAMMA_LUT_SIZE = 4096;
Var
  GSRGBGammaLUT: Array [0..SRGB_GAMMA_LUT_SIZE- 1] Of Double;
  GSRGBGammaLUTReady: Boolean= False;

Procedure EnsureSRGBGammaLUT;
Var
  I: Integer;
  X: Double;
Begin
  If GSRGBGammaLUTReady Then
    Exit;
  For I:= 0 To SRGB_GAMMA_LUT_SIZE- 1 Do
  Begin
    X:= I/ SRGB_GAMMA_LUT_SIZE;
    If X> 0.0031308 Then
      GSRGBGammaLUT[I]:= 1.055* Power(X, 1/ 2.4)- 0.055
    Else
      GSRGBGammaLUT[I]:= 12.92* X;
  End;
  GSRGBGammaLUTReady:= True;
End;

Function SRGBGamma(X: Double): Double;
Var
  Idx: Integer;
Begin
  If X<= 0 Then
    Result:= 0
  Else If X>= 1 Then
    Result:= 1
  Else
  Begin
    Idx:= Round(X* SRGB_GAMMA_LUT_SIZE);
    If Idx> SRGB_GAMMA_LUT_SIZE- 1 Then
      Idx:= SRGB_GAMMA_LUT_SIZE- 1;
    Result:= GSRGBGammaLUT[Idx];
  End;
End;

Tabela o 4096 slotach na zakresie wejściowym [0, 1] daje mniej więcej szesnastokrotnie większą rozdzielczość niż 8-bitowy kanał wyjściowy, więc kwantyzacja, którą wprowadza LUT, siedzi poniżej tego, co może reprezentować końcowy bajt RGB — wyszukanie w tabeli zastępuje tutaj matematykę transcendentalną bez widocznego kosztu precyzji. To samo rozumowanie pojawia się obok tego w Lab2XYZ, gdzie Power(LMN[i], 3) stało się zwykłym LMN[i]*LMN[i]*LMN[i]: potęga całkowita w ogóle nie potrzebuje Ln/Exp, więc to w ogóle nie jest kompromis LUT, tylko usunięte zbędne wywołanie Power. Sztuczka z LUT opłaca się tylko dlatego, że funkcja transferu jest czystą funkcją pojedynczego Double — nie rozszerzyłaby się czysto na transformację koloru zależną od kilku wartości pikseli lub od większej ilości stanu niż to

Jak szybko wysyłać do wykonania 73 operatory strumienia zawartości?

ContentOperatorFromName jest wywoływana raz na każdy token, który PDFlibPas odczytuje ze strumienia zawartości, dopasowując go do pełnego zestawu 73 operatorów z Tabeli 51 ISO 32000-1 — od w i q aż po rzadko widywane operatory metryk glifów Type 3 d0 i d1 — i dawniej przechodziła tę listę liniowo przy każdym pojedynczym tokenie, więc strona z kilkoma tysiącami operatorów oznaczała kilka tysięcy liniowych przeszukiwań tej samej 73-elementowej tabeli. PDFlibPas teraz koszykuje tabelę po pierwszym bajcie operatora przy starcie, do stałej tablicy slotów indeksowanej przez AnsiChar, więc wyszukanie staje się jednym indeksem tablicy plus przeszukaniem tylko garstki operatorów dzielących ten pierwszy znak

Type
  TOpSlot= Record
    Count: Integer;
    Ops: Array [0..15] Of TPDFContentOperator;
  End;

Var
  GOpBuckets: Array [AnsiChar] Of TOpSlot;
  GBucketsReady: Boolean= False;

Function ContentOperatorFromName(Const Name: AnsiString): TPDFContentOperator;
Var
  Ch: AnsiChar;
  Slot: ^TOpSlot;
  I: Integer;
  Op: TPDFContentOperator;
Begin
  Result:= coUnknown;
  If (Name= '') Then
    Exit;
  EnsureOpBuckets;
  Ch:= Name[1];
  Slot:= @GOpBuckets[Ch];
  If Slot^.Count= 0 Then
    Exit;
  For I:= 0 To Slot^.Count- 1 Do
  Begin
    Op:= Slot^.Ops[I];
    If (PDFContentOpInfo[Op].Name= Name) Then
    Begin
      Result:= Op;
      Exit;
    End;
  End;
End;

Operatory PDF rozróżniają wielkość liter — w i W, f i F, sc i SC to wszystko różne operatory — więc GOpBuckets kluczuje po surowym bajcie, a resztkowe porównanie wewnątrz koszyka to zwykła, rozróżniająca wielkość liter równość AnsiString. Tablica ma rozmiar 16 slotów na literę, co wygodnie pokrywa dzisiejszą tabelę — najbardziej zapełniony koszyk, T, trzyma trzynaście operatorów, ponieważ niemal każdy operator stanu tekstu i pozycjonowania tekstu zaczyna się na tę literę — ale EnsureOpBuckets po cichu przestaje dodawać do koszyka, gdy jego licznik osiągnie 16, więc koszyk, który kiedykolwiek potrzebowałby czternastego wpisu, zawiódłby cicho, a nie głośno: operator rozwiązałby się do coUnknown bez żadnego wyjątku wskazującego dlaczego. To koszt utrzymania wynikający z wymiany struktury danych, która degraduje się elegancko, na taką, która tego nie robi — wysyła do wykonania szybciej, ponieważ nigdy nie potrzebuje wzrostu ze sprawdzeniem granic, i potrzebuje człowieka pilnującego ten jeden koszyk bliski swojego sufitu

Wycinanie O(n²) z budowania łańcuchów znaków

Wzorzec Result := Result + Fragment w Pascalu realokuje i kopiuje cały zgromadzony łańcuch przy każdej iteracji, więc zbudowanie N-znakowego wyjścia po jednym fragmencie naraz kosztuje O(n²) zamiast O(n) — łatwo to przeoczyć podczas przeglądu, ponieważ każda linia wygląda jak jedno tanie dołączenie, i kosztowne w praktyce, ponieważ PLDirectEscapeLiteralString uruchamia się na każdym literale łańcuchowym PDF zapisywanym podczas zapisu, a XFDFXMLEscape uruchamia się na każdej wartości pola eksportowanej do XFDF. PDFlibPas naprawia oba różnymi technikami, wybranymi na podstawie tego, co każda funkcja może przewidzieć z góry. PLDirectEscapeLiteralString zna długość swojego wyjścia, zanim zapisze choć jeden bajt — jedno przejście klasyfikuje każdy znak jako zwykły lub wymagający ucieczki i sumuje razem, SetLength alokuje raz, a drugie przejście wypełnia bufor po indeksie. XFDFXMLEscape nie może tanio przewidzieć długości swojego wyjścia, ponieważ tekst pola Unicode zbyt się różni, by go z góry obliczyć, więc zamiast tego dołącza do TStringBuilder wstępnie rozmiarowanego mniej więcej na długość wejścia

Function XFDFXMLEscape(Const W: WideString): WideString;
Var
  I: Integer;
  Builder: TStringBuilder;
Begin
  // TStringBuilder avoids the O(n^2) WideString concatenation that
  // XFDF export used to hit on every field value
  Builder:= TStringBuilder.Create(Length(W)+ 16);
  Try
    For I:= 1 To Length(W) Do
    Begin
      Case W[I] Of
        '&':  Builder.Append('&');
        '<':  Builder.Append('&lt;');
        '>':  Builder.Append('&gt;');
        // ...'"', tab, CR and LF cases follow the same shape
      Else
        Builder.Append(W[I]);
      End;
    End;
    Result:= Builder.ToString;
  Finally
    Builder.Free;
  End;
End;

Wybór między tymi dwoma podejściami tak naprawdę dotyczy tego, co wiesz, zanim pętla się zacznie. Policz-a-potem-wypełnij jest szybsze z tych dwóch, gdy rozmiar wyjścia jest tani do obliczenia, ponieważ nie wykonuje żadnych realokacji ani żadnego księgowania poza licznikiem Integer, ale oznacza pisanie logiki klasyfikacji dwukrotnie — raz, żeby policzyć, raz, żeby wyemitować — co jest własnym ryzykiem utrzymaniowym, jeśli te dwie kopie się rozjadą. TStringBuilder rezygnuje z odrobiny tej szczytowej przepustowości na rzecz napisania logiki raz i uzyskania zamortyzowanych dołączeń O(1) dzięki geometrycznemu wzrostowi bufora, co jest bezpieczniejszym domyślnym wyborem zawsze, gdy rozmiar wyjścia nie jest łatwy do poznania z góry

Gdzie ten wzorzec ma zastosowanie, a gdzie nie

Wszystkie cztery powyższe poprawki to instancje jednego pomysłu: znajdź wywołanie, które uruchamia się raz na jednostkę wejścia — na klucz słownika, na piksel, na token operatora, na znak — i zastąp jego liniowy lub nieprzewidywalny koszt wstępnie obliczoną tabelą, indeksem hashowym lub wstępnie rozmiarowanym buforem. Nic z tego nie jest specyficzne dla PDF; usługa Delphi, która rozwiązuje ten sam klucz wyszukiwania tysiące razy na żądanie, konwertuje wartości w ciasnej pętli, wysyła do wykonania na podstawie stałego słownika tokenów, czy buduje długie łańcuchy znak po znaku, trafia na te same kształty awarii i wymaga tych samych poprawek. To, czego żadna z tych czterech zmian nie dotyka, to współbieżność ani zużycie pamięci: szybsze jednowątkowe wyszukiwanie w słowniku niczego nie daje dwóm wątkom ścigającym się na tej samej instancji TPDFlib, co jest problemem strukturalnym omówionym osobno w artykule o bezpieczeństwie wątkowym w równoległym renderowaniu stron, i niczego nie daje dla PDF zbyt dużego, by w ogóle wczytać go do pamięci jako drzewo obiektów, do czego służy warstwa Direct Access w PDFlibPas, omówiona w artykule o scalaniu i dzieleniu gigabajtowych PDF-ów

Kod słownika, zarządzania kolorem, dyspozycji strumienia zawartości i budowania łańcuchów znaków omówiony tutaj jest dostarczany jako część standardowego PDFlibPas, biblioteki PDF losLab dla Delphi i C++Buildera, bez żadnej dodatkowej konfiguracji potrzebnej, aby z tego skorzystać