Optimizacija V/I zmogljivosti za obdelavo PDF dokumentov gigabajtne velikosti

Prvo uporabno branje razčlenjevalnika PDF-jev se nahaja na napačnem koncu datoteke. Format postavi kazalec startxref v zadnje bajte, zato se obdelava 1,8 GB velikega arhiva začne s skokom (seek) na konec, prebiranjem enega kilobajta in nato skokom na mesto, kjer naj bi po navedbah tabele navzkrižnih referenc (cross-reference table) živel katalog dokumenta. Od tam naprej je razčlenjevanje naključno sprehajanje (random walk) po celotnem bajtnem razponu. Vse tisto, v čemer je medpomnjeni V/I (buffered IO) dober — zaporedno predčasno branje (sequential read-ahead) za kazalcem datoteke —, je usmerjeno v delovno obremenitev, ki je PDF nima

Prva različica tega članka je trdila, da v pomnilnik preslikana datoteka (memory-mapped file) reši 32-bitno napako pomanjkanja pomnilnika (out-of-memory failure), na katero naleti TMemoryStream pri 2 GB velikem vhodu. Ta trditev je napačna in način, kako je napačna, kaže na pravo rešitev: drsno okno preslikave (sliding mapping window). V nadaljevanju so opisani vzorec dostopa, popravljena 32-bitna zgodba s prevajljivim (compilable) oknastim preslikovalnikom in aritmetika sistemskih klicev (syscall) na testni datoteki, ki obsega 1,8 GB in vsebuje 300.000 objektov

Zakaj zgradba PDF dokumenta premaga medpomnjeno branje

V/I vzorec oblikujejo tri strukturna dejstva. Prvič, navigacija temelji na odmikih (offset-driven): tabela navzkrižnih referenc preslika številko vsakega objekta v absolutno pozicijo v bajtih (absolute byte position) in nič ne zahteva, da bi morale biti te pozicije urejene. Po letih postopnih posodobitev se lahko objekt 4102 nahaja na odmiku 1,6 GB, medtem ko objekt 4103 sedi na 30 KB. Zanka z uporabo TFileStream spremeni vsako pridobivanje (fetch) v Seek in dodaten Read, kar pomeni dva prehoda jedra (kernel transitions), pri čemer medpomnilnik ne prispeva ničesar, saj je naslednje pridobivanje na stotine megabajtov stran

Drugič, objektni tokovi (object streams, ISO 32000-1 §7.5.7) pakirajo desetine ali stotine majhnih slovarjev v en stisnjen (deflated) vsebnik. Pridobivanje enega 300-bajtnega slovarja strani lahko pomeni branje in napihovanje 100 KB velikega gruče (cluster). Druga plat medalje: objekti, ki so bili zapisani skupaj, se običajno berejo skupaj, zato medpomnilnik v velikosti gruče naslednjih dvanajst zahtevkov postreže zastonj — to pa je najbolj izkoriščana (exploitable) pravilnost v tem formatu

Tretjič, linearizacija. Linearizirana datoteka prvo stran in tabelo namigov (hint table) naloži na začetek, zato jo porabniki lahko prebirajo od začetka proti koncu. Gigabajtni arhivi so skoraj nikoli linearizirani: linearizacijo uničijo iste postopne posodobitve in združevanja (merges), ki so sploh povzročile velikost datoteke. Načrtujte za neprijazen primer: dolge skoke, nobenega vrstnega reda, prebiranje s konca

32-bitna zgodba, popravljena

32-bitni proces v sistemu Windows ima 2 GB uporabniškega naslovnega prostora in MapViewOfFile z vrednostjo bajtov nastavljeno na nič zaprosi za eno neprekinjeno rezervacijo velikosti celotne datoteke. Pri 2 GB velikem vhodu ta rezervacija ne more uspeti: po izvršljivi datoteki (EXE), raztresenih knjižnicah DLL in skladov nit (thread stacks) se največji prosti neprekinjeni blok v tipičnem 32-bitnem procesu Delphi nahaja nekje med 700 MB in 1,4 GB. Klic spodleti z napako ERROR_NOT_ENOUGH_MEMORY, na isto oviro naleti tudi TMemoryStream.LoadFromFile, le da se je tokrat premaknila iz odobrenega RAM-a (committed RAM) na rezervacijo naslovnega prostora. Popolna preslikava datoteke na 32-bitnem sistemu ni rešitev, temveč le isti neuspeh zakrinkan za lepše zvenečimi imeni API-jev

Rešitev je ločitev dveh stvari, ki ju preslikava (mapping) stori. CreateFileMapping ustvari objekt razdelka (section object) in ne stane prav nobenega naslovnega prostora, ne glede na velikost datoteke. Samo MapViewOfFile porabi naslovni prostor in ničesar ga ne sili, da mora preslikati celoten razdelek: sprejme 64-bitni začetni odmik in dolžino pogleda (view length). Ustvarite razdelek enkrat, preslikajte pogled, ki je dolg med 64 in 256 MB in prekriva področje, ki se trenutno razčlenjuje, ga odpreslikajte (unmap) in nato pomaknite naprej: strošek naslovnega prostora znaša le eno okno in ne ene datoteke. Edina omejitev je, da morajo biti odmiki pogledov večkratniki konstante SYSTEM_INFO.dwAllocationGranularity, kar v praksi pomeni 64 KB, zato se zahteva za odmik 1.000.000 zaokroži navzdol na 983.040, klicateljev kazalec (pointer) pa se popravi naprej za nastalo razliko

