PDFlibPas:n suorituskykyprofilointi: hakemistot Delphissä

PDFlibPas, losLabin PDF-kirjasto Delphille ja C++Builderille, nopeuttaa renderöinti- ja sisällöntuotantopolkujaan korvaamalla neljä toistuvan työn mallia amortisoiduilla vastineilla: laiskan hakemiston sanakirja-avainhauille, esilasketun sRGB-gamma-hakutaulun, ensimmäisen tavun mukaan lohkoituksen sisältövirran operaattorijakelulle, ja TStringBuilderin toistuvan merkkijonoliitoksen sijaan. Yksikään näistä neljästä ei tullut yhdestä dramaattisesta löydöksestä — ne tulivat samasta ei-hohdokkaasta mallista profiilissa: pieni funktio, jota kutsutaan kerran per operaattori, kerran per pikseli tai kerran per merkki, jossa lineaarinen kustannus kutsun sisällä muuttuu neliölliseksi tai lähes neliölliseksi koko asiakirjan yli. Se on tämän artikkelin punainen lanka: neljä pientä, toisiinsa liittymätöntä korjausta, jotka hyökkäävät samaa ongelmamuotoa vastaan, plus jokaisen rehelliset rajat

Mihin sisältövirran renderöijä todella käyttää aikansa

PDFlibPas:n sisältövirran renderöijä ohjaa lähes kaiken tokenikohtaisen kustannuksensa neljän kapean pisteen kautta: resurssisanakirjahaut kentille /Resources, /ColorSpace, /Font ja /ExtGState; gammakorjaus jokaiselle puretulle pikselille Lab-, Indexed- tai ICC-tunnisteisessa kuvassa; operaattorinimen täsmäytys jokaiselle tokenille jokaisessa sisältövirrassa; ja merkkijonon rakentaminen missä tahansa, missä kirjasto rakentaa tulostetta — kirjaimellisen merkkijonon paettu tallennuksessa, XFDF-vienti, leima- ja muuttujatokenin laajennus. Jokainen näistä neljästä tekee pienen määrän työtä itsessään, ja jokainen niistä ajetaan tuhansia tai miljoonia kertoja realistisen asiakirjan yli, mikä on juuri se funktiomuoto, jossa O(n)- tai O(n²)-toteutusyksityiskohta lakkaa olemasta näkymätön ja alkaa olla profiilin ylin merkintä

Miksi resurssisanakirjahaut hidastuvat suuressa PDF:ssä?

TPDFDictionary.FindIndexByKeyName on se, mitä renderöijä kutsuu ratkaistakseen jokaisen /Resources-, /ColorSpace-, /Font- ja /ExtGState-haun, ja se käveli aiemmin Entries-taulukon edestä joka kutsulla — hyvä kolmen merkinnän Resources-sanakirjalle, kallis Form XObjectille tai ExtGState-painotteiselle sivulle, jossa samaa sanakirjaa tutkitaan jokaisella operaattorilla, joka koskettaa väriä tai graafista tilaa. PDFlibPas rakentaa nyt laiskan hakemiston heti, kun sanakirja ylittää DICT_HASH_THRESHOLD-arvon (16) merkinnän, ja jättää pienemmät sanakirjat lineaariseen skannaukseen, koska useimmat PDF-sanakirjat eivät koskaan kasva niin suuriksi, ja kolmen avaimen hakemisto maksaisi enemmän rakentaa kuin se säästää. Hakemisto on tasainen avoimen osoituksen taulu, avaimena PLAnsiStringHash, FNV-1a-tiiviste kanonisella siirtymäpohjalla 2166136261 ja alkuluvulla 16777619, valittu välttääkseen System.Generics.Collections-tuonnin jollekin näin kokoherkälle

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;

Hakemisto mitätöidään sen sijaan, että sitä ylläpidettäisiin inkrementaalisesti: jokainen muuttava kutsu — AddEntry, DeleteEntryByKeyName, Assign, AddDict — tyhjentää tiivisteen ja antaa seuraavan haun rakentaa sen uudelleen alusta. Tämä näyttää tuhlaukselta, kunnes huomaat, että sanakirja-avain on TPDFName-olio, ja TPDFName.SetTo voi nimetä uudelleen avaimen, joka jo istuu sanakirjan Entries-taulukossa, kulkematta minkään sanakirjan omista metodeista — inkrementaalisella hakemistolla ei ole tapaa havaita tuota uudelleennimeämistä, kun taas laiska yksinkertaisesti rakentuu uudelleen ja pysyy oikeana rakenteensa ansiosta. Tuon turvallisuuden hinta on O(n)-uudelleenrakennus ensimmäistä kertaa, kun suurta sanakirjaa kysytään kirjoituksen jälkeen, plus itse hakemistotaulukon muisti, karkeasti yksi Integer per paikka kahden kolmasosan täyttöasteella — pyöristysvirhe kourallliselle ylikokoisia sanakirjoja tyypillisessä asiakirjassa, ja todellinen kustannus, jonka PDFlibPas välttää maksamasta jokaisella pienellä, pitämällä kynnyksen siellä missä se on

