PDFlibPas teljesítményprofilozás: hash-indexek Delphiben

A PDFlibPas, a losLab Delphihez és C++Builderhez készült PDF-könyvtára, felgyorsítja renderelési és tartalomgenerálási útvonalait négy ismétlődő-munka mintázat amortizált mintázatokra cserélésével: egy lusta hash-indexszel a szótárkulcs-keresésekhez, egy előre kiszámított sRGB gamma-keresőtáblával, első-bájt szerinti csoportosítással a tartalomfolyam-operátor diszpécseléshez, és TStringBuilder-rel ismételt sztring-összefűzés helyett. A négyből egyik sem egy drámai felfedezésből származott — ugyanabból a nem túl fényes mintázatból származtak egy profilban: egy kis függvény, amit dokumentumonként/pixelenként/operátoronként/karakterenként egyszer hívnak, ahol egy lineáris költség a hívás belsejében kvadratikussá vagy majdnem kvadratikussá válik egy teljes dokumentumon át. Ez a közös szál itt: négy kicsi, egymással kapcsolatban nem álló javítás, amely ugyanazt a probléma-alakot támadja, plusz mindegyik őszinte korlátai

Hol tölti egy tartalomfolyam-renderelő ténylegesen az idejét

A PDFlibPas tartalomfolyam-renderelője szinte minden tokenenkénti költségét négy szűk ponton keresztül tölcsérezi: erőforrás-szótár keresések a /Resources, /ColorSpace, /Font, és /ExtGState-en; gamma-korrekció minden dekódolt pixelen egy Lab-, Indexed-, vagy ICC-jelölt képen; operátornév-illesztés minden token minden tartalomfolyamában; és sztringépítés, bárhol a könyvtár kimenetet épít — literál sztring-menekítés mentéskor, XFDF-export, bélyegző- és változó-token bővítés. A négy mindegyike kis mennyiségű munkát végez önmagában, és mindegyik ezerszer vagy milliószor fut egy realisztikus dokumentumon, ami pontosan az a fajta függvényalak, ahol egy O(n) vagy O(n²) megvalósítási részlet megszűnik láthatatlan lenni, és a profil legfelső bejegyzésévé válik

Miért lassulnak le az erőforrás-szótár keresések egy nagy PDF-ben?

A TPDFDictionary.FindIndexByKeyName az, amit a renderelő meghív minden /Resources, /ColorSpace, /Font, és /ExtGState kereséshez, és korábban elölről bejárta az Entries tömböt minden híváskor — jó egy háromelemes Resources szótárnál, drága egy Form XObjectnél vagy egy ExtGState-nehéz oldalnál, ahol ugyanazt a szótárt vizsgálják minden operátornál, amely a színt vagy grafikai állapotot érinti. A PDFlibPas most egy lusta hash-indexet épít, amint egy szótár átlép egy DICT_HASH_THRESHOLD (16) bejegyzést, és a kisebb szótárakat lineáris vizsgálaton hagyja, mivel a legtöbb PDF-szótár soha nem lesz ilyen nagy, és egy hash-tábla három kulcshoz többe kerülne felépíteni, mint amennyit megspórolna. Az index egy lapos, nyílt címzésű tábla, a PLAnsiStringHash-szel kulcsolva, egy FNV-1a hash-sel, a kanonikus 2166136261 eltolási bázissal és 16777619 prímszámmal, azért választva, hogy elkerülje a System.Generics.Collections behúzását valami ennyire méret-érzékenyhez

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;

Az index inkább érvénytelenítésre kerül, mint inkrementálisan karbantartva: minden mutáló hívás — AddEntry, DeleteEntryByKeyName, Assign, AddDict — törli a hash-t, és hagyja, hogy a következő keresés nulláról építse újra. Ez pazarlónak tűnik, amíg észre nem veszed, hogy egy szótárkulcs egy TPDFName objektum, és a TPDFName.SetTo át tud nevezni egy már egy szótár Entries tömbjében ülő kulcsot anélkül, hogy a szótár saját metódusain keresztül menne — egy inkrementális indexnek nincs módja megfigyelni azt az átnevezést, míg egy lusta egyszerűen újraépül, és felépítésénél fogva helyes marad. Ennek a biztonságnak az ára egy O(n) újraépítés az első alkalommal, amikor egy nagy szótárt lekérdeznek egy írás után, plusz a hash-tábla saját memóriája, nagyjából egy Integer résenként kétharmados terhelési tényezőnél — kerekítési hiba egy tipikus dokumentum néhány túlméretezett szótáránál, és egy valós költség, amit a PDFlibPas elkerül minden kicsinél, azáltal hogy a küszöböt ott tartja, ahol van

