LБлог losLab по разработке программного обеспеченияИнженерные заметки для разработчиков PDF, Delphi и программного обеспечения для работы с документами.

Техническая статья

Профилирование производительности 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 до редко встречающихся операторов метрик глифов Type 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 не может дёшево предсказать длину своего вывода, поскольку юникодный текст поля варьируется слишком сильно для предвычисления, так что вместо этого он добавляет в 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, без какой-либо дополнительной настройки, чтобы это получить