Profilovanie výkonu PDFlibPas: hashovacie indexy v Delphi

PDFlibPas, PDF knižnica spoločnosti losLab pre Delphi a C++Builder, zrýchľuje svoje cesty vykresľovania a generovania obsahu tak, že štyri opakujúce sa vzory práce nahrádza amortizovanými: lenivým hashovacím indexom pre vyhľadávanie kľúčov v slovníkoch, vopred vypočítanou tabuľkou sRGB gama korekcie, rozdelením podľa prvého bajtu pre rýchle rozpoznávanie operátorov obsahového streamu a použitím TStringBuilder namiesto opakovaného skladania reťazcov. Žiadna z týchto štyroch zmien nevzišla z jedného dramatického objavu – všetky vzišli z toho istého nenápadného vzoru v profile: malá funkcia volaná raz na operátor, raz na pixel alebo raz na znak, kde sa lineárne náklady vnútri volania menia na kvadratické alebo takmer kvadratické naprieč celým dokumentom. Práve to je spoločná niť tohto článku: štyri malé, navzájom nesúvisiace opravy, ktoré útočia na ten istý tvar problému, plus poctivé priznanie limitov každej z nich

Kde vykresľovač obsahového streamu skutočne trávi svoj čas?

Vykresľovač obsahového streamu v PDFlibPas prepúšťa takmer všetky svoje náklady na token cez štyri úzke miesta: vyhľadávanie v slovníku zdrojov pre /Resources, /ColorSpace, /Font a /ExtGState; gama korekciu na každom dekódovanom pixeli obrázka Lab, Indexed alebo označeného ICC profilom; porovnávanie názvov operátorov na každom tokene každého obsahového streamu; a skladanie reťazcov všade tam, kde knižnica vytvára výstup – escapovanie literálnych reťazcov PDF pri uložení, export XFDF, expanziu pečiatok a premenných tokenov. Každá z týchto štyroch operácií vykoná malé množstvo práce sama osebe a každá beží tisíckrát či miliónkrát nad reálnym dokumentom, čo je presne ten tvar funkcie, kde implementačný detail so zložitosťou O(n) alebo O(n²) prestáva byť neviditeľný a stáva sa najvyššou položkou profilu

Prečo sa vyhľadávanie v slovníku zdrojov spomaľuje pri veľkom PDF?

TPDFDictionary.FindIndexByKeyName je to, čo vykresľovač volá na vyriešenie každého vyhľadávania /Resources, /ColorSpace, /Font a /ExtGState, a kedysi pri každom volaní prechádzal poľom Entries od začiatku – v poriadku pri trojpoložkovom slovníku Resources, no nákladné pri Form XObjecte alebo strane bohatej na ExtGState, kde sa ten istý slovník preveruje pri každom operátore dotýkajúcom sa farby alebo stavu grafiky. PDFlibPas teraz vybuduje lenivý hashovací index vo chvíli, keď slovník prekročí prah DICT_HASH_THRESHOLD (16) položiek, a menšie slovníky ponecháva na lineárnom prehľadávaní, keďže väčšina slovníkov PDF nikdy nedosiahne takú veľkosť a hashovacia tabuľka pre tri kľúče by stála viac, než by ušetrila. Index je plochá tabuľka s otvoreným adresovaním kľúčovaná pomocou PLAnsiStringHash, hash FNV-1a s kanonickým offsetovým základom 2166136261 a prvočíslom 16777619, zvolený tak, aby sa predišlo zaťahovaniu System.Generics.Collections pre niečo takto citlivé na veľkosť

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;

Index sa invaliduje, nie priebežne udržiava: každé mutujúce volanie – AddEntry, DeleteEntryByKeyName, Assign, AddDict – hash zruší a nechá ho pri ďalšom vyhľadávaní znovu vybudovať od začiatku. To pôsobí márnotratne, kým si nevšimnete, že kľúč slovníka je objekt TPDFName a TPDFName.SetTo dokáže premenovať kľúč, ktorý už sedí v poli Entries slovníka, bez toho, aby prešiel cez ktorúkoľvek z vlastných metód slovníka – priebežne udržiavaný index nemá spôsob, ako toto premenovanie zaznamenať, zatiaľ čo lenivý index sa jednoducho znovu vybuduje a zostáva korektný už zo svojej podstaty. Cenou za túto bezpečnosť je O(n) opätovné vybudovanie pri prvom dotaze na veľký slovník po zápise, plus pamäť pre samotnú hashovaciu tabuľku, zhruba jeden Integer na slot pri dvojtretinovom faktore zaplnenia – zaokrúhľovacia chyba pre hŕstku nadrozmerných slovníkov v typickom dokumente, a reálna cena, ktorej sa PDFlibPas vyhýba pri každom malom slovníku tým, že prah ponecháva tam, kde je

