Optimizacija I/O performansi za obradu gigabajtnih PDF-ova

Prvo korisno čitanje koje obavi PDF parser nalazi se na pogrešnom kraju datoteke. Format postavlja pokazivač startxref u poslednje bajtove, pa obrada 1.8 GB velike arhive počinje prelazom (seek) na rep, čitanjem od jednog kilobajta, i onda skokom gde god tabela unakrsnih referenci kaže da se nalazi katalog dokumenta. Odatle, parsiranje je nasumična šetnja preko celog opsega bajtova. Sve u čemu je baferovani I/O dobar — sekvencijalno čitanje unapred (read-ahead) iza pokazivača datoteke — cilja na radno opterećenje koje PDF nema

Prva verzija ovog članka tvrdila je da memorijski mapirana datoteka rešava 32-bitni ispad zbog nedostatka memorije u koji TMemoryStream udari na ulazu od 2 GB. Ta tvrdnja je pogrešna, a način na koji je pogrešna ukazuje na pravo rešenje: klizni prozor mapiranja. Ono što sledi je obrazac pristupa (access pattern), ispravljena 32-bitna priča uz prozor-maper (windowed mapper) koji se može kompajlirati, i aritmetika sistemskih poziva (syscalls) na probnoj datoteci od 1.8 GB sa 300.000 objekata

Zašto PDF raspored poražava baferovana čitanja

Tri strukturne činjenice oblikuju I/O obrazac. Prvo, navigacija je vođena ofsetima: tabela unakrsnih referenci mapira svaki broj objekta na apsolutnu poziciju bajta, i ništa ne zahteva da te pozicije budu poređane. Posle više godina inkrementalnih ažuriranja, objekat 4102 može da se nalazi na ofsetu 1.6 GB dok se objekat 4103 nalazi na 30 KB. TFileStream petlja pretvara svako dobavljanje u Seek plus Read, dva kernel prelaza, sa baferom koji ne doprinosi ničemu zato što je sledeće dobavljanje udaljeno stotinama megabajta

Drugo, tokovi objekata (object streams - ISO 32000-1 §7.5.7) pakuju na desetine ili stotine malih rečnika u jedan ispumpan (deflated) kontejner. Dobavljanje jednog rečnika stranice od 300 bajtova može značiti čitanje i naduvavanje klastera od 100 KB. Druga strana medalje: objekti napisani zajedno obično se i čitaju zajedno, tako da bafer dimenzionisan prema klasteru služi sledećih desetak dobavljanja besplatno — ovo je regularnost koju je najlakše iskoristiti (exploitable) u formatu

Treće, linearizacija. Linearizovana datoteka na početku učitava prvu stranicu i tabelu smernica (hint table) tako da potrošači mogu da je čitaju od napred ka nazad. Gigabajtne arhive gotovo nikad nisu linearizovane: linearizaciju uništavaju ista ona inkrementalna ažuriranja i spajanja koja su datoteku učinila velikom. Planirajte za najgori, neprijateljski slučaj: dugi skokovi, odsustvo redosleda, ulaz prvo od repa

32-bitna priča, ispravljena

32-bitni Windows proces ima 2 GB korisničkog adresnog prostora, i MapViewOfFile sa brojem bajtova jednakim nuli traži jednu uzastopnu rezervaciju veličine datoteke. Za ulaz od 2 GB ta rezervacija ne može uspeti: nakon EXE-a, rasutih DLL-ova i stekova za thread-ove (thread stacks), najveći slobodni uzastopni blok u tipičnom 32-bitnom Delphi procesu leži negde između 700 MB i 1.4 GB. Poziv ne uspeva uz ERROR_NOT_ENOUGH_MEMORY, što je isti zid u koji udara TMemoryStream.LoadFromFile, samo premešten sa zaduženog (committed) RAM-a na rezervaciju adresnog prostora. Mapiranje cele datoteke nije rešenje na 32 bita, već isti neuspeh samo iza bolje zvučećih API imena

Ispravka je odvajanje dve stvari koje mapiranje radi. CreateFileMapping kreira objekat sekcije i ne košta nikakvog adresnog prostora u opšte, kolika god da je veličina datoteke. Samo MapViewOfFile troši adresni prostor, i ništa ga ne sili da mapira čitavu sekciju: on uzima 64-bitni početni ofset i dužinu pogleda (view length). Kreirajte sekciju jednom, mapirajte pogled od 64 do 256 MB preko regije koja se parsira, i odmapirajte (unmap) pre nego što skliznete napred: trošak u adresnom prostoru iznosi jedan prozor, a ne jedna datoteka. Jedno ograničenje: ofseti pogleda moraju biti umnošci od SYSTEM_INFO.dwAllocationGranularity, u praksi 64 KB, pa se zahtev za ofsetom 1.000.000 zaokružuje nadole na 983.040, a pokazivač onog koji poziva podešava se unapred za tu razliku

