Optimalizácia IO výkonu pre spracovanie PDF v gigabajtovej mierke

Prvé užitočné čítanie z analyzátora PDF je na nesprávnom konci súboru. Formát umiestňuje ukazovateľ startxref do posledných bajtov, takže spracovanie 1,8 GB archívu začína presunutím na koniec, prečítaním jedného kilobajtu, a potom skokom na miesto, kde podľa krížovej referenčnej tabuľky leží katalóg dokumentu. Odtiaľ je analýza náhodnou prechádzkou po celom rozsahu bajtov. Všetko, v čom je vyrovnávacie IO (buffered IO) dobré — sekvenčné čítanie vopred za ukazovateľom súboru — je zamerané na pracovnú záťaž, ktorú formát PDF nemá

Prvá verzia tohto článku tvrdila, že súbor mapovaný do pamäte rieši 32-bitové zlyhanie z dôvodu nedostatku pamäte, s ktorým sa stretáva TMemoryStream pri 2 GB vstupe. Toto tvrdenie je nesprávne a spôsob, akým je nesprávne, poukazuje na skutočnú opravu: posuvné mapovacie okno. V nasledujúcom texte je popísaný vzor prístupu, opravený 32-bitový príbeh s kompilovateľným mapovačom s oknami a aritmetika systémových volaní na testovacom súbore veľkosti 1,8 GB s 300 000 objektmi

Prečo rozloženie PDF poráža čítanie do vyrovnávacej pamäte

Vzor IO formujú tri štrukturálne skutočnosti. Po prvé, navigácia je riadená ofsetom: krížová referenčná tabuľka mapuje každé číslo objektu na absolútnu pozíciu bajtu a nič nevyžaduje, aby tieto pozície boli usporiadané. Po rokoch prírastkových aktualizácií môže objekt 4102 ležať na ofsete 1,6 GB, zatiaľ čo objekt 4103 leží na 30 KB. Slučka TFileStream mení každé načítanie na Seek (vyhľadanie) plus Read (čítanie), dva prechody jadra, s vyrovnávacou pamäťou, ktorá ničím neprispieva, pretože ďalšie načítanie je vzdialené stovky megabajtov

Po druhé, toky objektov (ISO 32000-1 §7.5.7) balia desiatky alebo stovky malých slovníkov do jedného deflatovaného kontajnera. Získanie jedného 300-bajtového slovníka stránky môže znamenať prečítanie a infláciu (nahustenie) 100 KB klastra. Na druhej strane: objekty napísané spolu majú tendenciu byť čítané spolu, takže vyrovnávacia pamäť dimenzovaná na klaster slúži pre ďalšiu desiatku načítaní zadarmo — čo je najviac využiteľná pravidelnosť vo formáte

Po tretie, linearizácia. Linearizovaný súbor umiestňuje na začiatok prvú stránku a tabuľku nápovied, aby si ho spotrebitelia mohli čítať spredu dozadu. Gigabajtové archívy nie sú takmer nikdy linearizované: linearizácia je zničená tými istými prírastkovými aktualizáciami a zlučovaniami, vďaka ktorým je súbor veľký. Plánujte na najhorší prípad: dlhé skoky, žiadne usporiadanie, vstup najprv z konca

Opravený 32-bitový príbeh

32-bitový proces Windows má 2 GB užívateľského adresného priestoru a MapViewOfFile s počtom bajtov nula žiada o jednu súvislú rezerváciu o veľkosti súboru. Pre 2 GB vstup táto rezervácia nemôže uspieť: po EXE, rozptýlených DLL a zásobníkoch vlákien sa najväčší voľný súvislý blok v typickom 32-bitovom Delphi procese nachádza niekde medzi 700 MB a 1,4 GB. Volanie zlyhá s chybou ERROR_NOT_ENOUGH_MEMORY, rovnakou stenou, do ktorej narazí TMemoryStream.LoadFromFile, len presunutou z potvrdenej pamäte RAM na rezerváciu adresného priestoru. Celosúborové mapovanie nie je na 32-bitoch žiadnou opravou, len rovnakým zlyhaním za lepšie znejúcimi názvami API

