Profilování výkonu PDFlibPas: hashovací indexy v Delphi

PDFlibPas, knihovna PDF od losLab pro Delphi a C++Builder, zrychluje své cesty vykreslování a generování obsahu nahrazením čtyř vzorů opakované práce amortizovanými: líným hashovacím indexem pro vyhledávání klíčů slovníku, předpočítanou vyhledávací tabulkou gama sRGB, kbelíkováním podle prvního bajtu pro dispatch operátorů proudu obsahu, a TStringBuilder místo opakovaného spojování řetězců. Žádná ze čtyř nevzešla z jednoho dramatického objevu — vzešly ze stejného neokázalého vzoru v profilu: malá funkce volaná jednou na klíč slovníku, jednou na pixel, nebo jednou na znak, kde se lineární náklad uvnitř volání promění na kvadratický nebo skoro kvadratický přes celý dokument. To je společné vlákno zde: čtyři malé, na první pohled nesouvisející opravy, které útočí na stejný tvar problému, plus poctivé limity každé z nich

Kde vykreslovač proudu obsahu skutečně tráví svůj čas

Vykreslovač proudu obsahu PDFlibPas svádí téměř celý svůj náklad na token přes čtyři úzká místa: vyhledávání ve slovníku zdrojů na /Resources, /ColorSpace, /Font a /ExtGState; gama korekci na každém dekódovaném pixelu obrázku Lab, Indexed, nebo označeného ICC; porovnávání jmen operátorů na každém tokenu každého proudu obsahu; a stavbu řetězců kdekoli, kde knihovna staví výstup — escapování literálních řetězců při uložení, export XFDF, expanzi razítek a tokenů proměnných při ukládání. Každá z těchto čtyř dělá malé množství práce sama o sobě, a každá běží tisíckrát nebo milionkrát přes realistický dokument, což je přesně tvar funkce, kde detail implementace O(n) nebo O(n²) přestává být neviditelný a stává se vrchním záznamem profilu

Proč vyhledávání ve slovníku zdrojů zpomaluje ve velkém PDF?

TPDFDictionary.FindIndexByKeyName je to, co vykreslovač volá k rozřešení každého vyhledávání /Resources, /ColorSpace, /Font a /ExtGState, a dřív procházel pole Entries od začátku při každém volání — v pořádku pro tříprvkový slovník Resources, drahé pro Form XObject nebo stránku hustou na ExtGState, kde se stejný slovník prozkoumá při každém operátoru, který se dotkne barvy nebo stavu grafiky. PDFlibPas teď staví líný hashovací index, jakmile slovník překročí DICT_HASH_THRESHOLD (16) záznamů, a ponechává menší slovníky na lineárním prohledávání, protože většina slovníků PDF nikdy tak nenaroste a hashovací tabulka pro tři klíče by na postavení stála víc, než ušetří. Index je plochá tabulka s otevřeným adresováním klíčovaná přes PLAnsiStringHash, hash FNV-1a s kanonickou offsetovou bází 2166136261 a prvočíslem 16777619, zvolený tak, aby se vyhnul zatáhnutí System.Generics.Collections pro něco takto citlivého na velikost

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 se invaliduje místo toho, aby se udržoval přírůstkově: každé měnící volání — AddEntry, DeleteEntryByKeyName, Assign, AddDict — vyčistí hash a nechá další vyhledávání přestavět jej od nuly. To vypadá jako plýtvání, dokud si nevšimnete, že klíč slovníku je objekt TPDFName, a TPDFName.SetTo dokáže přejmenovat klíč už sedící v poli Entries slovníku, aniž by prošel kteroukoli z vlastních metod slovníku — přírůstkový index nemá způsob, jak toto přejmenování pozorovat, zatímco líný jednoduše přestaví a zůstane správný konstrukčně. Cenou za tuto bezpečnost je přestavba O(n) při první dotazu velkého slovníku po zápisu, plus paměť pro samotnou hashovací tabulku, zhruba jedno Integer na slot při zatížení dvou třetin — chyba zaokrouhlení pro hrstku předimenzovaných slovníků v typickém dokumentu, a skutečný náklad, kterému se PDFlibPas vyhýbá u každého malého tím, že drží práh tam, kde je

