PDFlibPas-ytelsesprofilering: hash-indekser i Delphi

PDFlibPas, losLabs PDF-bibliotek for Delphi og C++Builder, gjør sine gjengivelses- og innholdsgenererings-veier raskere ved å erstatte fire gjentatt-arbeid-mønstre med amortiserte en: en lat hash-indeks for ordbok-nøkkel-oppslag, en forhåndsberegnet sRGB-gamma-oppslagstabell, første-byte-bøtting for innholdsstrøm-operator-dispatch, og TStringBuilder i stedet for gjentatt strengkonkatenering. Ingen av de fire kom fra én dramatisk oppdagelse — de kom fra det samme lite glamorøse mønsteret i en profil: en liten funksjon kalt én gang per operator, én gang per piksel, eller én gang per tegn, der en lineær kostnad inne i kallet blir kvadratisk eller nær-kvadratisk over et helt dokument. Det er den røde tråden her: fire små, urelaterte-utseende fikser som angriper den samme formen problem, pluss de ærlige grensene til hver av dem

Hvor en innholdsstrøm-fremviser faktisk bruker tiden sin

PDFlibPas' innholdsstrøm-fremviser kanaliserer nesten hele per-token-kostnaden sin gjennom fire snevre punkter: ressursordbok-oppslag på /Resources, /ColorSpace, /Font, og /ExtGState; gammakorreksjon på hver dekodede piksel av et Lab-, Indexed-, eller ICC-merket bilde; operatornavn-matching på hvert token av hver innholdsstrøm; og strengkonstruksjon hvor enn biblioteket bygger utdata — bokstavelig-streng-escaping ved lagring, XFDF-eksport, stempel- og variabel-token-utvidelse. Hver av de fire gjør en liten mengde arbeid på egen hånd, og hver kjører tusener eller millioner av ganger over et realistisk dokument, noe som er nøyaktig den formen av funksjon der en O(n)- eller O(n²)-implementasjonsdetalj slutter å være usynlig og begynner å bli profilens toppoppføring

Hvorfor blir ressursordbok-oppslag trege i en stor PDF?

TPDFDictionary.FindIndexByKeyName er hva fremviseren kaller for å løse hvert /Resources-, /ColorSpace-, /Font-, og /ExtGState-oppslag, og den pleide å gå gjennom Entries-arrayet fra fronten ved hvert kall — greit for en tre-oppførings-Resources-ordbok, kostbart for en Form XObject eller en ExtGState-tung side der den samme ordboken proberes ved hver operator som rører farge eller grafikktilstand. PDFlibPas bygger nå en lat hash-indeks når en ordbok passerer DICT_HASH_THRESHOLD (16) oppføringer, og lar mindre ordbøker forbli på lineær skanning, ettersom de fleste PDF-ordbøker aldri blir så store, og en hash-tabell for tre nøkler ville koste mer å bygge enn den sparer. Indeksen er en flat åpen-adressering-tabell nøkkelsatt av PLAnsiStringHash, en FNV-1a-hash med den kanoniske offset-basisen 2166136261 og primtallet 16777619, valgt for å unngå å trekke inn System.Generics.Collections for noe så størrelsessensitivt

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;

Indeksen ugyldiggjøres i stedet for å vedlikeholdes inkrementelt: hvert muterende kall — AddEntry, DeleteEntryByKeyName, Assign, AddDict — tømmer hashen og lar neste oppslag gjenoppbygge den fra bunnen av. Det ser sløsende ut inntil man legger merke til at en ordboknøkkel er et TPDFName-objekt, og TPDFName.SetTo kan omdøpe en nøkkel som allerede sitter i en ordboks Entries-array uten å gå gjennom noen av ordbokens egne metoder — en inkrementell indeks har ingen måte å observere den omdøpingen på, mens en lat en bare gjenoppbygger og forblir korrekt ved konstruksjon. Prisen for den sikkerheten er en O(n)-gjenoppbygging første gang en stor ordbok spørres etter en skriving, pluss minnet for selve hash-tabellen, omtrent én Integer per slot ved en to-tredjedels belastningsfaktor — en avrundingsfeil for håndfullen overdimensjonerte ordbøker i et typisk dokument, og en reell kostnad PDFlibPas unngår å betale på hver liten en ved å holde grensen der den er

