Profiliranje PDFlibPas-a: hash indeksi i optimizacija

PDFlibPas, losLabova PDF biblioteka za Delphi i C++Builder, ubrzava putanje prikazivanja i generiranja sadržaja zamjenom četiri obrasca ponavljanog rada amortiziranim oblicima: lijeni hash indeks za traženje ključeva rječnika, unaprijed izračunata sRGB tablica gama, grupiranje operatora toka sadržaja prema prvom bajtu i TStringBuilder umjesto ponovljenog spajanja nizova. Nijedan od ta četiri zahvata nije proizašao iz jednog dramatičnog otkrića — svi su proizašli iz istog neuglednog obrasca u profilu: mala funkcija pozvana jednom po operatoru, pikselu ili znaku, gdje linearni trošak unutar poziva postaje kvadratni ili gotovo kvadratni preko cijelog dokumenta. To je nit koja ih povezuje: četiri mala, naizgled nepovezana popravka koja napadaju isti oblik problema, uz pošteno navedena ograničenja svakog od njih

Gdje program za iscrtavanje toka sadržaja zapravo troši vrijeme

Program za iscrtavanje toka sadržaja PDFlibPas-a gotovo sav trošak po tokenu usmjerava kroz četiri uska mjesta: traženja u rječnicima resursa za /Resources, /ColorSpace, /Font i /ExtGState; korekciju game na svakom dekodiranom pikselu slike Lab, Indexed ili s ICC oznakom; podudaranje imena operatora na svakom tokenu svakog toka sadržaja; i izgradnju nizova gdje god biblioteka stvara izlaz — escapiranje literalnih nizova pri spremanju, izvoz XFDF-a te proširivanje oznaka pečata i varijabli. Svaki od ta četiri postupka zasebno radi malo, a svaki se na realnom dokumentu pokrene tisućama ili milijunima puta, što je upravo oblik funkcije kod kojeg pojedinost implementacije O(n) ili O(n²) prestaje biti nevidljiva i postaje vodeća stavka profila

Zašto traženja u rječniku resursa postaju spora u velikom PDF-u

TPDFDictionary.FindIndexByKeyName program za iscrtavanje poziva za razrješavanje svakog traženja /Resources, /ColorSpace, /Font i /ExtGState, a ranije je pri svakom pozivu prolazio kroz polje Entries od početka — dobro za rječnik Resources s tri stavke, ali skupo za Form XObject ili stranicu s mnogo ExtGState stavki na kojoj se isti rječnik ispituje pri svakom operatoru koji dotiče boju ili grafičko stanje. PDFlibPas sada jednom gradi lijeni hash indeks kada rječnik prijeđe DICT_HASH_THRESHOLD od 16 stavki, a manje rječnike ostavlja na linearnom prolazu jer većina PDF rječnika nikada ne naraste toliko i izgradnja hash tablice za tri ključa koštala bi više nego što bi uštedjela. Indeks je ravna tablica s otvorenim adresiranjem, ključana funkcijom PLAnsiStringHash, FNV-1a hashom s kanonskom osnovom pomaka 2166136261 i prostim brojem 16777619, odabranim kako se ne bi uvodio System.Generics.Collections za nešto tako osjetljivo na veličinu

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 poništava umjesto da se održava inkrementalno: svaki poziv koji mijenja stanje — AddEntry, DeleteEntryByKeyName, Assign, AddDict — briše hash i dopušta da ga sljedeće traženje ponovno izgradi od početka. To izgleda rasipno dok ne primijetite da je ključ rječnika objekt TPDFName, a TPDFName.SetTo može preimenovati ključ koji već sjedi u polju Entries rječnika bez prolaska kroz njegove vlastite metode — inkrementalni indeks nema načina uočiti to preimenovanje, dok lijeni indeks jednostavno ponovno izgradi tablicu i po konstrukciji ostaje ispravan. Cijena te sigurnosti je ponovna izgradnja O(n) pri prvom traženju velikog rječnika nakon upisa, uz memoriju za samu hash tablicu, približno jedan Integer po pretincu pri faktoru popunjenosti od dvije trećine — zanemariv trošak za nekoliko prevelikih rječnika u tipičnom dokumentu, a stvaran trošak koji PDFlibPas izbjegava plaćati pri svakom malom traženju tako što prag ostavlja na ovoj vrijednosti

