LlosLab Software Development BlogEngineering notes for PDF, Delphi, and document software developers

Технічна стаття

Профілювання продуктивності PDFlibPas: хеш-індекси в Delphi

Delphi PDF Library

PDFlibPas, бібліотека PDF від losLab для Delphi та C++Builder, прискорює свої шляхи рендерингу та генерації вмісту, замінюючи чотири шаблони повторюваної роботи амортизованими: лінивий хеш-індекс для пошуку ключів словника, попередньо обчислена таблиця пошуку гама sRGB, розподіл по першому байту для диспетчеризації операторів потоку вмісту та TStringBuilder замість повторної конкатенації рядків. Жодне з чотирьох не з'явилося з одного драматичного відкриття — усі вони з'явилися з того самого неефектного шаблону в профілі: невелика функція, викликана один раз на ключ словника, один раз на піксель чи один раз на символ, де лінійна вартість усередині виклику стає квадратичною чи майже квадратичною по всьому документу. Ось наскрізна тема тут: чотири маленькі, на вигляд непов'язані виправлення, що атакують ту саму форму проблеми, плюс чесні межі кожного з них

Куди насправді витрачає час рендерер потоку вмісту

Рендерер потоку вмісту в PDFlibPas спрямовує майже всю свою вартість на токен через чотири вузькі точки: пошуки словника ресурсів на /Resources, /ColorSpace, /Font та /ExtGState; корекцію гами на кожному декодованому пікселі зображення Lab, Indexed чи з тегом ICC; зіставлення імен операторів на кожному токені кожного потоку вмісту; та побудову рядків будь-де, де бібліотека будує вивід — екранування буквального рядка при збереженні, експорт XFDF, розгортання токенів штампів та змінних. Кожне з чотирьох виконує невелику кількість роботи саме по собі, і кожне виконується тисячі чи мільйони разів над реалістичним документом, і це саме та форма функції, де деталь реалізації O(n) чи O(n²) перестає бути невидимою і починає бути найвищим записом профілю

Чому пошуки словника ресурсів стають повільними у великому PDF?

TPDFDictionary.FindIndexByKeyName — те, що викликає рендерер для розв'язання кожного пошуку /Resources, /ColorSpace, /Font та /ExtGState, і раніше він обходив масив Entries спереду при кожному виклику — нормально для трьохзаписного словника Resources, дорого для Form XObject чи сторінки, багатої на ExtGState, де той самий словник опитується при кожному операторі, що торкається кольору чи графічного стану. PDFlibPas тепер будує лінивий хеш-індекс, щойно словник перевищує поріг DICT_HASH_THRESHOLD (16) записів, і залишає менші словники на лінійному скануванні, оскільки більшість словників PDF ніколи не досягають такого розміру, а хеш-таблиця для трьох ключів коштувала б дорожче побудувати, ніж заощаджує. Індекс — пласка таблиця з відкритою адресацією, ключем якої є PLAnsiStringHash, хеш 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
    // 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;

Індекс інвалідується, а не підтримується інкрементально: кожен мутуючий виклик — AddEntry, DeleteEntryByKeyName, Assign, AddDict — очищає хеш і дозволяє наступному пошуку перебудувати його з нуля. Це виглядає марнотратно, доки не помітите, що ключ словника — об'єкт TPDFName, а TPDFName.SetTo може перейменувати ключ, що вже сидить у масиві Entries словника, не проходячи через жоден із власних методів словника, — інкрементальний індекс не має способу спостерігати це перейменування, тоді як лінивий просто перебудовується і залишається коректним за побудовою. Ціна цієї безпеки — перебудова O(n) перший раз, коли до великого словника надходить запит після запису, плюс пам'ять для самої хеш-таблиці, приблизно один Integer на слот при коефіцієнті заповнення дві третини, — похибка округлення для жменьки надмірних словників у типовому документі, і реальна вартість, якої PDFlibPas уникає платити на кожному маленькому, тримаючи поріг там, де він є

