Профилиране на производителността на PDFlibPas: hash индекси в Delphi

PDFlibPas, PDF библиотеката на losLab за Delphi и C++Builder, ускорява пътищата за rendering и content generation, като заменя четири модела на повтаряща се работа с такива с амортизирана цена: lazy hash index за търсене на ключове в dictionary, предварително изчислена sRGB gamma lookup table, групиране по first byte за dispatch на оператори в content stream и TStringBuilder вместо повтарящо се конкатениране на string. Нито една от четирите промени не произлезе от драматично откритие — всички започнаха от един и същ непретенциозен профилиращ модел: малка функция, извиквана веднъж за всеки operator, pixel или character, при която линейната цена вътре в извикването става квадратична или почти квадратична за целия документ. Това е общата нишка: четири малки, привидно несвързани поправки, които атакуват една и съща форма на проблема, плюс честните ограничения на всяка от тях

Къде renderer-ът на content stream действително прекарва времето си

Renderer-ът на content stream в PDFlibPas прокарва почти цялата цена за всеки token през четири тесни места: lookup в resource dictionary за /Resources, /ColorSpace, /Font и /ExtGState; gamma correction за всеки декодиран pixel в Lab, Indexed или ICC-tagged image; съпоставяне на името на operator за всеки token от всеки content stream; и изграждане на string навсякъде, където библиотеката създава изход — escaping на literal string при save, XFDF export и разширяване на token-и за stamp и променливи. Всяка от четирите операции сама по себе си върши малко работа, но всяка се изпълнява хиляди или милиони пъти върху реалистичен документ, което е точната форма на функция, при която детайл от реализацията с O(n) или O(n²) престава да бъде невидим и заема първото място в профила

Защо lookup-ите в resource dictionary се забавят при голям PDF?

TPDFDictionary.FindIndexByKeyName е функцията, която renderer-ът извиква за разрешаване на всеки lookup към /Resources, /ColorSpace, /Font и /ExtGState, а преди обхождаше масива Entries от началото при всяко извикване — приемливо за dictionary с три записа, но скъпо за Form XObject или страница с много ExtGState, където същият dictionary се проверява при всеки operator, който засяга цвета или graphics state. PDFlibPas вече изгражда lazy hash index, когато dictionary премине прага DICT_HASH_THRESHOLD от 16 entries, а по-малките dictionary остават с linear scan, тъй като повечето PDF dictionary никога не стават толкова големи и hash table за три ключа би струвала повече за изграждане, отколкото би спестила. Индексът е плоска open-addressing таблица с ключ PLAnsiStringHash, FNV-1a hash с канонична offset basis 2166136261 и prime 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 — изчиства hash-а и оставя следващия lookup да го изгради отново от нулата. Това изглежда разточително, докато не се види, че ключът в dictionary е обект TPDFName, а TPDFName.SetTo може да преименува ключ, който вече се намира в масива Entries, без да минава през собствените методи на dictionary — инкременталният index няма как да види това преименуване, докато lazy index-ът просто се изгражда отново и остава коректен по конструкция. Цената на тази безопасност е O(n) rebuild при първия query към голям dictionary след запис, плюс паметта за самата hash table, приблизително един Integer за slot при load factor две трети — пренебрежим разход за малкото oversized dictionary в типичен документ и реална цена, която PDFlibPas избягва за всеки малък dictionary, като запазва този праг

Предварително изчисляване на sRGB gamma вместо извикване на Power за всеки pixel

TPDFSimpleColorManager.XYZ2RGB прилага sRGB transfer function към всеки декодиран pixel от Lab, Indexed или ICC-based image — 1.055 * Power(x, 1/2.4) - 0.055 над прага на linear segment — а Power(x, y) за дробно y няма евтина затворена форма в Pascal RTL: разлага се на Ln(x) и след това Exp(y * Ln(x)), а тази двойка трансцендентни извиквания, изпълнявана три пъти за pixel за червения, зеления и синия канал, е доминиращата цена при декодиране на Lab или ICC image pixel по pixel. PDFlibPas заменя трите извиквания на Power за всеки pixel с един lookup в GSRGBGammaLUT, масив от 4096 стойности Double, изграден веднъж чрез EnsureSRGBGammaLUT и индексиран чрез закръгляне на clamp-натия вход до най-близкия slot

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 slot-а върху входния диапазон [0, 1] дава приблизително шестнадесет пъти по-висока резолюция от 8-битовия изходен канал, така че квантуването, внесено от LUT, остава под това, което крайният RGB byte може да представи — lookup в таблица заменя трансцендентната математика без видима загуба на точност. Същото разсъждение се вижда и в Lab2XYZ, където Power(LMN[i], 3) е заменен с директно LMN[i]*LMN[i]*LMN[i]: целочислена степен изобщо не се нуждае от Ln/Exp, така че това не е компромис с LUT, а само премахнато излишно извикване на Power. LUT подходът се отплаща само защото transfer function е чиста функция на една стойност Double — той не би се пренесъл добре към color transform, зависим от няколко pixel стойности или от повече state