Maper kliznog prozora u Delphiju

Klasa ispod zaokružuje celu disciplinu: jedan objekat sekcije, jedan živi pogled, ponovno poravnanje granularnosti, i čitanja koja prelaze preko granice prozora rešena rastom tog jednog pogleda umesto zašivanja 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;

Dva detalja nose težinu. Brza putanja (fast path) na vrhu Map funkcije vraća pokazivač bez ikakvog prelaza kernela kada zatraženi opseg već sedi unutar živog pogleda; zahvaljujući klasterovanju toka objekata, ovo je čest slučaj i izvor celokupne uštede. Zatim, zahtev koji opkoračuje kraj podrazumevanog prozora podiže (grows) MapSize za taj jedan pogled umesto da šije dva, čime drži ReadBytes u vidu jedne linije (one-liner) i klijente (callers) oslobađa petlji za delimično čitanje

Veličina prozora je opraštajuća (forgiving) opcija za podešavanje: na 64 MB, puni prolaz (sweep) datoteke od 1.8 GB donosi 29 pogleda, na 256 MB to je 8, ali svaku takvu rezervaciju teže je smestiti u fragmentiran 32-bitni prostor, dok se ispod oko 16 MB datoteke teške sa skokovima mapiraju dovoljno često da to postane osetno. Bilo gde u opsegu od 64 do 256 MB, saobraćaj mapiranja je tek statistički šum

Brojanje sistemskih poziva (syscalls)

Sada aritmetika. Probna datoteka: 1.8 GB, 300.000 indirektnih objekata koji u proseku imaju oko 600 bajtova korisnog sadržaja (payload-a). Per-object parser dobavlja svaki sa SetFilePointerEx plus 4 KB ReadFile: ukupno 600.000 prelaza (transitions) na nivou kernela. Keširan povratni sistemski poziv (syscall round-trip) čitanja iznosi otprilike 1,5 μs na trenutnom x64 hardveru, tako da je to 600.000 × 1,5 μs ≈ 0,9 sekundi čistog dodatnog troška (overhead) kernela pre no što je parsiran ijedan bajt — najbolji scenario toplog keša (warm-cache best case). Na hladno (cold), svaki skok (hop) je operacija uređaja: pri efektivnoj latenciji (latency) od oko 20 μs kod NVMe nasumičnih 4 KB čitanja, njih 300.000 košta oko 6 sekundi vremena samog uređaja; na SATA klasi skladišta, minute

Čitanja takođe premeštaju pogrešne podatke: 300.000 × 4 KB gura 1.2 GB kroz korisničke bafere da bi isporučilo oko 180 MB korisnog tereta — šestostruko umnožavanje (amplification), svaki bajt kopiran iz kernela do korisnika

Bafer za čitanje unapred (read-ahead buffer) dimenzionisan za klastere toka objekata jeste prvo iskreno poboljšanje: jedno čitanje od 256 KB po klasteru umesto po jednog za svaki objekat smanjuje broj prelaza za red ili dva veličine. Ovo je takođe pravi alat tamo gde je mapiranje nezgodno, obično na deljenim mrežnim lokacijama (network shares)

Maper u prozoru (windowed mapper) ide dalje. Puni prolaz iznosi 29 poziva za MapViewOfFile i 29 za UnmapViewOfFile, 58 eksplicitnih prelaza naspram 600.000. Pravo xref-vođeno parsiranje nije čisti prolaz, ali brza putanja (fast path) apsorbuje svako dobavljanje unutar aktivnog prozora; prolaz za indeksiranje metapodataka na probnoj arhivi skrasio se na tek nekoliko stotina ponovnih mapiranja (remaps). Mapiranje ne uklanja rad kernela: ono pretvara eksplicitne sistemske pozive u page fault-ove (greške usled promašaja stranice) koje menadžer memorije rešava u višestraničnim (multi-page) klasterima, direktno iz keša datoteke bez ikakvog kopiranja u korisnički prostor (user-space copy), a oblasti koje nisu ni dodirnute ne koštaju ništa. Posmatrano od kraja do kraja, indeksiranje je sa očitavanjima po objektu (per-object) zahtevalo 23 s na hladno i 7,1 s toplo, do samo 6,5 s na hladno i 1,9 s toplo kada se koristio maper; ono što preostaje je zlib inflate rad, a ne IO

