PDFlibPas-prestatieprofilering: hash-indexen in Delphi

PDFlibPas, de PDF-bibliotheek van losLab voor Delphi en C++Builder, versnelt zijn render- en inhoudsgeneratiepaden door vier patronen van herhaald werk te vervangen door geamortiseerde varianten: een luie hash-index voor dictionary-sleutelopzoekingen, een vooraf berekende sRGB-gamma-opzoektabel, first-byte-bucketing voor de dispatch van inhoudsstroom-operatoren, en TStringBuilder in plaats van herhaalde stringconcatenatie. Geen van de vier kwam uit één dramatische ontdekking — ze kwamen uit hetzelfde onopvallende patroon in een profiel: een kleine functie die één keer per operator, één keer per pixel, of één keer per teken wordt aangeroepen, waarbij een lineaire kost binnen de aanroep kwadratisch of bijna kwadratisch wordt over een heel document. Dat is de rode draad hier: vier kleine, ogenschijnlijk ongerelateerde fixes die dezelfde vorm van probleem aanpakken, plus de eerlijke grenzen van elk daarvan

Waar besteedt een inhoudsstroom-renderer daadwerkelijk zijn tijd?

De inhoudsstroom-renderer van PDFlibPas voert vrijwel al zijn kosten per token door vier smalle punten: resourcedictionary-opzoekingen op /Resources, /ColorSpace, /Font, en /ExtGState; gammacorrectie op elke gedecodeerde pixel van een Lab-, Indexed-, of ICC-getagd beeld; operatornaam-matching op elk token van elke inhoudsstroom; en stringopbouw waar de bibliotheek ook output bouwt — escapen van letterlijke strings bij opslaan, XFDF-export, stempel- en variabele-tokenexpansie. Elk van de vier doet op zichzelf een kleine hoeveelheid werk, en elk draait duizenden of miljoenen keren over een realistisch document, precies de vorm van functie waarbij een O(n)- of O(n²)-implementatiedetail ophoudt onzichtbaar te zijn en de topvermelding van het profiel wordt

Waarom worden resourcedictionary-opzoekingen traag in een grote PDF?

TPDFDictionary.FindIndexByKeyName is wat de renderer aanroept om elke /Resources-, /ColorSpace-, /Font-, en /ExtGState-opzoeking op te lossen, en het liep vroeger bij elke aanroep vanaf voren door de array Entries — prima voor een Resources-dictionary met drie items, kostbaar voor een Form-XObject of een ExtGState-zware pagina waar dezelfde dictionary bij elke operator die kleur of grafische toestand raakt, wordt opgevraagd. PDFlibPas bouwt nu een luie hash-index zodra een dictionary de drempel DICT_HASH_THRESHOLD (16) items passeert, en laat kleinere dictionaries op de lineaire scan, aangezien de meeste PDF-dictionaries nooit zo groot worden en een hashtabel voor drie sleutels meer zou kosten om te bouwen dan het bespaart. De index is een platte open-addressing-tabel gesleuteld op PLAnsiStringHash, een FNV-1a-hash met de canonieke offsetbasis 2166136261 en priemgetal 16777619, gekozen om te voorkomen dat System.Generics.Collections wordt binnengehaald voor iets zo groottegevoelig als dit

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;

De index wordt ongeldig gemaakt in plaats van incrementeel onderhouden: elke muterende aanroep — AddEntry, DeleteEntryByKeyName, Assign, AddDict — wist de hash en laat de volgende opzoeking deze vanaf nul herbouwen. Dat oogt verspillend totdat u opmerkt dat een dictionary-sleutel een TPDFName-object is, en TPDFName.SetTo een sleutel die al in de array Entries van een dictionary zit kan hernoemen zonder via enige eigen methode van de dictionary te gaan — een incrementele index heeft geen manier om die hernoeming waar te nemen, terwijl een luie index gewoon herbouwt en door constructie correct blijft. De prijs van die veiligheid is een O(n)-herbouw de eerste keer dat een grote dictionary wordt opgevraagd na een schrijfbewerking, plus het geheugen voor de hashtabel zelf, ruwweg één Integer per slot bij een belastingfactor van tweederde — een afrondingsfout voor het handjevol te grote dictionaries in een typisch document, en een echte kost die PDFlibPas vermijdt te betalen op elk klein exemplaar door de drempel te laten waar deze is

