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

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

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

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

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

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

Попереднє обчислення гами 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 по одному. PDF Library for Delphi замінює три виклики 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 викликається один раз для кожного токена, який PDF Library for Delphi читає з потоку вмісту, зіставляючи його з повним набором 73 операторів таблиці 51 ISO 32000-1 — від w та q до рідко бачених операторів метрик гліфів типу 3 d0 та d1, — і раніше він обходив цей список лінійно на кожному окремому токені, тож сторінка з кількома тисячами операторів означала кілька тисяч лінійних сканувань того самого 73-записного словника. PDF Library for Delphi тепер розподіляє таблицю за першим байтом оператора під час запуску в фіксований масив слотів, індексований 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. PDF Library for Delphi виправляє обидва різними техніками, обраними тим, що кожна функція може передбачити заздалегідь. PLDirectEscapeLiteralString знає довжину свого виводу до запису хоч одного байта — один прохід класифікує кожен символ як звичайний чи екранований і підсумовує загальну кількість, SetLength виділяє один раз, а другий прохід заповнює буфер за індексом. XFDFXMLEscape не може дешево передбачити довжину свого виводу, оскільки текст поля Unicode варіюється надто сильно для попереднього обчислення, тож натомість він додає в TStringBuilder, попередньо розрахований приблизно на довжину входу

Function XFDFXMLEscape(Const W: WideString): WideString;
Var
  I: Integer;
  Builder: TStringBuilder;
Begin
  // TStringBuilder уникає конкатенації WideString за O(n^2), на яку
  // раніше натрапляв експорт XFDF при кожному значенні поля
  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;');
        // ...регістри '"', табуляції, CR та LF йдуть за тією ж схемою
      Else
        Builder.Append(W[I]);
      End;
    End;
    Result:= Builder.ToString;
  Finally
    Builder.Free;
  End;
End;

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

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

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

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