LBlog Phát triển Phần mềm losLabGhi chú kỹ thuật dành cho các nhà phát triển phần mềm PDF, Delphi và tài liệu.

Bài viết kỹ thuật

Phân tích hiệu năng PDFlibPas: chỉ mục hash trong Delphi

Delphi PDF Library

PDFlibPas, thư viện PDF của losLab dành cho Delphi và C++Builder, tăng tốc các đường render và sinh nội dung của nó bằng cách thay bốn khuôn mẫu công việc lặp lại bằng các khuôn mẫu được khấu hao: một chỉ mục hash lười cho tra cứu khóa từ điển, một bảng tra cứu gamma sRGB tính sẵn, phân nhóm theo byte đầu cho việc phân phối toán tử content-stream, và TStringBuilder thay cho việc nối chuỗi lặp lại. Không cái nào trong bốn cái đến từ một khám phá kịch tính duy nhất — chúng đến từ cùng một khuôn mẫu không hào nhoáng trong một profile: một hàm nhỏ được gọi một lần cho mỗi khóa từ điển, một lần cho mỗi pixel, hay một lần cho mỗi ký tự, nơi một chi phí tuyến tính bên trong lệnh gọi trở thành bậc hai hay gần-bậc-hai trên toàn bộ một tài liệu. Đó là mạch xuyên suốt ở đây: bốn bản sửa nhỏ, trông không liên quan tấn công cùng một hình dạng vấn đề, cộng với các giới hạn trung thực của mỗi bản

Một bộ render content-stream thực sự dành thời gian của nó ở đâu

Bộ render content-stream của PDFlibPas dẫn gần như toàn bộ chi phí theo-từng-token qua bốn điểm hẹp: tra cứu từ điển tài nguyên trên /Resources, /ColorSpace, /Font, và /ExtGState; hiệu chỉnh gamma trên mỗi pixel đã giải mã của một ảnh Lab, Indexed, hay gắn nhãn ICC; so khớp tên toán tử trên mỗi token của mỗi content stream; và xây dựng chuỗi ở bất cứ đâu thư viện dựng đầu ra — escape chuỗi chữ nghĩa lúc lưu, xuất XFDF, mở rộng token dấu mộc và biến. Mỗi cái trong bốn cái tự thân làm một lượng công việc nhỏ, và mỗi cái chạy hàng nghìn hay hàng triệu lần trên một tài liệu thực tế, chính xác là hình dạng hàm nơi một chi tiết triển khai O(n) hay O(n²) ngừng vô hình và bắt đầu là mục hàng đầu của profile

Vì sao tra cứu từ điển tài nguyên trở nên chậm trong một PDF lớn?

TPDFDictionary.FindIndexByKeyName là thứ bộ render gọi để giải quyết mỗi tra cứu /Resources, /ColorSpace, /Font, và /ExtGState, và nó từng duyệt mảng Entries từ đầu ở mỗi lệnh gọi — ổn với một từ điển Resources ba mục, đắt đỏ với một Form XObject hay một trang nặng ExtGState nơi cùng từ điển bị thăm dò ở mỗi toán tử chạm vào màu sắc hay trạng thái đồ họa. PDFlibPas giờ dựng một chỉ mục hash lười một khi một từ điển vượt qua DICT_HASH_THRESHOLD (16) mục và để các từ điển nhỏ hơn ở lượt quét tuyến tính, vì hầu hết từ điển PDF không bao giờ lớn đến vậy và một bảng hash cho ba khóa sẽ tốn nhiều hơn để dựng so với những gì nó tiết kiệm được. Chỉ mục là một bảng địa chỉ mở phẳng được đánh khóa bởi PLAnsiStringHash, một hash FNV-1a với cơ sở offset kinh điển 2166136261 và số nguyên tố 16777619, được chọn để tránh kéo vào System.Generics.Collections cho thứ nhạy cảm về kích thước như thế này

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;

Chỉ mục bị vô hiệu hóa thay vì được duy trì tăng dần: mỗi lệnh gọi làm thay đổi — AddEntry, DeleteEntryByKeyName, Assign, AddDict — xóa hash và để lượt tra cứu tiếp theo dựng lại nó từ đầu. Điều đó trông lãng phí cho đến khi bạn nhận ra một khóa từ điển là một đối tượng TPDFName, và TPDFName.SetTo có thể đổi tên một khóa đã nằm trong mảng Entries của một từ điển mà không đi qua bất kỳ phương thức riêng nào của từ điển — một chỉ mục tăng dần không có cách nào để quan sát việc đổi tên đó, trong khi một chỉ mục lười chỉ đơn giản dựng lại và luôn đúng theo cấu trúc. Giá của sự an toàn đó là một lượt dựng lại O(n) lần đầu tiên một từ điển lớn được truy vấn sau một lượt ghi, cộng với bộ nhớ cho chính bảng hash, khoảng một Integer cho mỗi slot ở hệ số tải hai-phần-ba — một sai số làm tròn cho một nhúm từ điển quá khổ trong một tài liệu điển hình, và một chi phí thật mà PDFlibPas tránh trả cho mỗi từ điển nhỏ bằng cách giữ ngưỡng ở đúng vị trí