sRGB-gamma vooraf berekenen in plaats van Power per pixel aan te roepen

TPDFSimpleColorManager.XYZ2RGB past de sRGB-overdrachtsfunctie toe op elke gedecodeerde pixel van een Lab-, Indexed-, of ICC-gebaseerd beeld — 1.055 * Power(x, 1/2.4) - 0.055 boven de lineaire-segment-drempel — en Power(x, y) voor een fractionele y heeft geen goedkope gesloten vorm in de Pascal-RTL: het valt uiteen in Ln(x) en dan Exp(y * Ln(x)), en dat paar transcendentale aanroepen, drie keer per pixel gedraaid voor het rode, groene, en blauwe kanaal, is de dominante kost van het per pixel decoderen van een Lab- of ICC-beeld. PDFlibPas vervangt de drie per-pixel-Power-aanroepen door één opzoeking in GSRGBGammaLUT, een array van 4096 items van het type Double die één keer wordt gebouwd via EnsureSRGBGammaLUT en wordt geïndexeerd door de geclampte invoer af te ronden naar de dichtstbijzijnde 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;

Een tabel van 4096 slots over het invoerbereik [0, 1] geeft ruwweg zestien keer de resolutie van een 8-bits uitvoerkanaal, dus de kwantisatie die de LUT introduceert, blijft onder wat de uiteindelijke RGB-byte kan representeren — tabelopzoeking vervangt hier transcendentale wiskunde zonder zichtbare precisiekost. Dezelfde redenering duikt ernaast op in Lab2XYZ, waar Power(LMN[i], 3) een gewoon LMN[i]*LMN[i]*LMN[i] werd: een gehele macht heeft om te beginnen geen Ln/Exp nodig, dus dat is helemaal geen LUT-afweging, gewoon een overbodige Power-aanroep verwijderd. De LUT-truc betaalt zich alleen uit omdat de overdrachtsfunctie een pure functie van één enkele Double is — het zou niet netjes uitbreiden naar een kleurtransformatie die afhing van meerdere pixelwaarden of van meer toestand dan dat

Hoe verzendt u 73 inhoudsstroom-operatoren snel?

ContentOperatorFromName wordt één keer aangeroepen voor elk token dat PDFlibPas uit een inhoudsstroom leest, en matcht dit tegen de volledige set van 73 operatoren uit ISO 32000-1 Tabel 51 — van w en q tot de zelden geziene Type-3-glyphmetrieken-operatoren d0 en d1 — en het liep die lijst vroeger bij elk afzonderlijk token lineair door, dus een pagina met een paar duizend operatoren betekende een paar duizend lineaire scans over dezelfde tabel met 73 items. PDFlibPas bucketet de tabel nu bij het opstarten op de eerste byte van de operator, in een vaste, met AnsiChar geïndexeerde array van slots, zodat een opzoeking één array-index wordt plus een scan van slechts het handjevol operatoren dat dat eerste teken deelt

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-operatoren zijn hoofdlettergevoelig — w en W, f en F, sc en SC zijn allemaal verschillende operatoren — dus GOpBuckets sleutelt op de ruwe byte en de resterende vergelijking binnen een bucket is een gewone, hoofdlettergevoelige AnsiString-gelijkheid. De array heeft een grootte van 16 slots per letter, wat de huidige tabel ruimschoots dekt — de drukste bucket, T, bevat dertien operatoren, aangezien bijna elke tekst-toestand- en tekstpositioneringsoperator ermee begint — maar EnsureOpBuckets stopt stilzwijgend met toevoegen aan een bucket zodra het aantal 16 bereikt, dus een bucket die ooit een veertiende item nodig zou hebben, zou stil falen in plaats van luid: de operator zou oplossen naar coUnknown zonder uitzondering die aanwijst waarom. Dat is de onderhoudskost van het inruilen van een datastructuur die gracieus degradeert voor een die dat niet doet — het verzendt sneller omdat het nooit een bounds-gecontroleerde groei nodig heeft, en het heeft een mens nodig die de ene bucket in de gaten houdt die dicht bij zijn plafond zit