sRGB gamma előre kiszámítása Power hívása helyett pixelenként

A TPDFSimpleColorManager.XYZ2RGB alkalmazza az sRGB átviteli függvényt minden dekódolt pixelen egy Lab-, Indexed-, vagy ICC-alapú képen — 1.055 * Power(x, 1/2.4) - 0.055 a lineáris-szegmens küszöb fölött —, és a Power(x, y) egy törtrészű y-hoz nem rendelkezik olcsó zárt alakkal a Pascal RTL-ben: Ln(x)-re bontja, majd Exp(y * Ln(x))-ra, és ez a transzcendens hívás-pár, pixelenként háromszor futtatva a vörös, zöld, és kék csatornákhoz, egy Lab- vagy ICC-kép pixelenkénti dekódolásának domináns költsége. A PDFlibPas felváltja a három pixelenkénti Power hívást egy kereséssel a GSRGBGammaLUT-ba, egy 4096-bejegyzéses Double tömbbe, amelyet egyszer épít fel az EnsureSRGBGammaLUT, indexelve a levágott bemenet legközelebbi helyre kerekítésével

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;

Egy 4096-résű tábla a [0, 1] bemeneti tartomány fölött nagyjából tizenhatszor akkora felbontást ad, mint egy 8 bites kimeneti csatorna, így a kvantálás, amit a LUT bevezet, az alá esik, amit a végső RGB-bájt ábrázolni tud — a táblakeresés helyettesíti a transzcendens matematikát itt látható precíziós költség nélkül. Ugyanez az érvelés mellette bukkan fel a Lab2XYZ-ben, ahol a Power(LMN[i], 3) egyszerű LMN[i]*LMN[i]*LMN[i]-vé vált: egy egész kitevős hatványnak eleve nincs szüksége Ln/Exp-re, így az egyáltalán nem egy LUT-kompromisszum, csak egy redundáns Power-hívás eltávolítása. A LUT-trükk csak azért térül meg, mert az átviteli függvény egyetlen Double tiszta függvénye — nem terjedne ki tisztán egy olyan színtranszformációra, amely több pixelértéktől vagy annál több állapottól függene

Hogyan diszpécseld gyorsan a 73 tartalomfolyam-operátort?

A ContentOperatorFromName-et egyszer hívják meg minden tokenre, amit a PDFlibPas kiolvas egy tartalomfolyamból, illesztve azt az ISO 32000-1 51. táblázatának teljes 73 operátoros halmazához — a w-től és q-tól a ritkán látott d0 és d1 Type 3 glyph-metrika operátorokig —, és korábban lineárisan bejárta azt a listát minden egyes tokennél, így egy néhány ezer operátoros oldal néhány ezer lineáris vizsgálatot jelentett ugyanazon a 73-elemes táblán. A PDFlibPas most a táblát az operátor első bájtja szerint csoportosítja indításkor, egy fix, AnsiChar-indexelt résekből álló tömbbe, így egy keresés egy tömbindexszé válik, plusz egy vizsgálat csak azon néhány operátoron át, amely osztozik azon az első karakteren

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;

A PDF-operátorok kis- és nagybetűérzékenyek — a w és W, az f és F, az sc és SC mind különböző operátorok —, így a GOpBuckets a nyers bájtot kulcsolja, és a maradék összehasonlítás egy résen belül egy egyszerű, kis- és nagybetűérzékeny AnsiString egyenlőség. A tömb betűnként 16 résre méretezett, ami kényelmesen lefedi a mai táblát — a legforgalmasabb rés, a T, tizenhárom operátort tart, mivel szinte minden szöveg-állapot és szöveg-pozicionáló operátor azzal kezdődik —, de az EnsureOpBuckets csendben megáll egy résbe való hozzáadásnál, amint annak száma elér 16-ot, így egy rés, amelynek valaha egy tizennegyedik bejegyzésre lenne szüksége, csendben, nem hangosan bukna el: az operátor coUnknown-ra oldódna fel, kivétel nélkül, amely rámutatna, miért. Ez a karbantartási költsége annak, hogy egy kecsesen degradáló adatstruktúrát egy olyanra cseréljünk, amely nem: gyorsabban diszpécsel, mert soha nincs szüksége határellenőrzött növekedésre, és igényel egy embert, aki figyeli azt az egy rést, amely közel van a plafonjához

