LlosLab Software Development BlogInženjerske beleške za programere PDF-a, Delphi-ja i softvera za dokumente

Tehnički članak

Profilisanje performansi PDFlibPas-a: heš indeksi u Delphi-ju

Delphi PDF Library

PDFlibPas, losLab-ova PDF biblioteka za Delphi i C++Builder, ubrzava prikazivanje i generisanje sadržaja zamenom četiri obrasca ponavljanog rada amortizovanim pristupima: lenji heš indeks za traženje ključeva rečnika, unapred izračunata sRGB gama tabela, grupisanje operatora toka sadržaja po prvom bajtu i TStringBuilder umesto ponovljenog spajanja stringova. Nijedan od ta četiri zahvata nije proistekao iz jednog velikog otkrića — svi su potekli iz istog neupadljivog obrasca u profilu: mala funkcija pozvana jednom po operatoru, pikselu ili znaku, gde linearni trošak unutar poziva postaje kvadratan ili približno kvadratan kroz ceo dokument. To je zajednička nit: četiri mala, naizgled nepovezana popravka koja napadaju isti oblik problema, uz pošteno navedena ograničenja svake od njih

Gde renderer toka sadržaja zaista troši vreme

Prikazivač toka sadržaja u PDFlibPas-u gotovo sav trošak po tokenu usmerava kroz četiri uska mesta: traženje resursa u rečnicima /Resources, /ColorSpace, /Font i /ExtGState; gama korekciju svakog dekodiranog piksela slike Lab, Indexed ili sa ICC oznakom; poređenje imena operatora za svaki token svakog toka sadržaja; i izgradnju stringova svuda gde biblioteka pravi izlaz — izbegavanje znakova literalnih stringova pri čuvanju, XFDF izvoz i proširivanje tokena pečata i promenljivih. Svaka od te četiri radnje sama obavlja malo posla, ali se svaka izvršava hiljadama ili milionima puta nad stvarnim dokumentom, što je upravo oblik funkcije kod kog detalj implementacije O(n) ili O(n²) prestaje da bude nevidljiv i postaje najskuplja stavka profila

Zašto pretrage rečnika resursa usporavaju u velikom PDF-u

TPDFDictionary.FindIndexByKeyName je ono što prikazivač poziva da razreši svaku pretragu /Resources, /ColorSpace, /Font i /ExtGState, a ranije je pri svakom pozivu prolazio kroz niz Entries od početka — dovoljno dobro za rečnik Resources sa tri stavke, ali skupo za Form XObject ili stranicu sa mnogo ExtGState stavki, gde se isti rečnik proverava pri svakom operatoru koji dodiruje boju ili grafičko stanje. PDFlibPas sada lenji heš indeks gradi tek kada rečnik pređe DICT_HASH_THRESHOLD od 16 stavki, dok manje rečnike ostavlja na linearnom pretraživanju, jer većina PDF rečnika nikada ne naraste toliko, a heš tabela za tri ključa koštala bi više izgradnje nego što bi uštedela. Indeks je ravna tabela sa otvorenim adresiranjem, indeksirana pomoću PLAnsiStringHash, FNV-1a heša sa standardnom početnom osnovom 2166136261 i prostim brojem 16777619, izabranog da se zbog ovako osetljive veličine ne uvodi 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 poništava umesto da se održava inkrementalno: svaki poziv koji menja stanje — AddEntry, DeleteEntryByKeyName, Assign, AddDict — briše heš i prepušta sledećoj pretrazi da ga izgradi od početka. To deluje rasipnički dok se ne uoči da je ključ rečnika objekat TPDFName, a TPDFName.SetTo može da preimenuje ključ koji već sedi u nizu Entries bez prolaska kroz metode samog rečnika — inkrementalni indeks nema način da vidi takvo preimenovanje, dok lenji indeks samo ponovo izgradi stanje i po konstrukciji ostane tačan. Cena te bezbednosti je O(n) izgradnja pri prvom upitu velikog rečnika posle upisa, uz memoriju same heš tabele, približno jedan Integer po mestu pri faktoru popunjenosti od dve trećine — zanemarljivo za nekoliko velikih rečnika u tipičnom dokumentu, a stvaran trošak koji PDFlibPas izbegava kod svakog malog rečnika održavanjem postojećeg praga

Prethodno računanje sRGB game umesto poziva Power za svaki piksel

TPDFSimpleColorManager.XYZ2RGB primenjuje sRGB prenosnu funkciju na svaki dekodirani piksel slike Lab, Indexed ili zasnovane na ICC-u — 1.055 * Power(x, 1/2.4) - 0.055 iznad praga linearnog segmenta — a Power(x, y) za razlomljeno y nema jeftin zatvoren oblik u Pascal RTL-u: razlaže se na Ln(x), pa na Exp(y * Ln(x)), a taj par transcendentnih poziva, izvršen tri puta po pikselu za crveni, zeleni i plavi kanal, predstavlja glavni trošak dekodiranja Lab ili ICC slike piksel po piksel. PDFlibPas tri poziva Power po pikselu zamenjuje jednim traženjem u GSRGBGammaLUT, nizu od 4096 vrednosti tipa Double koji se jednom gradi preko EnsureSRGBGammaLUT, a indeksira zaokruživanjem ograničenog ulaza na najbliže mesto

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 sa 4096 mesta kroz ulazni opseg [0, 1] daje približno šesnaest puta veću rezoluciju od izlaznog kanala od 8 bita, pa je kvantizacija koju LUT uvodi ispod onoga što završni RGB bajt može da predstavi — traženje u tabeli ovde zamenjuje transcendentnu matematiku bez vidljivog gubitka preciznosti. Ista logika se vidi u susednom kodu Lab2XYZ, gde je Power(LMN[i], 3) postao običan izraz LMN[i]*LMN[i]*LMN[i]: celobrojni stepen ionako ne zahteva Ln/Exp, pa ovde nije reč o kompromisu LUT-a, već o uklanjanju suvišnog poziva Power. Trik sa LUT-om isplati se samo zato što je prenosna funkcija čista funkcija jednog Double-a — ne bi se jednostavno proširio na transformaciju boja koja zavisi od više vrednosti piksela ili od većeg broja stanja