Как се dispatch-ват бързо 73 operator-а от content stream?

ContentOperatorFromName се извиква веднъж за всеки token, който PDFlibPas прочита от content stream, и го съпоставя с пълния набор от 73 operator-а в ISO 32000-1 Table 51 — от w и q до рядко срещаните d0 и d1 оператори за glyph metrics на Type 3 — а преди обхождаше този списък линейно при всеки token, така че страница с няколко хиляди operator-а означаваше няколко хиляди линейни scan-а на една и съща таблица от 73 записа. PDFlibPas вече групира таблицата при стартиране според first byte на operator-а във фиксиран масив от slot-ове, индексиран по AnsiChar, така че lookup-ът става един array index плюс проверка само на малкото operator-и със същия първи знак

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 operator-ите са case-sensitive — w и W, f и F, sc и SC са различни operator-и — затова GOpBuckets използва raw byte като ключ, а остатъчното сравнение вътре в bucket е обикновено, чувствително към регистъра сравнение на AnsiString. Масивът е оразмерен с 16 slot-а за всяка буква, което удобно покрива днешната таблица — най-натовареният bucket, T, съдържа тринадесет operator-а, защото почти всеки operator за text state и text positioning започва с него — но EnsureOpBuckets тихо спира да добавя към bucket, когато count достигне 16, така че bucket, който някога се нуждае от четиринадесети запис, ще се провали тихо, вместо ясно: operator-ът ще се разреши до coUnknown без exception, който да посочи причината. Това е цената за подмяна на структура от данни, която се разпада постепенно, с такава, която не го прави — dispatch-ът е по-бърз, защото не се нуждае от grow с проверка на границите, но изисква човек да следи единствения bucket, който се приближава до тавана си

Премахване на O(n²) от изграждането на string

Моделът Result := Result + Fragment в Pascal заделя отново и копира целия натрупан string при всяка итерация, така че изграждането на изход от N знака, fragment по fragment, струва O(n²) вместо O(n) — лесно се пропуска при review, защото всеки ред изглежда като едно евтино добавяне, но е скъпо на практика, тъй като PLDirectEscapeLiteralString се изпълнява за всеки literal PDF string, записан при save, а XFDFXMLEscape се изпълнява за всяка стойност на поле, експортирана към XFDF. PDFlibPas поправя двете места с различни техники, избрани според това, което всяка функция може да предвиди предварително. PLDirectEscapeLiteralString знае изходната дължина, преди да запише и един byte — един проход класифицира всеки знак като обикновен или escape-нат и сумира общия размер, SetLength заделя веднъж, а втори проход запълва buffer-а по index. 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('&');
        '<':  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;

Изборът между двете техники всъщност зависи от това, което знаете, преди да започне loop-ът. Count-then-fill е по-бързият вариант, когато размерът на изхода се изчислява евтино, защото няма reallocations и няма bookkeeping извън един брояч Integer, но това означава да се напише логиката за класификация два пъти — веднъж за преброяване и веднъж за извеждане — което само по себе си е риск за поддръжката, ако двете копия се разминаят. TStringBuilder се отказва от малка част от пиковата пропускателна способност, за да запише логиката веднъж и да получи амортизирани O(1) добавяния чрез геометричен растеж на buffer-а, което е по-безопасният default, когато размерът на изхода не се предвижда лесно предварително

Къде се прилага този модел и къде не се прилага

И четирите поправки по-горе са прояви на една идея: намерете извикването, което се изпълнява веднъж за всяка единица вход — за всеки dictionary key, pixel, operator token или character — и заменете линейната или непредсказуемата му цена с предварително изчислена table, hash index или предварително оразмерен buffer. Нищо от това не е специфично за PDF; Delphi service, който разрешава един и същ lookup key хиляди пъти на request, преобразува стойности в tight loop, dispatch-ва по фиксиран речник от token-и или изгражда дълги string-ове character по character, среща същите форми на проблема и използва същите поправки. Това, което нито една от четирите промени не засяга, е concurrency или memory footprint: по-бързият single-threaded dictionary lookup не помага на два thread-а, които се състезават за един и същ TPDFlib instance, което е структурен проблем, разгледан отделно в статията за thread safety при паралелно rendering на страници, и не помага за PDF, твърде голям, за да бъде зареден изцяло в паметта като object tree, за което служи Direct Access layer-ът в PDFlibPas, разгледан в статията за сливане и разделяне на PDF файлове с размер гигабайти

Разгледаните тук dictionary, color-management, content-stream dispatch и string-building реализации са част от стандартния PDFlibPas, PDF библиотеката на losLab за Delphi и C++Builder, и не изискват допълнителна конфигурация, за да се използва която и да е от тях