Riešením je oddelenie dvoch vecí, ktoré mapovanie robí. CreateFileMapping vytvorí objekt sekcie a nestojí vôbec žiadny adresný priestor, bez ohľadu na veľkosť súboru. Iba MapViewOfFile míňa adresný priestor a nič ho nenúti mapovať celú sekciu: prijíma 64-bitový počiatočný ofset a dĺžku zobrazenia. Vytvorte sekciu raz, namapujte 64 až 256 MB zobrazenie na časť, ktorá sa analyzuje, zrušte mapovanie predtým, ako sa posuniete ďalej: nákladom na adresný priestor je jedno okno, nie jeden súbor. Jedno obmedzenie: ofsety zobrazenia musia byť násobky SYSTEM_INFO.dwAllocationGranularity, v praxi 64 KB, takže požiadavka na ofset 1 000 000 sa zaokrúhli nadol na 983 040 a ukazovateľ volajúceho sa upraví dopredu o tento rozdiel

Mapovač s posuvným oknom v Delphi

Nižšie uvedená trieda obaluje celú disciplínu: jeden objekt sekcie, jedno živé zobrazenie, opätovné zarovnanie granularity a čítania, ktoré prekračujú hranicu okna, sú riešené zväčšením tohto jedného zobrazenia namiesto spájania dvoch

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;

Dva detaily nesú najväčšiu záťaž. Rýchla cesta na vrchu Map vracia ukazovateľ bez prechodu jadrom, keď požadovaný rozsah už sedí vo vnútri živého zobrazenia; vďaka zhlukovaniu (clustering) toku objektov je to bežný prípad a zdroj úspor. A požiadavka, ktorá presahuje koniec predvoleného okna, zväčší MapSize pre toto jedno zobrazenie namiesto spájania dvoch, vďaka čomu zostáva ReadBytes jednoradovým príkazom a volajúci sú ušetrení slučiek čiastočného čítania

Veľkosť okna je odpúšťajúci parameter: pri 64 MB znamená úplný prechod 1,8 GB súboru 29 zobrazení, pri 256 MB je to 8, ale každá rezervácia sa ťažšie umiestňuje vo fragmentovanom 32-bitovom priestore a pod hranicou asi 16 MB sa súbory s veľkým množstvom skokov premapúvajú dostatočne často na to, aby to bolo vidieť. Kdekoľvek v rozsahu 64 až 256 MB je prevádzka máp iba štatistickým šumom

Počítanie systémových volaní

Teraz k aritmetike. Testovací súbor: 1,8 GB, 300 000 nepriamych objektov s priemerne asi 600 bajtmi užitočného zaťaženia. Analyzátor na úrovni jednotlivých objektov načítava každý jeden pomocou SetFilePointerEx plus 4 KB ReadFile: 600 000 prechodov jadrom. Uložené volanie na čítanie trvá približne 1,5 μs na súčasnom x64 hardvéri, takže to je 600 000 × 1,5 μs ≈ 0,9 sekundy čistej réžie jadra pred analyzovaním jediného bajtu — najlepší prípad pri zahriatej vyrovnávacej pamäti. Zastudena je každý skok operáciou zariadenia: pri zhruba 20 μs efektívnej latencii náhodného čítania NVMe blokov veľkosti 4 KB, 300 000 takýchto čítaní stojí asi 6 sekúnd času zariadenia; na úložisku triedy SATA sú to minúty

Tieto čítania zároveň presúvajú nesprávne údaje: 300 000 × 4 KB pretlačí 1,2 GB cez používateľské vyrovnávacie pamäte, aby sa doručilo približne 180 MB užitočného zaťaženia — šesťnásobné zosilnenie, každý bajt je kopírovaný z jadra používateľovi

Vyrovnávacia pamäť na čítanie vopred, dimenzovaná na veľkosť klastrov objektových tokov, je prvým skutočným zlepšením: jedno 256 KB čítanie na klaster namiesto jedného na objekt znižuje počet prechodov o jeden až dva rády. Je to tiež správny nástroj tam, kde je mapovanie neohrabané, zvyčajne na sieťových zdieľaných zložkách

Mapovač s oknami ide ešte ďalej. Úplný prechod je 29 volaní MapViewOfFile a 29 volaní UnmapViewOfFile, 58 explicitných prechodov v porovnaní so 600 000. Skutočná analýza riadená pomocou xref nie je čistým prechodom, ale rýchla cesta absorbuje každé načítanie vo vnútri živého okna; prechod indexujúci metadáta cez testovací archív sa ustálil na niekoľkých stovkách premapovaní. Mapovanie neodstráni prácu jadra: mení explicitné systémové volania na výpadky pamäťových stránok (page faults), ktoré správca pamäte rieši vo viacstránkových klastroch, priamo z vyrovnávacej pamäte súboru bez kopírovania do používateľského priestoru a regióny, ktorých sa nikdy nedotkne, nestoja nič. Od začiatku do konca prešla indexovacia fáza z 23 sekúnd zastudena a 7,1 sekundy zahriateho stavu s čítaniami pre každý objekt na 6,5 sekundy zastudena a 1,9 sekundy zahriateho stavu s mapovačom; to, čo zostáva, je zlib inflate (rozbaľovanie), nie IO

