IO-teljesítmény optimalizálása gigabájtos skálájú PDF-feldolgozáshoz

Egy PDF-feldolgozó (parser) első hasznos olvasása a fájl rossz végén történik. A formátum a startxref mutatót (pointer) a végső bájtokba helyezi, így egy 1,8 GB-os archívum feldolgozása a farokhoz való ugrással (seek), egy kilobájtos olvasással kezdődik, majd egy ugrással oda, ahol a kereszthivatkozási tábla szerint a dokumentumkatalógus él. Innentől kezdve a feldolgozás egy véletlenszerű séta a teljes bájttartományon. Minden, amiben a pufferelt IO jó — szekvenciális előreolvasás (read-ahead) a fájlmutató mögött —, egy olyan munkaterhelésre irányul, amivel a PDF nem rendelkezik

Ennek a cikknek az első verziója azt állította, hogy egy memóriába leképezett fájl megoldja azt a 32 bites memóriahiányos (out-of-memory) hibát, amelybe a TMemoryStream egy 2 GB-os bemenetnél ütközik. Ez az állítás téves, és az a mód, ahogyan téves, a valódi javításra mutat rá: egy csúszó leképezési ablakra. Az alábbiakban bemutatjuk a hozzáférési mintát, a javított 32 bites történetet egy lefordítható ablakos mapperrel (windowed mapper), valamint a rendszerhívások aritmetikáját egy 1,8 GB-os, 300 000 objektumot tartalmazó tesztfájlon

Miért hiúsítja meg a PDF elrendezése a pufferelt olvasásokat

Három szerkezeti tény alakítja az IO mintát. Először is, a navigáció eltolás-vezérelt (offset-driven): a kereszthivatkozási tábla minden objektumszámot egy abszolút bájtpozícióhoz rendel, és semmi sem követeli meg, hogy ezek a pozíciók sorrendben legyenek. Évekig tartó növekményes frissítések (incremental updates) után a 4102. objektum az 1,6 GB-os eltolásnál is ülhet, míg a 4103. objektum 30 KB-nál. Egy TFileStream ciklus minden lekérést egy Seek plusz egy Read hívássá, két kernel átmenetté (transition) alakít, egy olyan pufferrel, amely semmivel sem járul hozzá, mert a következő lekérés több száz megabájtra van

Másodszor, az objektum-adatfolyamok (ISO 32000-1 §7.5.7) több tucat vagy több száz kis szótárat csomagolnak egyetlen tömörített (deflated) tárolóba. Egyetlen 300 bájtos oldalszótár lekérése egy 100 KB-os fürt (cluster) beolvasását és felfújását (inflate) jelentheti. A másik oldal: az együtt írt objektumokat hajlamosak vagyunk együtt olvasni, így a fürt méretére beállított puffer a következő tucat lekérést ingyen kiszolgálja — ez a formátum leginkább kiaknázható szabályszerűsége

Harmadszor, a linearizáció. Egy linearizált fájl előre tölti (front-loads) az első oldalt és egy tipp (hint) táblát, így a fogyasztók elölről hátrafelé olvashatják azt. A gigabájtos archívumok szinte soha nem linearizáltak: a linearizációt ugyanazok a növekményes frissítések és összevonások (merges) teszik tönkre, amelyek a fájlt naggyá tették. Készüljön fel az ellenséges (hostile) esetre: hosszú ugrások, nincs sorrend, hátulról-előre haladó belépés

A 32 bites történet, javítva

Egy 32 bites Windows folyamat (process) 2 GB felhasználói címtartománnyal (address space) rendelkezik, és a MapViewOfFile nulla bájtszámmal a fájl méretének megfelelő, egyetlen összefüggő lefoglalást kér. Egy 2 GB-os bemenetnél ez a foglalás nem sikerülhet: az EXE, az elszórt DLL-ek és a szálak (thread) vermeinek lefoglalása után a legnagyobb szabad összefüggő blokk egy tipikus 32 bites Delphi folyamatban valahol 700 MB és 1,4 GB között van. A hívás ERROR_NOT_ENOUGH_MEMORY hibával meghiúsul, ugyanazzal a fallal, amelybe a TMemoryStream.LoadFromFile ütközik, csak a lekötött RAM-ról a címtartomány-foglalásra helyeződött át. Egy teljes fájlos leképezés nem jelent megoldást 32 biten, csak ugyanaz a hiba, jobban hangzó API-nevek mögött

