PDFlibPas-Performance-Profiling: Hash-Indizes in Delphi

PDFlibPas, losLabs PDF-Bibliothek für Delphi und C++Builder, beschleunigt ihre Render- und Inhaltserzeugungspfade, indem sie vier wiederholte-Arbeit-Muster durch amortisierte ersetzt: einen faulen (lazy) Hash-Index für Wörterbuch-Schlüssel-Lookups, eine vorberechnete sRGB-Gamma-Lookup-Tabelle, Erstbyte-Bucketing für Content-Stream-Operator-Dispatch, und TStringBuilder statt wiederholter String-Verkettung. Keine der vier kam aus einer einzelnen dramatischen Entdeckung — sie kamen aus demselben unglamourösen Muster in einem Profil: eine kleine Funktion, einmal pro Wörterbuch-Schlüssel, einmal pro Pixel, oder einmal pro Zeichen aufgerufen, wo eine lineare Kosten innerhalb des Aufrufs quadratisch oder nahezu quadratisch über ein ganzes Dokument wird. Das ist der rote Faden hier: vier kleine, unverwandt aussehende Lösungen, die dieselbe Problemform angreifen, plus die ehrlichen Grenzen jeder einzelnen

Wo ein Content-Stream-Renderer seine Zeit tatsächlich verbringt

PDFlibPas' Content-Stream-Renderer leitet fast seine gesamten Pro-Token-Kosten durch vier enge Punkte: Ressourcen-Wörterbuch-Lookups auf /Resources, /ColorSpace, /Font und /ExtGState; Gammakorrektur auf jedem dekodierten Pixel eines Lab-, Indexed- oder ICC-getaggten Bilds; Operator-Namens-Abgleich auf jedem Token jedes Content-Streams; und String-Konstruktion überall dort, wo die Bibliothek Ausgabe baut — literales String-Escaping beim Speichern, XFDF-Export, Stempel- und Variablen-Token-Expansion. Jede der vier verrichtet für sich eine kleine Menge Arbeit, und jede läuft Tausende oder Millionen Male über ein realistisches Dokument, genau die Form von Funktion, bei der ein O(n)- oder O(n²)-Implementierungsdetail aufhört, unsichtbar zu sein, und anfängt, der oberste Eintrag des Profils zu sein

Warum werden Ressourcen-Wörterbuch-Lookups in einem großen PDF langsam?

TPDFDictionary.FindIndexByKeyName ist das, was der Renderer aufruft, um jedes /Resources-, /ColorSpace-, /Font- und /ExtGState-Lookup aufzulösen, und es durchlief früher das Entries-Array von vorne bei jedem Aufruf — in Ordnung für ein Drei-Einträge-Resources-Wörterbuch, teuer für ein Form-XObject oder eine ExtGState-lastige Seite, wo dasselbe Wörterbuch bei jedem Operator sondiert wird, der Farbe oder Grafikzustand berührt. PDFlibPas baut jetzt einen faulen Hash-Index, sobald ein Wörterbuch die Schwelle DICT_HASH_THRESHOLD (16) Einträge überschreitet, und belässt kleinere Wörterbücher beim linearen Scan, da die meisten PDF-Wörterbücher nie so groß werden und eine Hash-Tabelle für drei Schlüssel mehr kosten würde zu bauen, als sie einspart. Der Index ist eine flache Open-Addressing-Tabelle, indiziert über PLAnsiStringHash, einen FNV-1a-Hash mit der kanonischen Offset-Basis 2166136261 und Primzahl 16777619, gewählt, um System.Generics.Collections für etwas so größenempfindliches nicht hereinziehen zu müssen

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;

Der Index wird invalidiert statt inkrementell gepflegt: Jeder mutierende Aufruf — AddEntry, DeleteEntryByKeyName, Assign, AddDict — löscht den Hash und lässt das nächste Lookup ihn von Grund auf neu aufbauen. Das sieht verschwenderisch aus, bis man bemerkt, dass ein Wörterbuchschlüssel ein TPDFName-Objekt ist, und TPDFName.SetTo einen bereits im Entries-Array eines Wörterbuchs sitzenden Schlüssel umbenennen kann, ohne über irgendeine der eigenen Methoden des Wörterbuchs zu laufen — ein inkrementeller Index hat keine Möglichkeit, diese Umbenennung zu beobachten, während ein fauler einfach neu aufbaut und konstruktionsbedingt korrekt bleibt. Der Preis dieser Sicherheit ist ein O(n)-Neuaufbau beim ersten Abfragen eines großen Wörterbuchs nach einem Schreibvorgang, plus der Speicher für die Hash-Tabelle selbst, grob ein Integer pro Slot bei einem Zwei-Drittel-Füllfaktor — ein Rundungsfehler für die Handvoll übergroßer Wörterbücher in einem typischen Dokument, und echte Kosten, die PDFlibPas vermeidet, für jedes kleine zu zahlen, indem die Schwelle dort bleibt, wo sie ist

