Profiliranje zmogljivosti PDFlibPas: zgoščevalni indeksi v Delphiju

PDFlibPas, losLabova knjižnica PDF za Delphi in C++Builder, pospeši svoje poti upodabljanja in ustvarjanja vsebine tako, da štiri vzorce ponavljajočega se dela zamenja z amortiziranimi vzorci: z odloženim zgoščevalnim indeksom za iskanje ključev v slovarju, s predizračunano iskalno tabelo gama sRGB, z razvrščanjem operatorjev podatkovnega toka po prvem bajtu in z TStringBuilder namesto ponavljajočega se združevanja nizov. Nobeden od teh štirih pristopov ni izšel iz enega dramatičnega odkritja — vsi so izšli iz istega nebleščečega vzorca v profilu: majhne funkcije, klicane enkrat na operator, enkrat na slikovno piko ali enkrat na znak, kjer linearni strošek znotraj klica postane kvadraten ali skoraj kvadraten za celoten dokument. To je rdeča nit: štirje majhni, navidezno nepovezani popravki, ki napadajo isto obliko težave, skupaj z iskrenimi omejitvami vsakega

Kje upodabljalnik podatkovnega toka dejansko porabi svoj čas

Upodabljalnik podatkovnega toka PDFlibPas skoraj vse stroške na žeton usmerja skozi štiri ozke točke: iskanja v slovarjih virov za /Resources, /ColorSpace, /Font in /ExtGState; popravek game na vsaki dekodirani slikovni piki slike Lab, Indexed ali z oznako ICC; ujemanje imen operatorjev na vsakem žetonu vsakega podatkovnega toka; ter ustvarjanje nizov povsod, kjer knjižnica gradi izhod — ubežanje dobesednih nizov pri shranjevanju, izvoz XFDF ter razširjanje žetonov žigov in spremenljivk. Vsak od teh postopkov sam zase opravi malo dela, vsak pa se na realnem dokumentu izvede tisočkrat ali milijonkrat, kar je natanko oblika funkcije, pri kateri podrobnost izvedbe O(n) ali O(n²) preneha biti nevidna in postane najvišji vnos profila

Zakaj postanejo iskanja v slovarjih virov pri velikem PDF počasna

TPDFDictionary.FindIndexByKeyName je funkcija, ki jo upodabljalnik kliče za razreševanje vsakega iskanja /Resources, /ColorSpace, /Font in /ExtGState, prej pa je ob vsakem klicu od začetka prehodila polje Entries — dovolj hitro za slovar virov s tremi vnosi, drago pa za Form XObject ali stran z veliko primeri ExtGState, kjer se isti slovar preveri pri vsakem operatorju, ki se dotika barvnega ali grafičnega stanja. PDFlibPas zdaj zgradi odložen zgoščevalni indeks, ko slovar preseže DICT_HASH_THRESHOLD (16) vnosov, manjše slovarje pa pusti pri linearnem pregledu, saj večina slovarjev PDF nikoli ne postane tako velika in bi bilo zgoščevalno tabelo za tri ključe dražje zgraditi, kot bi prihranila. Indeks je ploska tabela z odprtim naslavljanjem, ki uporablja PLAnsiStringHash, zgoščevalno funkcijo FNV-1a s kanonično osnovo odmika 2166136261 in praštevilom 16777619, izbrano zato, da za tako občutljivo velikost ne bi bilo treba vključiti System.Generics.Collections

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 se razveljavi, namesto da bi se vzdrževal inkrementalno: vsak spreminjajoči klic — AddEntry, DeleteEntryByKeyName, Assign, AddDict — počisti zgoščevanje in dovoli, da ga naslednje iskanje znova zgradi iz nič. To se zdi potratno, dokler ne opazimo, da je ključ slovarja objekt TPDFName in da lahko TPDFName.SetTo preimenuje ključ, ki že sedi v polju Entries slovarja, ne da bi šel skozi katero od lastnih metod slovarja — inkrementalni indeks takega preimenovanja ne more zaznati, odloženi pa ga preprosto znova zgradi in tako ostane pravilen po zasnovi. Cena te varnosti je ponovna gradnja O(n) ob prvem poizvedovanju velikega slovarja po pisanju, skupaj s pomnilnikom za samo zgoščevalno tabelo, približno eno celo število na režo pri faktorju zapolnjenosti dveh tretjin — za nekaj predimenzioniranih slovarjev v običajnem dokumentu zanemarljiv strošek, ki se mu PDFlibPas pri vsakem majhnem slovarju izogne tako, da prag ohrani na tej vrednosti