A javítás elválasztja azt a két dolgot, amit egy leképezés csinál. A CreateFileMapping létrehozza a szakasz (section) objektumot, és semmibe sem kerül a címtartomány szempontjából, függetlenül a fájl méretétől. Csak a MapViewOfFile költ címtartományt, és semmi sem kényszeríti arra, hogy a teljes szakaszt leképezze: egy 64 bites kezdő eltolást (offset) és egy nézet (view) hosszt fogad be. Hozza létre a szakaszt egyszer, képezzen le egy 64-256 MB-os nézetet a feldolgozás alatt álló terület fölött, szüntesse meg a leképezést (unmap), mielőtt tovább csúsztatja: a címtartomány-költség egyetlen ablak, nem egyetlen fájl. Egy korlátozás (constraint): a nézetek eltolásainak (view offsets) a SYSTEM_INFO.dwAllocationGranularity többszöröseinek kell lenniük, ami a gyakorlatban 64 KB, így egy 1 000 000 eltolásra vonatkozó kérés 983 040-re kerekítődik le, és a hívó mutatója a különbséggel előre tolódik

Egy csúszóablakos leképező (mapper) Delphiben

Az alábbi osztály az egész folyamatot (discipline) összefogja: egyetlen szakasz (section) objektum, egyetlen élő nézet, granularitási (granularity) újraigazítás, és egy ablak határát keresztező olvasások kezelése úgy, hogy egyetlen nézetet növel, nem pedig kettőt ölt össze

uses
  Winapi.Windows, System.SysUtils;

type
  TWindowedFileMapper = class
  private
    FFile: THandle;
    FMapping: THandle;
    FFileSize: Int64;
    FGranularity: DWORD;      // SYSTEM_INFO.dwAllocationGranularity
    FWindowSize: NativeUInt;  // alapértelmezett nézetméret
    FViewBase: PByte;         // a jelenlegi nézet alapja (igazított)
    FViewOffset: Int64;       // a fájl eltolás, aminek az FViewBase megfelel
    FViewSize: NativeUInt;    // a jelenlegi nézetben leképezett bájtok
    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;
  // A section objektum nem foglal le címtartományt, bármekkora is a fájl
  FMapping := CreateFileMapping(FFile, nil, PAGE_READONLY, 0, 0, nil);
  if FMapping = 0 then
    RaiseLastOSError;
  GetSystemInfo(Info);
  FGranularity := Info.dwAllocationGranularity;  // a gyakorlatban 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(
      'A %d helyen végzett %d bájtos leképezési kérés kívül esik a fájlon',
      [Offset, Int64(Size)]);

  // Gyors útvonal: a kért tartomány már a mostani élő nézeten belül van
  if (FViewBase <> nil) and (Offset >= FViewOffset) and
     (Offset + Int64(Size) <= FViewOffset + Int64(FViewSize)) then
    Exit(FViewBase + NativeInt(Offset - FViewOffset));

  Unmap;  // csúsztatás: soha ne tartson meg két nézetet egyszerre

  // A nézeteknek elosztási granularitási határon kell kezdődniük
  AlignedOffset := Offset - (Offset mod FGranularity);
  Delta := NativeUInt(Offset - AlignedOffset);

  MapSize := FWindowSize;
  if MapSize < Size + Delta then   // a kérés átnyúlik az ablak végén:
    MapSize := Size + Delta;       // növeljük meg ezt a nézetet, hogy lefedje
  if AlignedOffset + Int64(MapSize) > FFileSize then
    MapSize := NativeUInt(FFileSize - AlignedOffset);  // csonkolás az EOF-nál

  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;

Két részlet cipeli a súlyt. A gyors útvonal a Map tetején egy mutatóval (pointer) tér vissza kernel átmenet (kernel transition) nélkül, amikor a kért tartomány már az élő nézeten belül helyezkedik el; az objektum-adatfolyamok fürtözésének (clustering) köszönhetően ez az általános eset, és innen származnak a megtakarítások. Az a kérés pedig, amelyik átnyúlik az alapértelmezett ablak végén, a MapSize-t növeli meg annak az egyetlen nézetnek a számára ahelyett, hogy kettőt kötne össze, így a ReadBytes egysoros marad, és a hívók mentesülnek a részleges olvasási ciklusoktól