Tính sẵn gamma sRGB thay vì gọi Power cho mỗi pixel

TPDFSimpleColorManager.XYZ2RGB áp dụng hàm truyền sRGB cho mỗi pixel đã giải mã của một ảnh Lab, Indexed, hay dựa trên ICC — 1.055 * Power(x, 1/2.4) - 0.055 trên ngưỡng đoạn tuyến tính — và Power(x, y) cho một y phân số không có dạng đóng rẻ tiền nào trên RTL Pascal: nó phân rã thành Ln(x) rồi Exp(y * Ln(x)), và cặp lệnh gọi siêu việt đó, chạy ba lần cho mỗi pixel cho các kênh đỏ, xanh lá, và xanh dương, là chi phí chiếm ưu thế của việc giải mã một pixel ảnh Lab hay ICC từng pixel một. PDFlibPas thay ba lệnh gọi Power theo-từng-pixel bằng một lượt tra cứu vào GSRGBGammaLUT, một mảng Double 4096 mục được dựng một lần qua EnsureSRGBGammaLUT và được đánh chỉ số bằng cách làm tròn đầu vào đã kẹp đến slot gần nhất

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;

Một bảng 4096-slot trên phạm vi đầu vào [0, 1] cho ra khoảng mười sáu lần độ phân giải của một kênh đầu ra 8-bit, nên việc lượng tử hóa mà LUT đưa vào nằm dưới những gì byte RGB cuối cùng có thể biểu diễn — tra cứu bảng thay thế toán học siêu việt ở đây mà không có chi phí độ chính xác nhìn thấy được. Cùng lý lẽ đó xuất hiện cạnh nó trong Lab2XYZ, nơi Power(LMN[i], 3) trở thành một LMN[i]*LMN[i]*LMN[i] thuần túy: một lũy thừa nguyên ngay từ đầu không cần Ln/Exp, nên cái đó hoàn toàn không phải một sự đánh đổi LUT, chỉ là một lệnh gọi Power dư thừa bị loại bỏ. Thủ thuật LUT chỉ đem lại lợi ích vì hàm truyền là một hàm thuần túy của một Double đơn lẻ — nó sẽ không mở rộng gọn gàng sang một phép biến đổi màu phụ thuộc vào nhiều giá trị pixel hay nhiều trạng thái hơn thế

Làm sao để phân phối 73 toán tử content-stream nhanh chóng?

ContentOperatorFromName được gọi một lần cho mỗi token PDFlibPas đọc ra từ một content stream, so khớp nó với toàn bộ tập 73 toán tử của Bảng 51 ISO 32000-1 — từ w và q đến các toán tử số liệu glyph Type 3 hiếm khi thấy d0 và d1 — và nó từng duyệt danh sách đó tuyến tính ở mỗi token đơn lẻ, nên một trang với vài nghìn toán tử có nghĩa là vài nghìn lượt quét tuyến tính trên cùng bảng 73 mục. PDFlibPas giờ phân nhóm bảng theo byte đầu tiên của toán tử lúc khởi động, thành một mảng slot cố định được đánh chỉ số bởi AnsiChar, nên một lượt tra cứu trở thành một chỉ số mảng cộng một lượt quét chỉ trên nhúm toán tử chia sẻ ký tự đầu tiên đó

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;

Các toán tử PDF phân biệt hoa thường — w và W, f và F, sc và SC đều là các toán tử khác nhau — nên GOpBuckets đánh khóa theo byte thô và phép so sánh phần dư bên trong một nhóm là một phép so sánh bằng AnsiString thuần túy, phân biệt hoa thường. Mảng có kích thước 16 slot cho mỗi chữ cái, thoải mái bao phủ bảng hôm nay — nhóm bận rộn nhất, T, giữ mười ba toán tử, vì hầu như mọi toán tử trạng thái-văn-bản và định-vị-văn-bản đều bắt đầu bằng nó — nhưng EnsureOpBuckets âm thầm ngừng thêm vào một nhóm một khi số đếm của nó chạm 16, nên một nhóm nếu từng cần một mục thứ mười bốn sẽ thất bại âm thầm thay vì ồn ào: toán tử đó sẽ giải quyết thành coUnknown mà không có ngoại lệ nào chỉ ra vì sao. Đó là chi phí bảo trì của việc đánh đổi một cấu trúc dữ liệu suy giảm nhẹ nhàng lấy một cấu trúc không làm vậy — nó phân phối nhanh hơn vì nó không bao giờ cần một lượt tăng trưởng có kiểm tra biên, và nó cần một con người theo dõi nhóm duy nhất gần trần của nó

