PDFlibPas-ydeevneprofilering: hash-indekser i Delphi

PDFlibPas, losLabs PDF-bibliotek til Delphi og C++Builder, fremskynder sine gengivelses- og indholds-genererings-veje ved at erstatte fire gentaget-arbejde-mønstre med amortiserede: et dovent hash-indeks til ordbogs-nøgle-opslag, en forudberegnet sRGB-gamma-opslagstabel, første-byte-bucketing til content-stream-operator-dispatch, og TStringBuilder i stedet for gentagen strengsammenkædning. Ingen af de fire kom fra én dramatisk opdagelse — de kom fra det samme uglamourøse mønster i en profil: en lille funktion kaldt én gang pr. ordbogs-nøgle, én gang pr. pixel, eller én gang pr. tegn, hvor en lineær omkostning inde i kaldet bliver kvadratisk eller nær-kvadratisk på tværs af et helt dokument. Det er den røde tråd her: fire små, urelateret-udseende fixes der angriber den samme problemform, plus de ærlige grænser for hver

Hvor en content-stream-renderer rent faktisk bruger sin tid

PDFlibPas' content-stream-renderer render næsten hele sin per-token-omkostning gennem fire snævre punkter: ressource-ordbogs-opslag på /Resources, /ColorSpace, /Font og /ExtGState; gamma-korrektion på hver dekodet pixel af et Lab-, Indexed- eller ICC-mærket billede; operator-navn-matching på hvert token i hver content-stream; og strengkonstruktion, hvor end biblioteket bygger output — bogstavelig-streng-escaping ved gemning, XFDF-eksport, stempel- og variabel-token-udvidelse. Hver af de fire udfører en lille mængde arbejde alene, og hver kører tusinder eller millioner af gange over et realistisk dokument, hvilket er præcis den form funktion, hvor en O(n)- eller O(n²)-implementeringsdetalje holder op med at være usynlig og begynder at være profilens topindslag

Hvorfor bliver ressource-ordbogs-opslag langsomme i en stor PDF?

TPDFDictionary.FindIndexByKeyName er, hvad rendereren kalder for at løse hvert /Resources-, /ColorSpace-, /Font- og /ExtGState-opslag, og den plejede at gennemgå Entries-arrayet fra fronten ved hvert kald — fint til en tre-posters Resources-ordbog, dyrt for et Form-XObject eller en ExtGState-tung side, hvor den samme ordbog sonderes ved hver operator, der rører farve eller grafiktilstand. PDFlibPas bygger nu et dovent hash-indeks, når en ordbog passerer DICT_HASH_THRESHOLD (16) poster, og lader mindre ordbøger blive på den lineære skanning, da de fleste PDF-ordbøger aldrig bliver så store, og en hash-tabel til tre nøgler ville koste mere at bygge, end den sparer. Indekset er en flad open-addressing-tabel nøglet af PLAnsiStringHash, en FNV-1a-hash med den kanoniske forskydnings-basis 2166136261 og primtal 16777619, valgt for at undgå at trække System.Generics.Collections ind for noget så størrelsesfølsomt

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;

Indekset invalideres frem for at blive vedligeholdt inkrementelt: hvert muterende kald — AddEntry, DeleteEntryByKeyName, Assign, AddDict — rydder hashen og lader det næste opslag genopbygge den fra bunden. Det ser spild ud, indtil man bemærker, at en ordbogs-nøgle er et TPDFName-objekt, og TPDFName.SetTo kan omdøbe en nøgle allerede siddende i en ordbogs Entries-array uden at gå gennem nogen af ordbogens egne metoder — et inkrementelt indeks har ingen måde at observere den omdøbning, mens et dovent bare genopbygger og forbliver korrekt ved konstruktion. Prisen for den sikkerhed er en O(n)-genopbygning første gang en stor ordbog forespørges efter en skrivning, plus hukommelsen til selve hash-tabellen, groft sagt ét Integer pr. plads ved en to-tredjedele belastningsfaktor — en afrundingsfejl for den håndfuld overdimensionerede ordbøger i et typisk dokument, og en reel omkostning PDFlibPas undgår at betale på hver lille en ved at holde tærsklen hvor den er

At forudberegne sRGB-gamma i stedet for at kalde Power pr. pixel

TPDFSimpleColorManager.XYZ2RGB anvender sRGB-overførselsfunktionen på hver dekodet pixel af et Lab-, Indexed- eller ICC-baseret billede — 1.055 * Power(x, 1/2.4) - 0.055 over den lineære-segment-tærskel — og Power(x, y) for et brøkdels-y har ingen billig lukket form på Pascal-RTL'en: den dekomponerer til Ln(x) så Exp(y * Ln(x)), og det par af transcendentale kald, kørt tre gange pr. pixel til de røde, grønne og blå kanaler, er den dominerende omkostning ved at dekode en Lab- eller ICC-billedpixel for pixel. PDFlibPas erstatter de tre per-pixel-Power-kald med ét opslag ind i GSRGBGammaLUT, et 4096-posters Double-array bygget én gang via EnsureSRGBGammaLUT og indekseret ved at afrunde det klemte input til den nærmeste plads

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-plads-tabel over [0, 1]-input-intervallet giver groft sagt seksten gange opløsningen af en 8-bit-output-kanal, så den kvantisering, LUT'en introducerer, sidder under, hvad den endelige RGB-byte kan repræsentere — tabelopslag erstatter transcendental matematik her uden en synlig præcisionsomkostning. Det samme ræsonnement dukker op ved siden af det i Lab2XYZ, hvor Power(LMN[i], 3) blev til et almindeligt LMN[i]*LMN[i]*LMN[i]: en heltals-eksponent har ikke brug for Ln/Exp i første omgang, så det er slet ikke en LUT-afvejning, bare et overflødigt Power-kald fjernet. LUT-tricket betaler sig kun, fordi overførselsfunktionen er en ren funktion af en enkelt Double — det ville ikke udvide rent til en farvetransformation, der afhang af flere pixelværdier eller mere tilstand end det