Az ablakméret egy megbocsátó beállítási gomb (knob): 64 MB-nál egy 1,8 GB-os fájl teljes letapogatása (sweep) 29 nézetet jelent, 256 MB-nál ez 8, de minden foglalást (reservation) nehezebb elhelyezni egy töredezett (fragmented) 32 bites térben, és nagyjából 16 MB alatt a sok ugrást tartalmazó (hop-heavy) fájlok észrevehetően gyakran végeznek újra-leképezést (remap). Bárhol a 64 és 256 MB közötti tartományban, a leképezési forgalom csupán statisztikai zaj

Rendszerhívások (syscalls) számolása

Most jöjjön az aritmetika. Tesztfájl: 1,8 GB, 300 000 indirekt objektum, átlagosan nagyjából 600 bájt hasznos teherrel (payload). Egy objektumonkénti értelmező (parser) mindegyiket egy SetFilePointerEx plusz egy 4 KB-os ReadFile hívással kéri le: ez 600 000 kernel átmenet. Egy gyorsítótárazott (cached) olvasási rendszerhívás nagyjából 1,5 μs alatt fut le egy oda-vissza úton (round-trip) a jelenlegi x64 hardvereken, szóval ez 600 000 × 1,5 μs ≈ 0,9 másodperc tisztán kernel rezsiköltség (overhead), mielőtt egyetlen bájtot is értelmeznénk — ez a legjobb eset (warm-cache). Hidegen (cold), minden ugrás egy eszközművelet: az NVMe 4 KB-os véletlenszerű olvasásának ~20 μs-os tényleges késleltetésével (latency) számolva 300 000 ilyen ugrás körülbelül 6 másodperc eszközidőbe kerül; SATA-osztályú tárolón ez percekig is eltarthat

Az olvasások ráadásul rossz adatokat mozgatnak: 300 000 × 4 KB összesen 1,2 GB adatot nyom át a felhasználói puffereken, hogy nagyjából 180 MB hasznos terhet (payload) kézbesítsen — ez hatszoros erősítés (amplification), minden egyes bájtot a kernelből a felhasználóhoz másolva

Az objektum-adatfolyamok fürtjeihez (clusters) igazított előreolvasási puffer (read-ahead buffer) az első őszinte előrelépés: egy 256 KB-os olvasás fürtönként az objektumonkénti egy helyett, egy-két nagyságrenddel csökkenti az átmenetek számát. Ráadásul ez a megfelelő eszköz ott, ahol a leképezés (mapping) nehézkes, általában a hálózati megosztásoknál (network shares)

Az ablakos mapper (windowed mapper) még tovább megy. Egy teljes letapogatás 29 MapViewOfFile és 29 UnmapViewOfFile hívást, 58 explicit átmenetet jelent a 600 000-rel szemben. Egy valódi xref-vezérelt értelmezés (parse) nem jelent tiszta letapogatást, de a gyors útvonal minden lekérést (fetch) elnyel az élő ablakon belül; egy metaadat-indexelő menet a tesztarchívumon néhány száz újra-leképezésnél (remap) állapodott meg. A leképezés nem távolítja el a kernelmunkát: az explicit rendszerhívásokat laphibákká (page faults) alakítja, amelyeket a memóriakezelő többoldalas (multi-page) fürtökben (clusters) old meg, egyenesen a fájl gyorsítótárból (file cache) user-space másolás nélkül, és a soha nem érintett régiók semmibe sem kerülnek. A folyamat elejétől a végéig az indexelési menet a hideg 23 mp-ről és a meleg 7,1 mp-ről (objektumonkénti olvasással) hideg 6,5 mp-re és meleg 1,9 mp-re csökkent a mapperrel; ami maradt, az a zlib inflate, nem pedig az IO

Hova illik a FILE_FLAG_NO_BUFFERING