Predpočítanie sRGB gama namiesto volania Power na pixel

TPDFSimpleColorManager.XYZ2RGB aplikuje prevodovú funkciu sRGB na každý dekódovaný pixel obrázka Lab, Indexed alebo založeného na ICC – 1.055 * Power(x, 1/2.4) - 0.055 nad prahom lineárneho segmentu – a Power(x, y) pre necelé y nemá v Pascal RTL žiadny lacný uzavretý tvar: rozkladá sa na Ln(x) a potom Exp(y * Ln(x)), a práve táto dvojica transcendentálnych volaní, spustená trikrát na pixel pre červený, zelený a modrý kanál, je dominantnou nákladovou položkou pri dekódovaní pixelu obrázka Lab alebo ICC po pixeli. PDFlibPas nahrádza tieto tri volania Power na pixel jedným vyhľadaním v GSRGBGammaLUT, poli typu Double so 4096 položkami, vybudovanom raz cez EnsureSRGBGammaLUT a indexovanom zaokrúhlením orezaného vstupu na najbližší 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;

Tabuľka so 4096 slotmi nad vstupným rozsahom [0, 1] dáva približne šestnásťnásobne vyššie rozlíšenie, než aké dokáže vyjadriť 8-bitový výstupný kanál, takže kvantizácia, ktorú tabuľka zavádza, sedí pod tým, čo dokáže reprezentovať finálny bajt RGB – vyhľadávanie v tabuľke tu nahrádza transcendentálne výpočty bez viditeľnej straty presnosti. Rovnaká úvaha sa objavuje hneď vedľa toho vo funkcii Lab2XYZ, kde sa Power(LMN[i], 3) zmenilo na obyčajné LMN[i]*LMN[i]*LMN[i]: celočíselná mocnina vôbec nepotrebuje Ln/Exp, takže tu vôbec nejde o kompromis s vyhľadávacou tabuľkou, len o odstránenie zbytočného volania Power. Trik s vyhľadávacou tabuľkou sa oplatí len preto, že prevodová funkcia je čistou funkciou jedinej hodnoty Double – nedal by sa čisto rozšíriť na farebnú transformáciu, ktorá by závisela od viacerých hodnôt pixelu alebo od väčšieho množstva stavu

Ako rozpoznať 73 operátorov obsahového streamu rýchlo?

ContentOperatorFromName sa volá pre každý token, ktorý PDFlibPas prečíta z obsahového streamu, a porovnáva ho s celou sadou 73 operátorov z tabuľky 51 ISO 32000-1 – od w a q až po zriedkavo videné operátory metrík glyfov typu 3 d0 a d1 – a kedysi pri každom jednom tokene prechádzal tento zoznam lineárne, takže strana s niekoľkými tisíckami operátorov znamenala niekoľko tisíc lineárnych prehľadávaní toho istého 73-položkového zoznamu. PDFlibPas teraz pri štarte rozdelí tabuľku podľa prvého bajtu operátora do pevného poľa slotov indexovaného typom AnsiChar, takže vyhľadanie sa zredukuje na jeden index v poli a prehľadanie len tej hŕstky operátorov, ktoré zdieľajú rovnaký prvý 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;

Operátory PDF rozlišujú veľkosť písmen – w a W, f a F, sc a SC sú všetko odlišné operátory – takže GOpBuckets kľúčuje podľa surového bajtu a zvyškové porovnanie vnútri jedného slotu je obyčajná, na veľkosť písmen citlivá rovnosť AnsiString. Pole má veľkosť 16 slotov na písmeno, čo pohodlne pokrýva dnešnú tabuľku – najviac zaplnený slot, T, obsahuje trinásť operátorov, keďže takmer každý operátor textového stavu a textového polohovania ním začína – ale EnsureOpBuckets ticho prestane pridávať do slotu, akonáhle jeho počet dosiahne 16, takže slot, ktorý by niekedy potreboval štrnástu položku, by zlyhal ticho, nie nahlas: operátor by sa vyriešil ako coUnknown bez akejkoľvek výnimky poukazujúcej na príčinu. To je náklad na údržbu za výmenu dátovej štruktúry, ktorá elegantne degraduje, za takú, ktorá to nerobí – rozpoznáva rýchlejšie, pretože nikdy nepotrebuje rast s kontrolou hraníc, a potrebuje človeka, ktorý sleduje jediný slot blízko svojho stropu

