Profiling Απόδοσης PDFlibPas: Ευρετήρια Hash σε Delphi

Το PDFlibPas, η βιβλιοθήκη PDF της losLab για Delphi και C++Builder, επιταχύνει τις διαδρομές απόδοσης και παραγωγής περιεχομένου αντικαθιστώντας τέσσερα μοτίβα επαναλαμβανόμενης εργασίας με αποσβεσμένα ισοδύναμα: ένα οκνηρό (lazy) ευρετήριο hash για αναζητήσεις κλειδιών λεξικού, έναν προϋπολογισμένο πίνακα αναζήτησης gamma sRGB, ομαδοποίηση κατά πρώτο byte για την αποστολή τελεστών content-stream, και TStringBuilder αντί επαναλαμβανόμενης συνένωσης συμβολοσειρών. Καμία από τις τέσσερις δεν προήλθε από μία εντυπωσιακή ανακάλυψη — προήλθαν όλες από το ίδιο ασυνήθιστα ατυχές μοτίβο σε ένα profile: μια μικρή συνάρτηση που καλείται μία φορά ανά τελεστή, μία φορά ανά pixel, ή μία φορά ανά χαρακτήρα, όπου ένα γραμμικό κόστος μέσα στην κλήση γίνεται τετραγωνικό ή σχεδόν τετραγωνικό σε ολόκληρο ένα έγγραφο. Αυτό είναι το κοινό νήμα εδώ: τέσσερις μικρές, φαινομενικά ασύνδετες διορθώσεις που επιτίθενται στο ίδιο σχήμα προβλήματος, μαζί με τα ειλικρινή όρια της καθεμιάς

Πού Ξοδεύει Πράγματι τον Χρόνο του ένας Renderer Content-Stream

Ο renderer content-stream του PDFlibPas διοχετεύει σχεδόν όλο το κόστος ανά token μέσα από τέσσερα στενά σημεία: αναζητήσεις λεξικού πόρων στα /Resources, /ColorSpace, /Font και /ExtGState· διόρθωση gamma σε κάθε αποκωδικοποιημένο pixel μιας εικόνας Lab, Indexed, ή με σήμανση ICC· αντιστοίχιση ονόματος τελεστή σε κάθε token κάθε content stream· και κατασκευή συμβολοσειρών όπου η βιβλιοθήκη χτίζει έξοδο — διαφυγή (escaping) κυριολεκτικών συμβολοσειρών κατά την αποθήκευση, εξαγωγή XFDF, επέκταση σφραγίδων και token μεταβλητών. Καθεμία από τις τέσσερις κάνει μια μικρή ποσότητα εργασίας από μόνη της, και καθεμία τρέχει χιλιάδες ή εκατομμύρια φορές πάνω σε ένα ρεαλιστικό έγγραφο, ακριβώς το σχήμα συνάρτησης όπου μια λεπτομέρεια υλοποίησης O(n) ή O(n²) σταματά να είναι αόρατη και γίνεται η κορυφαία καταχώριση του profile

Γιατί Επιβραδύνονται οι Αναζητήσεις Λεξικού Πόρων σε ένα Μεγάλο PDF;

Η TPDFDictionary.FindIndexByKeyName είναι αυτό που καλεί ο renderer για να επιλύσει κάθε αναζήτηση /Resources, /ColorSpace, /Font και /ExtGState, και παλαιότερα διέτρεχε τον πίνακα Entries από την αρχή σε κάθε κλήση — μια χαρά για ένα λεξικό Resources με τρεις καταχωρίσεις, ακριβό για μια Form XObject ή μια σελίδα με πολλά ExtGState όπου το ίδιο λεξικό εξετάζεται σε κάθε τελεστή που αγγίζει χρώμα ή κατάσταση γραφικών. Το PDFlibPas τώρα χτίζει ένα οκνηρό ευρετήριο hash μόλις ένα λεξικό ξεπεράσει το DICT_HASH_THRESHOLD (16) καταχωρίσεις και αφήνει τα μικρότερα λεξικά στη γραμμική σάρωση, αφού τα περισσότερα λεξικά PDF ποτέ δεν φτάνουν τόσο μεγάλα και ένας πίνακας hash για τρία κλειδιά θα κόστιζε περισσότερο να χτιστεί απ' όσο θα εξοικονομούσε. Το ευρετήριο είναι ένας επίπεδος πίνακας ανοιχτής διευθυνσιοδότησης με κλειδί το PLAnsiStringHash, ένα hash FNV-1a με την κανονική βάση μετατόπισης 2166136261 και τον πρώτο αριθμό 16777619, επιλεγμένο για να αποφευχθεί η εισαγωγή του System.Generics.Collections για κάτι τόσο ευαίσθητο στο μέγεθος

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;