Preslikovalnik z drsnim oknom v Delphiju

Spodnji razred zajema celotno disciplino: en objekt razdelka, en aktiven pogled (live view), ponovno poravnavanje zrnatosti (granularity realignment) in branja, ki prečkajo mejo okna ter so urejena tako, da pogled raje razširijo, namesto da bi zašila dva pogleda

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;

Dve podrobnosti nosita glavno težo. Hitra pot (fast path) na vrhu metode Map vrne kazalec brez prehoda jedra, ko se zahtevani razpon že nahaja znotraj aktivnega pogleda; zahvaljujoč združevanju v gruče pri objektnih tokovih (object-stream clustering) je to najbolj pogost primer in tu nastanejo prihranki. Zahteva, ki sega preko konca privzetega okna, poveča velikost preslikave (MapSize) za ta eden pogled, namesto da bi zašila dva, zaradi česar ReadBytes ostane enovrstična koda, klicateljem pa ni treba pisati zank za delna branja

Velikost okna je prizanesljiva nastavitev: pri 64 MB poln pregled 1,8 GB velike datoteke pomeni 29 pogledov, pri 256 MB jih je 8, vendar pa je takrat posamezno rezervacijo težje umestiti v razdrobljen (fragmented) 32-bitni prostor, medtem ko se pod približno 16 MB datoteke z veliko skoki preslikujejo dovolj pogosto, da se to opazi. Kjerkoli v razponu od 64 do 256 MB predstavlja promet preslikovanja zgolj statistični šum

Štetje sistemskih klicev

Zdaj pa še k aritmetiki. Testna datoteka: 1,8 GB, 300.000 posrednih (indirect) objektov s povprečno približno 600 bajti koristnega tovora (payload). Razčlenjevalnik, ki deluje na ravni posameznih objektov, pridobi vsakega posebej s klicem SetFilePointerEx in dodatnim 4 KB velikim ReadFile klicem: 600.000 prehodov jedra. Z medpomnjenim (cached) sistemskim klicem branja poteka prenos na trenutni x64 strojni opremi v obeh smereh približno 1,5 μs, torej 600.000 × 1,5 μs ≈ 0,9 sekunde čiste sistemske režije jedra, preden se razčleni en sam bajt — to je najboljši scenarij z "ogretim" (warm) medpomnilnikom. V "hladnem" (cold) stanju pa vsak skok predstavlja operacijo na napravi: pri približno 20 μs efektivne latence NVMe pogona ob naključnem branju 4 KB dolgih blokov, jih 300.000 stane približno 6 sekund časa naprave; na shrambah razreda SATA to traja cele minute

Branja obenem premikajo napačne podatke: 300.000 × 4 KB potisne 1,2 GB skozi uporabniške medpomnilnike samo zato, da bi dostavili okoli 180 MB koristnega tovora — to pomeni šestkratno ojačanje ob tem, da je prav vsak bajt kopiran iz jedra k uporabniku

Medpomnilnik za predčasno branje (read-ahead), ki je v velikosti prilagojen gručam objektnih tokov, predstavlja prvo resno izboljšavo: eno 256 KB branje na gručo namesto po enega na vsak objekt zmanjša število prehodov za eno do dve stopnji velikosti (orders of magnitude). Prav tako je to pravo orodje na mestih, kjer je preslikovanje nerodno, najpogosteje na omrežnih pogonih

Preslikovalnik z drsnim oknom pa gre še dlje. Poln pregled (full sweep) opravi 29 klicev MapViewOfFile in 29 klicev UnmapViewOfFile, to je 58 eksplicitnih prehodov v primerjavi s 600.000. Resnično razčlenjevanje, vodeno z navzkrižnimi referencami (xref-driven), ni enostaven in čist pregled, vendar pa hitra pot (fast path) vpije vsako pridobivanje znotraj aktivnega okna; indeksiranje metapodatkov testnega arhiva se je ob koncu ustavilo pri le nekaj sto ponovnih preslikavah (remaps). Preslikovanje samo po sebi ne odpravi dela jedra: pretvori zgolj eksplicitne sistemske klice (syscalls) v napake strani (page faults), ki jih upravitelj pomnilnika (memory manager) razreši v gručah več strani naravnost iz datotečnega predpomnilnika brez kakršnegakoli kopiranja v uporabniški prostor, pri čemer področja, ki se jih program nikoli ne dotakne, sploh nič ne stanejo. Od začetka do konca se je čas prehoda indeksiranja izboljšal z 23 s pri "hladnem" ter 7,1 s pri "ogretem" stanju ob branju vsakega objekta posebej na 6,5 s (hladno) in 1,9 s (ogreto) v primeru uporabe preslikovalnika; kar preostane, je le zlib dekompresija (inflate), ne pa V/I

