Profiling Performa PDFlibPas: Hash Index di Delphi

PDFlibPas, library PDF losLab untuk Delphi dan C++Builder, mempercepat jalur rendering dan pembuatan-konten-nya dengan mengganti empat pola pekerjaan-berulang dengan yang teramortisasi: sebuah hash index malas untuk lookup key dictionary, sebuah tabel lookup gamma sRGB yang dihitung lebih dulu, pengelompokan byte-pertama untuk dispatch operator content-stream, dan TStringBuilder menggantikan konkatenasi string berulang. Tak satu pun dari keempatnya berasal dari satu penemuan dramatis — mereka berasal dari pola yang sama yang kurang glamor dalam sebuah profil: sebuah fungsi kecil yang dipanggil sekali per operator, sekali per piksel, atau sekali per karakter, di mana sebuah biaya linear di dalam pemanggilan itu menjadi kuadratik atau nyaris-kuadratik di seluruh sebuah dokumen. Itulah benang merah di sini: empat perbaikan kecil yang terlihat tidak berkaitan yang menyerang bentuk masalah yang sama, plus batas jujur masing-masing

Di Mana Sebenarnya Sebuah Renderer Content-Stream Menghabiskan Waktunya

Renderer content-stream milik PDFlibPas menyalurkan hampir semua biaya per-token-nya lewat empat titik sempit: lookup dictionary resource pada /Resources, /ColorSpace, /Font, dan /ExtGState; koreksi gamma pada setiap piksel terdekode sebuah gambar Lab, Indexed, atau ber-tag-ICC; pencocokan nama-operator pada setiap token dari setiap content stream; dan konstruksi string di mana pun library ini membangun output — escaping string literal saat save, ekspor XFDF, ekspansi token stamp dan variable. Masing-masing dari keempatnya melakukan sedikit pekerjaan dengan sendirinya, dan masing-masing berjalan ribuan atau jutaan kali di atas sebuah dokumen realistis, yang persis merupakan bentuk fungsi di mana sebuah detail implementasi O(n) atau O(n²) berhenti tidak terlihat dan mulai menjadi entri teratas profil

Mengapa Lookup Dictionary Resource Menjadi Lambat dalam Sebuah PDF Besar?

TPDFDictionary.FindIndexByKeyName adalah yang dipanggil renderer untuk menyelesaikan setiap lookup /Resources, /ColorSpace, /Font, dan /ExtGState, dan dulunya menelusuri array Entries dari depan pada setiap pemanggilan — baik-baik saja untuk sebuah dictionary Resources tiga-entri, mahal untuk sebuah Form XObject atau sebuah halaman berat-ExtGState di mana dictionary yang sama diperiksa pada setiap operator yang menyentuh warna atau graphics state. PDFlibPas sekarang membangun sebuah hash index malas begitu sebuah dictionary melewati DICT_HASH_THRESHOLD (16) entri dan membiarkan dictionary lebih kecil pada pemindaian linear, karena kebanyakan dictionary PDF tidak pernah sebesar itu dan sebuah hash table untuk tiga key akan lebih mahal dibangun daripada yang dihematnya. Index-nya adalah sebuah tabel open-addressing datar yang dikunci PLAnsiStringHash, sebuah hash FNV-1a dengan offset basis kanonik 2166136261 dan prime 16777619, dipilih untuk menghindari menarik System.Generics.Collections untuk sesuatu yang sensitif-ukuran ini

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 itu dibatalkan alih-alih dipelihara secara inkremental: setiap pemanggilan pengubah — AddEntry, DeleteEntryByKeyName, Assign, AddDict — mengosongkan hash dan membiarkan lookup berikutnya membangunnya ulang dari nol. Itu terlihat boros sampai Anda memperhatikan bahwa sebuah key dictionary adalah sebuah objek TPDFName, dan TPDFName.SetTo bisa mengganti nama sebuah key yang sudah duduk dalam array Entries sebuah dictionary tanpa melalui metode dictionary itu sendiri mana pun — sebuah index inkremental tidak punya cara mengamati pergantian nama itu, sementara yang malas sekadar membangun ulang dan tetap benar berdasarkan konstruksi. Harga keamanan itu adalah sebuah rebuild O(n) kali pertama sebuah dictionary besar dikueri setelah sebuah penulisan, plus memori untuk hash table itu sendiri, kira-kira satu Integer per slot pada faktor beban dua-pertiga — sebuah kesalahan pembulatan untuk segelintir dictionary berlebih-ukuran dalam sebuah dokumen tipikal, dan biaya sungguhan yang dihindari PDFlibPas membayarnya pada setiap yang kecil dengan menjaga ambangnya di tempatnya

