Оптимізація продуктивності введення-виведення для обробки PDF гігабайтного масштабу

Перше корисне зчитування парсера PDF знаходиться на неправильному кінці файлу. Формат розміщує вказівник startxref в останніх байтах, тому обробка архіву розміром 1,8 ГБ починається з переходу в кінець, зчитування одного кілобайта, потім стрибка туди, де, згідно з таблицею перехресних посилань, знаходиться каталог документа. Звідти розбір є випадковим переміщенням по всьому діапазону байтів. Усе, в чому буферизоване введення-виведення є хорошим — послідовне попереднє зчитування за вказівником файлу — націлене на робоче навантаження, якого PDF не має

Перша версія цієї статті стверджувала, що файл, відображений у пам'ять, вирішує проблему збою нестачі пам'яті (out-of-memory) 32-бітної системи, з яким стикається TMemoryStream на файлах розміром 2 ГБ. Це твердження неправильне, і те, в чому воно неправильне, вказує на справжнє виправлення: ковзне вікно відображення. Далі йдеться про шаблон доступу, виправлена історія 32-бітної системи з компільованим віконним відображувачем і арифметика системних викликів на тестовому файлі розміром 1,8 ГБ із 300 000 об'єктів

Чому структура PDF руйнує буферизоване зчитування

Три структурні факти формують шаблон введення-виведення. По-перше, навігація керується зміщеннями: таблиця перехресних посилань зіставляє кожен номер об'єкта з абсолютною позицією в байтах, і нічого не вимагає, щоб ці позиції були впорядковані. Після років поступових оновлень об'єкт 4102 може знаходитися на зміщенні 1,6 ГБ, тоді як об'єкт 4103 знаходиться на 30 КБ. Цикл TFileStream перетворює кожне отримання на Seek плюс Read, два переходи ядра, з буфером, який нічого не дає, оскільки наступне отримання знаходиться за сотні мегабайтів

По-друге, потоки об'єктів (ISO 32000-1 §7.5.7) пакують десятки або сотні невеликих словників в один стиснутий контейнер (deflated container). Отримання одного словника сторінки розміром 300 байтів може означати зчитування та розпакування кластера розміром 100 КБ. Зворотний бік: об'єкти, записані разом, як правило, зчитуються разом, тому буфер, розміром з кластер, обслуговує наступний десяток отримань безкоштовно — найбільша закономірність формату, яку можна використовувати

По-третє, лінеаризація. Лінеаризований файл розміщує спереду першу сторінку та таблицю підказок, щоб споживачі могли читати його від початку до кінця. Гігабайтні архіви майже ніколи не лінеаризуються: лінеаризація руйнується тими ж поступовими оновленнями та злиттями, які зробили файл великим. Плануйте для гіршого випадку: довгі стрибки, відсутність впорядкування, вхід з кінця

32-бітна історія, виправлена

32-бітний процес Windows має 2 ГБ адресного простору користувача, а MapViewOfFile з кількістю байтів рівною нулю запитує одне безперервне резервування розміром з файл. Для вхідних даних розміром 2 ГБ це резервування не може бути успішним: після EXE, розкиданих DLL та стеків потоків найбільший вільний безперервний блок у типовому 32-бітному процесі Delphi знаходиться десь між 700 МБ і 1,4 ГБ. Виклик завершується помилкою ERROR_NOT_ENOUGH_MEMORY, тією ж стіною, в яку вдаряється TMemoryStream.LoadFromFile, лише переміщеною із зафіксованої пам'яті (committed RAM) до резервування адресного простору. Відображення всього файлу не є виправленням на 32-бітній системі, це та ж сама помилка за більш красивими іменами API

