פרופיילינג ביצועים ב-PDF Library for Delphi: אינדקסי hash ב-Delphi

PDF Library for Delphi, ספריית ה-PDF של losLab עבור Delphi ו-C++Builder, מאיצה את נתיבי העיבוד ויצירת-התוכן שלה על ידי החלפת ארבע תבניות עבודה-חוזרת בכאלה עם עלות מופחתת: אינדקס hash עצל עבור חיפושי מפתח-מילון, טבלת חיפוש (LUT) מחושבת-מראש עבור גמא sRGB, קיבוץ-לפי-בייט-ראשון עבור שיגור אופרטור זרם-תוכן, ו-TStringBuilder במקום צירוף מחרוזת חוזר. אף אחת מארבעת לא הגיעה מגילוי דרמטי אחד — הן הגיעו מאותה תבנית לא-זוהרת בפרופיל: פונקציה קטנה שנקראת פעם אחת לכל אופרטור, פעם אחת לכל פיקסל, או פעם אחת לכל תו, שבה עלות ליניארית בתוך הקריאה הופכת ריבועית או כמעט-ריבועית על פני מסמך שלם. זה החוט המקשר כאן: ארבעה תיקונים קטנים, בלתי-קשורים-במבט-ראשון, שתוקפים את אותה צורת בעיה, בתוספת הגבולות הכנים של כל אחד

איפה מעבד זרם-תוכן בפועל מבזבז את זמנו

מעבד זרם-התוכן של PDF Library for Delphi מזרים כמעט את כל העלות שלו לכל-טוקן דרך ארבע נקודות צרות: חיפושי מילון-משאב על /Resources, ‏/ColorSpace, ‏/Font, ו-/ExtGState; תיקון-גמא על כל פיקסל מפוענח של תמונת Lab, ‏Indexed, או מתויגת-ICC; התאמת שם-אופרטור על כל טוקן של כל זרם תוכן; ובניית מחרוזת בכל מקום שהספרייה בונה פלט — בריחת מחרוזת מילולית בשמירה, ייצוא XFDF, הרחבת טוקן חותמת ומשתנה. כל אחת מהארבע עושה כמות קטנה של עבודה בפני עצמה, וכל אחת רצה אלפים או מיליוני פעמים על פני מסמך ריאלי, שזו בדיוק הצורה של פונקציה שבה פרט מימוש O(n) או O(n²) מפסיק להיות בלתי-נראה ומתחיל להיות הרשומה העליונה של הפרופיל

למה חיפושי מילון-משאב הופכים איטיים ב-PDF גדול?

TPDFDictionary.FindIndexByKeyName היא מה שמעבד העיבוד קורא לו כדי לפתור כל חיפוש /Resources, ‏/ColorSpace, ‏/Font, ו-/ExtGState, והיא נהגה לעבור על מערך Entries מהחזית בכל קריאה — בסדר עבור מילון Resources בן שלוש-רשומות, יקר עבור Form XObject או עמוד כבד-ExtGState שבו אותו מילון נבדק בכל אופרטור שנוגע בצבע או מצב-גרפיקה. PDF Library for Delphi עכשיו בונה אינדקס 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
    // עדיין לא נבנה; מילונים קטנים נשארים ליניארים משום
    // שעלות הבנייה לא הייתה מופחתת (amortized) על פני קומץ רשומות.
    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 אחד לכל משבצת ביחס-עומס של שני-שליש — שגיאת עיגול עבור קומץ המילונים הגדולים-מדי במסמך טיפוסי, ועלות אמיתית ש-PDF Library for Delphi נמנעת מלשלם על כל מילון קטן על ידי שמירה על הסף היכן שהוא

חישוב-מראש של גמא sRGB במקום קריאה ל-Power לכל פיקסל