Menghitung Lebih Dulu Gamma sRGB Alih-alih Memanggil Power Per Piksel

TPDFSimpleColorManager.XYZ2RGB menerapkan fungsi transfer sRGB pada setiap piksel terdekode sebuah gambar Lab, Indexed, atau berbasis-ICC — 1.055 * Power(x, 1/2.4) - 0.055 di atas ambang segmen-linear — dan Power(x, y) untuk sebuah y pecahan tidak memiliki bentuk tertutup murah di RTL Pascal: ia terurai menjadi Ln(x) lalu Exp(y * Ln(x)), dan pasangan pemanggilan transendental itu, dijalankan tiga kali per piksel untuk kanal merah, hijau, dan biru, adalah biaya dominan mendekode sebuah piksel gambar Lab atau ICC per piksel. PDFlibPas mengganti ketiga pemanggilan Power per-piksel dengan satu lookup ke dalam GSRGBGammaLUT, sebuah array Double 4096-entri yang dibangun sekali lewat EnsureSRGBGammaLUT dan diindeks dengan membulatkan input yang di-clamp ke slot terdekat

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;

Sebuah tabel 4096-slot di atas rentang input [0, 1] memberikan kira-kira enam belas kali resolusi sebuah kanal output 8-bit, sehingga kuantisasi yang diperkenalkan LUT berada di bawah apa yang bisa direpresentasikan byte RGB final — lookup tabel menggantikan matematika transendental di sini tanpa biaya presisi yang terlihat. Alasan yang sama muncul di sebelahnya di Lab2XYZ, di mana Power(LMN[i], 3) menjadi LMN[i]*LMN[i]*LMN[i] polos: sebuah power integer sejak awal tidak membutuhkan Ln/Exp, sehingga yang itu sama sekali bukan sebuah trade-off LUT, hanya sebuah pemanggilan Power redundan yang dihapus. Trik LUT hanya membuahkan hasil karena fungsi transfer itu adalah sebuah fungsi murni dari satu Double tunggal — ia tidak akan meluas dengan bersih ke sebuah transform warna yang bergantung pada beberapa nilai piksel atau lebih banyak state daripada itu

Bagaimana Anda Men-dispatch 73 Operator Content-Stream dengan Cepat?

ContentOperatorFromName dipanggil sekali untuk setiap token yang dibaca PDFlibPas dari sebuah content stream, mencocokkannya terhadap seluruh set 73 operator ISO 32000-1 Table 51 — dari w dan q hingga operator metrik-glyph Type 3 d0 dan d1 yang jarang terlihat — dan dulunya menelusuri daftar itu secara linear pada setiap token tunggal, sehingga sebuah halaman dengan beberapa ribu operator berarti beberapa ribu pemindaian linear di atas tabel 73-entri yang sama. PDFlibPas sekarang mengelompokkan tabel itu berdasarkan byte-pertama operator saat startup, ke dalam sebuah array slot ber-indeks-AnsiChar tetap, sehingga sebuah lookup menjadi satu indeks array plus sebuah pemindaian hanya segelintir operator yang berbagi karakter pertama itu

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 case-sensitive — w dan W, f dan F, sc dan SC semuanya operator berbeda — sehingga GOpBuckets mengunci pada byte mentah dan perbandingan residual di dalam sebuah bucket adalah sebuah kesetaraan AnsiString case-sensitive polos. Array itu berukuran 16 slot per huruf, yang mencakup nyaman tabel hari ini — bucket tersibuk, T, memegang tiga belas operator, karena hampir setiap operator text-state dan text-positioning dimulai dengannya — tetapi EnsureOpBuckets diam-diam berhenti menambah ke sebuah bucket begitu hitungannya mencapai 16, sehingga sebuah bucket yang pernah membutuhkan entri keempat belas akan gagal secara diam-diam alih-alih keras: operator itu akan terselesaikan menjadi coUnknown tanpa exception yang menunjuk mengapa. Itulah biaya pemeliharaan menukar sebuah struktur data yang menurun dengan anggun untuk yang tidak — ia men-dispatch lebih cepat karena tidak pernah membutuhkan sebuah grow bounds-checked, dan ia membutuhkan seorang manusia yang mengawasi satu bucket yang dekat dengan batasnya