Odstránenie O(n²) zo skladania reťazcov

Pascalovský vzor Result := Result + Fragment pri každej iterácii alokuje a kopíruje celý dosiaľ nazbieraný reťazec, takže vytvorenie N-znakového výstupu po jednom fragmente stojí O(n²) namiesto O(n) – ľahko sa to prehliadne pri kontrole kódu, keďže každý riadok vyzerá ako jedno lacné pripojenie, a v praxi je to nákladné, pretože PLDirectEscapeLiteralString beží pri každom literálnom reťazci PDF zapísanom počas uloženia a XFDFXMLEscape beží pri každej hodnote poľa exportovanej do XFDF. PDFlibPas opravuje oba dvomi odlišnými technikami, zvolenými podľa toho, čo dokáže každá funkcia vopred predpovedať. PLDirectEscapeLiteralString pozná dĺžku svojho výstupu skôr, než zapíše čo i len jeden bajt – jeden priechod zaradí každý znak ako obyčajný alebo escapovaný a spočíta celkový súčet, SetLength alokuje raz a druhý priechod naplní buffer podľa indexu. XFDFXMLEscape nedokáže lacno predpovedať dĺžku svojho výstupu, keďže text poľa v Unicode sa príliš líši na to, aby sa dal vopred vypočítať, takže namiesto toho pripája do TStringBuilder vopred veľkostne odhadnutého približne na dĺžku vstupu

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;

Voľba medzi oboma prístupmi je v skutočnosti o tom, čo viete ešte pred začiatkom cyklu. Najprv spočítať a potom naplniť je rýchlejšie z oboch riešení vtedy, keď je veľkosť výstupu lacné vypočítať, keďže nerobí žiadne opätovné alokácie a žiadnu réžiu okrem počítadla typu Integer, no znamená to napísať klasifikačnú logiku dvakrát – raz na počítanie, raz na zápis – čo je samo osebe riziko údržby, ak sa obe kópie časom rozídu. TStringBuilder sa vzdáva kúska tejto špičkovej priepustnosti výmenou za napísanie logiky iba raz a amortizované pripájanie s konštantnou zložitosťou vďaka geometrickému rastu vyrovnávacej pamäte, čo je bezpečnejšia predvolená voľba vždy, keď nie je ľahké dopredu poznať veľkosť výstupu

Kde sa tento vzor uplatňuje a kde nie

Všetky štyri opravy vyššie sú príkladmi jedinej myšlienky: nájsť volanie, ktoré beží raz na jednotku vstupu – na kľúč slovníka, na pixel, na token operátora, na znak – a nahradiť jeho lineárne alebo nepredvídateľné náklady vopred vypočítanou tabuľkou, hashovacím indexom alebo vopred veľkostne odhadnutým bufferom. Nič z toho nie je špecifické pre PDF; služba v Delphi, ktorá tisíckrát na požiadavku rieši ten istý vyhľadávací kľúč, konvertuje hodnoty v tesnom cykle, rozpoznáva podľa pevného slovníka tokenov alebo skladá dlhé reťazce znak po znaku, naráža na rovnaké tvary zlyhania a rieši ich rovnakými opravami. Čoho sa žiadna z týchto štyroch zmien nedotýka, je súbežnosť ani pamäťová stopa: rýchlejšie jednovláknové vyhľadávanie v slovníku nič nerobí pre dve vlákna pretekajúce sa nad tou istou inštanciou TPDFlib, čo je štrukturálny problém pokrytý samostatne v článku o bezpečnosti vlákien pri paralelnom vykresľovaní strán, a nič nerobí ani pre PDF príliš veľké na to, aby sa vôbec dalo načítať do pamäte ako strom objektov, na čo slúži vrstva priameho prístupu v PDFlibPas, pokrytá v článku o zlučovaní a delení gigabajtových PDF

Kód pre slovníky, správu farieb, rozpoznávanie operátorov obsahového streamu a skladanie reťazcov opísaný v tomto článku je súčasťou štandardnej knižnice PDFlibPas, PDF knižnice spoločnosti losLab pre Delphi a C++Builder, bez potreby akéhokoľvek dodatočného nastavenia