Cắt O(n²) ra khỏi việc xây dựng chuỗi

Khuôn mẫu Result := Result + Fragment của Pascal tái cấp phát và copy toàn bộ chuỗi đã tích lũy ở mỗi lượt lặp, nên việc xây dựng một đầu ra N-ký-tự từng mảnh một tốn O(n²) thay vì O(n) — dễ bị bỏ sót trong review, vì mỗi dòng trông như một lượt nối rẻ tiền, và tốn kém trong thực tế vì PLDirectEscapeLiteralString chạy trên mỗi chuỗi PDF chữ nghĩa được viết trong lúc lưu và XFDFXMLEscape chạy trên mỗi giá trị trường được xuất sang XFDF. PDFlibPas sửa hai cái bằng các kỹ thuật khác nhau, được chọn theo những gì mỗi hàm có thể dự đoán trước. PLDirectEscapeLiteralString biết độ dài đầu ra của nó trước khi viết một byte nào — một lượt phân loại mỗi ký tự là thuần túy hay được escape và cộng tổng, SetLength cấp phát một lần, và một lượt thứ hai điền vào bộ đệm theo chỉ số. XFDFXMLEscape không thể rẻ tiền dự đoán độ dài đầu ra của nó, vì văn bản trường Unicode thay đổi quá nhiều để tính trước, nên nó nối vào một TStringBuilder được định cỡ trước khoảng bằng độ dài đầu vào thay vào đó

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('&amp;');
        '<':  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;

Lựa chọn giữa hai cách thực sự là về những gì bạn biết trước khi vòng lặp bắt đầu. Đếm-rồi-điền là cách nhanh hơn trong hai khi kích thước đầu ra rẻ để tính, vì nó không tái cấp phát lần nào và không kế toán gì ngoài một bộ đếm Integer, nhưng nó có nghĩa là phải viết logic phân loại hai lần — một lần để đếm, một lần để phát ra — chính đó là một rủi ro bảo trì riêng nếu hai bản sao trôi dạt khỏi nhau. TStringBuilder từ bỏ một chút thông lượng đỉnh đó để đổi lấy việc viết logic một lần và có được các lượt nối O(1) khấu hao từ việc tăng trưởng bộ đệm theo cấp số nhân, mặc định an toàn hơn bất cứ khi nào kích thước đầu ra không dễ biết trước

Khuôn mẫu này áp dụng ở đâu, và không áp dụng ở đâu

Cả bốn bản sửa ở trên đều là các trường hợp của một ý tưởng: tìm lệnh gọi chạy một lần cho mỗi đơn vị đầu vào — mỗi khóa từ điển, mỗi pixel, mỗi token toán tử, mỗi ký tự — và thay chi phí tuyến tính hay khó dự đoán của nó bằng một bảng tính sẵn, một chỉ mục hash, hay một bộ đệm định cỡ trước. Không cái nào đặc thù cho PDF; một dịch vụ Delphi giải quyết cùng một khóa tra cứu hàng nghìn lần cho mỗi request, chuyển đổi giá trị trong một vòng lặp chặt, phân phối theo một từ vựng token cố định, hay xây dựng chuỗi dài từng ký tự một chạm phải cùng hình dạng lỗi và nhận cùng bản sửa. Điều mà không cái nào trong bốn thay đổi này chạm tới là tính đồng thời hay dung lượng bộ nhớ: một tra cứu từ điển đơn luồng nhanh hơn không làm gì cho hai luồng chạy đua trên cùng một instance TPDFlib, một vấn đề cấu trúc được nói đến riêng trong bài viết về an toàn luồng trong render trang song song, và nó không làm gì cho một PDF quá lớn để nạp vào bộ nhớ như một cây đối tượng ngay từ đầu, đó là điều lớp Direct Access trong PDFlibPas dành cho, được nói đến trong bài viết về gộp và tách PDF cỡ gigabyte

Code từ điển, quản lý màu sắc, phân phối content-stream, và xây dựng chuỗi được thảo luận ở đây đi kèm sẵn trong PDFlibPas tiêu chuẩn, thư viện PDF của losLab dành cho Delphi và C++Builder, không cần cấu hình thêm nào để có được bất kỳ điều nào trong số này