A FILE_FLAG_NO_BUFFERING megkerüli a rendszer gyorsítótárát szigorú illesztési szabályok cserébe: az eltolások, a hosszak és a puffercímek mind szektor-igazítottak (sector-aligned) kellenek hogy legyenek. Ez azokon az egymenetes (single-pass) szekvenciális feladatokon hozza be az árát, amelyek egyébként elárasztanák a gyorsítótárat olyan bájtokkal, amiket senki sem olvas el kétszer — egy kötegelt (batch) újra-szerializálás (re-serialization), amely újraírja a teljes archívumot, vagy egy linearizációs menet a kész kimeneten. 4-8 MB-os illesztett (aligned) pufferekkel megközelíti az eszköz szekvenciális sávszélességét anélkül, hogy szennyezné a gyorsítótárat

De ez pontosan rossz a feldolgozáshoz (parsing). A véletlenszerű xref ugrások egy nem pufferelt leírón (handle) keresztül minden 300 bájtos szótár lekérést egy teljes fizikai olvasássá alakítanak gyorsítótár nélkül, ami elnyelné a második látogatást — és a PDF értelmezése folyamatosan újra meglátogatja a régiókat, mivel a különböző oldalak ugyanazokba az objektum-adatfolyamokba (object streams) oldódnak fel. Nem pufferelt IO a szekvenciális újraíráshoz, leképezett vagy gyorsítótárazott IO a véletlenszerű értelmezéshez; a jelző (flag) leírónkénti (per-handle), így egy folyamat mindkettőt tartalmazhatja ugyanazon a fájlon

64-bit, munkakészletek (working sets) és az írási oldal

Egy 64 bites verzión a címtartománnyal (address space) kapcsolatos kifogás eltűnik: adja meg a fájl méretét ablakként, és a fenti osztály egyetlen teljes leképezéssé (full mapping) degradálódik. A buktató (catch) a hosszan futó szolgáltatásoknál van: az írásvédett, fájl-alapú oldalak (file-backed pages) nem terhelik a memóriafoglalási (commit) pultokat, így a commit számlálók nyugodtak maradnak, de minden érintett oldal csatlakozik a munkakészlethez (working set); értelmezze egy 1,8 GB-os fájl nagy részét, és a munkakészlet úgy nő, hogy ehhez igazodjon, mindent mást kilakoltatva (evicting). A korlátozott ablakok plafont szabnak ennek, így a csúszó minta (sliding pattern) marad a helyes alapértelmezés még ott is, ahol a címtér szabad

Az írási oldalon a legolcsóbb IO az az IO, amit soha nem adnak ki. A PDF növekményes frissítési mechanizmusa (ISO 32000-1 §7.5.6) a megváltozott objektumokat és egy új kereszthivatkozási szakaszt (cross-reference section) az eredeti bájtok után fűzi hozzá, amelyek soha nem mozdulnak el. Ha rábélyegzünk egy oldalt az 1,8 GB-os archívumra, több tíz kilobájtot fűz hozzá; egy teljes újraírás az egész 1,8 GB-ot mozgatja, ami öt nagyságrendnyi különbséget jelent, és a hozzáfűzés tiszta szekvenciális kimenet (sequential output) a farkánál (tail)

Hova illeszkednek a losLab könyvtárai

Mindkét losLab PDF-könyvtár API-felületként (API surface) szállítja ezt a módszertant. A HotPDF Direct File API fájlleírón keresztül (file handle) olvassa az oldalszámokat és a struktúrát anélkül, hogy felépítené az objektumfát, fájlszinten másol és dekódol, valamint a változásokat (deltas) a BeginIncrementalUpdate-en keresztül írja ki — ami a fenti, csak hozzáfűző (append-only) stratégia, becsomagolva. A PDFlibPas ugyanazt az utat járja be a Direct Access rétegével: egy stream olvasó, amely a helyén (in place) járja be a kereszthivatkozási (cross-reference) táblát, lusta (lazy) módon kéri le az objektumokat, fájlból fájlba bont ki oldaltartományokat (page ranges), és a szerkesztéseket (edits) növekményes (incremental) felülvizsgálatokként (revisions) menti. Ha saját feldolgozót (parser) ír, a leképező osztályt (mapper class) elviheti magával; ha egy dokumentum folyamatot (document pipeline) futtat, hagyja, hogy a könyvtár tartsa kordában az ablakot

Megjegyzés: A gigabájtos nagyságrendű dokumentumok optimalizált IO-kezelése közvetlenül be van építve a Delphihez és C++Builderhez készült HotPDF VCL Komponensbe