Оптимизиране на IO производителността за обработка на PDF в гигабайтов мащаб

Първото полезно четене на един PDF парсер е в грешния край на файла. Форматът поставя показалеца startxref в последните байтове, така че обработката на 1.8 GB архив започва с търсене (seek) до опашката (tail), четене на един килобайт, след това скок (hop) до там, където таблицата с кръстосани препратки казва, че живее каталогът на документа. Оттам парсването е случайна разходка (random walk) в целия диапазон от байтове. Всичко, в което буферираното IO (buffered IO) е добро — последователно четене напред (sequential read-ahead) зад файловия показалец — е насочено към работно натоварване (workload), което PDF няма

Първата версия на тази статия твърдеше, че memory-mapped файл решава 32-битовия провал поради липса на памет (out-of-memory failure), който TMemoryStream удря при 2 GB вход. Това твърдение е грешно и начинът, по който е грешно, сочи към истинското решение: плъзгащ се mapping прозорец (sliding mapping window). Това, което следва, е моделът на достъп (access pattern), коригираната 32-битова история с компилируем прозоречен мапер (windowed mapper) и аритметиката на системните извиквания (syscall arithmetic) на тестов файл с размер 1.8 GB и 300 000 обекта

Защо PDF оформлението (layout) побеждава буферираните четения

Три структурни факта оформят IO модела. Първо, навигацията е управлявана от отмествания (offset-driven): таблицата с кръстосани препратки картографира номера на всеки обект до абсолютна позиция в байтове и нищо не изисква тези позиции да бъдат подредени. След години на инкрементални обновления, обект 4102 може да седи на отместване 1.6 GB, докато обект 4103 седи на 30 KB. Един цикъл на TFileStream превръща всяко извличане (fetch) в Seek плюс Read, два прехода в ядрото (kernel transitions), с буфер, който не допринася с нищо, защото следващото извличане е на стотици мегабайти разстояние

Второ, потоците от обекти (object streams - ISO 32000-1 §7.5.7) пакетират десетки или стотици малки речници в един deflated (сплескан) контейнер. Извличането на един 300-байтов речник на страница може да означава четене и надуване (inflating) на 100 KB клъстер. Обратната страна (The flip side): обекти, написани заедно, са склонни да бъдат четени заедно, така че буфер, оразмерен според клъстера, обслужва следващата дузина извличания безплатно — най-експлоатираната закономерност във формата

Трето, линеаризация (linearization). Един линеаризиран файл зарежда първата страница и таблица с подсказки (hint table) в началото (front-loads), така че потребителите да могат да го четат отпред назад. Гигабайтовите архиви почти никога не са линеаризирани: линеаризацията се унищожава от същите инкрементални обновления и сливания (merges), които са направили файла голям. Планирайте за враждебния случай: дълги скокове (hops), без подреждане, влизане първо откъм опашката (tail-first entry)

32-битовата история, коригирана

Един 32-битов Windows процес има 2 GB потребителско адресно пространство (user address space) и MapViewOfFile с брой байтове нула иска една непрекъсната резервация с размера на файла. За 2 GB вход тази резервация не може да успее: след EXE-то, разпръснатите DLL файлове и стековете на нишките, най-големият свободен непрекъснат блок в типичен 32-битов Delphi процес седи някъде между 700 MB и 1.4 GB. Извикването се проваля с ERROR_NOT_ENOUGH_MEMORY, същата стена, която TMemoryStream.LoadFromFile удря, просто преместена от ангажирана RAM памет (committed RAM) към резервация на адресно пространство. Mapping на целия файл не е решение при 32-бита, а просто същият провал зад по-добре звучащи API имена

Решението (The fix) е разделяне на двете неща, които един mapping прави. CreateFileMapping създава обекта section (раздел) и не струва никакво адресно пространство, независимо от размера на файла. Само MapViewOfFile изразходва адресно пространство и нищо не го принуждава да мапне целия section: той взема 64-битово начално отместване (starting offset) и дължина на изгледа (view length). Създайте section-а веднъж, мапнете изглед (view) от 64 до 256 MB върху региона, който се парсва, демапнете (unmap), преди да се плъзнете напред (sliding on): цената в адресно пространство е един прозорец, а не един файл. Едно ограничение: отместванията на изгледа (view offsets) трябва да са кратни на SYSTEM_INFO.dwAllocationGranularity, 64 KB на практика, така че заявка за отместване 1 000 000 се закръгля надолу до 983 040 и показалецът на извикващия се коригира напред с разликата

Мапер с плъзгащ се прозорец (sliding-window mapper) в Delphi