TPDFSimpleColorManager.XYZ2RGB מיישמת את פונקציית ההעברה sRGB על כל פיקסל מפוענח של תמונת Lab, ‏Indexed, או מבוססת-ICC — 1.055 * Power(x, 1/2.4) - 0.055 מעל סף המקטע-הליניארי — ול-Power(x, y) עבור y שברי אין נוסחה סגורה זולה ב-RTL של Pascal: היא מתפרקת ל-Ln(x) ואז Exp(y * Ln(x)), והזוג ההוא של קריאות טרנסצנדנטיות, רץ שלוש פעמים לכל פיקסל עבור ערוצי האדום, הירוק, והכחול, הוא העלות הדומיננטית של פענוח פיקסל תמונת Lab או ICC פיקסל-אחר-פיקסל. PDF Library for Delphi מחליפה את שלוש קריאות ה-Power לכל-פיקסל בחיפוש אחד לתוך 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-סיביות, כך שהקוונטיזציה שה-LUT מכניס יושבת מתחת למה שבייט ה-RGB הסופי יכול לייצג — חיפוש-טבלה מחליף מתמטיקה טרנסצנדנטית כאן בלי עלות דיוק נראית לעין. אותו היגיון מופיע לצידו ב-Lab2XYZ, שם Power(LMN[i], 3) הפכה ל-LMN[i]*LMN[i]*LMN[i] פשוט: חזקה שלמה לא זקוקה ל-Ln/Exp מלכתחילה, כך שזו בכלל לא פשרת-LUT, סתם קריאת Power מיותרת שהוסרה. תחבולת ה-LUT משתלמת רק משום שפונקציית ההעברה היא פונקציה טהורה של Double בודד — היא לא הייתה מתרחבת בנקיות לטרנספורמציית צבע שהייתה תלויה בכמה ערכי פיקסל או ביותר מצב מזה

איך אתה משגר 73 אופרטורי זרם-תוכן מהר?

ContentOperatorFromName נקראת פעם אחת עבור כל טוקן ש-PDF Library for Delphi קוראת מחוץ לזרם תוכן, מתאימה אותו מול קבוצת ה-73 אופרטורים המלאה של ISO 32000-1 טבלה 51 — מ-w ו-q עד d0 ו-d1 אופרטורי מדדי-גליף Type 3 שנראים לעיתים רחוקות — והיא נהגה לעבור על הרשימה ההיא ליניארית בכל טוקן בודד, כך שעמוד עם כמה אלפי אופרטורים אמר כמה אלפי סריקות ליניאריות על אותה טבלה בת 73-רשומות. PDF Library for Delphi עכשיו מקבצת את הטבלה לפי הבייט הראשון של האופרטור בהתחלה, לתוך מערך משבצות ממופתח-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 ממפתחת לפי הבייט הגולמי וההשוואה השארית בתוך משבצת היא שוויון AnsiString פשוט, תלוי-רישיות. המערך בגודל 16 משבצות לכל אות, שמכסה בנוחות את הטבלה של היום — המשבצת העמוסה ביותר, ‏T, מחזיקה שלושה-עשר אופרטורים, שכן כמעט כל אופרטור מצב-טקסט ומיקום-טקסט מתחיל בה — אבל EnsureOpBuckets בשקט מפסיקה להוסיף למשבצת ברגע שהספירה שלה מגיעה ל-16, כך שמשבצת שאי-פעם תזדקק לרשומה ארבע-עשרה תיכשל בשקט ולא בקול: האופרטור ייפתר ל-coUnknown ללא שום חריגה שמצביעה למה. זו עלות התחזוקה של החלפת מבנה-נתונים שמתדרדר בחן באחד שלא — הוא משגר מהר יותר משום שהוא אף פעם לא זקוק לגדילה נבדקת-גבולות, והוא זקוק לבן-אדם שמשגיח על המשבצת האחת הקרובה לתקרה שלה

הוצאת O(n²) מתוך בניית מחרוזת

