Profilage de performance PDFlibPas : index de hachage en Delphi

PDFlibPas, la bibliothèque PDF de losLab pour Delphi et C++Builder, accélère ses chemins de rendu et de génération de contenu en remplaçant quatre schémas de travail répété par des schémas amortis : un index de hachage paresseux pour les recherches de clé de dictionnaire, une table de correspondance gamma sRGB précalculée, un regroupement par premier octet pour la répartition des opérateurs de flux de contenu, et TStringBuilder à la place de la concaténation de chaînes répétée. Aucune des quatre n'est venue d'une découverte spectaculaire unique — elles sont venues du même schéma peu glamour dans un profil : une petite fonction appelée une fois par opérateur, une fois par pixel, ou une fois par caractère, où un coût linéaire à l'intérieur de l'appel devient quadratique ou presque quadratique sur tout un document. C'est le fil conducteur ici : quatre petites corrections d'apparence sans rapport qui attaquent la même forme de problème, plus les limites honnêtes de chacune

Où un moteur de rendu de flux de contenu passe-t-il réellement son temps

Le moteur de rendu de flux de contenu de PDFlibPas achemine presque tout son coût par jeton à travers quatre points étroits : les recherches de dictionnaire de ressources sur /Resources, /ColorSpace, /Font, et /ExtGState ; la correction gamma sur chaque pixel décodé d'une image Lab, Indexed, ou étiquetée ICC ; la correspondance de nom d'opérateur sur chaque jeton de chaque flux de contenu ; et la construction de chaînes partout où la bibliothèque construit une sortie — échappement de chaîne littérale à l'enregistrement, export XFDF, expansion de jetons de tampon et de variable. Chacun des quatre effectue une petite quantité de travail à lui seul, et chacun s'exécute des milliers ou des millions de fois sur un document réaliste, ce qui est exactement la forme de fonction où un détail d'implémentation O(n) ou O(n²) cesse d'être invisible et devient l'entrée la plus haute du profil

Pourquoi les recherches de dictionnaire de ressources deviennent-elles lentes dans un grand PDF ?

TPDFDictionary.FindIndexByKeyName est ce que le moteur de rendu appelle pour résoudre chaque recherche /Resources, /ColorSpace, /Font, et /ExtGState, et il parcourait auparavant le tableau Entries depuis le début à chaque appel — bien pour un dictionnaire Resources à trois entrées, coûteux pour un Form XObject ou une page riche en ExtGState où le même dictionnaire est sondé à chaque opérateur qui touche la couleur ou l'état graphique. PDFlibPas construit désormais un index de hachage paresseux une fois qu'un dictionnaire dépasse DICT_HASH_THRESHOLD (16) entrées et laisse les dictionnaires plus petits sur le scan linéaire, car la plupart des dictionnaires PDF n'atteignent jamais cette taille et une table de hachage pour trois clés coûterait plus cher à construire qu'elle n'économise. L'index est une table plate à adressage ouvert indexée par PLAnsiStringHash, un hachage FNV-1a avec la base de décalage canonique 2166136261 et le nombre premier 16777619, choisi pour éviter de tirer System.Generics.Collections pour quelque chose d'aussi sensible à la taille

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'index est invalidé plutôt que maintenu de façon incrémentale : chaque appel mutant — AddEntry, DeleteEntryByKeyName, Assign, AddDict — efface le hachage et laisse la prochaine recherche le reconstruire de zéro. Cela paraît gaspilleur jusqu'à ce qu'on remarque qu'une clé de dictionnaire est un objet TPDFName, et TPDFName.SetTo peut renommer une clé déjà assise dans le tableau Entries d'un dictionnaire sans passer par aucune des propres méthodes du dictionnaire — un index incrémental n'a aucun moyen d'observer ce renommage, tandis qu'un index paresseux se contente de reconstruire et reste correct par construction. Le prix de cette sécurité est une reconstruction O(n) la première fois qu'un grand dictionnaire est interrogé après une écriture, plus la mémoire pour la table de hachage elle-même, environ un Integer par emplacement à un facteur de charge de deux tiers — une erreur d'arrondi pour la poignée de dictionnaires surdimensionnés dans un document typique, et un coût réel que PDFlibPas évite de payer sur chaque petit dictionnaire en gardant le seuil où il est