sRGB-Gamma vorberechnen statt Power pro Pixel aufzurufen

TPDFSimpleColorManager.XYZ2RGB wendet die sRGB-Transferfunktion auf jedes dekodierte Pixel eines Lab-, Indexed- oder ICC-basierten Bilds an — 1.055 * Power(x, 1/2.4) - 0.055 oberhalb der Linearsegment-Schwelle —, und Power(x, y) für ein gebrochenzahliges y hat in der Pascal-RTL keine billige geschlossene Form: Es zerlegt sich in Ln(x) und dann Exp(y * Ln(x)), und dieses Paar transzendenter Aufrufe, dreimal pro Pixel für die Rot-, Grün- und Blau-Kanäle ausgeführt, ist die dominante Kosten beim Dekodieren eines Lab- oder ICC-Bildpixels für Pixel. PDFlibPas ersetzt die drei Pro-Pixel-Power-Aufrufe durch ein Lookup in GSRGBGammaLUT, ein 4096-Einträge-Double-Array, einmal über EnsureSRGBGammaLUT aufgebaut und über Runden der geklemmten Eingabe auf den nächsten Slot indiziert

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;

Eine 4096-Slot-Tabelle über den [0, 1]-Eingabebereich gibt etwa das Sechzehnfache der Auflösung eines 8-Bit-Ausgabekanals, sodass die von der LUT eingeführte Quantisierung unterhalb dessen liegt, was das finale RGB-Byte darstellen kann — Tabellen-Lookup ersetzt hier transzendente Mathematik ohne sichtbare Präzisionskosten. Dieselbe Überlegung zeigt sich direkt daneben in Lab2XYZ, wo Power(LMN[i], 3) zu einem schlichten LMN[i]*LMN[i]*LMN[i] wurde: Eine ganzzahlige Potenz braucht von vornherein kein Ln/Exp, sodass dies überhaupt kein LUT-Kompromiss ist, nur ein entfernter redundanter Power-Aufruf. Der LUT-Trick zahlt sich nur aus, weil die Transferfunktion eine reine Funktion eines einzelnen Double ist — er würde sich nicht sauber auf eine Farbtransformation erweitern lassen, die von mehreren Pixelwerten oder mehr Zustand als diesem abhängt

Wie versendet man 73 Content-Stream-Operatoren schnell?

ContentOperatorFromName wird einmal für jedes Token aufgerufen, das PDFlibPas aus einem Content-Stream liest, und gleicht es gegen die vollständige Menge von 73 Operatoren aus ISO 32000-1 Tabelle 51 ab — von w und q bis hin zu den selten gesehenen Type-3-Glyphenmetrik-Operatoren d0 und d1 —, und es durchlief diese Liste früher linear bei jedem einzelnen Token, sodass eine Seite mit ein paar Tausend Operatoren ein paar Tausend lineare Durchläufe über dieselbe 73-Einträge-Tabelle bedeutete. PDFlibPas gruppiert die Tabelle jetzt beim Start nach dem ersten Byte des Operators, in ein festes, nach AnsiChar indiziertes Array von Slots, sodass ein Lookup zu einem Array-Index plus einem Scan nur der Handvoll Operatoren wird, die dieses erste Zeichen teilen

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;

PDF-Operatoren sind case-sensitiv — w und W, f und F, sc und SC sind alle unterschiedliche Operatoren —, sodass GOpBuckets über das rohe Byte indiziert und der Restvergleich innerhalb eines Buckets eine schlichte, case-sensitive AnsiString-Gleichheit ist. Das Array ist auf 16 Slots pro Buchstabe dimensioniert, was die heutige Tabelle bequem abdeckt — der belebteste Bucket, T, hält dreizehn Operatoren, da fast jeder Textzustands- und Textpositionierungs-Operator damit beginnt —, aber EnsureOpBuckets hört still auf, einem Bucket etwas hinzuzufügen, sobald sein Zähler 16 erreicht, sodass ein Bucket, der je einen vierzehnten Eintrag bräuchte, still statt laut scheitern würde: Der Operator würde zu coUnknown auflösen, ohne Exception, die auf den Grund zeigt. Das sind die Wartungskosten dafür, eine sich elegant degradierende Datenstruktur gegen eine einzutauschen, die das nicht tut — sie versendet schneller, weil sie nie ein bereichsgeprüftes Wachstum braucht, und sie braucht einen Menschen, der den einen Bucket nahe seiner Obergrenze im Auge behält