Το ευρετήριο ακυρώνεται αντί να συντηρείται σταδιακά: κάθε κλήση που μεταβάλλει — AddEntry, DeleteEntryByKeyName, Assign, AddDict — καθαρίζει το hash και αφήνει την επόμενη αναζήτηση να το ξαναχτίσει από το μηδέν. Αυτό φαίνεται σπάταλο μέχρι να παρατηρήσετε ότι ένα κλειδί λεξικού είναι ένα αντικείμενο TPDFName, και η TPDFName.SetTo μπορεί να μετονομάσει ένα κλειδί που ήδη κάθεται στον πίνακα Entries ενός λεξικού χωρίς να περάσει από καμία από τις μεθόδους του ίδιου του λεξικού — ένα σταδιακό ευρετήριο δεν έχει τρόπο να παρατηρήσει αυτή τη μετονομασία, ενώ ένα οκνηρό απλώς ξαναχτίζεται και παραμένει σωστό από κατασκευής. Το τίμημα αυτής της ασφάλειας είναι μια ανακατασκευή O(n) την πρώτη φορά που ερωτάται ένα μεγάλο λεξικό μετά από μια εγγραφή, συν τη μνήμη για τον ίδιο τον πίνακα hash, περίπου ένα Integer ανά θέση σε συντελεστή πλήρωσης δύο τρίτων — ένα αμελητέο σφάλμα στρογγυλοποίησης για τα ελάχιστα υπερμεγέθη λεξικά ενός τυπικού εγγράφου, και ένα πραγματικό κόστος που το PDFlibPas αποφεύγει να πληρώνει σε κάθε μικρό διατηρώντας το όριο εκεί που είναι

Προϋπολογισμός Gamma sRGB Αντί για Κλήση Power ανά Pixel

Η TPDFSimpleColorManager.XYZ2RGB εφαρμόζει τη συνάρτηση μεταφοράς sRGB σε κάθε αποκωδικοποιημένο pixel μιας εικόνας Lab, Indexed, ή βασισμένης σε ICC — 1.055 * Power(x, 1/2.4) - 0.055 πάνω από το κατώφλι του γραμμικού τμήματος — και η Power(x, y) για κλασματικό y δεν έχει φθηνή κλειστή μορφή στο Pascal RTL: αναλύεται σε Ln(x) και μετά Exp(y * Ln(x)), και αυτό το ζεύγος υπερβατικών κλήσεων, που εκτελείται τρεις φορές ανά pixel για τα κανάλια κόκκινου, πράσινου και μπλε, είναι το κυρίαρχο κόστος στην αποκωδικοποίηση μιας εικόνας Lab ή ICC pixel προς pixel. Το PDFlibPas αντικαθιστά τις τρεις κλήσεις Power ανά pixel με μία αναζήτηση στο GSRGBGammaLUT, έναν πίνακα Double 4096 θέσεων που χτίζεται μία φορά μέσω της EnsureSRGBGammaLUT και ευρετηριάζεται στρογγυλοποιώντας την περιορισμένη είσοδο στην πλησιέστερη θέση

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;

Ένας πίνακας 4096 θέσεων πάνω στο εύρος εισόδου [0, 1] δίνει περίπου δεκαέξι φορές την ανάλυση ενός καναλιού εξόδου 8-bit, οπότε η κβαντοποίηση που εισάγει ο LUT βρίσκεται κάτω από αυτό που μπορεί να αναπαραστήσει το τελικό byte RGB — η αναζήτηση πίνακα αντικαθιστά εδώ τα υπερβατικά μαθηματικά χωρίς ορατό κόστος ακρίβειας. Η ίδια λογική εμφανίζεται δίπλα της στην Lab2XYZ, όπου η Power(LMN[i], 3) έγινε ένα απλό LMN[i]*LMN[i]*LMN[i]: μια ακέραια δύναμη δεν χρειάζεται καν Ln/Exp εξαρχής, οπότε αυτή δεν είναι καθόλου ανταλλαγή τύπου LUT, απλώς μια περιττή κλήση Power που αφαιρέθηκε. Το τέχνασμα του LUT αποδίδει μόνο επειδή η συνάρτηση μεταφοράς είναι μια καθαρή συνάρτηση ενός μοναδικού Double — δεν θα επεκτεινόταν καθαρά σε έναν μετασχηματισμό χρώματος που εξαρτιόταν από πολλές τιμές pixel ή από περισσότερη κατάσταση απ' αυτό

