PDFlibPas Performans Profilleme: Delphi'de Hash İndeksleri

losLab'ın Delphi ve C++Builder için PDF kütüphanesi olan PDFlibPas, render ve içerik üretim yollarını, dört tekrarlanan-iş örüntüsünü amortize edilmiş olanlarla değiştirerek hızlandırır: sözlük anahtarı aramaları için tembel bir hash indeksi, önceden hesaplanmış bir sRGB gama arama tablosu, içerik akışı operatör gönderimi için ilk-bayt kovalaması ve tekrarlanan dize birleştirmesi yerine TStringBuilder. Dördünün hiçbiri tek bir çarpıcı keşiften gelmedi -bir profildeki aynı sıradan örüntüden geldiler: operatör başına, piksel başına veya karakter başına bir kez çağrılan küçük bir fonksiyon, burada çağrı içindeki doğrusal bir maliyet, tüm bir belge genelinde ikinci dereceden veya neredeyse ikinci dereceden hale gelir. Buradaki ortak iplik budur: aynı sorun şeklini hedefleyen dört küçük, birbiriyle ilgisiz görünen düzeltme, artı her birinin dürüst sınırları

Bir içerik akışı render motoru zamanını gerçekte nerede harcar?

PDFlibPas'ın içerik akışı render motoru, token başına neredeyse tüm maliyetini dört dar noktaya yönlendirir: /Resources, /ColorSpace, /Font ve /ExtGState üzerinde kaynak sözlüğü aramaları; bir Lab, Indexed veya ICC-etiketli görüntünün her kod çözülmüş pikselinde gama düzeltmesi; her içerik akışının her token'ında operatör-adı eşleştirmesi; ve kütüphanenin çıktı kurduğu her yerde dize kurma -kayıtta gerçek PDF dizesi kaçışı, XFDF dışa aktarımı, damga ve değişken token genişletmesi. Dördü de kendi başına küçük bir miktar iş yapar ve her biri gerçekçi bir belge üzerinde binlerce veya milyonlarca kez çalışır ki bu, bir O(n) veya O(n²) uygulama detayının görünmez olmaktan çıkıp profilin en üst girdisi olmaya başladığı tam olarak bu tür fonksiyonun şeklidir

Kaynak sözlüğü aramaları büyük bir PDF'te neden yavaşlar?

TPDFDictionary.FindIndexByKeyName, render motorunun her /Resources, /ColorSpace, /Font ve /ExtGState aramasını çözmek için çağırdığı şeydir ve eskiden her çağrıda Entries dizisini önden dolaşırdı -üç girdilik bir Resources sözlüğü için sorunsuz, aynı sözlüğün rengi veya grafik durumunu dokunan her operatörde araştırıldığı bir Form XObject veya ExtGState-yoğun bir sayfa için pahalı. PDFlibPas artık bir sözlük DICT_HASH_THRESHOLD (16) girdisini geçtiğinde tembel bir hash indeksi kurar ve daha küçük sözlükleri doğrusal taramada bırakır, çünkü çoğu PDF sözlüğü hiçbir zaman bu kadar büyümez ve üç anahtar için bir hash tablosu, tasarruf ettiğinden daha fazlasına mal olur. İndeks, PLAnsiStringHash ile anahtarlanan düz bir açık-adresleme tablosudur; kanonik ofset tabanı 2166136261 ve asal 16777619 olan bir FNV-1a hash'i, bu boyuta duyarlı bir şey için System.Generics.Collections'ı çekmekten kaçınmak için seçilmiştir

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;

İndeks, artımlı olarak korunmak yerine geçersiz kılınır: her değiştiren çağrı -AddEntry, DeleteEntryByKeyName, Assign, AddDict- hash'i temizler ve bir sonraki aramanın onu sıfırdan yeniden kurmasına izin verir. Bir sözlük anahtarının bir TPDFName nesnesi olduğunu ve TPDFName.SetTo'nun, sözlüğün kendi metotlarından hiçbirinden geçmeden zaten bir sözlüğün Entries dizisinde oturan bir anahtarı yeniden adlandırabildiğini fark edene kadar bu israf gibi görünür -artımlı bir indeksin o yeniden adlandırmayı gözlemlemesinin hiçbir yolu yoktur, oysa tembel bir tanesi basitçe yeniden kurulur ve yapı gereği doğru kalır. Bu güvenliğin bedeli, bir yazmadan sonra büyük bir sözlük ilk sorgulandığında O(n)'lik bir yeniden kurulum, artı hash tablosunun kendisi için bellek, üçte iki dolu faktörde slot başına kabaca bir Integer -tipik bir belgedeki bir avuç aşırı büyük sözlük için yuvarlama hatası ve PDFlibPas'ın eşiği olduğu yerde tutarak her küçük sözlükte ödemekten kaçındığı gerçek bir maliyet