Класът по-долу обвива (wraps) цялата дисциплина: един section обект, един жив изглед (live view), пренареждане на гранулярността (granularity realignment) и четения, които пресичат границата на прозорец, обработени чрез разширяване на този един изглед, вместо чрез зашиване (stitching) на два

uses
  Winapi.Windows, System.SysUtils;

type
  TWindowedFileMapper = class
  private
    FFile: THandle;
    FMapping: THandle;
    FFileSize: Int64;
    FGranularity: DWORD;      // SYSTEM_INFO.dwAllocationGranularity
    FWindowSize: NativeUInt;  // размер на изгледа (view size) по подразбиране
    FViewBase: PByte;         // база на текущия изглед (подравнена - aligned)
    FViewOffset: Int64;       // отместване във файла (file offset), на което съответства FViewBase
    FViewSize: NativeUInt;    // байтове, мапнати в текущия изглед
    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;
  // Section обектът не резервира адресно пространство, какъвто и да е размерът на файла
  FMapping := CreateFileMapping(FFile, nil, PAGE_READONLY, 0, 0, nil);
  if FMapping = 0 then
    RaiseLastOSError;
  GetSystemInfo(Info);
  FGranularity := Info.dwAllocationGranularity;  // 64 KB на практика
  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): заявеният диапазон вече седи в живия изглед
  if (FViewBase <> nil) and (Offset >= FViewOffset) and
     (Offset + Int64(Size) <= FViewOffset + Int64(FViewSize)) then
    Exit(FViewBase + NativeInt(Offset - FViewOffset));

  Unmap;  // плъзгане (slide): никога не дръжте два изгледа едновременно

  // Изгледите (Views) трябва да започват на граница на allocation-granularity
  AlignedOffset := Offset - (Offset mod FGranularity);
  Delta := NativeUInt(Offset - AlignedOffset);

  MapSize := FWindowSize;
  if MapSize < Size + Delta then   // заявката прекрачва (straddles) края на прозореца:
    MapSize := Size + Delta;       // разширете този един изглед, за да я покрие
  if AlignedOffset + Int64(MapSize) > FFileSize then
    MapSize := NativeUInt(FFileSize - AlignedOffset);  // ограничи (clamp) в края на файла (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;

Два детайла носят тежестта. Бързият път (fast path) в горната част на Map връща показалец без преход в ядрото (kernel transition), когато заявеният диапазон вече седи вътре в живия изглед (live view); благодарение на клъстеризирането на потоците от обекти, това е често срещаният случай и оттам идват спестяванията. А заявка, която прекрачва (straddles) края на прозореца по подразбиране, увеличава MapSize за този един изглед, вместо да зашива (stitching) два, което запазва ReadBytes като един ред (one-liner) и освобождава извикващите от цикли за частично четене

Размерът на прозореца е прощаващо копче (forgiving knob): при 64 MB едно пълно обхождане (full sweep) на 1.8 GB файл е 29 изгледа, при 256 MB е 8, но всяка резервация е по-трудна за поставяне във фрагментирано 32-битово пространство, а под около 16 MB файлове с много скокове (hop-heavy) ремапват достатъчно често, за да се забележи. Навсякъде в диапазона от 64 до 256 MB, трафикът от мапвания (map traffic) е статистически шум

Броене на системните извиквания (syscalls)

Сега аритметиката. Тестов файл: 1.8 GB, 300 000 непреки обекта (indirect objects), усреднени на около 600 байта полезен товар. Парсер на ниво обект (per-object parser) извлича всеки един с SetFilePointerEx плюс 4 KB ReadFile: 600 000 прехода в ядрото (kernel transitions). Едно кеширано системно извикване (syscall) за четене прави двупосочно пътуване (round-trips) за грубо 1.5 µs на съвременен x64 хардуер, така че това са 600 000 × 1.5 µs ≈ 0.9 секунди чист режиен разход (overhead) на ядрото, преди да се парсне и един байт — най-добрият случай с топъл кеш (warm-cache). Студен (Cold), всеки скок е операция на устройството: при ~20 µs ефективна латентност на NVMe 4 KB случайни четения, 300 000 от тях струват около 6 секунди време на устройството; при хранилище от SATA-клас — минути

Четенията също така движат грешни данни: 300 000 × 4 KB избутват 1.2 GB през потребителски буфери, за да доставят грубо 180 MB полезен товар — шесткратно усилване (amplification), всеки байт копиран от ядрото (kernel) към потребителя (user)

Един read-ahead буфер (за четене напред), оразмерен според клъстерите на потоците от обекти, е първото честно подобрение: едно 256 KB четене на клъстер вместо едно на обект намалява броя на преходите с един до два порядъка (orders of magnitude). Това е и правилният инструмент там, където mapping-ът е неудобен, обикновено мрежови споделяния (network shares)