Hvordan afsender man 73 content-stream-operatorer hurtigt?

ContentOperatorFromName kaldes én gang for hvert token, PDFlibPas læser ud af en content-stream, og matcher det mod ISO 32000-1 Tabel 51's fulde sæt af 73 operatorer — fra w og q op til de sjældent-sete d0- og d1-Type-3-glyf-metrik-operatorer — og den plejede at gennemgå den liste lineært ved hvert enkelt token, så en side med et par tusind operatorer betød et par tusind lineære skanninger over den samme 73-posters tabel. PDFlibPas bucketer nu tabellen efter operatorens første byte ved opstart, ind i et fast AnsiChar-indekseret array af pladser, så et opslag bliver ét array-indeks plus en skanning af kun den håndfuld operatorer, der deler det første tegn

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 skelner mellem store og små bogstaver — w og W, f og F, sc og SC er alle forskellige operatorer — så GOpBuckets nøgler på den rå byte, og rest-sammenligningen inde i en bucket er en almindelig, store/små-bogstaver-følsom AnsiString-lighed. Arrayet er dimensioneret til 16 pladser pr. bogstav, hvilket komfortabelt dækker dagens tabel — den travleste bucket, T, holder tretten operatorer, da næsten hver tekst-tilstands- og tekst-positionerings-operator starter med det — men EnsureOpBuckets stopper i stilhed med at tilføje til en bucket, når dens optælling når 16, så en bucket der nogensinde havde brug for en fjortende post, ville fejle stille frem for højlydt: operatoren ville løse til coUnknown uden nogen undtagelse der peger på hvorfor. Det er vedligeholdelsesomkostningen ved at bytte en datastruktur, der degraderer elegant, for en der ikke gør — den afsender hurtigere, fordi den aldrig har brug for en grænse-tjekket vækst, og den har brug for et menneske der holder øje med den ene bucket tæt på sit loft

At skære O(n²) ud af strengbygning

Pascals Result := Result + Fragment-mønster geallokerer og kopierer hele den akkumulerede streng ved hver iteration, så at bygge et N-tegns output ét fragment ad gangen koster O(n²) i stedet for O(n) — let at overse i kodegennemgang, da hver linje ser ud som ét billigt tilføj, og dyrt i praksis, fordi PLDirectEscapeLiteralString kører på hver bogstavelig PDF-streng skrevet under gemning, og XFDFXMLEscape kører på hver felt-værdi eksporteret til XFDF. PDFlibPas fixer de to med forskellige teknikker, valgt ud fra hvad hver funktion kan forudsige på forhånd. PLDirectEscapeLiteralString kender sin output-længde, før den skriver en enkelt byte — ét gennemløb klassificerer hvert tegn som almindeligt eller escaped og summerer totalen, SetLength allokerer én gang, og et andet gennemløb fylder bufferen efter indeks. XFDFXMLEscape kan ikke billigt forudsige sin output-længde, da Unicode-felt-tekst varierer for meget til at forudberegne, så den tilføjer i stedet ind i en TStringBuilder forudstørret til groft sagt input-længden

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 mellem de to handler egentlig om, hvad man ved, før løkken starter. Optæl-så-fyld er den hurtigere af de to, når output-størrelsen er billig at beregne, da den udfører nul genallokeringer og intet regnskab ud over en Integer-tæller, men det betyder at skrive klassificeringslogikken to gange — én gang for at tælle, én gang for at udsende — hvilket er sin egen vedligeholdelsesrisiko, hvis de to kopier driver fra hinanden. TStringBuilder giver lidt af den spids-gennemløb op til gengæld for at skrive logikken én gang og få amortiseret O(1)-tilføjelser fra geometrisk buffer-vækst, hvilket er den sikrere standard, hver gang output-størrelsen ikke er let at kende på forhånd

Hvor dette mønster gælder, og hvor det ikke gør

Alle fire fixes ovenfor er instanser af én idé: find kaldet der kører én gang pr. enhed input — pr. ordbogs-nøgle, pr. pixel, pr. operator-token, pr. tegn — og erstat dets lineære eller uforudsigelige omkostning med en forudberegnet tabel, et hash-indeks, eller en forudstørret buffer. Intet af det er specifikt for PDF; en Delphi-tjeneste, der løser den samme opslagsnøgle tusindvis af gange pr. forespørgsel, konverterer værdier i en tæt løkke, afsender på et fast vokabular af tokens, eller bygger lange strenge ét tegn ad gangen, rammer de samme fejlformer og tager de samme fixes. Hvad ingen af de fire ændringer rører, er samtidighed eller hukommelses-fodaftryk: et hurtigere enkelt-trådet ordbogs-opslag gør intet for to tråde, der kapløber på den samme TPDFlib-instans, hvilket er et strukturelt problem dækket separat i artiklen om trådsikkerhed i parallel side-gengivelse, og det gør intet for en PDF for stor til at indlæse i hukommelsen som et objekttræ overhovedet, hvilket er, hvad Direct-Access-laget i PDFlibPas er til, dækket i artiklen om at flette og opdele gigabyte-PDF'er

Ordbogs-, farvestyring-, content-stream-dispatch- og strengbygnings-koden diskuteret her leveres som en del af standard-PDFlibPas, losLabs PDF-bibliotek til Delphi og C++Builder, uden nogen ekstra konfiguration nødvendig for at få noget af det