การ Profile ประสิทธิภาพของ PDFlibPas: Hash Index ใน Delphi

PDFlibPas ไลบรารี PDF ของ losLab สำหรับ Delphi และ C++Builder เร่งความเร็วเส้นทางการ render และการสร้างเนื้อหาของมันด้วยการแทนที่รูปแบบงานซ้ำสี่แบบด้วยรูปแบบที่ตัดจ่ายต้นทุนแล้ว คือ hash index แบบ lazy สำหรับการค้นหา key ของ dictionary, ตาราง lookup gamma sRGB ที่คำนวณไว้ล่วงหน้า, การจัดกลุ่มตามไบต์แรกสำหรับการ dispatch operator ของ content-stream และ TStringBuilder แทนที่การต่อ string ซ้ำๆ ไม่มีสักตัวในสี่ตัวนี้ที่มาจากการค้นพบที่น่าตื่นเต้นครั้งเดียว พวกมันมาจากรูปแบบที่ไม่หรูหราเดียวกันในผลการ profile คือฟังก์ชันเล็กๆ ที่ถูกเรียกครั้งเดียวต่อ operator, ครั้งเดียวต่อพิกเซล หรือครั้งเดียวต่อตัวอักษร ที่ต้นทุนเชิงเส้นภายในการเรียกกลายเป็นกำลังสองหรือใกล้เคียงกำลังสองข้ามทั้งเอกสาร นั่นคือเส้นด้ายที่ร้อยตรงนี้ คือการแก้ไขสี่อย่างเล็กๆ ที่ดูไม่เกี่ยวข้องกันซึ่งโจมตีปัญหารูปร่างเดียวกัน บวกขีดจำกัดที่ตรงไปตรงมาของแต่ละตัว

ตัว render content-stream ใช้เวลาไปกับอะไรจริงๆ

ตัว render content-stream ของ PDFlibPas ส่งต้นทุนต่อ token เกือบทั้งหมดผ่านสี่จุดที่แคบ คือการค้นหาใน resource dictionary บน /Resources, /ColorSpace, /Font และ /ExtGState; การแก้ gamma บนทุกพิกเซลที่ถอดรหัสแล้วของภาพแบบ Lab, Indexed หรือติด ICC; การจับคู่ชื่อ operator บนทุก token ของทุก content stream; และการสร้าง string ที่ใดก็ตามที่ไลบรารีสร้างเอาต์พุต การ escape literal string ตอนบันทึก, การ export XFDF, การขยาย token ตราประทับและตัวแปร แต่ละอย่างในสี่นี้ทำงานเพียงเล็กน้อยด้วยตัวเอง และแต่ละอย่างรันหลายพันหรือหลายล้านครั้งข้ามเอกสารจริงหนึ่งฉบับ ซึ่งเป็นรูปร่างพอดีของฟังก์ชันที่รายละเอียด implementation แบบ O(n) หรือ O(n²) หยุดที่จะมองไม่เห็นและเริ่มเป็น entry อันดับต้นของผลการ profile

ทำไมการค้นหา resource dictionary ถึงช้าลงใน PDF ขนาดใหญ่

TPDFDictionary.FindIndexByKeyName คือสิ่งที่ renderer เรียกเพื่อ resolve การค้นหา /Resources, /ColorSpace, /Font และ /ExtGState ทุกครั้ง และมันเคยเดินผ่าน array Entries จากด้านหน้าในทุกการเรียก ซึ่งใช้ได้ดีสำหรับ Resources dictionary สามรายการ แต่แพงสำหรับ Form XObject หรือหน้าที่หนัก ExtGState ที่ dictionary เดียวกันถูกตรวจสอบในทุก operator ที่แตะสีหรือ graphics state PDFlibPas ตอนนี้สร้าง hash index แบบ lazy เมื่อ dictionary ผ่าน entry DICT_HASH_THRESHOLD (16) รายการ และปล่อยให้ dictionary ที่เล็กกว่าใช้การสแกนเชิงเส้น เพราะ dictionary PDF ส่วนใหญ่ไม่เคยใหญ่ขนาดนั้น และ hash table สำหรับสาม key จะมีต้นทุนสร้างมากกว่าที่มันประหยัดได้ ตัว index เป็น open-addressing table แบบแบน key ด้วย PLAnsiStringHash ซึ่งเป็นแฮช FNV-1a ที่มี offset basis 2166136261 และ prime 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;