Πώς Αποστέλλετε 73 Τελεστές Content-Stream Γρήγορα;

Η ContentOperatorFromName καλείται μία φορά για κάθε token που διαβάζει το PDFlibPas από ένα content stream, αντιστοιχίζοντάς το με το πλήρες σύνολο των 73 τελεστών του Πίνακα 51 του ISO 32000-1 — από τα w και q έως τους σπάνια εμφανιζόμενους τελεστές μετρικών glyph Type 3 d0 και d1 — και παλαιότερα διέτρεχε γραμμικά αυτή τη λίστα σε κάθε μεμονωμένο token, οπότε μια σελίδα με μερικές χιλιάδες τελεστές σήμαινε μερικές χιλιάδες γραμμικές σαρώσεις πάνω στον ίδιο πίνακα 73 καταχωρίσεων. Το PDFlibPas τώρα ομαδοποιεί τον πίνακα κατά το πρώτο byte του τελεστή κατά την εκκίνηση, σε έναν σταθερό πίνακα θέσεων με ευρετήριο AnsiChar, οπότε μια αναζήτηση γίνεται ένα ευρετήριο πίνακα συν μια σάρωση μόνο των λίγων τελεστών που μοιράζονται εκείνον τον πρώτο χαρακτήρα

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 κάνουν διάκριση πεζών/κεφαλαίων — τα w και W, f και F, sc και SC είναι όλα διαφορετικοί τελεστές — οπότε το GOpBuckets έχει ως κλειδί το ακατέργαστο byte και η υπολειπόμενη σύγκριση μέσα σε μια ομάδα είναι μια απλή, ευαίσθητη σε πεζά/κεφαλαία ισότητα AnsiString. Ο πίνακας έχει μέγεθος 16 θέσεων ανά γράμμα, κάτι που καλύπτει άνετα τον σημερινό πίνακα — η πιο πολυάσχολη ομάδα, το T, κρατά δεκατρείς τελεστές, αφού σχεδόν κάθε τελεστής κατάστασης και τοποθέτησης κειμένου ξεκινά μ' αυτό — αλλά η EnsureOpBuckets σιωπηλά σταματά να προσθέτει σε μια ομάδα μόλις ο μετρητής της φτάσει τα 16, οπότε μια ομάδα που κάποτε θα χρειαζόταν δέκατη τέταρτη καταχώριση θα απέτυχε σιωπηλά αντί για δυνατά: ο τελεστής θα επιλυόταν σε coUnknown χωρίς καμία εξαίρεση να δείχνει το γιατί. Αυτό είναι το κόστος συντήρησης της ανταλλαγής μιας δομής δεδομένων που υποβαθμίζεται με χάρη για μία που δεν το κάνει — αποστέλλει γρηγορότερα γιατί ποτέ δεν χρειάζεται ελεγμένη ανάπτυξη ορίων, και χρειάζεται έναν άνθρωπο να παρακολουθεί τη μία ομάδα που πλησιάζει το ανώτατό της όριο

Αφαιρώντας το O(n²) από την Κατασκευή Συμβολοσειρών

Το μοτίβο του Pascal Result := Result + Fragment αναδιανέμει και αντιγράφει ολόκληρη τη συσσωρευμένη συμβολοσειρά σε κάθε επανάληψη, οπότε η κατασκευή μιας εξόδου N χαρακτήρων ένα θραύσμα τη φορά κοστίζει O(n²) αντί για O(n) — εύκολο να παραβλεφθεί σε review, αφού κάθε γραμμή φαίνεται σαν μια φθηνή προσάρτηση, και ακριβό στην πράξη γιατί η PLDirectEscapeLiteralString τρέχει σε κάθε κυριολεκτική συμβολοσειρά PDF που γράφεται κατά την αποθήκευση και η XFDFXMLEscape τρέχει σε κάθε τιμή πεδίου που εξάγεται σε XFDF. Το PDFlibPas διορθώνει τις δύο με διαφορετικές τεχνικές, επιλεγμένες βάσει του τι μπορεί να προβλέψει εκ των προτέρων η καθεμία συνάρτηση. Η PLDirectEscapeLiteralString γνωρίζει το μήκος εξόδου της πριν γράψει έστω κι ένα byte — ένα πέρασμα ταξινομεί κάθε χαρακτήρα ως απλό ή διαφεύγοντα και αθροίζει το σύνολο, η SetLength κατανέμει μία φορά, και ένα δεύτερο πέρασμα γεμίζει τον buffer κατά δείκτη. Η XFDFXMLEscape δεν μπορεί να προβλέψει φθηνά το μήκος εξόδου της, αφού το κείμενο πεδίου Unicode ποικίλλει υπερβολικά για να προϋπολογιστεί, οπότε αντ' αυτού προσαρτά σε ένα TStringBuilder προδιαστασιολογημένο περίπου στο μήκος της εισόδου

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;