תבנית Result := Result + Fragment של Pascal מקצה מחדש ומעתיקה את כל המחרוזת הצבורה בכל איטרציה, כך שבניית פלט בן N-תווים פיסה-בכל-פעם עולה O(n²) במקום O(n) — קל לפספס בסקירה, שכן כל שורה נראית כצירוף זול אחד, ויקר בפועל משום ש-PLDirectEscapeLiteralString רצה על כל מחרוזת PDF מילולית שנכתבת במהלך שמירה ו-XFDFXMLEscape רצה על כל ערך שדה שמיוצא ל-XFDF. PDF Library for Delphi מתקנת את השתיים בטכניקות שונות, נבחרות לפי מה שכל פונקציה יכולה לחזות מראש. ‏PLDirectEscapeLiteralString יודעת את אורך הפלט שלה לפני כתיבת בייט בודד — מעבר אחד מסווג כל תו כרגיל או בורח וסוכם את הסך, ‏SetLength מקצה פעם אחת, ומעבר שני ממלא את המאגר לפי אינדקס. ‏XFDFXMLEscape לא יכולה לחזות בזול את אורך הפלט שלה, שכן טקסט שדה יוניקוד משתנה יותר מדי כדי לחשב מראש, כך שהיא מצרפת לתוך TStringBuilder קדם-מוגדל בערך לגודל הקלט במקום זאת

Function XFDFXMLEscape(Const W: WideString): WideString;
Var
  I: Integer;
  Builder: TStringBuilder;
Begin
  // TStringBuilder נמנעת מצירוף ה-WideString בסיבוכיות O(n^2) ש-
  // ייצוא XFDF נהג להיתקל בו על כל ערך שדה
  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 ו-LF פועלים באותה צורה
      Else
        Builder.Append(W[I]);
      End;
    End;
    Result:= Builder.ToString;
  Finally
    Builder.Free;
  End;
End;

הבחירה בין השתיים היא באמת לגבי מה שאתה יודע לפני שהלולאה מתחילה. ספור-ואז-מלא היא המהירה מבין השתיים כשגודל הפלט זול לחישוב, שכן היא עושה אפס הקצאות-מחדש ואין חשבונאות מעבר למונה Integer, אבל זה אומר כתיבת לוגיקת הסיווג פעמיים — פעם אחת לספור, פעם אחת לפלוט — שהיא סיכון תחזוקה משלה אם שני העותקים סוחפים זה מזה. ‏TStringBuilder מוותרת על מעט מתפוקת-השיא ההיא עבור כתיבת הלוגיקה פעם אחת וקבלת צירופים O(1) מופחתים מגדילת מאגר גיאומטרית, שברירת המחדל הבטוחה יותר בכל פעם שגודל הפלט לא קל לדעת מראש

איפה התבנית הזו חלה, ואיפה לא

כל ארבעת התיקונים לעיל הם מופעים של רעיון אחד: מצא את הקריאה שרצה פעם אחת לכל יחידת קלט — לכל מפתח-מילון, לכל פיקסל, לכל טוקן-אופרטור, לכל תו — והחלף את העלות הליניארית או הבלתי-צפויה שלה בטבלה מחושבת-מראש, אינדקס hash, או מאגר קדם-מוגדל. שום דבר מזה ספציפי ל-PDF; שירות Delphi שפותר את אותו מפתח-חיפוש אלפי פעמים לבקשה, ממיר ערכים בלולאה צפופה, משגר על אוצר-מילים קבוע של טוקנים, או בונה מחרוזות ארוכות תו-בכל-פעם פוגע באותן צורות-כשל ולוקח את אותם תיקונים. מה שאף אחד מארבעת השינויים האלה לא נוגע בו הוא concurrency או טביעת-רגל-זיכרון: חיפוש-מילון חד-תהליכוני מהיר יותר לא עושה כלום עבור שני תהליכונים שמתחרים על אותו מופע TPDFlib, שהיא בעיה מבנית המכוסה בנפרד בהמאמר על בטיחות-תהליכונים בעיבוד עמודים מקבילי, והיא לא עושה כלום עבור PDF גדול מדי מכדי להיטען לזיכרון כעץ אובייקטים בכלל, שזה מה ששכבת ה-Direct Access ב-PDF Library for Delphi נועדה עבורו, מכוסה בהמאמר על מיזוג ופיצול קובצי PDF בני-גיגה-בייט

קוד המילון, ניהול-הצבע, שיגור-זרם-התוכן, ובניית-המחרוזת הנדונים כאן נשלחים כחלק מPDF Library for Delphi הסטנדרטי, ספריית ה-PDF של losLab עבור Delphi ו-C++Builder, ללא הגדרה נוספת נדרשת כדי לקבל את זה