Piksel başına Power çağırmak yerine sRGB gamayı önceden hesaplamak

TPDFSimpleColorManager.XYZ2RGB, bir Lab, Indexed veya ICC tabanlı görüntünün her kod çözülmüş pikseline sRGB aktarım fonksiyonunu uygular -doğrusal-segment eşiğinin üzerinde 1.055 * Power(x, 1/2.4) - 0.055- ve kesirli bir y için Power(x, y)'nin Pascal RTL'inde ucuz bir kapalı formu yoktur: Ln(x)'e sonra Exp(y * Ln(x))'e ayrışır ve kırmızı, yeşil ve mavi kanallar için piksel başına üç kez çalıştırılan bu aşkın çağrı çifti, bir Lab veya ICC görüntüsünü piksel piksel kod çözmenin baskın maliyetidir. PDFlibPas, piksel başına üç Power çağrısını, EnsureSRGBGammaLUT aracılığıyla bir kez kurulan ve girdiği kırpılmış girişi en yakın slota yuvarlayarak indekslenen 4096 girdilik bir Double dizisi olan GSRGBGammaLUT'a tek bir arama ile değiştirir

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;

[0, 1] girdi aralığı üzerinde 4096 slotlu bir tablo, 8-bit bir çıktı kanalının çözünürlüğünün kabaca on altı katını verir; bu yüzden LUT'un getirdiği nicemleme, son RGB baytının temsil edebileceğinin altında oturur -tablo araması burada aşkın matematiği görünür bir hassasiyet maliyeti olmadan değiştirir. Aynı gerekçe, Lab2XYZ'de yanında ortaya çıkar; burada Power(LMN[i], 3), düz bir LMN[i]*LMN[i]*LMN[i] haline geldi: bir tam sayı kuvveti en baştan Ln/Exp'e ihtiyaç duymaz; bu yüzden o hiç bir LUT ödünleşimi değildir, yalnızca kaldırılmış gereksiz bir Power çağrısıdır. LUT numarası yalnızca aktarım fonksiyonu tek bir Double'ın saf bir fonksiyonu olduğu için işe yarar -birkaç piksel değerine veya bundan daha fazla duruma bağlı bir renk dönüşümüne temiz bir şekilde genişlemezdi

73 içerik akışı operatörünü nasıl hızlı gönderirsiniz?

ContentOperatorFromName, PDFlibPas'ın bir içerik akışından okuduğu her token için bir kez çağrılır ve onu ISO 32000-1 Tablo 51'in tam 73 operatör kümesine karşı eşleştirir -w ve q'dan nadiren görülen d0 ve d1 Type 3 glif-ölçüt operatörlerine kadar- ve eskiden her tek token'da o listeyi doğrusal olarak dolaşırdı; bu yüzden birkaç bin operatörlü bir sayfa, aynı 73 girdilik tablo üzerinde birkaç bin doğrusal tarama demekti. PDFlibPas artık tabloyu başlangıçta operatörün ilk baytına göre, sabit bir AnsiChar-indeksli slot dizisine kovalar; bu yüzden bir arama, bir dizi indeksine artı yalnızca o ilk karakteri paylaşan bir avuç operatörün taranmasına dönüşür

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 operatörleri büyük/küçük harfe duyarlıdır -w ve W, f ve F, sc ve SC hepsi farklı operatörlerdir- bu yüzden GOpBuckets, ham bayta göre anahtarlanır ve bir kova içindeki kalan karşılaştırma, düz, büyük/küçük harfe duyarlı bir AnsiString eşitliğidir. Dizi, harf başına 16 slot olarak boyutlandırılmıştır ki bu bugünkü tabloyu rahatça kapsar -en yoğun kova, T, on üç operatör tutar, çünkü hemen hemen her metin-durumu ve metin-konumlandırma operatörü onunla başlar- ama EnsureOpBuckets, sayısı 16'ya ulaştığında bir kovaya eklemeyi sessizce durdurur; bu yüzden hiç on dördüncü bir girdiye ihtiyaç duyan bir kova, gürültülü değil sessizce başarısız olurdu: operatör, nedenine işaret eden hiçbir istisna olmadan coUnknown'a çözülürdü. Bu, zarifçe bozulan bir veri yapısını, bozulmayan biriyle takas etmenin bakım maliyetidir -sınır kontrollü bir büyümeye hiç ihtiyaç duymadığı için daha hızlı gönderir ve tavanına yakın tek kovayı izleyen bir insana ihtiyaç duyar