Η επιλογή ανάμεσα στις δύο αφορά πραγματικά το τι γνωρίζετε πριν ξεκινήσει ο βρόχος. Η μέθοδος "μέτρα-και-γέμισε" είναι η γρηγορότερη από τις δύο όταν το μέγεθος εξόδου είναι φθηνό να υπολογιστεί, αφού δεν κάνει καμία ανακατανομή και καμία λογιστική πέρα από έναν μετρητή Integer, αλλά σημαίνει να γράφετε τη λογική ταξινόμησης δύο φορές — μία για να μετρήσετε, μία για να εκπέμψετε — κάτι που είναι δικός του κίνδυνος συντήρησης αν τα δύο αντίγραφα αποκλίνουν. Το TStringBuilder παραχωρεί λίγη από αυτή την κορυφαία απόδοση για να γράψει τη λογική μία φορά και να αποκτήσει αποσβεσμένες προσαρτήσεις O(1) από τη γεωμετρική ανάπτυξη buffer, κάτι που είναι η ασφαλέστερη προεπιλογή όποτε το μέγεθος εξόδου δεν είναι εύκολο να γνωρίζεται εκ των προτέρων

Πού Εφαρμόζεται Αυτό το Μοτίβο, και Πού Όχι

Και οι τέσσερις παραπάνω διορθώσεις είναι περιπτώσεις μιας ιδέας: βρείτε την κλήση που τρέχει μία φορά ανά μονάδα εισόδου — ανά κλειδί λεξικού, ανά pixel, ανά token τελεστή, ανά χαρακτήρα — και αντικαταστήστε το γραμμικό ή απρόβλεπτο κόστος της με έναν προϋπολογισμένο πίνακα, ένα ευρετήριο hash, ή έναν προδιαστασιολογημένο buffer. Τίποτα από αυτά δεν είναι ειδικό για PDF· μια υπηρεσία Delphi που επιλύει το ίδιο κλειδί αναζήτησης χιλιάδες φορές ανά αίτημα, μετατρέπει τιμές σε έναν στενό βρόχο, αποστέλλει βάσει ενός σταθερού λεξιλογίου tokens, ή χτίζει μακριές συμβολοσειρές έναν χαρακτήρα τη φορά, πέφτει στα ίδια σχήματα αποτυχίας και δέχεται τις ίδιες διορθώσεις. Αυτό που καμία από τις τέσσερις αλλαγές δεν αγγίζει είναι η συγχρονικότητα ή το αποτύπωμα μνήμης: μια γρηγορότερη μονοπύρηνη αναζήτηση λεξικού δεν κάνει τίποτα για δύο νήματα που ανταγωνίζονται στην ίδια παρουσία TPDFlib, κάτι που είναι ένα δομικό πρόβλημα που καλύπτεται ξεχωριστά στο άρθρο για την ασφάλεια νημάτων στην παράλληλη απόδοση σελίδων, και δεν κάνει τίποτα για ένα PDF πολύ μεγάλο για να φορτωθεί στη μνήμη ως δέντρο αντικειμένων, κάτι για το οποίο υπάρχει το επίπεδο Direct Access στο PDFlibPas, που καλύπτεται στο άρθρο για συγχώνευση και διαχωρισμό PDF μεγέθους gigabyte

Ο κώδικας λεξικών, διαχείρισης χρώματος, αποστολής content-stream και κατασκευής συμβολοσειρών που συζητήθηκε εδώ αποστέλλεται ως μέρος του τυπικού PDFlibPas, της βιβλιοθήκης PDF της losLab για Delphi και C++Builder, χωρίς να χρειάζεται καμία επιπλέον διαμόρφωση για να τα αποκτήσετε