O(n²) aus dem String-Aufbau entfernen

Pascals Muster Result := Result + Fragment alloziert und kopiert bei jeder Iteration den gesamten akkumulierten String neu, sodass der Aufbau einer N-Zeichen-Ausgabe Fragment für Fragment O(n²) statt O(n) kostet — in der Review leicht zu übersehen, da jede Zeile wie ein billiges Anhängen aussieht, und in der Praxis teuer, weil PLDirectEscapeLiteralString bei jedem beim Speichern geschriebenen literalen PDF-String läuft und XFDFXMLEscape bei jedem zu XFDF exportierten Feldwert läuft. PDFlibPas löst die beiden mit unterschiedlichen Techniken, gewählt danach, was jede Funktion im Voraus vorhersagen kann. PLDirectEscapeLiteralString kennt seine Ausgabelänge, bevor auch nur ein Byte geschrieben wird — ein Durchgang klassifiziert jedes Zeichen als schlicht oder escaped und summiert die Gesamtlänge, SetLength alloziert einmal, und ein zweiter Durchgang füllt den Puffer nach Index. XFDFXMLEscape kann seine Ausgabelänge nicht billig vorhersagen, da Unicode-Feldtext zu sehr variiert, um vorab zu berechnen, sodass es stattdessen in einen auf ungefähr die Eingabelänge vordimensionierten TStringBuilder anhängt

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;

Die Wahl zwischen beiden dreht sich tatsächlich darum, was man vor Beginn der Schleife weiß. Zählen-dann-Füllen ist das schnellere der beiden, wenn die Ausgabegröße billig zu berechnen ist, da es null Neuallokationen macht und keine Buchhaltung über einen Integer-Zähler hinaus, aber es bedeutet, die Klassifizierungslogik zweimal zu schreiben — einmal zum Zählen, einmal zum Ausgeben —, was sein eigenes Wartungsrisiko ist, falls die beiden Kopien auseinanderdriften. TStringBuilder gibt etwas von diesem Spitzendurchsatz dafür auf, die Logik einmal zu schreiben und amortisiertes O(1)-Anhängen durch geometrisches Pufferwachstum zu bekommen, was der sicherere Standard ist, wann immer die Ausgabegröße nicht leicht vorab zu kennen ist

Wo dieses Muster gilt, und wo nicht

Alle vier obigen Lösungen sind Instanzen einer Idee: den Aufruf finden, der einmal pro Einheit der Eingabe läuft — pro Wörterbuchschlüssel, pro Pixel, pro Operator-Token, pro Zeichen — und seine lineare oder unvorhersagbare Kosten durch eine vorberechnete Tabelle, einen Hash-Index oder einen vordimensionierten Puffer ersetzen. Nichts davon ist PDF-spezifisch; ein Delphi-Dienst, der denselben Lookup-Schlüssel Tausende Male pro Anfrage auflöst, Werte in einer engen Schleife konvertiert, über ein festes Vokabular von Tokens versendet, oder lange Strings Zeichen für Zeichen baut, trifft dieselben Fehlerformen und braucht dieselben Lösungen. Was keine dieser vier Änderungen anfasst, ist Nebenläufigkeit oder Speicherbedarf: ein schnelleres Single-Thread-Wörterbuch-Lookup tut nichts für zwei Threads, die um dieselbe TPDFlib-Instanz konkurrieren, ein strukturelles Problem, das separat in dem Artikel zur Thread-Sicherheit bei parallelem Seiten-Rendering behandelt wird, und es tut nichts für ein PDF, das zu groß ist, um überhaupt als Objektbaum in den Speicher geladen zu werden, wofür die Direct-Access-Schicht in PDFlibPas gedacht ist, behandelt in dem Artikel zum Zusammenführen und Aufteilen von Gigabyte-PDFs

Der hier besprochene Wörterbuch-, Farbmanagement-, Content-Stream-Dispatch- und String-Aufbau-Code ist Teil der Standard-PDFlibPas, losLabs PDF-Bibliothek für Delphi und C++Builder, ohne dass zusätzliche Konfiguration nötig wäre, um von irgendetwas davon zu profitieren