Прозоречният мапер (windowed mapper) отива по-далеч. Едно пълно обхождане е 29 MapViewOfFile и 29 UnmapViewOfFile извиквания, 58 изрични прехода срещу 600 000. Едно реално xref-управлявано парсване не е чисто обхождане, но бързият път абсорбира всяко извличане вътре в живия прозорец; пасаж (pass) за индексиране на метаданни върху тестовия архив се установи на няколкостотин ремапвания. Mapping-ът не премахва работата на ядрото: той преобразува изричните системни извиквания (syscalls) в откази на страници (page faults), които мениджърът на паметта (memory manager) разрешава в многостранични клъстери (multi-page clusters), направо от файловия кеш (file cache) без копиране в потребителското пространство (no user-space copy), и регионите, които никога не са докоснати, не струват нищо. От край до край (End to end), пасажът за индексиране премина от 23 сек студен (cold) и 7.1 сек топъл (warm) с четения на ниво обект към 6.5 сек студен и 1.9 сек топъл с мапера; това, което остава, е zlib inflate (декомпресия), а не IO

Къде се вписва FILE_FLAG_NO_BUFFERING

FILE_FLAG_NO_BUFFERING заобикаля системния кеш в замяна на строги правила за подравняване (hard alignment rules): отмествания, дължини и адреси на буфери, всички подравнени по сектори (sector-aligned). Той изработва прехраната си (earns its keep) при еднопроходни (single-pass) последователни задачи, които иначе биха наводнили кеша с байтове, които никой не чете два пъти — пакетна (batch) повторна сериализация, която пренаписва целия архив, или линеаризационен пасаж върху завършен изход (finished output). С 4 до 8 MB подравнени буфери той се доближава до последователната честотна лента (sequential bandwidth) на устройството, без да замърсява кеша

Това е точно погрешно за парсване (parsing). Случайните xref скокове (hops) през небуфериран манипулатор (unbuffered handle) превръщат всяко извличане на 300-байтов речник в пълно физическо четене без кеш, който да абсорбира второто посещение — а PDF парсването посещава региони отново постоянно, защото различни страници се разрешават (resolve) в едни и същи потоци от обекти. Небуферирано IO за последователното пренаписване, мапнато (mapped) или кеширано IO за случайното парсване; флагът е на база манипулатор (per-handle), така че един конвейер (pipeline) може да държи и двете на един и същ файл

64-бита, работни набори (working sets) и страната на записа (write side)

При 64-битов билд възражението за адресното пространство изчезва: подайте размера на файла като прозорец и класът по-горе дегенерира до един-единствен пълен mapping. Уловката (The catch) при дългоработещи услуги (long-running services): read-only file-backed страниците (страници само за четене, подкрепени от файл) не таксуват (charge) ангажимент (commit), така че commit броячите остават спокойни, но всяка докосната страница се присъединява към работния набор (working set); парснете по-голямата част от 1.8 GB и работният набор нараства, за да съвпадне, изгонвайки (evicting) всичко останало. Ограничените прозорци слагат таван на това, така че плъзгащият се модел (sliding pattern) остава правилната опция по подразбиране, дори когато адресното пространство е свободно

От страната на записа (write side), най-евтиното IO е IO, което никога не е издадено. Механизмът за инкрементално обновяване (incremental update) на PDF (ISO 32000-1 §7.5.6) добавя (appends) променените обекти и нова секция с кръстосани препратки след оригиналните байтове, които никога не се движат. Подпечатването (Stamping) на една страница върху 1.8 GB архив добавя десетки килобайти; пълно пренаписване движи всички 1.8 GB, на пет порядъка (orders of magnitude) разстояние, а добавянето (append) е чист последователен изход на опашката (tail)

Къде се вписват библиотеките на losLab

И двете PDF библиотеките на losLab доставят тази дисциплина като API повърхност. HotPDF Direct File API чете броя на страниците и структурата чрез файлов манипулатор (file handle), без да изгражда дървото на обектите, копира и декриптира на ниво файл, и записва делти (deltas) чрез BeginIncrementalUpdate — стратегията само за добавяне (append-only) по-горе, пакетирана. PDFlibPas поема по същия път със своя Direct Access слой: поточен четец (streaming reader), който обхожда таблицата с кръстосани препратки на място (in place), извлича обекти мързеливо (lazily), извлича (extracts) диапазони от страници от файл във файл и запазва редакциите като инкрементални ревизии. Ако пишете свой собствен парсер, класът mapper е ваш да го вземете; ако изпълнявате конвейер за документи (document pipeline), оставете библиотеката да поддържа прозореца честен (honest)

Забележка: Оптимизираната обработка на IO за документи в гигабайтов мащаб е вградена директно в компонента HotPDF VCL за Delphi и C++Builder