Unaprijed izračunata sRGB gama umjesto poziva Power za svaki piksel

TPDFSimpleColorManager.XYZ2RGB primjenjuje sRGB prijenosnu funkciju na svaki dekodirani piksel slike Lab, Indexed ili utemeljene na ICC-u — 1.055 * Power(x, 1/2.4) - 0.055 iznad praga linearnog segmenta — a Power(x, y) za razlomljeni y nema jeftin zatvoren oblik u Pascal RTL-u: rastavlja se na Ln(x), zatim Exp(y * Ln(x)), a taj par transcendentnih poziva, izvršen tri puta po pikselu za crveni, zeleni i plavi kanal, dominantan je trošak dekodiranja Lab ili ICC slike piksel po piksel. PDFlibPas zamjenjuje tri poziva Power po pikselu jednim dohvatom iz GSRGBGammaLUT, polja od 4096 vrijednosti tipa Double koje se jednom izgradi kroz EnsureSRGBGammaLUT i indeksira zaokruživanjem ograničenog ulaza na najbliži pretinac

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;

Tablica s 4096 pretinaca preko ulaznog raspona [0, 1] daje približno šesnaest puta veću razlučivost od 8-bitnog izlaznog kanala, pa kvantizacija koju LUT uvodi ostaje ispod onoga što završni RGB bajt može prikazati — dohvat iz tablice ovdje zamjenjuje transcendentnu matematiku bez vidljivog gubitka preciznosti. Isto se obrazloženje pojavljuje odmah uz nju u Lab2XYZ, gdje je Power(LMN[i], 3) postao običan LMN[i]*LMN[i]*LMN[i]: cjelobrojna potencija uopće ne treba Ln/Exp, pa to nije kompromis s LUT-om nego samo uklanjanje suvišnog poziva Power. Trik s LUT-om isplati se samo zato što je prijenosna funkcija čista funkcija jedne vrijednosti tipa Double — ne bi se uredno proširio na transformaciju boje koja ovisi o više vrijednosti piksela ili o većem stanju

Kako brzo rasporediti 73 operatora toka sadržaja

ContentOperatorFromName poziva se jednom za svaki token koji PDFlibPas pročita iz toka sadržaja i uspoređuje ga s potpunim skupom od 73 operatora iz ISO 32000-1 Tablice 51 — od w i q do rijetko viđenih operatora metrike glifova tipa 3 d0 i d1 — a ranije je taj popis pri svakom pojedinom tokenu prolazio linearno, pa je stranica s nekoliko tisuća operatora značila nekoliko tisuća linearnih prolaza kroz istu tablicu od 73 stavke. PDFlibPas sada pri pokretanju grupira tablicu prema prvom bajtu operatora u fiksno polje pretinaca indeksirano pomoću AnsiChar, pa traženje postaje jedan indeks polja i prolaz samo kroz nekoliko operatora koji dijele isti početni 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;

PDF operatori razlikuju velika i mala slova — w i W, f i F, sc i SC svi su različiti operatori — pa GOpBuckets koristi izvorni bajt kao ključ, a preostala usporedba unutar pretinca obična je usporedba AnsiString osjetljiva na velika i mala slova. Polje je veličine 16 mjesta po slovu, što bez problema pokriva današnju tablicu — najopterećeniji pretinac, T, sadrži trinaest operatora jer gotovo svaki operator stanja teksta i pozicioniranja teksta počinje slovom T — ali EnsureOpBuckets tiho prestaje dodavati u pretinac kada broj dosegne 16, pa bi pretinac kojem bi ikada trebao četrnaesti unos tiho zakazao umjesto da glasno prijavi problem: operator bi se razriješio u coUnknown bez iznimke koja bi pokazala zašto. To je trošak održavanja zamjene podatkovne strukture koja se postupno pogoršava onom koja to ne čini — raspoređivanje je brže jer nikada ne treba rast provjeren granicama, ali čovjek mora pratiti jedan pretinac koji se približava gornjoj granici