Dize kurmadan O(n²)'yi çıkarmak

Pascal'ın Result := Result + Fragment örüntüsü, her yinelemede birikmiş dizenin tamamını yeniden tahsis eder ve kopyalar; bu yüzden N karakterlik bir çıktıyı seferinde bir parça oluşturmak O(n) yerine O(n²)'ye mal olur -incelemede kaçırılması kolaydır, çünkü her satır tek bir ucuz ekleme gibi görünür ve pratikte pahalıdır çünkü PLDirectEscapeLiteralString, kayıt sırasında yazılan her gerçek PDF dizesinde çalışır ve XFDFXMLEscape, XFDF'e dışa aktarılan her alan değerinde çalışır. PDFlibPas ikisini, her fonksiyonun önceden ne tahmin edebileceğine göre seçilen farklı tekniklerle düzeltir. PLDirectEscapeLiteralString, tek bir bayt yazmadan önce çıktı uzunluğunu bilir -bir geçiş her karakteri düz veya kaçışlı olarak sınıflandırır ve toplamı toplar, SetLength bir kez tahsis eder ve ikinci bir geçiş arabelleği indekse göre doldurur. XFDFXMLEscape, Unicode alan metni önceden hesaplamak için çok fazla değiştiğinden çıktı uzunluğunu ucuza tahmin edemez; bu yüzden bunun yerine girdi uzunluğuna kabaca önceden boyutlandırılmış bir TStringBuilder'a ekler

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;

İkisi arasındaki seçim, gerçekte döngü başlamadan önce ne bildiğinizle ilgilidir. Say-sonra-doldur, çıktı boyutunun hesaplanması ucuz olduğunda ikisinden daha hızlı olanıdır, çünkü sıfır yeniden tahsis yapar ve bir Integer sayacın ötesinde hiçbir muhasebe gerektirmez, ama sınıflandırma mantığını iki kez yazmak anlamına gelir -bir kez saymak için, bir kez yaymak için- ki bu, iki kopya birbirinden ayrılırsa kendi başına bir bakım riskidir. TStringBuilder, mantığı bir kez yazmak ve geometrik arabellek büyümesinden amortize edilmiş O(1) eklemeler elde etmek için o tepe verimin biraz vazgeçer ki bu, çıktı boyutunun önceden bilinmesi kolay olmadığında daha güvenli varsayılandır

Bu örüntü nerede uygulanır, nerede uygulanmaz

Yukarıdaki dört düzeltmenin hepsi tek bir fikrin örnekleridir: girdi birimi başına bir kez çalışan çağrıyı -sözlük anahtarı başına, piksel başına, operatör token'ı başına, karakter başına- bulun ve doğrusal veya öngörülemez maliyetini önceden hesaplanmış bir tablo, bir hash indeksi veya önceden boyutlandırılmış bir arabellekle değiştirin. Bunların hiçbiri PDF'e özgü değildir; istek başına aynı arama anahtarını binlerce kez çözen, sıkı bir döngüde değerleri dönüştüren, sabit bir token sözcük dağarcığına göre gönderen veya uzun dizeleri karakter karakter kuran bir Delphi servisi, aynı başarısızlık şekillerine çarpar ve aynı düzeltmeleri alır. Bu dört değişikliğin hiçbirinin dokunmadığı şey, eşzamanlılık veya bellek ayak izidir: daha hızlı tek iş parçacıklı bir sözlük araması, aynı TPDFlib örneği üzerinde yarışan iki iş parçacığı için hiçbir şey yapmaz ki bu, paralel sayfa render işleminde iş parçacığı güvenliği üzerine makalede ayrıca ele alınan yapısal bir sorundur ve bir nesne ağacı olarak hiç belleğe yüklenemeyecek kadar büyük bir PDF için hiçbir şey yapmaz ki bu, PDFlibPas'taki Doğrudan Erişim katmanının ne için olduğudur, gigabaytlık PDF'leri birleştirme ve bölme üzerine makalede ele alınmıştır

Burada tartışılan sözlük, renk yönetimi, içerik akışı gönderimi ve dize kurma kodu, losLab'ın Delphi ve C++Builder için PDF kütüphanesi olan standart PDFlibPas'ın bir parçası olarak gönderilir, hiçbirini elde etmek için ekstra yapılandırma gerekmez