index ถูกทำให้ไม่ถูกต้องแทนที่จะบำรุงรักษาแบบค่อยเป็นค่อยไป ทุกการเรียกที่เปลี่ยนแปลงข้อมูล ได้แก่ AddEntry, DeleteEntryByKeyName, Assign, AddDict เคลียร์ hash และปล่อยให้การค้นหาครั้งถัดไปสร้างมันใหม่ตั้งแต่ต้น สิ่งนี้ดูสิ้นเปลืองจนกว่าคุณจะสังเกตเห็นว่า key ของ dictionary เป็น object TPDFName และ TPDFName.SetTo สามารถเปลี่ยนชื่อ key ที่นั่งอยู่ใน array Entries ของ dictionary แล้วได้โดยไม่ผ่าน method ใดๆ ของ dictionary เอง index แบบ incremental ไม่มีทางสังเกตการเปลี่ยนชื่อนั้นได้เลย ในขณะที่ index แบบ lazy แค่สร้างใหม่และยังคงถูกต้องโดยโครงสร้าง ราคาของความปลอดภัยนั้นคือการสร้างใหม่แบบ O(n) ครั้งแรกที่ dictionary ขนาดใหญ่ถูก query หลังการเขียน บวกกับหน่วยความจำสำหรับ hash table เอง ประมาณหนึ่ง Integer ต่อช่องที่ load factor สองในสาม เป็นข้อผิดพลาดในการปัดเศษสำหรับ dictionary ขนาดใหญ่เกินไปจำนวนหนึ่งกำมือในเอกสารทั่วไป และเป็นต้นทุนจริงที่ PDFlibPas หลีกเลี่ยงการจ่ายในทุก dictionary เล็กๆ ด้วยการรักษา threshold ไว้ที่ตำแหน่งเดิม

การคำนวณ Gamma sRGB ล่วงหน้าแทนการเรียก Power ต่อพิกเซล

TPDFSimpleColorManager.XYZ2RGB ใช้ฟังก์ชัน transfer sRGB กับทุกพิกเซลที่ถอดรหัสแล้วของภาพแบบ Lab, Indexed หรืออิง ICC คือ 1.055 * Power(x, 1/2.4) - 0.055 เหนือ threshold ส่วนเชิงเส้น และ Power(x, y) สำหรับ y แบบเศษส่วนไม่มีรูปแบบปิดที่ถูกใน Pascal RTL เลย มันแยกเป็น Ln(x) แล้ว Exp(y * Ln(x)) และคู่การเรียกทรานเซนเดนทัลนั้น รันสามครั้งต่อพิกเซลสำหรับช่องแดง, เขียว และน้ำเงิน เป็นต้นทุนหลักของการถอดรหัสภาพ Lab หรือ ICC ทีละพิกเซล PDFlibPas แทนที่การเรียก Power สามครั้งต่อพิกเซลด้วยการ lookup เดียวเข้า GSRGBGammaLUT ซึ่งเป็น array Double ขนาด 4096 รายการ สร้างครั้งเดียวผ่าน EnsureSRGBGammaLUT และ index ด้วยการปัดอินพุตที่ clamp แล้วไปยังช่องที่ใกล้ที่สุด

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 สุดท้ายจะแสดงได้ การ lookup ตารางแทนที่คณิตศาสตร์ทรานเซนเดนทัลตรงนี้โดยไม่มีต้นทุนความแม่นยำที่มองเห็นได้ เหตุผลเดียวกันปรากฏถัดจากมันใน Lab2XYZ ที่ Power(LMN[i], 3) กลายเป็น LMN[i]*LMN[i]*LMN[i] ธรรมดา กำลังจำนวนเต็มไม่ต้องการ Ln/Exp ตั้งแต่แรกเลย ดังนั้นตัวนี้ไม่ใช่การแลกเปลี่ยนแบบ LUT เลย แค่เป็นการเรียก Power ที่ซ้ำซ้อนถูกลบออกไป กลเม็ด LUT คุ้มค่าก็ต่อเมื่อฟังก์ชัน transfer เป็นฟังก์ชันบริสุทธิ์ของ Double ตัวเดียวเท่านั้น มันจะไม่ขยายได้อย่างสะอาดไปยัง color transform ที่ขึ้นอยู่กับค่าพิกเซลหลายค่าหรือ state มากกว่านั้น