Попереднє обчислення гами 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 по одному. PDFlibPas замінює три виклики 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-бітний вихідний канал, тож квантування, яке вносить таблиця пошуку, сидить нижче того, що може представити фінальний байт RGB, — пошук у таблиці замінює трансцендентну математику тут без видимої втрати точності. Те саме міркування з'являється поряд у Lab2XYZ, де Power(LMN[i], 3) став простим LMN[i]*LMN[i]*LMN[i]: цілочисельний степінь узагалі не потребує Ln/Exp, тож це взагалі не компроміс таблиці пошуку, просто прибраний зайвий виклик Power. Трюк із таблицею пошуку окупається лише тому, що передавальна функція — чиста функція одного Double; вона не поширилася б чисто на перетворення кольору, що залежить від кількох значень пікселя чи від більшого стану, ніж це

Як швидко диспетчеризувати 73 оператори потоку вмісту?

ContentOperatorFromName викликається один раз для кожного токена, який PDFlibPas читає з потоку вмісту, зіставляючи його з повним набором 73 операторів таблиці 51 ISO 32000-1 — від w та q до рідко бачених операторів метрик гліфів типу 3 d0 та d1, — і раніше він обходив цей список лінійно на кожному окремому токені, тож сторінка з кількома тисячами операторів означала кілька тисяч лінійних сканувань того самого 73-записного словника. PDFlibPas тепер розподіляє таблицю за першим байтом оператора під час запуску в фіксований масив слотів, індексований 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²) з побудови рядків

Шаблон Pascal Result := Result + Fragment перевиділяє й копіює весь накопичений рядок при кожній ітерації, тож побудова N-символьного виводу по одному фрагменту за раз коштує O(n²) замість O(n) — легко пропустити при перегляді, бо кожен рядок виглядає як один дешевий додаток, і дорого на практиці, бо PLDirectEscapeLiteralString виконується на кожному буквальному рядку PDF, записаному під час збереження, а XFDFXMLEscape виконується на кожному значенні поля, експортованому в XFDF. PDFlibPas виправляє обидва різними техніками, обраними тим, що кожна функція може передбачити заздалегідь. PLDirectEscapeLiteralString знає довжину свого виводу до запису хоч одного байта — один прохід класифікує кожен символ як звичайний чи екранований і підсумовує загальну кількість, SetLength виділяє один раз, а другий прохід заповнює буфер за індексом. 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('&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;

Вибір між двома насправді про те, що ви знаєте перед початком циклу. Підрахувати-потім-заповнити швидше з цих двох, коли розмір виводу дешево обчислити, бо він робить нуль перевиділень і жодного обліку понад лічильник Integer, але це означає написання логіки класифікації двічі — один раз для підрахунку, один раз для видачі, — що власний ризик супроводу, якщо дві копії розійдуться. TStringBuilder жертвує невеликою частиною цієї пікової пропускної здатності заради написання логіки один раз і отримання амортизованих O(1) додатків через геометричне зростання буфера, що безпечніший за замовчуванням варіант, коли розмір виводу нелегко знати наперед

Де цей шаблон застосовується, а де ні

Усі чотири виправлення вище — приклади однієї ідеї: знайти виклик, що виконується один раз на одиницю входу — на ключ словника, на піксель, на токен оператора, на символ, — і замінити його лінійну чи непередбачувану вартість попередньо обчисленою таблицею, хеш-індексом чи буфером попереднього розміру. Ніщо з цього не специфічне для PDF; служба Delphi, що розв'язує той самий ключ пошуку тисячі разів на запит, перетворює значення в щільному циклі, диспетчеризує на фіксованому словнику токенів чи будує довгі рядки по символу за раз, наштовхується на ті самі форми збою й отримує ті самі виправлення. Що жодна з цих чотирьох змін не торкається, так це паралелізм чи слід пам'яті: швидший однопотоковий пошук словника нічого не робить для двох потоків, що змагаються за той самий екземпляр TPDFlib, — структурна проблема, розглянута окремо в статті про безпеку потоків у паралельному рендерингу сторінок, і нічого не робить для PDF, надто великого, щоб узагалі завантажити в пам'ять як дерево об'єктів, — для цього призначений шар прямого доступу в PDFlibPas, розглянутий у статті про об'єднання й розділення гігабайтних PDF

Код словника, керування кольором, диспетчеризація потоку вмісту та побудова рядків, обговорені тут, постачаються як частина стандартного PDFlibPas, бібліотеки PDF від losLab для Delphi та C++Builder, без потреби в жодному додатковому налаштуванні для отримання будь-чого з цього