Profilare de performanță PDFlibPas: indexuri hash în Delphi

PDFlibPas, biblioteca PDF a losLab pentru Delphi și C++Builder, accelerează căile sale de randare și generare de conținut înlocuind patru tipare de muncă repetată cu unele amortizate: un index hash leneș pentru căutări de cheie de dicționar, un tabel de căutare de gamma sRGB precalculat, gruparea pe primul octet pentru dispecerizarea operatorilor de flux de conținut, și TStringBuilder în locul concatenării repetate de șiruri. Niciuna din cele patru nu a venit dintr-o singură descoperire dramatică — au venit din același tipar neglamuros dintr-un profil: o funcție mică apelată o dată per cheie de dicționar, o dată per pixel, sau o dată per caracter, unde un cost liniar în interiorul apelului devine pătratic sau aproape-pătratic pe un întreg document. Acesta este firul conducător aici: patru soluții mici, cu aspect fără legătură, care atacă aceeași formă de problemă, plus limitele oneste ale fiecăreia

Unde își petrece efectiv timpul un renderer de flux de conținut

Renderer-ul de flux de conținut al PDFlibPas canalizează aproape tot costul său per-token prin patru puncte înguste: căutări de dicționar de resurse pe /Resources, /ColorSpace, /Font și /ExtGState; corecția de gamma pe fiecare pixel decodat al unei imagini Lab, Indexed, sau etichetate ICC; potrivirea de nume de operator pe fiecare token al fiecărui flux de conținut; și construcția de șiruri oriunde biblioteca construiește ieșire — escaparea de șiruri literale la salvare, exportul XFDF, expandarea de token-uri de ștampilă și variabile. Fiecare din cele patru face o cantitate mică de muncă de una singură, iar fiecare rulează de mii sau milioane de ori peste un document realist, ceea ce este exact forma de funcție unde un detaliu de implementare O(n) sau O(n²) încetează să fie invizibil și devine intrarea de top a profilului

De ce devin lente căutările de dicționar de resurse într-un PDF mare?

TPDFDictionary.FindIndexByKeyName este ceea ce apelează renderer-ul pentru a rezolva fiecare căutare /Resources, /ColorSpace, /Font și /ExtGState, și obișnuia să parcurgă tabloul Entries de la început la fiecare apel — bine pentru un dicționar Resources cu trei intrări, costisitor pentru un Form XObject sau o pagină intensivă în ExtGState unde același dicționar este sondat la fiecare operator care atinge culoarea sau starea grafică. PDFlibPas acum construiește un index hash leneș odată ce un dicționar depășește DICT_HASH_THRESHOLD (16) intrări și lasă dicționarele mai mici pe scanarea liniară, întrucât majoritatea dicționarelor PDF nu ajung niciodată atât de mari, iar un tabel hash pentru trei chei ar costa mai mult de construit decât economisește. Indexul este un tabel plat cu adresare deschisă cheiat de PLAnsiStringHash, un hash FNV-1a cu baza canonică de offset 2166136261 și primul 16777619, ales pentru a evita atragerea System.Generics.Collections pentru ceva atât de sensibil la dimensiune

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;

Indexul este invalidat, nu menținut incremental: fiecare apel mutant — AddEntry, DeleteEntryByKeyName, Assign, AddDict — golește hash-ul și lasă următoarea căutare să îl reconstruiască de la zero. Asta pare risipitor până când observați că o cheie de dicționar este un obiect TPDFName, iar TPDFName.SetTo poate redenumi o cheie deja așezată în tabloul Entries al unui dicționar fără a trece prin niciuna din propriile metode ale dicționarului — un index incremental nu are nicio modalitate de a observa acea redenumire, în timp ce unul leneș pur și simplu se reconstruiește și rămâne corect prin construcție. Prețul acelei siguranțe este o reconstrucție O(n) prima dată când un dicționar mare este interogat după o scriere, plus memoria pentru tabelul hash însuși, aproximativ un Integer per slot la un factor de încărcare de două treimi — o eroare de rotunjire pentru cele câteva dicționare supra-dimensionate dintr-un document tipic, și un cost real pe care PDFlibPas evită să îl plătească pe fiecare unul mic păstrând pragul unde este