คุณ Dispatch Operator ของ Content-Stream 73 ตัวให้เร็วได้อย่างไร

ContentOperatorFromName ถูกเรียกครั้งเดียวสำหรับทุก token ที่ PDFlibPas อ่านออกจาก content stream จับคู่มันกับชุด operator เต็ม 73 ตัวของ ISO 32000-1 Table 51 ตั้งแต่ w และ q ไปจนถึง operator เมตริก glyph Type 3 ที่หายากอย่าง d0 และ d1 และมันเคยเดินผ่านรายการนั้นแบบเชิงเส้นในทุก token เดียว ดังนั้นหน้าที่มี operator หลายพันตัวหมายถึงการสแกนเชิงเส้นหลายพันครั้งข้าม table 73 entry เดียวกัน PDFlibPas ตอนนี้จัดกลุ่ม table ตามไบต์แรกของ operator ตอน startup เข้าไปใน array ของช่อง index ด้วย AnsiChar คงที่ ดังนั้นการ lookup จึงกลายเป็น array index หนึ่งตัวบวกการสแกนแค่ operator จำนวนหนึ่งกำมือที่ใช้ตัวอักษรแรกร่วมกันเท่านั้น

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;

operator ของ PDF แยกตัวพิมพ์เล็กใหญ่ w กับ W, f กับ F, sc กับ SC ล้วนเป็น operator ที่ต่างกัน ดังนั้น GOpBuckets จึง key ด้วยไบต์ดิบ และการเปรียบเทียบที่เหลือภายในกลุ่มเป็นการเปรียบเทียบ AnsiString แบบแยกตัวพิมพ์ใหญ่เล็กธรรมดา array มีขนาด 16 ช่องต่อตัวอักษร ซึ่งครอบคลุม table ปัจจุบันได้อย่างสบายๆ กลุ่มที่ยุ่งที่สุดคือ T ถือ operator สิบสามตัว เพราะ operator ด้าน text-state และ text-positioning เกือบทุกตัวเริ่มด้วยมัน แต่ EnsureOpBuckets หยุดเพิ่มเข้ากลุ่มอย่างเงียบๆ ทันทีที่จำนวนของมันถึง 16 ดังนั้นกลุ่มที่ต้องการ entry ตัวที่สิบสี่จะล้มเหลวอย่างเงียบๆ แทนที่จะดัง operator จะ resolve เป็น coUnknown โดยไม่มี exception ชี้ว่าทำไม นั่นคือต้นทุนการบำรุงรักษาของการแลกโครงสร้างข้อมูลที่เสื่อมสภาพอย่างนุ่มนวลกับตัวที่ไม่เสื่อม มัน dispatch เร็วกว่าเพราะไม่เคยต้องการการขยายที่ตรวจสอบขอบเขต และต้องการมนุษย์เฝ้ากลุ่มเดียวที่ใกล้เพดานของมัน

การตัด O(n²) ออกจากการสร้าง String

รูปแบบ Result := Result + Fragment ของ Pascal จัดสรรใหม่และ copy string ที่สะสมไว้ทั้งหมดในทุกรอบ ดังนั้นการสร้างเอาต์พุต N ตัวอักษรทีละชิ้นจึงมีต้นทุน O(n²) แทนที่จะเป็น O(n) พลาดได้ง่ายใน review เพราะแต่ละบรรทัดดูเหมือนการต่อท้ายราคาถูกหนึ่งครั้ง และแพงในทางปฏิบัติเพราะ PLDirectEscapeLiteralString รันบนทุก literal PDF string ที่เขียนระหว่างการบันทึก และ XFDFXMLEscape รันบนทุกค่าฟิลด์ที่ export เข้า XFDF PDFlibPas แก้ทั้งสองด้วยเทคนิคที่ต่างกัน เลือกตามสิ่งที่แต่ละฟังก์ชันคาดการณ์ได้ล่วงหน้า PLDirectEscapeLiteralString รู้ความยาวเอาต์พุตของมันก่อนที่จะเขียนไบต์เดียว รอบแรกจัดประเภทแต่ละตัวอักษรว่าธรรมดาหรือ escape และรวมยอด 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;

