Profiling delle Prestazioni di PDFlibPas: Indici Hash in Delphi

PDFlibPas, la libreria PDF di losLab per Delphi e C++Builder, velocizza i propri percorsi di rendering e generazione contenuto sostituendo quattro schemi di lavoro ripetuto con altrettanti ammortizzati: un indice hash lazy per i lookup di chiave di dizionario, una tabella di lookup gamma sRGB precalcolata, un raggruppamento per primo byte per il dispatch degli operatori del content stream, e TStringBuilder al posto della concatenazione ripetuta di stringhe. Nessuno dei quattro è nato da una singola scoperta eclatante — sono nati dallo stesso schema poco affascinante in un profiler: una piccola funzione chiamata una volta per operatore, una volta per pixel, o una volta per carattere, dove un costo lineare dentro la chiamata diventa quadratico o quasi-quadratico su un intero documento. Questo è il filo conduttore qui: quattro correzioni piccole e apparentemente non correlate che attaccano la stessa forma di problema, più i limiti onesti di ciascuna

Dove spende realmente il proprio tempo un renderer di content stream

Il renderer di content stream di PDFlibPas incanala quasi tutto il proprio costo per token attraverso quattro punti ristretti: i lookup del dizionario di risorse su /Resources, /ColorSpace, /Font, e /ExtGState; la correzione gamma su ogni pixel decodificato di un'immagine Lab, Indexed, o con tag ICC; la corrispondenza dei nomi operatore su ogni token di ogni content stream; e la costruzione di stringhe ovunque la libreria costruisca output — escape di stringhe letterali al salvataggio, esportazione XFDF, espansione di token timbro e variabile. Ognuno dei quattro fa una piccola quantità di lavoro da sé, e ognuno gira migliaia o milioni di volte su un documento realistico, che è esattamente la forma di funzione dove un dettaglio implementativo O(n) o O(n²) smette di essere invisibile e inizia a essere la voce principale del profiler

Perché i lookup del dizionario di risorse diventano lenti in un PDF grande?

TPDFDictionary.FindIndexByKeyName è ciò che il renderer chiama per risolvere ogni lookup /Resources, /ColorSpace, /Font, e /ExtGState, e in passato percorreva l'array Entries dall'inizio a ogni chiamata — va bene per un dizionario Resources a tre voci, costoso per un Form XObject o una pagina ricca di ExtGState dove lo stesso dizionario viene sondato a ogni operatore che tocca colore o stato grafico. PDFlibPas ora costruisce un indice hash lazy una volta che un dizionario supera la soglia DICT_HASH_THRESHOLD (16) voci e lascia i dizionari più piccoli sulla scansione lineare, poiché la maggior parte dei dizionari PDF non diventa mai così grande e una tabella hash per tre chiavi costerebbe più da costruire di quanto risparmi. L'indice è una tabella piatta a indirizzamento aperto indicizzata da PLAnsiStringHash, un hash FNV-1a con la base offset canonica 2166136261 e primo 16777619, scelta per evitare di importare System.Generics.Collections per qualcosa così sensibile alla dimensione

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;

L'indice viene invalidato invece che mantenuto in modo incrementale: ogni chiamata mutante — AddEntry, DeleteEntryByKeyName, Assign, AddDict — azzera l'hash e lascia che il lookup successivo lo ricostruisca da zero. Sembra dispendioso finché non ti accorgi che una chiave di dizionario è un oggetto TPDFName, e TPDFName.SetTo può rinominare una chiave già seduta nell'array Entries di un dizionario senza passare per nessuno dei metodi propri del dizionario — un indice incrementale non ha modo di osservare quella rinomina, mentre uno lazy si limita a ricostruirsi e resta corretto per costruzione. Il prezzo di quella sicurezza è una ricostruzione O(n) la prima volta che un grande dizionario viene interrogato dopo una scrittura, più la memoria per la tabella hash stessa, all'incirca un Integer per slot a un fattore di carico di due terzi — un errore di arrotondamento per la manciata di dizionari sovradimensionati in un tipico documento, e un costo reale che PDFlibPas evita di pagare su ogni piccolo dizionario mantenendo la soglia dove sta

Precalcolare il gamma sRGB invece di chiamare Power per pixel

TPDFSimpleColorManager.XYZ2RGB applica la funzione di trasferimento sRGB a ogni pixel decodificato di un'immagine Lab, Indexed, o basata su ICC — 1.055 * Power(x, 1/2.4) - 0.055 sopra la soglia del segmento lineare — e Power(x, y) per una y frazionaria non ha una forma chiusa economica nell'RTL Pascal: si scompone in Ln(x) poi Exp(y * Ln(x)), e quella coppia di chiamate trascendenti, eseguita tre volte per pixel per i canali rosso, verde e blu, è il costo dominante della decodifica di un pixel di immagine Lab o ICC pixel per pixel. PDFlibPas sostituisce le tre chiamate Power per pixel con un unico lookup in GSRGBGammaLUT, un array Double a 4096 voci costruito una volta tramite EnsureSRGBGammaLUT e indicizzato arrotondando l'input limitato allo slot più vicino

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;

Una tabella a 4096 slot sull'intervallo di input [0, 1] offre circa sedici volte la risoluzione di un canale di output a 8 bit, quindi la quantizzazione che la LUT introduce si colloca sotto ciò che il byte RGB finale può rappresentare — il lookup di tabella qui sostituisce la matematica trascendente senza un costo di precisione visibile. Lo stesso ragionamento compare accanto ad esso in Lab2XYZ, dove Power(LMN[i], 3) è diventato un semplice LMN[i]*LMN[i]*LMN[i]: una potenza intera non ha affatto bisogno di Ln/Exp in primo luogo, quindi quella non è affatto un compromesso LUT, solo una chiamata Power ridondante rimossa. Il trucco della LUT paga solo perché la funzione di trasferimento è una funzione pura di un singolo Double — non si estenderebbe pulitamente a una trasformazione colore che dipendesse da più valori di pixel o da più stato di quello