Précalculer le gamma sRGB plutôt qu'appeler Power par pixel

TPDFSimpleColorManager.XYZ2RGB applique la fonction de transfert sRGB à chaque pixel décodé d'une image Lab, Indexed, ou basée ICC — 1.055 * Power(x, 1/2.4) - 0.055 au-dessus du seuil de segment linéaire — et Power(x, y) pour un y fractionnaire n'a pas de forme close bon marché sur le RTL Pascal : elle se décompose en Ln(x) puis Exp(y * Ln(x)), et cette paire d'appels transcendants, exécutée trois fois par pixel pour les canaux rouge, vert, et bleu, est le coût dominant du décodage d'un pixel d'image Lab ou ICC pixel par pixel. PDFlibPas remplace les trois appels Power par pixel par une seule recherche dans GSRGBGammaLUT, un tableau Double à 4096 entrées construit une fois via EnsureSRGBGammaLUT et indexé en arrondissant l'entrée bornée à l'emplacement le plus proche

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;

Une table de 4096 emplacements sur la plage d'entrée [0, 1] donne environ seize fois la résolution d'un canal de sortie 8 bits, si bien que la quantification que la LUT introduit se trouve sous ce que l'octet RVB final peut représenter — la recherche de table remplace ici les mathématiques transcendantes sans coût de précision visible. Le même raisonnement apparaît juste à côté dans Lab2XYZ, où Power(LMN[i], 3) est devenu un simple LMN[i]*LMN[i]*LMN[i] : une puissance entière n'a pas du tout besoin de Ln/Exp en premier lieu, si bien que celle-là n'est pas du tout un compromis de LUT, juste un appel Power redondant retiré. L'astuce de la LUT ne porte ses fruits que parce que la fonction de transfert est une fonction pure d'un seul Double — elle ne s'étendrait pas proprement à une transformation de couleur qui dépendrait de plusieurs valeurs de pixel ou de plus d'état que cela

Comment répartir 73 opérateurs de flux de contenu rapidement ?

ContentOperatorFromName est appelée une fois pour chaque jeton que PDFlibPas lit d'un flux de contenu, le faisant correspondre contre l'ensemble complet de 73 opérateurs du Tableau 51 d'ISO 32000-1 — de w et q jusqu'aux opérateurs de métriques de glyphe Type 3 rarement vus d0 et d1 — et elle parcourait auparavant cette liste linéairement à chaque jeton unique, si bien qu'une page avec quelques milliers d'opérateurs signifiait quelques milliers de scans linéaires sur la même table à 73 entrées. PDFlibPas regroupe désormais la table par le premier octet de l'opérateur au démarrage, dans un tableau fixe d'emplacements indexé par AnsiChar, si bien qu'une recherche devient un index de tableau plus un scan de seulement la poignée d'opérateurs partageant ce premier caractère

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;

Les opérateurs PDF sont sensibles à la casse — w et W, f et F, sc et SC sont tous des opérateurs différents — si bien que GOpBuckets indexe sur l'octet brut et la comparaison résiduelle à l'intérieur d'un compartiment est une simple égalité AnsiString sensible à la casse. Le tableau est dimensionné à 16 emplacements par lettre, ce qui couvre confortablement la table actuelle — le compartiment le plus occupé, T, contient treize opérateurs, puisque presque tous les opérateurs d'état de texte et de positionnement de texte commencent par lui — mais EnsureOpBuckets s'arrête silencieusement d'ajouter à un compartiment une fois que son compte atteint 16, si bien qu'un compartiment qui aurait un jour besoin d'une quatorzième entrée échouerait silencieusement plutôt que bruyamment : l'opérateur se résoudrait à coUnknown sans aucune exception pointant vers la raison. C'est le coût de maintenance d'échanger une structure de données qui se dégrade en douceur contre une qui ne le fait pas — elle répartit plus vite car elle n'a jamais besoin d'une croissance vérifiée par bornes, et elle a besoin d'un humain surveillant le seul compartiment proche de son plafond