Predizračun game sRGB namesto klica potence za vsako slikovno piko

TPDFSimpleColorManager.XYZ2RGB uporabi prenosno funkcijo sRGB za vsako dekodirano slikovno piko slike Lab, Indexed ali na osnovi ICC — 1.055 * Power(x, 1/2.4) - 0.055 nad pragom linearnega odseka — funkcija Power(x, y) pa za ulomek y v izvajalnem okolju Pascal RTL nima poceni zaprte oblike: razstavi se na Ln(x) in nato Exp(y * Ln(x)), ta par transcendentnih klicev, izveden trikrat na slikovno piko za rdeči, zeleni in modri kanal, pa je prevladujoči strošek dekodiranja slike Lab ali ICC po slikovnih pikah. PDFlibPas tri klice Power na slikovno piko zamenja z enim iskanjem v GSRGBGammaLUT, polju Double s 4096 vnosi, ki se enkrat zgradi prek EnsureSRGBGammaLUT in se indeksira z zaokroževanjem omejenega vhoda na najbližjo režo

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 s 4096 režami na vhodnem območju [0, 1] ponuja približno šestnajstkrat večjo ločljivost od 8-bitnega izhodnega kanala, zato kvantizacija, ki jo uvede LUT, ostane pod tem, kar lahko predstavi končni bajt RGB — iskanje v tabeli tukaj zamenja transcendentno matematiko brez vidnega stroška natančnosti. Enako razmišljanje se pojavi poleg tega v Lab2XYZ, kjer je Power(LMN[i], 3) postal navaden LMN[i]*LMN[i]*LMN[i]: celoštevilska potenca najprej ne potrebuje Ln/Exp, zato to sploh ni kompromis LUT, temveč le odstranjeni odvečni klic Power. Zvijača z LUT se izplača le zato, ker je prenosna funkcija čista funkcija ene vrednosti Double — ne bi se gladko razširila na barvno pretvorbo, ki je odvisna od več slikovnih pik ali od več stanja

Kako hitro razpošiljati 73 operatorjev podatkovnega toka

ContentOperatorFromName se pokliče enkrat za vsak žeton, ki ga PDFlibPas prebere iz podatkovnega toka, in ga primerja s celotnim naborom 73 operatorjev iz tabele 51 standarda ISO 32000-1 — od w in q do redko videnih operatorjev meritev glifov Type 3 d0 in d1 — prej pa je ta seznam ob vsakem žetonu linearno prehodil, zato je stran z nekaj tisoč operatorji pomenila nekaj tisoč linearnih pregledov iste tabele s 73 vnosi. PDFlibPas zdaj ob zagonu razvrsti tabelo po prvem bajtu operatorja v fiksno polje rež, indeksirano z AnsiChar, zato iskanje postane en indeks polja in pregled le peščice operatorjev, ki imajo isto začetno črko

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;

Operatorji PDF razlikujejo velike in male črke — w in W, f in F, sc in SC so vsi različni operatorji — zato GOpBuckets uporablja surovi bajt, preostala primerjava znotraj rež pa je navadna primerjava AnsiString, občutljiva na velikost črk. Polje je dimenzionirano na 16 rež na črko, kar udobno pokriva današnjo tabelo — najbolj obremenjena reža, T, vsebuje trinajst operatorjev, saj se skoraj vsak operator stanja in pozicioniranja besedila začne s T — vendar EnsureOpBuckets tiho preneha dodajati v režo, ko njeno število doseže 16, zato bi štirinajsti vnos v reži tiho odpovedal namesto glasno: operator bi se razrešil v coUnknown brez izjeme, ki bi pokazala razlog. To je vzdrževalni strošek menjave podatkovne strukture, ki se postopno slabša, za tako, ki tega ne počne — razpošilja hitreje, ker nikoli ne potrebuje rasti s preverjanjem meja, in zahteva človeka, ki spremlja eno režo blizu njenega stropa