Виправлення полягає у розділенні двох речей, які виконує відображення. CreateFileMapping створює об'єкт розділу і не потребує адресного простору взагалі, незалежно від розміру файлу. Лише MapViewOfFile витрачає адресний простір, і нічого не змушує його відображати весь розділ: він приймає 64-бітне початкове зміщення і довжину вікна. Створіть розділ один раз, відображайте вікно від 64 до 256 МБ над областю, що аналізується, скасуйте відображення перед ковзанням далі: вартість адресного простору — одне вікно, а не один файл. Одне обмеження: зміщення відображення має бути кратним SYSTEM_INFO.dwAllocationGranularity, 64 КБ на практиці, тому запит на зміщення 1 000 000 округляється вниз до 983 040, а вказівник абонента коригується вперед на різницю

Віконний відображувач із ковзанням у Delphi

Наведений нижче клас охоплює всю дисципліну: один об'єкт розділу, одне активне вікно, вирівнювання гранулярності та зчитування, які перетинають межу вікна, що обробляються шляхом збільшення цього одного вікна замість зшивання двох

uses
  Winapi.Windows, System.SysUtils;

type
  TWindowedFileMapper = class
  private
    FFile: THandle;
    FMapping: THandle;
    FFileSize: Int64;
    FGranularity: DWORD;      // SYSTEM_INFO.dwAllocationGranularity
    FWindowSize: NativeUInt;  // default view size
    FViewBase: PByte;         // base of the current view (aligned)
    FViewOffset: Int64;       // file offset FViewBase corresponds to
    FViewSize: NativeUInt;    // bytes mapped in the current view
    procedure Unmap;
  public
    constructor Create(const FileName: string;
      WindowSize: NativeUInt = 64 * 1024 * 1024);
    destructor Destroy; override;
    function Map(Offset: Int64; Size: NativeUInt): PByte;
    procedure ReadBytes(Offset: Int64; var Buffer; Count: NativeUInt);
    property FileSize: Int64 read FFileSize;
  end;

constructor TWindowedFileMapper.Create(const FileName: string;
  WindowSize: NativeUInt);
var
  Info: TSystemInfo;
begin
  inherited Create;
  FFile := CreateFile(PChar(FileName), GENERIC_READ, FILE_SHARE_READ, nil,
    OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);
  if FFile = INVALID_HANDLE_VALUE then
    RaiseLastOSError;
  if not GetFileSizeEx(FFile, FFileSize) then
    RaiseLastOSError;
  // The section object reserves no address space, whatever the file size
  FMapping := CreateFileMapping(FFile, nil, PAGE_READONLY, 0, 0, nil);
  if FMapping = 0 then
    RaiseLastOSError;
  GetSystemInfo(Info);
  FGranularity := Info.dwAllocationGranularity;  // 64 KB in practice
  FWindowSize := WindowSize;
end;

destructor TWindowedFileMapper.Destroy;
begin
  Unmap;
  if FMapping <> 0 then CloseHandle(FMapping);
  if FFile <> INVALID_HANDLE_VALUE then CloseHandle(FFile);
  inherited;
end;

procedure TWindowedFileMapper.Unmap;
begin
  if FViewBase <> nil then
  begin
    UnmapViewOfFile(FViewBase);
    FViewBase := nil;
    FViewSize := 0;
  end;
end;

function TWindowedFileMapper.Map(Offset: Int64; Size: NativeUInt): PByte;
var
  AlignedOffset: Int64;
  Delta, MapSize: NativeUInt;