sRGB-gamman esilaskeminen Power-kutsun sijaan per pikseli

TPDFSimpleColorManager.XYZ2RGB soveltaa sRGB-siirtofunktiota jokaiseen puretun Lab-, Indexed- tai ICC-pohjaisen kuvan pikseliin — 1.055 * Power(x, 1/2.4) - 0.055 lineaarisegmentin kynnyksen yläpuolella — ja Power(x, y):llä murtoluvulliselle y:lle ei ole halpaa suljettua muotoa Pascal-RTL:ssä: se hajoaa Ln(x):ksi ja sitten Exp(y * Ln(x)):ksi, ja tuo pari transkendenttisia kutsuja, ajettuna kolme kertaa per pikseli punaiselle, vihreälle ja siniselle kanavalle, on Lab- tai ICC-kuvan pikselikohtaisen purun hallitseva kustannus. PDFlibPas korvaa kolme pikselikohtaista Power-kutsua yhdellä haulla GSRGBGammaLUT-taulukkoon, 4096 merkinnän Double-taulukkoon, joka rakennetaan kerran EnsureSRGBGammaLUT-funktion kautta ja indeksoidaan pyöristämällä rajattu syöte lähimpään paikkaan

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;

4096 paikan taulukko [0, 1]-syötealueen yli antaa karkeasti kuusitoista kertaa 8-bittisen tulostekanavan resoluution, joten kvantisointi, jonka hakutaulu tuo, istuu lopullisen RGB-tavun esitettävissä olevan tarkkuuden alapuolella — taulukkohaku korvaa transkendenttisen matematiikan täällä ilman näkyvää tarkkuuskustannusta. Sama päättely näkyy sen vieressä funktiossa Lab2XYZ, jossa Power(LMN[i], 3) muuttui tavalliseksi LMN[i]*LMN[i]*LMN[i]:ksi: kokonaislukupotenssi ei tarvitse Ln/Exp-pareja ylipäätään, joten se ei ole lainkaan hakutaulukompromissi, vain redundantti Power-kutsu poistettu. Hakutaulutemppu kannattaa vain, koska siirtofunktio on puhdas funktio yhdestä Double-arvosta — se ei laajenisi puhtaasti värimuunnokseen, joka riippuisi useista pikseliarvoista tai enemmästä tilasta kuin tuo

Miten jaat 73 sisältövirran operaattoria nopeasti?

ContentOperatorFromName kutsutaan kerran jokaiselle tokenille, jonka PDFlibPas lukee sisältövirrasta, täsmäyttäen sitä ISO 32000-1 taulukon 51 täyttä 73 operaattorin joukkoa vasten — w:stä ja q:sta harvoin nähtyihin d0- ja d1-Type 3-glyfimittaoperaattoreihin asti — ja se käveli aiemmin tuon listan lineaarisesti jokaisella yksittäisellä tokenilla, joten sivu, jolla oli muutama tuhat operaattoria, tarkoitti muutamaa tuhatta lineaarista skannausta saman 73 merkinnän taulukon yli. PDFlibPas lohkoo nyt taulukon operaattorin ensimmäisen tavun mukaan käynnistyksessä, kiinteään AnsiChar-indeksoituun paikkataulukkoon, joten haku muuttuu yhdeksi taulukkoindeksiksi plus skannaukseksi vain kourallisen operaattoreita, jotka jakavat tuon ensimmäisen merkin

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-operaattorit ovat kirjainkoosta riippuvaisia — w ja W, f ja F, sc ja SC ovat kaikki eri operaattoreita — joten GOpBuckets avaimena on raaka tavu, ja jäljelle jäävä vertailu lohkon sisällä on tavallinen, kirjainkokoherkkä AnsiString-yhtäläisyys. Taulukko on mitoitettu 16 paikkaan per kirjain, mikä kattaa mukavasti tämän päivän taulukon — kiireisin lohko, T, kantaa kolmetoista operaattoria, koska lähes jokainen tekstitila- ja tekstinsijoitusoperaattori alkaa sillä — mutta EnsureOpBuckets lakkaa hiljaa lisäämästä lohkoon heti, kun sen määrä saavuttaa 16:n, joten lohko, joka koskaan tarvitsisi neljännentoista merkinnän, epäonnistuisi hiljaa eikä äänekkäästi: operaattori ratkeaisi coUnknown:ksi ilman poikkeusta osoittamassa miksi. Se on ylläpitokustannus siitä, että vaihdat sulavasti heikkenevän tietorakenteen sellaiseen, joka ei heikkene — se jakelee nopeammin, koska se ei koskaan tarvitse rajatarkistettua kasvua, ja se tarvitsee ihmisen tarkkailemassa sitä yhtä lohkoa, joka on lähellä kattoaan