Å forhåndsberegne sRGB-gamma i stedet for å kalle Power per piksel

TPDFSimpleColorManager.XYZ2RGB anvender sRGB-overføringsfunksjonen på hver dekodede piksel av et Lab-, Indexed-, eller ICC-basert bilde — 1.055 * Power(x, 1/2.4) - 0.055 over det lineære-segment-terskelen — og Power(x, y) for en brøkdel-y har ingen billig lukket form på Pascal-RTL-en: den dekomponeres til Ln(x) og deretter Exp(y * Ln(x)), og det paret av transcendentale kall, kjørt tre ganger per piksel for de røde, grønne, og blå kanalene, er den dominerende kostnaden ved å dekode et Lab- eller ICC-bilde piksel for piksel. PDFlibPas erstatter de tre per-piksel-Power-kallene med ett oppslag i GSRGBGammaLUT, et 4096-oppførings Double-array bygget én gang via EnsureSRGBGammaLUT og indeksert ved å runde av det klemte input-et til nærmeste slot

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;

En 4096-slot-tabell over [0, 1]-inndataområdet gir omtrent seksten ganger oppløsningen til en 8-bit utdatakanal, så kvantiseringen LUT-en introduserer, sitter under hva den endelige RGB-byten kan representere — tabelloppslag erstatter transcendental matematikk her uten en synlig presisjonskostnad. Det samme resonnementet dukker opp ved siden av det i Lab2XYZ, der Power(LMN[i], 3) ble en ren LMN[i]*LMN[i]*LMN[i]: en heltallspotens trenger ikke Ln/Exp i utgangspunktet, så den er ikke en LUT-avveining i det hele tatt, bare et redundant Power-kall fjernet. LUT-trikset lønner seg bare fordi overføringsfunksjonen er en ren funksjon av én enkelt Double — det ville ikke utvide seg rent til en fargetransformasjon som var avhengig av flere pikselverdier eller mer tilstand enn det

Hvordan dispatcher man 73 innholdsstrøm-operatorer raskt?

ContentOperatorFromName kalles én gang for hvert token PDFlibPas leser ut av en innholdsstrøm, og matcher det mot ISO 32000-1 Tabell 51s fulle sett med 73 operatorer — fra w og q opp til de sjeldent-sette d0- og d1-Type-3-glyf-metrikk-operatorene — og den pleide å gå gjennom den listen lineært ved hvert eneste token, så en side med noen tusen operatorer betydde noen tusen lineære skanninger over den samme 73-oppførings-tabellen. PDFlibPas bøtter nå tabellen etter operatorens første byte ved oppstart, inn i et fast AnsiChar-indeksert array av sloter, så et oppslag blir én array-indeks pluss en skanning av bare håndfullen operatorer som deler det første tegnet

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-operatorer skiller mellom store og små bokstaver — w og W, f og F, sc og SC er alle forskjellige operatorer — så GOpBuckets nøkkelsettes på den rå byten, og resten-sammenligningen inne i en bøtte er en ren, store/små-bokstav-sensitiv AnsiString-likhet. Arrayet er dimensjonert til 16 sloter per bokstav, noe som komfortabelt dekker dagens tabell — den travleste bøtten, T, holder tretten operatorer, ettersom nesten hver tekst-tilstand- og tekst-posisjonerings-operator starter med den — men EnsureOpBuckets slutter stille å legge til en bøtte når telleren når 16, så en bøtte som noensinne trengte en fjortende oppføring, ville feile stille i stedet for høylytt: operatoren ville løses til coUnknown uten noe unntak som peker på hvorfor. Det er vedlikeholdskostnaden ved å bytte en datastruktur som degraderer elegant mot en som ikke gjør det — den dispatcher raskere fordi den aldri trenger en grense-sjekket vekst, og den trenger et menneske som følger med på den ene bøtten nær taket sitt