Kde sa hodí FILE_FLAG_NO_BUFFERING

Príznak FILE_FLAG_NO_BUFFERING obchádza systémovú vyrovnávaciu pamäť (cache) výmenou za tvrdé pravidlá zarovnania: ofsety, dĺžky a adresy vyrovnávacej pamäte sú všetky zarovnané so sektormi. Oplatí sa to pri jednopriechodových sekvenčných úlohách, ktoré by inak zaplavili vyrovnávaciu pamäť bajtmi, ktoré nikto nečíta dvakrát — dávková reserializácia, ktorá prepíše celý archív, alebo linearizačný prechod cez hotový výstup. S usporiadanými 4 až 8 MB vyrovnávacími pamäťami sa približuje sekvenčnej šírke pásma zariadenia bez znečistenia vyrovnávacej pamäte

Na analýzu je to ale úplne zlé. Náhodné xref skoky cez ne-bufferovaný handle zmenia každé načítanie 300-bajtového slovníka na plné fyzické čítanie, pričom neexistuje vyrovnávacia pamäť, ktorá by absorbovala druhú návštevu — a analýza PDF neustále navštevuje tie isté oblasti, pretože rôzne stránky odkazujú do rovnakých objektových tokov. Ne-bufferované IO pre sekvenčné prepísanie, mapované alebo zacheované IO pre náhodnú analýzu; príznak platí pre handle (identifikátor), takže jedno pripojenie môže obsahovať oba pre ten istý súbor

64-bit, pracovné sady (working sets) a strana zápisu

V 64-bitovom zostavení (builde) mizne námietka o adresnom priestore: odovzdajte veľkosť súboru ako okno a vyššie uvedená trieda degraduje na jedno jediné plné mapovanie. Háčik v dlho bežiacich službách: stránky mapované iba na čítanie nežiadajú žiadne potvrdenie pamäte (commit), takže počítadlá potvrdení (commit) zostávajú pokojné, ale každá navštívená stránka sa pripojí k pracovnej sade (working set); analyzujte väčšinu z 1,8 GB a pracovná sada narastie tak, že vytlačí všetko ostatné. Ohraničené okná na to kladú strop, takže vzor s posuvným oknom zostáva správnou voľbou, aj keď je adresný priestor voľný

Na strane zápisu je najlacnejšie to IO (čítanie/zápis), ktoré sa nikdy nevykoná. Mechanizmus prírastkovej aktualizácie PDF (ISO 32000-1 §7.5.6) pripája zmenené objekty a novú sekciu s krížovými referenciami (cross-reference) za pôvodné bajty, ktoré sa nikdy nepresúvajú. Opečiatkovanie jednej stránky na 1,8 GB archív pripojí len desiatky kilobajtov; úplné prepísanie presunie celých 1,8 GB, čo je rozdiel piatich rádov a pripojenie na koniec je iba čisto sekvenčný výstup

Kam zapadajú knižnice losLab

Obe PDF knižnice losLab obsahujú túto disciplínu zabudovanú do API rozhrania. Priame súborové API v knižnici HotPDF Direct File API číta počty stránok a štruktúru prostredníctvom odovzdaného file handle (ovládač súboru) bez budovania stromu objektov, kopíruje a dešifruje sa na úrovni súboru a zapisuje delty (zmeny) prostredníctvom BeginIncrementalUpdate — teda využíva stratégiu, ktorá pripája iba to, čo je spomenuté vyššie. PDFlibPas sa vydáva rovnakou cestou s vrstvou Direct Access: prináša streamovací analyzátor, ktorý prehľadáva priamo krížovú referenčnú tabuľku (cross-reference table), získava objekty iba v prípade ich požiadania (lazily), exportuje/extrahuje celé rady stránok od súboru do súboru a ukladá zmeny ako prírastkové revízie. Ak si píšete svoj vlastný analyzátor (parser), kľudne si vezmite triedu pre mapovač (mapper), prečítajte si vyššie zmienenú problematiku; ak plánujete riešiť komplexnú prácu pre dokumenty, jednoducho nechajte správu na samotnej knižnici a okno (window) bude v bezpečí

Poznámka: Optimalizované IO ovládanie na manipuláciu gigabajtových dokumentov je zabudované priamo do komponenty HotPDF VCL Component pre jazyk Delphi a C++Builder