Gde se uklapa FILE_FLAG_NO_BUFFERING

FILE_FLAG_NO_BUFFERING zaobilazi sistemski keš u zamenu za tvrda pravila poravnanja (alignment rules): ofseti, dužine i adrese bafera u potpunosti poravnani sa sektorima (sector-aligned). On zarađuje svoju platu na sekvencijalnim poslovima u jednom prolazu (single-pass) koji bi inače poplavili keš bajtovima koje niko neće pročitati dva puta — prilikom serijske (batch) reserijalizacije koja prepisuje celu arhivu, ili kod pokušaja linearizacije završenog izlaza. Sa poravnanim baferima veličine 4 do 8 MB uspeva da se približi sekvencijalnoj propusnoj moći (bandwidth) uređaja bez zagađivanja keša

Ovo je pak potpuno pogrešno za parsiranje. Nasumični xref skokovi preko nebaferovanog (unbuffered) handle-a pretvaraju svako dobavljanje rečnika od 300 bajtova u puno fizičko čitanje bez ikakvog keša koji bi apsorbovao drugu posetu — a PDF parsiranje stalno posećuje i nanovo revidira regije, jer se različite stranice razrešavaju u iste tokove objekata. Nebaferovan I/O za sekvencijalno prepisivanje (rewrite), mapiran ili keširan I/O za nasumično parsiranje; ova oznaka (flag) se dodeljuje po handle-u, tako da jedan cevovod (pipeline) može imati oba pristupa na istoj datoteci

64-bita, radni skupovi (working sets) i strana za pisanje

Na 64-bitnoj izradi prigovor o adresnom prostoru nestaje: propustite veličinu datoteke kao prozor i navedena klasa degeneriše se u jedno celovito mapiranje. Kaka kod usluga dugog trajanja (long-running services) leži u sledećem: stranice namenjene isključivo za čitanje, a iza kojih stoji datoteka (read-only file-backed pages), ne zadužuju memoriju (commit), tako da brojila commit-a miruju, ali svaka dodirnuta stranica se pridružuje radnom skupu (working set); parsirajte najveći deo fajla od 1.8 GB i radni skup će isto tako porasti (grows to match), izbacujući na ulicu sve ostalo. Ograničeni (bounded) prozori stavljaju plafon na to, pa klizni obrazac ostaje ispravan (default) izbor čak i tamo gde je adresni prostor slobodan

Kada je u pitanju strana pisanja, najjeftiniji IO je onaj koji se nikada ne izda. PDF-ov mehanizam za inkrementalno ažuriranje (ISO 32000-1 §7.5.6) nadovezuje (appends) izmenjene objekte i novu sekciju za unakrsne reference iza originalnih bajtova, koji se nikada ne premeštaju. Štancanje (stamping) jedne stranice na arhivu od 1.8 GB dodaje mu tek nekoliko desetina kilobajta; potpuno prepisivanje bi istumbavalo svih 1.8 GB, što predstavlja razliku u pet redova veličine, dok je dodavanje (append) čisti sekvencijalni izlaz na samom repu fajla

Gde se losLab biblioteke uklapaju

Obe losLab PDF biblioteke isporučuju ovu disciplinu kao API površinu. API pod imenom HotPDF Direct File API čita broj stranica i samu strukturu kroz handle za datoteku bez izgradnje celokupnog stabla objekata, a kopira i dešifruje na nivou datoteke, te ispisuje delte (promene) korišćenjem metode BeginIncrementalUpdate — u suštini spakovane prethodne append-only strategije. U paketu PDFlibPas je išao po istom principu sa sopstvenim slojem pod imenom Direct Access: to je u suštini streaming reader koji pregledava i pretražuje tabelu unakrsnih referenci direktno na licu mesta, na isti način (lazily) dobavlja objekte, rasparčava te preuzima delove i raspone između datoteka i ispisuje, čuvajući ispravke (edits) kao inkrementalne revizije. Ako pišete sopstveni parser, klasa mapera je tu da je slobodno uzmete; ukoliko gurate cevovod za dokumente, pustite da biblioteka održava prozor poštenim (honest)

Napomena: Optimizovano I/O rukovanje gigabajtnim dokumentima (gigabyte-scale) je direktno ugrađeno u HotPDF VCL komponentu za Delphi i C++Builder