PDFlibPas prestandaprofilering: hashindex i Delphi

PDFlibPas, losLabs PDF-bibliotek för Delphi och C++Builder, snabbar upp sina rendrerings- och innehållsgenereringsvägar genom att ersätta fyra upprepade-arbete-mönster med amorterade sådana: ett lat hashindex för uppslagningar av ordboksnycklar, en förberäknad sRGB-gammauppslagningstabell, första-byte-hinkning för dispatch av innehållsströmsoperatorer, och TStringBuilder istället för upprepad strängsammanfogning. Ingen av de fyra kom från en enda dramatisk upptäckt — de kom från samma oglamorösa mönster i en profil: en liten funktion anropad en gång per operator, en gång per pixel, eller en gång per tecken, där en linjär kostnad inuti anropet blir kvadratisk eller nästan kvadratisk över ett helt dokument. Det är den röda tråden här: fyra små, till synes orelaterade fixar som angriper samma problemform, plus de ärliga gränserna för var och en

Var en innehållsströmsrendrerare faktiskt spenderar sin tid

PDFlibPas innehållsströmsrendrerare kanaliserar nästan hela sin per-token-kostnad genom fyra smala punkter: resursordbokuppslagningar på /Resources, /ColorSpace, /Font, och /ExtGState; gammakorrigering på varje avkodad pixel av en Lab-, Indexed-, eller ICC-taggad bild; operatornamnsmatchning på varje token i varje innehållsström; och strängkonstruktion var biblioteket än bygger utdata — bokstavlig strängescapning vid sparning, XFDF-export, stämpel- och variabeltoken-expansion. Var och en av de fyra gör en liten mängd arbete på egen hand, och var och en körs tusentals eller miljontals gånger över ett realistiskt dokument, vilket är precis den formen av funktion där en O(n)- eller O(n²)-implementationsdetalj slutar vara osynlig och börjar bli profilens toppinlägg

Varför blir resursordboksuppslagningar långsamma i en stor PDF?

TPDFDictionary.FindIndexByKeyName är vad rendreraren anropar för att lösa upp varje /Resources-, /ColorSpace-, /Font-, och /ExtGState-uppslagning, och den brukade gå igenom Entries-arrayen från fronten vid varje anrop — fint för en trepost-Resources-ordbok, kostsamt för en Form XObject eller en ExtGState-tung sida där samma ordbok proberas vid varje operator som rör färg eller grafiktillstånd. PDFlibPas bygger nu ett lat hashindex när en ordbok passerar DICT_HASH_THRESHOLD (16) poster och lämnar mindre ordböcker på den linjära skanningen, eftersom de flesta PDF-ordböcker aldrig blir så stora och en hashtabell för tre nycklar skulle kosta mer att bygga än den sparar. Indexet är en platt öppen-adressering-tabell nyckelmed av PLAnsiStringHash, en FNV-1a-hash med den kanoniska offsetbasen 2166136261 och primtalet 16777619, valda för att undvika att dra in System.Generics.Collections för något så storlekskänsligt

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;

Indexet invalideras snarare än underhålls inkrementellt: varje muterande anrop — AddEntry, DeleteEntryByKeyName, Assign, AddDict — rensar hashen och låter nästa uppslagning bygga om den från grunden. Det ser slösaktigt ut tills man märker att en ordboksnyckel är ett TPDFName-objekt, och TPDFName.SetTo kan byta namn på en nyckel som redan sitter i en ordboks Entries-array utan att gå genom någon av ordbokens egna metoder — ett inkrementellt index har inget sätt att observera det namnbytet, medan ett lat ett bara bygger om och förblir korrekt genom konstruktion. Priset för den säkerheten är en O(n)-ombyggnad första gången en stor ordbok frågas efter en skrivning, plus minnet för själva hashtabellen, ungefär ett Integer per plats vid en två-tredjedels lastfaktor — ett avrundningsfel för handfullen av överdimensionerade ordböcker i ett typiskt dokument, och en riktig kostnad PDFlibPas undviker att betala på varje liten en genom att hålla tröskeln där den är

Att förberäkna sRGB-gamma istället för att anropa Power per pixel

TPDFSimpleColorManager.XYZ2RGB tillämpar sRGB-överföringsfunktionen på varje avkodad pixel av en Lab-, Indexed-, eller ICC-baserad bild — 1.055 * Power(x, 1/2.4) - 0.055 ovanför det linjära segmenttröskeln — och Power(x, y) för ett bråktal y har ingen billig sluten form i Pascal-RTL:n: den bryts ner till Ln(x) och sedan Exp(y * Ln(x)), och det paret av transcendentala anrop, kört tre gånger per pixel för de röda, gröna, och blå kanalerna, är den dominerande kostnaden för att avkoda en Lab- eller ICC-bild pixel för pixel. PDFlibPas ersätter de tre per-pixel-Power-anropen med en uppslagning i GSRGBGammaLUT, en 4096-post Double-array byggd en gång via EnsureSRGBGammaLUT och indexerad genom att avrunda den klämda indatan till närmaste plats

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-plats-tabell över [0, 1]-indataintervallet ger ungefär sexton gånger upplösningen av en 8-bitars utdatakanal, så kvantiseringen LUT:n introducerar sitter under vad den slutliga RGB-byten kan representera — tabelluppslagning ersätter transcendental matematik här utan en synlig precisionskostnad. Samma resonemang dyker upp bredvid den i Lab2XYZ, där Power(LMN[i], 3) blev en vanlig LMN[i]*LMN[i]*LMN[i]: en heltalspotens behöver inte Ln/Exp från början, så den är ingen LUT-avvägning alls, bara ett överflödigt Power-anrop borttaget. LUT-tricket lönar sig bara eftersom överföringsfunktionen är en ren funktion av ett enskilt Double — det skulle inte utökas rent till en färgtransform som berodde på flera pixelvärden eller mer tillstånd än det