Kako brzo rasporediti 73 operatora toka sadržaja

ContentOperatorFromName poziva se jednom za svaki token koji PDFlibPas pročita iz toka sadržaja, poredeći ga sa svih 73 operatora iz Tabele 51 standarda ISO 32000-1 — od w i q do retko viđenih operatora d0 i d1 za metriku glifova Type 3 — a ranije je tu listu linearno prolazio za svaki token, pa je stranica sa nekoliko hiljada operatora značila nekoliko hiljada linearnih prolaza kroz istu tabelu od 73 stavke. PDFlibPas sada pri pokretanju grupiše tabelu prema prvom bajtu operatora u fiksni niz mesta indeksiran tipom AnsiChar, pa se pretraga svodi na jedan indeks niza i prolaz samo kroz nekoliko operatora koji dele isti prvi 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 potpuno su različiti operatori — zato GOpBuckets koristi sirovi bajt kao ključ, a preostalo poređenje unutar grupe je obično poređenje AnsiString vrednosti sa razlikovanjem velikih i malih slova. Niz ima 16 mesta po slovu, što bez problema pokriva današnju tabelu — najpunija grupa, T, sadrži trinaest operatora, jer gotovo svaki operator tekstualnog stanja i pozicioniranja teksta počinje njime — ali EnsureOpBuckets tiho prestaje da dodaje u grupu kada broj dostigne 16, pa bi četrnaesti unos propao bez jasne greške: operator bi postao coUnknown bez izuzetka koji objašnjava razlog. To je cena održavanja pri zameni strukture podataka koja se postepeno pogoršava onom koja to ne čini — raspoređivanje je brže jer nikada ne mora da proširuje niz uz proveru granica, ali čovek mora da prati grupu koja se približava plafonu

Uklanjanje O(n²) iz izgradnje stringova

Pascalov obrazac Result := Result + Fragment pri svakoj iteraciji ponovo alocira i kopira ceo do tada sakupljeni string, pa izgradnja izlaza od N znakova deo po deo košta O(n²) umesto O(n) — lako se previdi pri pregledu, jer svaki red izgleda kao jeftino dodavanje, a u praksi je skupo zato što se PLDirectEscapeLiteralString izvršava za svaki literalni PDF string upisan pri čuvanju, dok se XFDFXMLEscape izvršava za svaku vrednost polja izvezenu u XFDF. PDFlibPas ih popravlja različitim tehnikama, izabranim prema onome što svaka funkcija može unapred da predvidi. PLDirectEscapeLiteralString zna dužinu izlaza pre upisa prvog bajta — jednim prolazom klasifikuje svaki znak kao običan ili escapovan i sabira ukupnu dužinu, SetLength jednom alocira prostor, a drugi prolaz popunjava bafer po indeksu. XFDFXMLEscape ne može jeftino da predvidi dužinu izlaza, jer se Unicode tekst polja previše razlikuje, pa umesto toga dodaje u TStringBuilder unapred podešen približno na dužinu 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('&amp;');
        '<':  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 te dve tehnike zapravo zavisi od onoga što znate pre početka petlje. Brojanje pa popunjavanje je brže kada se veličina izlaza lako izračuna, jer nema ponovnih alokacija ni pomoćnog vođenja osim brojača Integer, ali zahteva da se logika klasifikacije napiše dvaput — jednom za brojanje, jednom za upis — što samo po sebi nosi rizik održavanja ako se kopije raziđu. TStringBuilder odustaje od dela vršnog protoka da bi se logika napisala jednom i dobila amortizovana O(1) dodavanja kroz geometrijsko širenje bafera, pa je bezbedniji podrazumevani izbor kada veličinu izlaza nije lako unapred znati

Gde se ovaj obrazac primenjuje, a gde ne

Sve četiri navedene ispravke primeri su jedne ideje: pronaći poziv koji se izvršava jednom po jedinici ulaza — po ključu rečnika, pikselu, tokenu operatora ili znaku — i zameniti njegov linearan ili nepredvidiv trošak unapred izračunatom tabelom, heš indeksom ili unapred proširenim baferom. Ništa od toga nije posebno za PDF; Delphi servis koji hiljadama puta po zahtevu razrešava isti ključ pretrage, pretvara vrednosti u tesnoj petlji, raspoređuje po fiksnom rečniku tokena ili gradi duge stringove znak po znak nailazi na iste oblike problema i dobija ista rešenja. Nijedna od ove četiri izmene ne dotiče konkurentnost ni memorijski otisak: brže pretraživanje rečnika u jednoj niti ne pomaže dvema nitima koje se nadmeću nad istom instancom TPDFlib, što je strukturni problem obrađen u članku o bezbednosti niti pri paralelnom prikazivanju stranica, niti pomaže PDF-u koji je prevelik da se uopšte učita kao stablo objekata, za šta služi sloj Direct Access opisan u članku o spajanju i deljenju PDF-ova veličine gigabajta

Kod za rečnike, upravljanje bojama, raspoređivanje toka sadržaja i izgradnju stringova opisan ovde isporučuje se kao deo standardne biblioteke PDFlibPas, losLab-ove PDF biblioteke za Delphi i C++Builder, bez dodatnog podešavanja