O(n²):n leikkaaminen pois merkkijonon rakentamisesta

Pascalin Result := Result + Fragment -malli varaa uudelleen ja kopioi koko kertyneen merkkijonon jokaisella iteraatiolla, joten N-merkkisen tulosteen rakentaminen yksi fragmentti kerrallaan maksaa O(n²) O(n):n sijaan — helppo ohittaa katselmuksessa, koska jokainen rivi näyttää yhdeltä halvalta lisäykseltä, ja kallis käytännössä, koska PLDirectEscapeLiteralString ajetaan jokaisella tallennuksen aikana kirjoitetulla kirjaimellisella PDF-merkkijonolla ja XFDFXMLEscape ajetaan jokaisella XFDF:ään viedyllä kenttäarvolla. PDFlibPas korjaa nämä kaksi eri tekniikoilla, valittuina sen mukaan, mitä kukin funktio voi ennustaa etukäteen. PLDirectEscapeLiteralString tietää tulostepituutensa ennen kuin se kirjoittaa yhtäkään tavua — yksi kierros luokittelee jokaisen merkin tavalliseksi tai paetuksi ja summaa kokonaismäärän, SetLength varaa kerran, ja toinen kierros täyttää puskurin indeksin mukaan. XFDFXMLEscape ei voi halvalla ennustaa tulostepituuttaan, koska Unicode-kenttäteksti vaihtelee liikaa etukäteen laskettavaksi, joten se liittää sen sijaan TStringBuilder-olioon, esimitoitettuna karkeasti syötteen pituuteen

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;

Valinta näiden kahden välillä koskee todella sitä, mitä tiedät ennen silmukan alkamista. Laske-sitten-täytä on nopeampi näistä kahdesta, kun tulostekoko on halpa laskea, koska se ei tee lainkaan uudelleenvarauksia eikä kirjanpitoa Integer-laskurin lisäksi, mutta se tarkoittaa luokittelulogiikan kirjoittamista kahdesti — kerran laskemista varten, kerran tuottamista varten — mikä on oma ylläpitoriskinsä, jos nuo kaksi kopiota ajautuvat erilleen. TStringBuilder luopuu pienestä osasta tuota huippulävistyskykyä kirjoittamalla logiikan kerran ja saamalla amortisoidut O(1)-lisäykset geometrisesta puskurin kasvusta, mikä on turvallisempi oletus aina, kun tulostekokoa ei ole helppo tietää etukäteen

Mihin tämä malli soveltuu, ja mihin ei

Kaikki neljä yllä olevaa korjausta ovat esimerkkejä yhdestä ideasta: löydä kutsu, joka ajetaan kerran per syötteen yksikkö — per sanakirja-avain, per pikseli, per operaattoritoken, per merkki — ja korvaa sen lineaarinen tai ennustamaton kustannus esilasketulla taulukolla, hakemistolla tai esimitoitetulla puskurilla. Mikään tästä ei ole PDF-spesifistä; Delphi-palvelu, joka ratkaisee saman hakuavaimen tuhansia kertoja per pyyntö, muuntaa arvoja tiukassa silmukassa, jakelee kiinteän tokenisanaston perusteella tai rakentaa pitkiä merkkijonoja merkki kerrallaan, osuu samoihin vikamalleihin ja ottaa samat korjaukset. Mihinkään näistä neljästä muutoksesta ei kosketa samanaikaisuutta tai muistijalanjälkeä: nopeampi yksisäikeinen sanakirjahaku ei tee mitään kahdelle säikeelle, jotka kilpailevat samasta TPDFlib-instanssista, mikä on rakenteellinen ongelma, joka käsitellään erikseen artikkelissa säikeidenturvallisuus rinnakkaisessa sivunrenderöinnissä, eikä se tee mitään PDF:lle, joka on liian suuri ladattavaksi muistiin olio-puuna ylipäätään, mikä on se, mitä varten Direct Access -kerros PDFlibPas:ssa on, käsitelty artikkelissa gigatavuisten PDF-tiedostojen yhdistäminen ja jakaminen

Tässä käsitelty sanakirja-, värienhallinta-, sisältövirran jakelu- ja merkkijononrakennuskoodi toimitetaan osana vakiomuotoista PDFlibPas:aa, losLabin PDF-kirjastoa Delphille ja C++Builderille, ilman että mikään näistä vaatii lisämääritystä