Az O(n²) kivágása a sztringépítésből

A Pascal Result := Result + Fragment mintája újraallokálja és lemásolja a teljes felhalmozott sztringet minden iterációnál, így egy N-karakteres kimenet felépítése egyszerre egy töredékkel O(n²)-be kerül O(n) helyett — könnyű elmulasztani áttekintéskor, mivel minden sor egy olcsó hozzáfűzésnek néz ki, és drága a gyakorlatban, mert a PLDirectEscapeLiteralString minden literál PDF-sztringen fut, ami mentéskor íródik, és az XFDFXMLEscape minden mezőértéken fut, ami XFDF-be exportálódik. A PDFlibPas két különböző technikával javítja a kettőt, azt választva, amit mindegyik függvény előre meg tud jósolni. A PLDirectEscapeLiteralString egyetlen bájt megírása előtt tudja kimeneti hosszát — egy átfutás minden karaktert egyszerűnek vagy menekítettnek osztályoz, és összegzi az összeget, a SetLength egyszer allokál, és egy második átfutás tölti ki a puffert indexenként. Az XFDFXMLEscape nem tudja olcsón megjósolni kimeneti hosszát, mivel a Unicode mezőszöveg túl sokat változik előszámításhoz, így ehelyett egy TStringBuilder-be fűz hozzá, amely nagyjából a bemeneti hosszra van előméretezve

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;

A két megközelítés közötti választás valójában arról szól, mit tudsz a ciklus indulása előtt. A számold-majd-töltsd a gyorsabb kettő közül, amikor a kimeneti méret olcsón kiszámítható, mivel nulla újraallokálást végez, és nincs könyvelés egy Integer számlálón túl, de azt jelenti, hogy az osztályozási logikát kétszer kell megírni — egyszer a számoláshoz, egyszer a kibocsátáshoz —, ami saját karbantartási kockázat, ha a két másolat szétdriftel. A TStringBuilder feladja e csúcsteljesítmény egy kis részét azért, hogy egyszer írja meg a logikát, és amortizált O(1) hozzáfűzéseket kapjon a geometriai puffer-növekedésből, ami a biztonságosabb alapértelmezés, amikor a kimeneti méret nem könnyen ismerhető előre

Hol alkalmazható ez a minta, és hol nem

A fenti mind a négy javítás egyetlen ötlet példánya: találd meg a hívást, amely egyszer fut bemeneti egységenként — szótárkulcsonként, pixelenként, operátor-tokenenként, karakterenként —, és cseréld le lineáris vagy kiszámíthatatlan költségét egy előre kiszámított táblára, egy hash-indexre, vagy egy előméretezett pufferre. Ebből semmi nem PDF-specifikus; egy Delphi szolgáltatás, amely ugyanazt a keresési kulcsot ezerszer oldja fel kérésenként, értékeket konvertál egy szoros ciklusban, egy fix tokenszókészletre diszpécsel, vagy hosszú sztringeket épít karakterenként, ugyanazokba a hibaalakokba ütközik, és ugyanazokat a javításokat veszi. Amit ez a négy változtatás egyike sem érint, az a konkurencia vagy a memórialenyomat: egy gyorsabb egyszálas szótárkeresés semmit nem tesz két szálért, amely ugyanazon TPDFlib-példányon versenyez, ami egy strukturális probléma, amelyet külön tárgyal a párhuzamos oldalrenderelés szálbiztonságáról szóló cikk, és semmit nem tesz egy PDF-hez, amely túl nagy ahhoz, hogy egyáltalán objektumfaként betöltsük memóriába, ami az, amire a PDFlibPas Direct Access rétege való, amit a gigabájtos PDF-ek egyesítéséről és felosztásáról szóló cikk tárgyal

Az itt tárgyalt szótár-, színkezelési, tartalomfolyam-diszpécselési, és sztringépítési kód a Delphihez és C++Builderhez készült szabványos PDFlibPas, a losLab PDF-könyvtárának részeként érkezik, semmilyen extra konfiguráció nélkül, hogy bármelyiket megkapjuk