begin
  if (Offset < 0) or (Offset + Int64(Size) > FFileSize) then
    raise ERangeError.CreateFmt(
      'Map request at %d for %d bytes is outside the file',
      [Offset, Int64(Size)]);

  // Fast path: the requested range already sits inside the live view
  if (FViewBase <> nil) and (Offset >= FViewOffset) and
     (Offset + Int64(Size) <= FViewOffset + Int64(FViewSize)) then
    Exit(FViewBase + NativeInt(Offset - FViewOffset));

  Unmap;  // slide: never hold two views at once

  // Views must start on an allocation-granularity boundary
  AlignedOffset := Offset - (Offset mod FGranularity);
  Delta := NativeUInt(Offset - AlignedOffset);

  MapSize := FWindowSize;
  if MapSize < Size + Delta then   // request straddles the window end:
    MapSize := Size + Delta;       // grow this one view to cover it
  if AlignedOffset + Int64(MapSize) > FFileSize then
    MapSize := NativeUInt(FFileSize - AlignedOffset);  // clamp at EOF

  FViewBase := MapViewOfFile(FMapping, FILE_MAP_READ,
    DWORD(AlignedOffset shr 32), DWORD(AlignedOffset and $FFFFFFFF),
    MapSize);
  if FViewBase = nil then
    RaiseLastOSError;

  FViewOffset := AlignedOffset;
  FViewSize := MapSize;
  Result := FViewBase + NativeInt(Delta);
end;

procedure TWindowedFileMapper.ReadBytes(Offset: Int64; var Buffer;
  Count: NativeUInt);
begin
  Move(Map(Offset, Count)^, Buffer, Count);
end;

Дві деталі несуть основне навантаження. Швидкий шлях на початку Map повертає вказівник без переходу ядра, коли запитаний діапазон уже знаходиться всередині активного вікна; завдяки кластеризації потоків об'єктів це звичайний випадок і те, звідки береться економія. А запит, який перетинає кінець вікна за замовчуванням, збільшує MapSize для цього одного відображення, а не зшиває два, що залишає ReadBytes однорядковим, а абонентів вільними від циклів часткового зчитування

Розмір вікна — це поблажливий регулятор: при 64 МБ повне проходження файлу розміром 1,8 ГБ — це 29 вікон, при 256 МБ — 8, але кожне резервування важче розмістити у фрагментованому 32-бітному просторі, а нижче приблизно 16 МБ файли з великою кількістю стрибків повторно відображаються досить часто, щоб це було помітно. Десь у діапазоні від 64 до 256 МБ трафік відображення — це статистичний шум

Підрахунок системних викликів

Тепер арифметика. Тестовий файл: 1,8 ГБ, 300 000 непрямих об'єктів, що в середньому мають близько 600 байтів корисного навантаження. Парсер для кожного об'єкта отримує кожен із них за допомогою SetFilePointerEx плюс ReadFile на 4 КБ: 600 000 переходів ядра. Кешований системний виклик зчитування туди й назад займає приблизно 1,5 мкс на сучасному обладнанні x64, тому це 600 000 × 1,5 мкс ≈ 0,9 секунди чистих накладних витрат ядра перед розбором хоча б одного байта — найкращий випадок з прогрітим кешем. З холодним кешем кожен стрибок — це операція пристрою: при ефективній затримці ~20 мкс для випадкових зчитувань 4 КБ на NVMe, 300 000 з них коштуватимуть близько 6 секунд часу пристрою; на сховищах класу SATA — хвилини

Зчитування також переміщує неправильні дані: 300 000 × 4 КБ просуває 1,2 ГБ через буфери користувача, щоб доставити приблизно 180 МБ корисного навантаження — шестиразове збільшення, кожен байт копіюється з ядра до користувача

Буфер попереднього зчитування (read-ahead), розміром з кластери потоків об'єктів, є першим чесним покращенням: одне зчитування на 256 КБ на кластер замість одного на об'єкт зменшує кількість переходів на один-два порядки. Це також правильний інструмент там, де відображення є незручним, зазвичай для мережевих ресурсів