Hur dispatchar man 73 innehållsströmsoperatorer snabbt?

ContentOperatorFromName anropas en gång för varje token PDFlibPas läser ut ur en innehållsström, matchar den mot ISO 32000-1 Tabell 51:s fullständiga uppsättning av 73 operatorer — från w och q upp till de sällan sedda d0- och d1-Typ 3-glyfmåttoperatorerna — och den brukade gå igenom den listan linjärt vid varje enskild token, så en sida med några tusen operatorer betydde några tusen linjära skanningar över samma 73-posts-tabell. PDFlibPas hinkar nu tabellen efter operatorns första byte vid uppstart, in i en fast AnsiChar-indexerad array av platser, så en uppslagning blir ett array-index plus en skanning av bara handfullen operatorer som delar det första tecknet

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 är skiftlägeskänsliga — w och W, f och F, sc och SC är alla olika operatorer — så GOpBuckets nyckelmed av den råa byten och restjämförelsen inuti en hink är en vanlig, skiftlägeskänslig AnsiString-likhet. Arrayen är dimensionerad till 16 platser per bokstav, vilket bekvämt täcker dagens tabell — den mest upptagna hinken, T, håller tretton operatorer, eftersom nästan varje textilstånds- och textpositioneringsoperator börjar med den — men EnsureOpBuckets slutar tyst lägga till i en hink när dess antal når 16, så en hink som någonsin behövde en fjortonde post skulle misslyckas tyst snarare än högljutt: operatorn skulle lösa upp till coUnknown utan något undantag som pekar på varför. Det är underhållskostnaden för att byta en datastruktur som degraderar graciöst mot en som inte gör det — den dispatchar snabbare eftersom den aldrig behöver en gränskontrollerad tillväxt, och den behöver en människa som håller koll på den enda hinken nära sitt tak

Att skära bort O(n²) ur strängbyggande

Pascals Result := Result + Fragment-mönster återallokerar och kopierar hela den ackumulerade strängen vid varje iteration, så att bygga en N-teckens utdata ett fragment i taget kostar O(n²) istället för O(n) — lätt att missa vid granskning, eftersom varje rad ser ut som ett billigt tillägg, och kostsamt i praktiken eftersom PLDirectEscapeLiteralString körs på varje bokstavlig PDF-sträng skriven vid sparning och XFDFXMLEscape körs på varje fältvärde exporterat till XFDF. PDFlibPas fixar de två med olika tekniker, valda efter vad varje funktion kan förutsäga i förväg. PLDirectEscapeLiteralString vet sin utdatalängd innan den skriver en enda byte — en passering klassificerar varje tecken som vanligt eller escapat och summerar totalen, SetLength allokerar en gång, och en andra passering fyller bufferten efter index. XFDFXMLEscape kan inte billigt förutsäga sin utdatalängd, eftersom Unicode-fälttext varierar för mycket för att förberäknas, så den lägger till in i en TStringBuilder förhandsdimensionerad till ungefär indatans längd istället

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;

Valet mellan de två handlar egentligen om vad man vet innan loopen startar. Räkna-sedan-fyll är den snabbare av de två när utdatastorleken är billig att beräkna, eftersom den gör noll återallokeringar och ingen bokföring bortom en Integer-räknare, men det betyder att skriva klassificeringslogiken två gånger — en för att räkna, en för att avge — vilket är sin egen underhållsrisk om de två kopiorna driver isär. TStringBuilder ger upp lite av den toppgenomströmningen för att skriva logiken en gång och få amorterade O(1)-tillägg från geometrisk buffertillväxt, vilket är standardvalet när utdatastorleken inte är lätt att veta i förväg

Var det här mönstret gäller, och var det inte gör

Alla fyra fixar ovan är instanser av en idé: hitta anropet som körs en gång per enhet indata — per ordboksnyckel, per pixel, per operatortoken, per tecken — och ersätt dess linjära eller oförutsägbara kostnad med en förberäknad tabell, ett hashindex, eller en förhandsdimensionerad buffert. Inget av det är specifikt för PDF; en Delphi-tjänst som löser upp samma uppslagningsnyckel tusentals gånger per förfrågan, konverterar värden i en tät loop, dispatchar på ett fast vokabulär av tokens, eller bygger långa strängar ett tecken i taget stöter på samma felformer och tar samma fixar. Vad ingen av de här fyra ändringarna rör är samtidighet eller minnesfotavtryck: en snabbare entrådig ordboksuppslagning gör ingenting för två trådar som kapplöper på samma TPDFlib-instans, vilket är ett strukturellt problem täckt separat i artikeln om trådsäkerhet i parallell sidrendrering, och den gör ingenting för en PDF för stor för att laddas in i minnet som ett objektträd alls, vilket är vad Direct Access-lagret i PDFlibPas är till för, täckt i artikeln om att sammanfoga och dela gigabyte-PDF:er

Ordbok-, färghanterings-, innehållsströmsdispatch-, och strängbyggnadskoden som diskuteras här levereras som en del av standard-PDFlibPas, losLabs PDF-bibliotek för Delphi och C++Builder, utan extra konfiguration som behövs för att få någon av dem