O(n²) uit stringopbouw snijden

Het Pascal-patroon Result := Result + Fragment wijst de hele opgebouwde string bij elke iteratie opnieuw toe en kopieert deze, dus het bouwen van een N-teken-uitvoer één fragment tegelijk kost O(n²) in plaats van O(n) — gemakkelijk over het hoofd te zien bij review, aangezien elke regel eruitziet als één goedkope toevoeging, en kostbaar in de praktijk omdat PLDirectEscapeLiteralString draait op elke letterlijke PDF-string die tijdens opslaan wordt geschreven en XFDFXMLEscape draait op elke veldwaarde die naar XFDF wordt geëxporteerd. PDFlibPas repareert de twee met verschillende technieken, gekozen op basis van wat elke functie vooraf kan voorspellen. PLDirectEscapeLiteralString kent zijn uitvoerlengte voordat het één enkele byte schrijft — één doorgang classificeert elk teken als gewoon of geëscaped en telt het totaal op, SetLength wijst één keer toe, en een tweede doorgang vult de buffer per index. XFDFXMLEscape kan zijn uitvoerlengte niet goedkoop voorspellen, aangezien Unicode-veldtekst te veel varieert om vooraf te berekenen, dus voegt het in plaats daarvan toe aan een TStringBuilder die vooraf op ruwweg de invoerlengte is gedimensioneerd

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;

De keuze tussen de twee draait eigenlijk om wat u weet voordat de lus begint. Tellen-dan-vullen is de snellere van de twee wanneer de uitvoergrootte goedkoop te berekenen is, aangezien het nul heraanmaakbewerkingen en geen boekhouding kost buiten een Integer-teller, maar het betekent dat de classificatielogica twee keer wordt geschreven — één keer om te tellen, één keer om uit te voeren — wat zijn eigen onderhoudsrisico is als de twee kopieën uit elkaar drijven. TStringBuilder geeft een beetje van die piekdoorvoer op voor het één keer schrijven van de logica en het krijgen van geamortiseerde O(1)-toevoegingen door geometrische buffergroei, wat de veiligere standaard is telkens wanneer de uitvoergrootte niet gemakkelijk vooraf te kennen is

Waar dit patroon van toepassing is, en waar niet

Alle vier bovenstaande fixes zijn instanties van één idee: vind de aanroep die één keer per invoereenheid draait — per dictionarysleutel, per pixel, per operatortoken, per teken — en vervang de lineaire of onvoorspelbare kost ervan door een vooraf berekende tabel, een hash-index, of een vooraf gedimensioneerde buffer. Niets hiervan is specifiek voor PDF; een Delphi-service die duizenden keren per verzoek dezelfde opzoeksleutel oplost, waarden converteert in een strakke lus, verzendt op een vaste woordenschat van tokens, of lange strings teken voor teken bouwt, treft dezelfde faalvormen en krijgt dezelfde fixes. Wat geen van deze vier wijzigingen aanraakt, is concurrency of geheugenvoetafdruk: een snellere single-threaded dictionary-opzoeking doet niets voor twee threads die racen op dezelfde TPDFlib-instantie, wat een structureel probleem is dat apart wordt behandeld in het artikel over threadveiligheid bij parallelle paginarendering, en het doet niets voor een PDF te groot om helemaal als objectboom in het geheugen te laden, waar de Direct-Access-laag in PDFlibPas voor is, behandeld in het artikel over het samenvoegen en splitsen van gigabyte-PDF's

De hier besproken code voor dictionaries, kleurbeheer, inhoudsstroom-dispatch, en stringopbouw wordt geleverd als onderdeel van de standaard PDFlibPas, de PDF-bibliotheek van losLab voor Delphi en C++Builder, zonder dat er extra configuratie nodig is om er iets van te krijgen