Віконний відображувач йде ще далі. Повне проходження — це 29 викликів MapViewOfFile і 29 UnmapViewOfFile, 58 явних переходів проти 600 000. Справжній розбір на основі xref не є чистим проходженням, але швидкий шлях поглинає кожне отримання всередині активного вікна; прохід індексації метаданих через тестовий архів осів на кількох сотнях повторних відображень. Відображення не усуває роботу ядра: воно перетворює явні системні виклики на помилки сторінки (page faults), які диспетчер пам'яті вирішує в багатосторінкових кластерах, безпосередньо з файлового кешу без копіювання в простір користувача, а області, до яких ніколи не торкаються, нічого не коштують. Від початку до кінця прохід індексації пройшов від 23 с із холодним і 7,1 с із теплим кешем для пооб'єктних зчитувань до 6,5 с із холодним і 1,9 с із теплим за допомогою відображувача; те, що залишається — це розпакування zlib (inflate), а не введення-виведення

Де підходить FILE_FLAG_NO_BUFFERING

FILE_FLAG_NO_BUFFERING оминає системний кеш в обмін на суворі правила вирівнювання: зміщення, довжини та адреси буферів мають бути вирівняні по секторах. Він виправдовує себе на однопрохідних послідовних завданнях, які інакше затопили б кеш байтами, які ніхто не читає двічі — пакетна повторна серіалізація, яка переписує весь архів, або прохід лінеаризації готового результату. З вирівняними буферами від 4 до 8 МБ він наближається до послідовної пропускної здатності пристрою, не забруднюючи кеш

Це абсолютно неправильно для розбору. Випадкові стрибки xref через небуферизований дескриптор перетворюють кожне отримання словника на 300 байтів на повне фізичне зчитування без кешу, який міг би поглинути другий візит — а розбір PDF постійно повертається до областей, оскільки різні сторінки посилаються на ті ж самі потоки об'єктів. Небуферизоване введення-виведення для послідовного переписування, відображене або кешоване введення-виведення для випадкового розбору; прапорець застосовується до дескриптора, тому один конвеєр може тримати обидва для того самого файлу

64-бітна система, робочі набори (working sets) та сторона запису

На 64-бітній збірці заперечення щодо адресного простору зникає: передайте розмір файлу як вікно, і наведений вище клас вироджується в одне повне відображення. Заковика в довготривалих службах: сторінки, що підтримуються файлом лише для зчитування (read-only file-backed), не стягують плату за фіксацію (commit), тому лічильники фіксації залишаються спокійними, але кожна зачеплена сторінка приєднується до робочого набору (working set); розберіть більшу частину з 1,8 ГБ, і робочий набір виросте відповідно, витіснивши все інше. Обмежені вікна встановлюють стелю для цього, тому ковзний шаблон залишається правильним за замовчуванням, навіть коли адресний простір є вільним

На стороні запису найдешевше введення-виведення — це те, яке ніколи не було видане. Механізм поступового оновлення PDF (ISO 32000-1 §7.5.6) додає змінені об'єкти та новий розділ перехресних посилань після оригінальних байтів, які ніколи не переміщуються. Нанесення однієї сторінки на архів розміром 1,8 ГБ додає десятки кілобайтів; повне переписування переміщує всі 1,8 ГБ, що є різницею в п'ять порядків, а додавання є суто послідовним виводом у хвіст

Де підходять бібліотеки losLab

Обидві бібліотеки PDF від losLab постачають цю дисципліну як поверхню API. HotPDF Direct File API зчитує кількість сторінок і структуру через дескриптор файлу без побудови дерева об'єктів, копіює та розшифровує на рівні файлу і записує дельти через BeginIncrementalUpdate — стратегія додавання, описана вище, упакована. PDFlibPas йде тим самим шляхом зі своїм шаром Direct Access: потоковий зчитувач, який проходить таблицю перехресних посилань на місці, отримує об'єкти ліниво, витягує діапазони сторінок з файлу у файл і зберігає редагування як поступові ревізії. Якщо ви пишете власний парсер, клас відображувача ваш; якщо ви використовуєте конвеєр документів, дозвольте бібліотеці тримати вікно чесним

Примітка: Оптимізована обробка введення-виведення для документів гігабайтного масштабу вбудована безпосередньо у компонент HotPDF VCL для Delphi та C++Builder