Retirer l'O(n²) de la construction de chaînes

Le schéma Pascal Result := Result + Fragment réalloue et copie toute la chaîne accumulée à chaque itération, si bien que construire une sortie de N caractères un fragment à la fois coûte O(n²) au lieu d'O(n) — facile à manquer en relecture, car chaque ligne a l'air d'un simple ajout bon marché, et coûteux en pratique car PLDirectEscapeLiteralString s'exécute sur chaque chaîne littérale PDF écrite à l'enregistrement et XFDFXMLEscape s'exécute sur chaque valeur de champ exportée en XFDF. PDFlibPas corrige les deux avec des techniques différentes, choisies selon ce que chaque fonction peut prédire à l'avance. PLDirectEscapeLiteralString connaît sa longueur de sortie avant d'écrire un seul octet — une passe classe chaque caractère comme brut ou échappé et additionne le total, SetLength alloue une fois, et une seconde passe remplit le tampon par index. XFDFXMLEscape ne peut pas prédire à bon marché sa longueur de sortie, car le texte de champ Unicode varie trop pour être précalculé, si bien qu'elle ajoute à la place dans un TStringBuilder pré-dimensionné à environ la longueur d'entrée

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;

Le choix entre les deux porte en réalité sur ce que vous savez avant que la boucle ne commence. Compter-puis-remplir est la plus rapide des deux quand la taille de sortie est bon marché à calculer, car elle n'effectue aucune réallocation et aucune comptabilité au-delà d'un compteur Integer, mais cela signifie écrire la logique de classification deux fois — une fois pour compter, une fois pour émettre — ce qui est son propre risque de maintenance si les deux copies dérivent l'une de l'autre. TStringBuilder abandonne un peu de ce débit de pointe pour n'écrire la logique qu'une fois et obtenir des ajouts amortis O(1) grâce à une croissance de tampon géométrique, ce qui est le choix par défaut plus sûr chaque fois que la taille de sortie n'est pas facile à connaître à l'avance

Où ce schéma s'applique, et où il ne s'applique pas

Les quatre corrections ci-dessus sont toutes des instances d'une seule idée : trouver l'appel qui s'exécute une fois par unité d'entrée — par clé de dictionnaire, par pixel, par jeton d'opérateur, par caractère — et remplacer son coût linéaire ou imprévisible par une table précalculée, un index de hachage, ou un tampon pré-dimensionné. Rien de tout cela n'est spécifique au PDF ; un service Delphi qui résout la même clé de recherche des milliers de fois par requête, convertit des valeurs dans une boucle serrée, répartit sur un vocabulaire fixe de jetons, ou construit de longues chaînes un caractère à la fois rencontre les mêmes formes d'échec et prend les mêmes corrections. Ce qu'aucun de ces quatre changements ne touche est la concurrence ou l'empreinte mémoire : une recherche de dictionnaire monothread plus rapide ne fait rien pour deux threads en concurrence sur la même instance TPDFlib, ce qui est un problème structurel couvert séparément dans l'article sur la sécurité des threads dans le rendu de page parallèle, et cela ne fait rien pour un PDF trop volumineux pour être chargé en mémoire comme un arbre d'objets du tout, ce à quoi sert la couche d'accès direct dans PDFlibPas, couverte dans l'article sur la fusion et la division de PDF de plusieurs gigaoctets

Le code de dictionnaire, de gestion des couleurs, de répartition de flux de contenu, et de construction de chaînes discuté ici fait partie du PDFlibPas standard, la bibliothèque PDF de losLab pour Delphi et C++Builder, sans configuration supplémentaire nécessaire pour en bénéficier