Uklanjanje O(n²) iz izgradnje nizova

Pascalov obrazac Result := Result + Fragment pri svakoj iteraciji ponovno alocira i kopira cijeli već izgrađeni niz, pa izgradnja izlaza od N znakova dio po dio košta O(n²) umjesto O(n) — lako ga je previdjeti pri pregledu jer svaki redak izgleda kao jedno jeftino dodavanje, a u praksi je skup jer se PLDirectEscapeLiteralString izvršava za svaki literalni PDF niz zapisan tijekom spremanja, dok se XFDFXMLEscape izvršava za svaku vrijednost polja izvezenu u XFDF. PDFlibPas to rješava na dva različita načina, odabrana prema tome što svaka funkcija može unaprijed predvidjeti. PLDirectEscapeLiteralString zna duljinu izlaza prije zapisivanja ijednog bajta — jednim prolazom razvrstava svaki znak kao običan ili escapiran i zbraja ukupnu duljinu, SetLength jednom alocira prostor, a drugi prolaz popunjava međuspremnik prema indeksu. XFDFXMLEscape ne može jeftino predvidjeti duljinu izlaza jer se tekst polja Unicode previše razlikuje da bi se unaprijed izračunao, pa umjesto toga dodaje u TStringBuilder unaprijed veličine približno jednake duljini ulaza

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;

Izbor između ta dva pristupa zapravo ovisi o tome što znate prije početka petlje. Brojanje pa popunjavanje brže je kada je veličinu izlaza lako izračunati jer nema ponovnih alokacija ni knjigovodstva osim brojača tipa Integer, ali znači pisanje logike razvrstavanja dvaput — jednom za brojanje i jednom za ispis — što je vlastiti rizik održavanja ako se dvije kopije raziđu. TStringBuilder odustaje od dijela vršnog protoka podataka kako bi se logika napisala jednom i dobila amortizirana dodavanja O(1) uz geometrijski rast međuspremnika, što je sigurnija zadana vrijednost kada veličinu izlaza nije lako unaprijed znati

Gdje se ovaj obrazac primjenjuje, a gdje ne

Sva četiri navedena popravka primjeri su iste ideje: pronađite poziv koji se izvršava jednom po jedinici ulaza — po ključu rječnika, pikselu, tokenu operatora ili znaku — i zamijenite njegov linearni ili nepredvidivi trošak unaprijed izračunatom tablicom, hash indeksom ili unaprijed dimenzioniranim međuspremnikom. Ništa od toga nije specifično za PDF; Delphi servis koji tisućama puta po zahtjevu razrješava isti ključ traženja, pretvara vrijednosti u tijesnoj petlji, raspoređuje prema fiksnom rječniku tokena ili gradi duge nizove znak po znak nailazi na iste oblike kvara i dobiva ista rješenja. Ono što nijedna od te četiri promjene ne dotiče jest konkurentnost ili memorijski otisak: brže traženje u rječniku u jednoj niti ne pomaže dvjema nitima koje se nadmeću za istu instancu TPDFlib, što je strukturni problem zasebno obrađen u članku o sigurnosti niti pri paralelnom prikazivanju stranica, a ne pomaže ni PDF-u toliko velikom da ga uopće nije moguće učitati u memoriju kao stablo objekata, za što služi sloj Direct Access u PDFlibPas-u i što je obrađeno u članku o spajanju i dijeljenju PDF-ova veličine gigabajta

Rječnik, upravljanje bojama, raspoređivanje toka sadržaja i kod za izgradnju nizova o kojem se ovdje govori isporučuju se kao dio standardnog PDFlibPas-a, losLabove PDF biblioteke za Delphi i C++Builder, bez potrebe za dodatnom konfiguracijom kako bi se išta od toga koristilo