Memotong O(n²) dari Pembangunan String

Pola Result := Result + Fragment milik Pascal mengalokasikan ulang dan menyalin seluruh string terakumulasi pada setiap iterasi, sehingga membangun sebuah output N-karakter satu fragmen pada satu waktu menelan biaya O(n²) alih-alih O(n) — mudah terlewat dalam review, karena setiap baris terlihat seperti satu append murah, dan mahal dalam praktik karena PLDirectEscapeLiteralString berjalan pada setiap string literal PDF yang ditulis selama save dan XFDFXMLEscape berjalan pada setiap nilai field yang diekspor ke XFDF. PDFlibPas memperbaiki keduanya dengan teknik berbeda, dipilih berdasarkan apa yang bisa diprediksi masing-masing fungsi lebih dulu. PLDirectEscapeLiteralString mengetahui panjang outputnya sebelum menulis satu byte pun — satu lintasan mengklasifikasikan setiap karakter sebagai polos atau di-escape dan menjumlahkan totalnya, SetLength mengalokasikan sekali, dan lintasan kedua mengisi buffer berdasarkan indeks. XFDFXMLEscape tidak bisa dengan murah memprediksi panjang outputnya, karena teks field Unicode bervariasi terlalu banyak untuk dihitung lebih dulu, sehingga ia menambahkan ke dalam sebuah TStringBuilder yang pra-berukuran kira-kira panjang input sebagai gantinya

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;

Pilihan di antara keduanya sebenarnya tentang apa yang Anda ketahui sebelum loop dimulai. Count-then-fill lebih cepat dari keduanya ketika ukuran output murah dihitung, karena ia melakukan nol realokasi dan tidak ada pembukuan di luar sebuah counter Integer, tetapi itu berarti menulis logika klasifikasi dua kali — sekali untuk menghitung, sekali untuk memancarkan — yang merupakan risiko pemeliharaannya sendiri jika kedua salinan itu melenceng terpisah. TStringBuilder mengorbankan sedikit throughput puncak itu untuk menulis logika sekali dan mendapatkan append O(1) teramortisasi dari pertumbuhan buffer geometrik, yang merupakan default yang lebih aman kapan pun ukuran output tidak mudah diketahui lebih dulu

Di Mana Pola Ini Berlaku, dan Di Mana Tidak

Keempat perbaikan di atas adalah instance dari satu ide: temukan pemanggilan yang berjalan sekali per unit input — per key dictionary, per piksel, per token operator, per karakter — dan gantikan biaya linear atau tak terprediksinya dengan sebuah tabel yang dihitung lebih dulu, sebuah hash index, atau sebuah buffer pra-berukuran. Tak satu pun dari itu spesifik untuk PDF; sebuah service Delphi yang menyelesaikan key lookup yang sama ribuan kali per request, mengonversi nilai dalam sebuah loop ketat, men-dispatch pada sebuah kosakata token tetap, atau membangun string panjang satu karakter pada satu waktu menabrak bentuk kegagalan yang sama dan mengambil perbaikan yang sama. Yang tidak disentuh keempat perubahan ini adalah konkurensi atau jejak memori: sebuah lookup dictionary single-threaded yang lebih cepat tidak melakukan apa-apa untuk dua thread yang berlomba pada instance TPDFlib yang sama, yang merupakan sebuah masalah struktural yang dibahas terpisah di artikel tentang thread safety dalam rendering halaman paralel, dan tidak melakukan apa-apa untuk sebuah PDF yang terlalu besar untuk dimuat ke dalam memori sebagai sebuah object tree sama sekali, yang untuk itulah lapisan Direct Access di PDFlibPas ada, dibahas di artikel tentang menggabung dan membelah PDF berukuran gigabyte

Kode dictionary, manajemen-warna, dispatch content-stream, dan pembangunan-string yang dibahas di sini disertakan sebagai bagian dari PDFlibPas standar, library PDF losLab untuk Delphi dan C++Builder, tanpa konfigurasi ekstra yang dibutuhkan untuk mendapatkan semuanya