Kje se obnese zastavica FILE_FLAG_NO_BUFFERING

Zastavica FILE_FLAG_NO_BUFFERING obide sistemski predpomnilnik (system cache) v zameno za stroga pravila poravnave (alignment rules): odmiki, dolžine in naslovi medpomnilnikov morajo biti poravnani po sektorjih. Svojo uporabnost dokazuje predvsem pri enoprehodnih zaporednih nalogah (single-pass sequential jobs), ki bi sicer preplavile predpomnilnik z bajti, ki jih nihče ne bi prebral dvakrat — na primer pri paketni re-serializaciji, ki ponovno zapiše celoten arhiv, ali pri linearizaciji čez zaključen izhod. Skupaj s 4 do 8 MB poravnanimi medpomnilniki se približa zaporedni pasovni širini (sequential bandwidth) naprave brez da bi onesnaževal predpomnilnik

Vendar pa je za namene razčlenjevanja to povsem napačna izbira. Naključni skoki navzkrižnih referenc prek ne-medpomnjenega ročaja (unbuffered handle) spremenijo vsako pridobivanje 300-bajtnega slovarja v popolno fizično branje brez predpomnilnika, ki bi lahko ublažil drugi obisk — razčlenjevanje PDF datotek pa stalno ponovno obiskuje določena območja, saj se različne strani vedno znova razrešujejo v enake objektne tokove. Ne-medpomnjen V/I (unbuffered IO) naj bo torej za zaporedno ponovno zapisovanje (sequential rewrite), medtem ko za naključno razčlenjevanje uporabljajte v pomnilnik preslikan (mapped) ali medpomnjen (cached) V/I; mimogrede, zastavica deluje na ravni ročaja, tako da imate lahko v enem samem cevovodu oba pristopa na isti datoteki hkrati

64-bitno okolje, delovni nizi (working sets) in zaledje pisanja

V 64-bitni gradnji pa ugovor glede naslovnega prostora preprosto izgine: zgolj posredujte velikost datoteke kot velikost okna in zgornji razred se bo degeneriral v eno samo polno preslikavo (full mapping). A past tiči pri dolgo-tekočih storitvah (long-running services): le-za-branje (read-only) strani, podprte z datoteko (file-backed), ne prinašajo dodatnih stroškov odobrenega pomnilnika (commit), tako da ostanejo števci odobritev umirjeni, vendar pa se vsaka dotaknjena stran pridruži delovnemu nizu (working set); ko razčlenite večino od 1,8 GB, bo zrasel tudi delovni niz ter izpodrinil vse ostalo. Omejena okna na to postavijo neke vrste zgornjo mejo, zato vzorec drsenja ostaja pravilna privzeta izbira tudi tam, kjer je naslovni prostor prazen (free)

Na zaledju pisanja ostaja najcenejši V/I tisti V/I, ki ni nikoli izveden. PDF-jev mehanizem inkrementalne posodobitve (ISO 32000-1 §7.5.6) doda spremenjene objekte ter nov odsek navzkrižnih referenc neposredno za izvirne bajte, ki pa se nikoli ne premaknejo. Če želite odtisniti pečat na eno stran v 1,8 GB velikem arhivu, mu dodate na desetine kilobajtov; celotno prepisovanje bi moralo premakniti vseh 1,8 GB, kar je za pet stopenj velikosti več, samo dodajanje (append) pa pomeni zgolj čisti zaporedni izhod (sequential output) ob repu

Kje nastopijo knjižnice losLab

Obe PDF knjižnici losLab ponujata to disciplino že kot svoj API vmesnik. Orodje HotPDF Direct File API namreč bere število strani in strukturo prek datotečnega ročaja, ne da bi mu bilo treba graditi predmetno drevo (object tree), prav tako omogoča kopiranje ter dešifriranje na ravni datoteke, spremembe in razlike (deltas) pa zapiše prek BeginIncrementalUpdate — na tak način je zgoraj omenjena strategija dodajanja (append-only) v celoti zapakirana. Tudi PDFlibPas ubere popolnoma enako pot s svojim slojem Direct Access: bralnik v obliki toka na mestu prehodi tabelo navzkrižnih referenc, leno (lazily) prenaša in pridobiva objekte, lušči določene razpone strani iz ene v drugo datoteko ter shrani (persists) vse urejene spremembe kot inkrementalne revizije. Če morda pišete svoj lastni razčlenjevalnik, vam je razred preslikovalnika (mapper class) vedno na voljo; če izvajate celoten cevovod za dokumente, naj za iskrenost in konsistentnost drsnega okna raje poskrbi naša knjižnica

Opomba: Optimizirano upravljanje V/I zmogljivosti za dokumente velikosti več gigabajtov je vgrajeno neposredno v VCL komponento HotPDF za Delphi in C++Builder