การเลือกระหว่างสองวิธีนี้จริงๆ แล้วเป็นเรื่องของสิ่งที่คุณรู้ก่อนที่ loop จะเริ่ม นับ-แล้ว-เติม เร็วกว่าในสองวิธีเมื่อขนาดเอาต์พุตคำนวณได้ถูก เพราะมันไม่มีการจัดสรรใหม่เลยและไม่มีการทำบัญชีเกินกว่าตัวนับ Integer แต่มันหมายถึงการเขียน logic การจัดประเภทสองครั้ง ครั้งหนึ่งเพื่อนับ ครั้งหนึ่งเพื่อปล่อยออก ซึ่งเป็นความเสี่ยงด้านการบำรุงรักษาของตัวมันเองถ้าสองสำเนานั้นเลื่อนไหลออกจากกัน TStringBuilder ยอมสละ throughput สูงสุดนั้นไปเล็กน้อยเพื่อเขียน logic ครั้งเดียวและได้การต่อท้ายแบบ amortized O(1) จากการเติบโตของ buffer แบบเรขาคณิต ซึ่งเป็นค่าเริ่มต้นที่ปลอดภัยกว่าเมื่อใดก็ตามที่ขนาดเอาต์พุตไม่ง่ายที่จะรู้ล่วงหน้า

รูปแบบนี้ใช้ได้ที่ไหน และใช้ไม่ได้ที่ไหน

การแก้ไขทั้งสี่อย่างข้างต้นล้วนเป็นตัวอย่างของแนวคิดเดียว คือหาการเรียกที่รันครั้งเดียวต่อหน่วยของอินพุต ต่อ key ของ dictionary, ต่อพิกเซล, ต่อ token operator, ต่อตัวอักษร แล้วแทนที่ต้นทุนเชิงเส้นหรือคาดเดาไม่ได้ของมันด้วยตารางที่คำนวณไว้ล่วงหน้า, hash index หรือ buffer ที่กำหนดขนาดไว้ล่วงหน้า ไม่มีสักอย่างที่เจาะจงกับ PDF เลย service Delphi ที่ resolve key การค้นหาเดียวกันหลายพันครั้งต่อ request, แปลงค่าใน loop ที่แน่น, dispatch ตามคำศัพท์ token คงที่ หรือสร้าง string ยาวๆ ทีละตัวอักษร ล้วนชนรูปร่างความล้มเหลวเดียวกันและใช้ทางแก้เดียวกัน สิ่งที่การเปลี่ยนแปลงทั้งสี่นี้ไม่ได้แตะเลยคือ concurrency หรือ memory footprint การค้นหา dictionary แบบ single-threaded ที่เร็วขึ้นไม่ได้ทำอะไรเลยสำหรับสอง thread ที่แข่งกันบน TPDFlib instance เดียวกัน ซึ่งเป็นปัญหาเชิงโครงสร้างที่ครอบคลุมแยกต่างหากในบทความเรื่องความปลอดภัยของ thread ในการ render หน้าแบบขนาน และไม่ได้ทำอะไรเลยสำหรับ PDF ที่ใหญ่เกินกว่าจะโหลดเข้าหน่วยความจำเป็น object tree ได้เลย ซึ่งเป็นสิ่งที่ชั้น Direct Access ใน PDFlibPas มีไว้เพื่อสิ่งนั้น ครอบคลุมในบทความเรื่องการรวมและแยก PDF ขนาดกิกะไบต์

โค้ดด้าน dictionary, การจัดการสี, การ dispatch content-stream และการสร้าง string ที่กล่าวถึงตรงนี้มาพร้อมกับPDFlibPasรุ่นมาตรฐาน ไลบรารี PDF ของ losLab สำหรับ Delphi และ C++Builder โดยไม่ต้องตั้งค่าเพิ่มเติมใดๆ เพื่อให้ได้มันมา