Odstranjevanje O(n²) iz gradnje nizov

Vzorec Result := Result + Fragment v Pascalu ob vsaki iteraciji znova dodeli in kopira celoten že zgrajeni niz, zato gradnja izhoda z N znaki po delčkih stane O(n²) namesto O(n) — pri pregledu ga je lahko spregledati, saj je vsaka vrstica videti kot en poceni dodatek, v praksi pa je drag, ker se PLDirectEscapeLiteralString izvede za vsak dobesedni niz PDF, zapisan med shranjevanjem, XFDFXMLEscape pa za vsako vrednost polja, izvoženo v XFDF. PDFlibPas ti funkciji popravi z različnima tehnikama, izbranima glede na to, kaj lahko vsaka vnaprej napove. PLDirectEscapeLiteralString pozna dolžino izhoda, še preden zapiše en sam bajt — v enem prehodu vsak znak razvrsti kot navaden ali ubežen in sešteje skupno dolžino, SetLength enkrat dodeli pomnilnik, drugi prehod pa zapolni medpomnilnik po indeksu. XFDFXMLEscape svoje izhodne dolžine ne more poceni napovedati, ker se besedilo polj Unicode preveč razlikuje za predizračun, zato dodaja v TStringBuilder, vnaprej nastavljen približno na dolžino vhoda

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;

Izbira med obema pristopoma je v resnici odvisna od tega, kaj veste, preden se zanka začne. Štetje in nato zapolnjevanje je hitrejše od obeh, ko je velikost izhoda poceni izračunati, saj ne povzroči nobenega ponovnega dodeljevanja in ne potrebuje drugega beleženja kot števca tipa Integer, vendar pomeni dvakratno pisanje logike razvrščanja — enkrat za štetje in enkrat za izpis — kar je samo po sebi tveganje za vzdrževanje, če se kopiji razideta. TStringBuilder se odpove delu največje prepustnosti, da se logika napiše enkrat in pridobi amortizirane dodatke O(1) z geometrijsko rastjo medpomnilnika, kar je varnejša privzeta izbira, kadar izhodne velikosti ni lahko vnaprej poznati

Kje ta vzorec velja in kje ne

Vsi štirje zgornji popravki so primer ene zamisli: poiščite klic, ki se izvede enkrat na enoto vhoda — na ključ slovarja, slikovno piko, žeton operatorja ali znak — in njegov linearni ali nepredvidljivi strošek zamenjajte s predizračunano tabelo, zgoščevalnim indeksom ali vnaprej določeno velikostjo medpomnilnika. Nič od tega ni značilno samo za PDF; storitev Delphi, ki tisočkrat na zahtevo razreši isti iskalni ključ, pretvarja vrednosti v tesni zanki, razpošilja po stalnem besednjaku žetonov ali gradi dolge nize znak za znakom, naleti na iste oblike odpovedi in uporabi iste popravke. Nobena od teh štirih sprememb pa se ne dotakne sočasnosti ali pomnilniškega odtisa: hitrejše enonitno iskanje v slovarju ne pomaga dvema nitma, ki tekmujeta za isti primerek TPDFlib, kar je strukturna težava, ločeno obravnavana v članku o varnosti niti pri vzporednem upodabljanju strani, prav tako pa ne pomaga PDF-ju, ki je prevelik, da bi ga bilo mogoče v celoti naložiti v pomnilnik kot drevo objektov, za kar je namenjen sloj Direct Access v PDFlibPas, obravnavan v članku o združevanju in razdeljevanju gigabajtnih PDF-jev

Koda za slovarje, upravljanje barv, razpošiljanje podatkovnih tokov in gradnjo nizov, obravnavana tukaj, je del standardnega PDFlibPas, losLabove knjižnice PDF za Delphi in C++Builder, zato za uporabo ničesar od tega ni potrebna dodatna konfiguracija