Precalcularea gamma sRGB în loc de a apela Power per pixel

TPDFSimpleColorManager.XYZ2RGB aplică funcția de transfer sRGB pe fiecare pixel decodat al unei imagini Lab, Indexed, sau bazate pe ICC — 1.055 * Power(x, 1/2.4) - 0.055 peste pragul de segment liniar — iar Power(x, y) pentru un y fracționar nu are nicio formă închisă ieftină pe RTL-ul Pascal: se descompune în Ln(x) apoi Exp(y * Ln(x)), iar acea pereche de apeluri transcendentale, rulate de trei ori per pixel pentru canalele roșu, verde și albastru, este costul dominant al decodării unui pixel de imagine Lab sau ICC pixel-cu-pixel. PDFlibPas înlocuiește cele trei apeluri Power per pixel cu o căutare într-un GSRGBGammaLUT, un tablou Double de 4096 de intrări construit o dată prin EnsureSRGBGammaLUT și indexat rotunjind intrarea limitată la cel mai apropiat slot

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;

Un tabel cu 4096 de sloturi peste intervalul de intrare [0, 1] oferă aproximativ șaisprezece ori rezoluția unui canal de ieșire pe 8 biți, așa că cuantizarea pe care o introduce LUT-ul stă sub ce poate reprezenta octetul final RGB — căutarea în tabel înlocuiește matematica transcendentală aici fără un cost de precizie vizibil. Același raționament apare alături în Lab2XYZ, unde Power(LMN[i], 3) a devenit un simplu LMN[i]*LMN[i]*LMN[i]: o putere întreagă nu are nevoie de Ln/Exp în primul rând, așa că aceasta nu este deloc un compromis LUT, doar un apel Power redundant eliminat. Trucul LUT se plătește doar pentru că funcția de transfer este o funcție pură a unui singur Double — nu s-ar extinde curat la o transformare de culoare care depindea de mai multe valori de pixel sau de mai multă stare decât atât

Cum dispecerizați 73 de operatori de flux de conținut rapid?

ContentOperatorFromName este apelat o dată pentru fiecare token pe care PDFlibPas îl citește dintr-un flux de conținut, potrivindu-l față de setul complet de 73 de operatori din Tabelul 51 al ISO 32000-1 — de la w și q până la operatorii de metrici de glifă Type 3 rar văzuți d0 și d1 — și obișnuia să parcurgă acea listă liniar la fiecare token individual, așa că o pagină cu câteva mii de operatori însemna câteva mii de scanări liniare peste același tabel de 73 de intrări. PDFlibPas acum grupează tabelul după primul octet al operatorului la pornire, într-un tablou fix indexat de AnsiChar de sloturi, așa că o căutare devine un index de tablou plus o scanare doar a mânii de operatori care împart acel prim caracter

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;

Operatorii PDF sunt sensibili la majuscule — w și W, f și F, sc și SC sunt toți operatori diferiți — așa că GOpBuckets chiază pe octetul brut, iar comparația reziduală în interiorul unui bucket este o egalitate AnsiString simplă, sensibilă la majuscule. Tabloul este dimensionat la 16 sloturi per literă, ceea ce acoperă confortabil tabelul de astăzi — cel mai aglomerat bucket, T, conține treisprezece operatori, întrucât aproape fiecare operator de stare-text și poziționare-text începe cu el — dar EnsureOpBuckets se oprește silențios din a adăuga la un bucket odată ce numărul său ajunge la 16, așa că un bucket care ar avea vreodată nevoie de o a paisprezecea intrare ar eșua silențios, nu zgomotos: operatorul s-ar rezolva la coUnknown fără nicio excepție care să indice de ce. Acesta este costul de întreținere al schimbării unei structuri de date care se degradează grațios pentru una care nu o face — dispecerizează mai rapid pentru că nu are niciodată nevoie de o creștere cu verificare de limite, iar are nevoie de un om care urmărește singurul bucket aproape de plafonul său