Å kutte O(n²) ut av strengbygging

Pascals Result := Result + Fragment-mønster reallokerer og kopierer hele den akkumulerte strengen ved hver iterasjon, så å bygge en N-tegns utdata ett fragment om gangen koster O(n²) i stedet for O(n) — lett å overse i kodegjennomgang, ettersom hver linje ser ut som ett billig tillegg, og kostbart i praksis fordi PLDirectEscapeLiteralString kjører på hver bokstavelig PDF-streng skrevet under lagring, og XFDFXMLEscape kjører på hver feltverdi eksportert til XFDF. PDFlibPas fikser de to med forskjellige teknikker, valgt etter hva hver funksjon kan forutsi på forhånd. PLDirectEscapeLiteralString vet utdatalengden sin før den skriver en eneste byte — én passering klassifiserer hvert tegn som vanlig eller escaped og summerer totalen, SetLength allokerer én gang, og en andre passering fyller bufferen etter indeks. XFDFXMLEscape kan ikke billig forutsi utdatalengden sin, ettersom Unicode-felttekst varierer for mye til å forhåndsberegne, så den legger i stedet til inn i en TStringBuilder forhåndsdimensjonert til omtrent inndatalengden

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;

Valget mellom de to handler egentlig om hva man vet før løkken starter. Tell-så-fyll er den raskeste av de to når utdatastørrelsen er billig å beregne, ettersom den gjør null reallokeringer og ingen regnskapsføring utover en Integer-teller, men det betyr å skrive klassifiseringslogikken to ganger — én gang for å telle, én gang for å utstede — noe som er sin egen vedlikeholdsrisiko hvis de to kopiene driver fra hverandre. TStringBuilder gir opp litt av den topp-gjennomstrømningen for å skrive logikken én gang og få amortiserte O(1)-tillegg fra geometrisk buffervekst, noe som er det tryggere standardvalget når utdatastørrelsen ikke er lett å vite på forhånd

Hvor dette mønsteret gjelder, og hvor det ikke gjør det

Alle fire fiksene ovenfor er instanser av én idé: finn kallet som kjører én gang per enhet inndata — per ordboknøkkel, per piksel, per operator-token, per tegn — og erstatt dets lineære eller uforutsigbare kostnad med en forhåndsberegnet tabell, en hash-indeks, eller en forhåndsdimensjonert buffer. Ingenting av det er spesifikt for PDF; en Delphi-tjeneste som løser den samme oppslagsnøkkelen tusenvis av ganger per forespørsel, konverterer verdier i en tett løkke, dispatcher på et fast vokabular av tokens, eller bygger lange strenger ett tegn om gangen, treffer de samme feilformene og tar de samme fiksene. Hva ingen av disse fire endringene rører, er samtidighet eller minne-fotavtrykk: et raskere enkelttrådet ordbok-oppslag gjør ingenting for to tråder som kappløper på den samme TPDFlib-instansen, noe som er et strukturelt problem dekket separat i artikkelen om trådsikkerhet i parallell sidegjengivelse, og det gjør ingenting for en PDF for stor til å laste inn i minnet som et objekttre i det hele tatt, noe som er hva Direct-Access-laget i PDFlibPas er til for, dekket i artikkelen om å slå sammen og dele gigabyte-PDF-er

Ordbok-, fargehåndterings-, innholdsstrøm-dispatch-, og strengbyggings-koden diskutert her, følger med som en del av standard PDFlibPas, losLabs PDF-bibliotek for Delphi og C++Builder, uten at noen ekstra konfigurasjon trengs for å få noe av det