Come si esegue il dispatch veloce di 73 operatori di content stream?

ContentOperatorFromName viene chiamata una volta per ogni token che PDFlibPas legge da un content stream, facendolo corrispondere all'intero insieme di 73 operatori della Tabella 51 di ISO 32000-1 — da w e q fino ai raramente visti operatori di metriche glifo Tipo 3 d0 e d1 — e in passato percorreva quell'elenco linearmente a ogni singolo token, quindi una pagina con qualche migliaio di operatori significava qualche migliaio di scansioni lineari sulla stessa tabella a 73 voci. PDFlibPas ora raggruppa la tabella per il primo byte dell'operatore all'avvio, in un array fisso di slot indicizzato per AnsiChar, cosicché un lookup diventi un indice di array più una scansione solo della manciata di operatori che condividono quel primo carattere

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;

Gli operatori PDF sono sensibili alle maiuscole/minuscole — w e W, f e F, sc e SC sono tutti operatori diversi — quindi GOpBuckets indicizza sul byte grezzo e il confronto residuo dentro un bucket è una semplice uguaglianza AnsiString sensibile alle maiuscole/minuscole. L'array è dimensionato a 16 slot per lettera, che copre comodamente la tabella odierna — il bucket più affollato, T, contiene tredici operatori, poiché quasi ogni operatore di stato testo e posizionamento testo inizia con esso — ma EnsureOpBuckets smette silenziosamente di aggiungere a un bucket una volta che il suo conteggio raggiunge 16, quindi un bucket che avesse mai bisogno di una quattordicesima voce fallirebbe silenziosamente anziché rumorosamente: l'operatore si risolverebbe in coUnknown senza alcuna eccezione che indichi il perché. Questo è il costo di manutenzione dello scambiare una struttura dati che degrada con eleganza per una che non lo fa — esegue il dispatch più velocemente perché non ha mai bisogno di una crescita con controllo dei limiti, e ha bisogno di un essere umano che tenga d'occhio l'unico bucket vicino al proprio tetto

Eliminare O(n²) dalla costruzione di stringhe

Lo schema Pascal Result := Result + Fragment rialloca e copia l'intera stringa accumulata a ogni iterazione, quindi costruire un output di N caratteri un frammento alla volta costa O(n²) invece di O(n) — facile da perdere in una revisione, poiché ogni riga sembra un'unica aggiunta economica, e costoso nella pratica perché PLDirectEscapeLiteralString gira su ogni stringa PDF letterale scritta durante il salvataggio e XFDFXMLEscape gira su ogni valore di campo esportato in XFDF. PDFlibPas corregge i due con tecniche diverse, scelte in base a cosa ciascuna funzione può prevedere in anticipo. PLDirectEscapeLiteralString conosce la propria lunghezza di output prima di scrivere un solo byte — un passaggio classifica ogni carattere come semplice o con escape e somma il totale, SetLength alloca una volta, e un secondo passaggio riempie il buffer per indice. XFDFXMLEscape non può prevedere economicamente la propria lunghezza di output, poiché il testo di campo Unicode varia troppo per precalcolarlo, quindi accoda invece in un TStringBuilder pre-dimensionato a circa la lunghezza dell'input

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;

La scelta tra i due riguarda realmente cosa sai prima che il ciclo inizi. Conta-poi-riempi è il più veloce dei due quando la dimensione dell'output è economica da calcolare, poiché non fa zero riallocazioni e nessuna contabilità oltre un contatore Integer, ma significa scrivere la logica di classificazione due volte — una per contare, una per emettere — che è di per sé un rischio di manutenzione se le due copie divergono. TStringBuilder rinuncia a un po' di quel picco di throughput per scrivere la logica una sola volta e ottenere append ammortizzati O(1) dalla crescita geometrica del buffer, che è il default più sicuro ogni volta che la dimensione dell'output non è facile da conoscere in anticipo

Dove si applica questo schema, e dove no

Tutte e quattro le correzioni sopra sono istanze di un'unica idea: trova la chiamata che gira una volta per unità di input — per chiave di dizionario, per pixel, per token operatore, per carattere — e sostituisci il suo costo lineare o imprevedibile con una tabella precalcolata, un indice hash, o un buffer pre-dimensionato. Nulla di ciò è specifico del PDF; un servizio Delphi che risolve la stessa chiave di lookup migliaia di volte per richiesta, converte valori in un ciclo stretto, esegue il dispatch su un vocabolario fisso di token, o costruisce lunghe stringhe un carattere alla volta incontra le stesse forme di fallimento e adotta le stesse correzioni. Ciò che nessuna di queste quattro modifiche tocca è la concorrenza o l'ingombro di memoria: un lookup di dizionario single-thread più veloce non fa nulla per due thread in competizione sulla stessa istanza TPDFlib, che è un problema strutturale trattato separatamente nell'articolo sulla thread safety nel rendering di pagina parallelo, e non fa nulla per un PDF troppo grande per essere caricato in memoria come albero di oggetti affatto, che è a cosa serve il livello Direct Access in PDFlibPas, trattato nell'articolo sull'unione e divisione di PDF da gigabyte

Il codice di dizionario, gestione colore, dispatch content stream, e costruzione stringhe discusso qui fa parte del PDFlibPas standard, la libreria PDF di losLab per Delphi e C++Builder, senza necessità di alcuna configurazione extra per ottenerlo