Eliminarea O(n²) din construcția de șiruri

Tiparul Pascal Result := Result + Fragment realocă și copiază întregul șir acumulat la fiecare iterație, așa că construirea unei ieșiri de N caractere câte un fragment odată costă O(n²) în loc de O(n) — ușor de ratat la revizuire, întrucât fiecare linie arată ca un adăugat ieftin, și costisitor în practică pentru că PLDirectEscapeLiteralString rulează pe fiecare șir literal PDF scris în timpul salvării, iar XFDFXMLEscape rulează pe fiecare valoare de câmp exportată în XFDF. PDFlibPas rezolvă cele două cu tehnici diferite, alese în funcție de ce poate prezice fiecare funcție în avans. PLDirectEscapeLiteralString își cunoaște lungimea de ieșire înainte de a scrie un singur octet — o trecere clasifică fiecare caracter ca simplu sau escapat și însumează totalul, SetLength alocă o singură dată, iar o a doua trecere umple bufferul după index. XFDFXMLEscape nu poate prezice ieftin lungimea sa de ieșire, întrucât textul de câmp Unicode variază prea mult pentru a fi precalculat, așa că adaugă în schimb într-un TStringBuilder pre-dimensionat aproximativ la lungimea intrării

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;

Alegerea între cele două este de fapt despre ce știți înainte ca bucla să înceapă. Numără-apoi-umple este cea mai rapidă din cele două atunci când dimensiunea de ieșire este ieftin de calculat, întrucât nu face nicio realocare și nicio contabilitate dincolo de un contor Integer, dar înseamnă scrierea logicii de clasificare de două ori — o dată pentru numărare, o dată pentru emitere — ceea ce este propriul său risc de întreținere dacă cele două copii se depărtează. TStringBuilder renunță la puțin din acel debit maxim pentru a scrie logica o singură dată și a obține adăugări amortizate O(1) din creșterea geometrică a bufferului, ceea ce este implicitul mai sigur ori de câte ori dimensiunea de ieșire nu este ușor de cunoscut în avans

Unde se aplică acest tipar și unde nu

Toate cele patru soluții de mai sus sunt instanțe ale unei singure idei: găsiți apelul care rulează o dată per unitate de intrare — per cheie de dicționar, per pixel, per token de operator, per caracter — și înlocuiți costul său liniar sau imprevizibil cu un tabel precalculat, un index hash, sau un buffer pre-dimensionat. Nimic din asta nu este specific PDF-ului; un serviciu Delphi care rezolvă aceeași cheie de căutare de mii de ori per cerere, convertește valori într-o buclă strânsă, dispecerizează pe un vocabular fix de token-uri, sau construiește șiruri lungi câte un caracter odată lovește aceleași forme de eșec și primește aceleași soluții. Ce nu ating niciuna din aceste patru schimbări este concurența sau amprenta de memorie: o căutare de dicționar single-thread mai rapidă nu face nimic pentru două thread-uri care se întrec pe aceeași instanță TPDFlib, ceea ce este o problemă structurală acoperită separat în articolul despre siguranța thread-urilor în randarea paralelă a paginilor, și nu face nimic pentru un PDF prea mare pentru a fi încărcat în memorie ca un arbore de obiecte deloc, ceea ce este pentru ce există stratul Direct Access din PDFlibPas, acoperit în articolul despre îmbinarea și divizarea PDF-urilor de gigabytes

Codul de dicționar, gestionare a culorii, dispecerizare de flux de conținut, și construcție de șiruri discutat aici este livrat ca parte a PDFlibPas standard, biblioteca PDF a losLab pentru Delphi și C++Builder, fără nicio configurare suplimentară necesară pentru a obține oricare din ele