Předpočítání gama sRGB místo volání Power na pixel

TPDFSimpleColorManager.XYZ2RGB aplikuje přenosovou funkci sRGB na každý dekódovaný pixel obrázku Lab, Indexed, nebo založeného na ICC — 1.055 * Power(x, 1/2.4) - 0.055 nad prahem lineárního segmentu — a Power(x, y) pro zlomkové y nemá v RTL Pascalu žádný levný uzavřený tvar: rozloží se na Ln(x) pak Exp(y * Ln(x)), a tato dvojice transcendentálních volání, spuštěná třikrát na pixel pro červený, zelený a modrý kanál, je dominantní náklad dekódování pixelu obrázku Lab nebo ICC po pixelu. PDFlibPas nahrazuje tři volání Power na pixel jedním vyhledáním do GSRGBGammaLUT, pole Double se 4096 záznamy postaveném jednou přes EnsureSRGBGammaLUT a indexovaném zaokrouhlením ořezaného vstupu na nejbližší 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;

Tabulka se 4096 sloty přes vstupní rozsah [0, 1] dává zhruba šestnáctkrát vyšší rozlišení, než jaké má 8bitový výstupní kanál, takže kvantizace, kterou LUT zavádí, sedí pod tím, co dokáže reprezentovat finální bajt RGB — vyhledání v tabulce tady nahrazuje transcendentální matematiku bez viditelného nákladu na přesnost. Stejná úvaha se objevuje vedle toho v Lab2XYZ, kde se Power(LMN[i], 3) stalo obyčejným LMN[i]*LMN[i]*LMN[i]: celočíselná mocnina vůbec nepotřebuje Ln/Exp na prvním místě, takže tohle vůbec není kompromis LUT, jen odstraněné nadbytečné volání Power. Trik s LUT se vyplatí jen proto, že je přenosová funkce čistá funkce jednoho Double — nerozšířilo by se to čistě na transformaci barvy, která by závisela na několika hodnotách pixelu nebo na víc stavu než tomto

Jak rychle dispatchovat 73 operátorů proudu obsahu?

ContentOperatorFromName se volá jednou pro každý token, který PDFlibPas přečte z proudu obsahu, porovnává jej proti plné sadě 73 operátorů z tabulky 51 ISO 32000-1 — od w a q až po vzácně vídané operátory metrik glyfů Typu 3 d0 a d1 — a dřív tento seznam procházel lineárně při každém jednotlivém tokenu, takže stránka s pár tisíci operátory znamenala pár tisíc lineárních průchodů přes stejnou 73záznamovou tabulku. PDFlibPas teď kbelíkuje tabulku podle prvního bajtu operátoru při startu, do pevného pole slotů indexovaného AnsiChar, takže se vyhledání stane jedním indexem pole plus průchodem jen hrstky operátorů sdílejících tento první 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í velikost písmen — w a W, f a F, sc a SC jsou všechny odlišné operátory — takže GOpBuckets klíčuje na surový bajt a zbytkové porovnání uvnitř kbelíku je obyčejná, na velikost citlivá rovnost AnsiString. Pole je velikostně dimenzované na 16 slotů na písmeno, což pohodlně pokrývá dnešní tabulku — nejrušnější kbelík, T, drží třináct operátorů, protože skoro každý operátor stavu textu a pozicování textu jím začíná — ale EnsureOpBuckets tiše přestane přidávat do kbelíku, jakmile jeho počet dosáhne 16, takže kbelík, který by kdy potřeboval čtrnáctý záznam, by selhal tiše místo hlasitě: operátor by se rozřešil na coUnknown bez jakékoli výjimky ukazující proč. To je náklad na údržbu za výměnu datové struktury, která se elegantně degraduje, za tu, která to nedělá — dispatchuje rychleji, protože nikdy nepotřebuje růst s kontrolou mezí, a potřebuje člověka sledujícího ten jeden kbelík blízko svého stropu

Odříznutí O(n²) ze stavby řetězců

Vzor Pascalu Result := Result + Fragment při každé iteraci znovu alokuje a kopíruje celý nahromaděný řetězec, takže stavba N-znakového výstupu po jednom fragmentu stojí O(n²) místo O(n) — snadné přehlédnout při revizi, protože každý řádek vypadá jako jedno levné připojení, a drahé v praxi, protože PLDirectEscapeLiteralString běží na každém literálním řetězci PDF zapsaném během ukládání a XFDFXMLEscape běží na každé hodnotě pole exportované do XFDF. PDFlibPas opravuje tyto dvě odlišnými technikami, zvolenými podle toho, co každá funkce dokáže předem odhadnout. PLDirectEscapeLiteralString zná svou výstupní délku, ještě než zapíše jediný bajt — jeden průchod klasifikuje každý znak jako obyčejný nebo escapovaný a sečte celkovou délku, SetLength alokuje jednou, a druhý průchod naplní buffer podle indexu. XFDFXMLEscape nedokáže levně předpovědět svou výstupní délku, protože unikódový text pole se liší příliš na to, aby se to dalo předpočítat, takže místo toho připojuje do TStringBuilder předdimenzovaného zhruba na délku 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;

Volba mezi oběma je skutečně o tom, co víte ještě před začátkem smyčky. Napočítej-pak-naplň je rychlejší z obou, když je výstupní velikost levné spočítat, protože nedělá žádné realokace a žádné účetnictví nad rámec počítadla Integer, ale znamená to napsat klasifikační logiku dvakrát — jednou na počítání, jednou na výstup — což je vlastní riziko údržby, pokud se obě kopie rozejdou. TStringBuilder vzdává trochu z této špičkové propustnosti za napsání logiky jednou a získání amortizovaných O(1) připojení z geometrického růstu bufferu, což je bezpečnější výchozí volba, kdykoli velikost výstupu není snadné znát předem

Kde se tento vzor uplatní, a kde ne

Všechny čtyři opravy výše jsou instance jedné myšlenky: najít volání, které běží jednou na jednotku vstupu — na klíč slovníku, na pixel, na token operátoru, na znak — a nahradit jeho lineární nebo nepředvídatelný náklad předpočítanou tabulkou, hashovacím indexem, nebo předdimenzovaným bufferem. Nic z toho není specifické pro PDF; služba v Delphi, která rozřešuje stejný klíč vyhledání tisíckrát na požadavek, převádí hodnoty v těsné smyčce, dispatchuje na pevném slovníku tokenů, nebo staví dlouhé řetězce po jednom znaku, naráží na stejné tvary selhání a bere stejné opravy. Co žádná z těchto čtyř změn nezasahuje, je souběžnost nebo paměťová stopa: rychlejší jednovláknové vyhledávání ve slovníku nedělá nic pro dvě vlákna soupeřící o stejnou instanci TPDFlib, což je strukturální problém popsaný samostatně v článku o bezpečnosti vláken v paralelním vykreslování stránek, a nedělá nic pro PDF příliš velké na to, aby se vůbec dalo načíst do paměti jako strom objektů, což je k čemu slouží vrstva Direct Access v PDFlibPas, popsaná v článku o slučování a rozdělování gigabajtových PDF

Kód slovníku, správy barev, dispatche proudu obsahu a stavby řetězců popsaný zde se dodává jako součást standardní PDFlibPas, knihovny PDF od losLab pro Delphi a C++Builder, bez potřeby jakékoli dodatečné konfigurace, aby cokoli z toho fungovalo