Optimizacija IO performansi za obradu PDF-a na gigabajtnoj skali

Prvo korisno čitanje PDF parsera nalazi se na pogrešnom kraju datoteke. Format smješta pokazivač startxref u zadnje bajtove, pa tako obrada arhive od 1.8 GB počinje skokom na sam kraj, čitanjem jednog kilobajta, a zatim skokom tamo gdje tablica unakrsnih referenci kaže da živi katalog dokumenta. Od tamo pa nadalje parsiranje je nasumična šetnja kroz cijeli raspon bajtova. Sve ono u čemu je buffered IO dobar — sekvencijalno unaprijedno čitanje iza pokazivača datoteke — usmjereno je na radno opterećenje kakvo PDF jednostavno nema

Prva verzija ovog članka tvrdila je da memorijski mapirana datoteka rješava 32-bitni kvar s manjkom memorije s kojim se susreće TMemoryStream pri unosu od 2 GB. Ta je tvrdnja pogrešna, a način na koji je pogrešna ukazuje na pravo rješenje: pomični prozor mapiranja. Ono što slijedi jest obrazac pristupa, ispravljena 32-bitna priča s kompilabilnim prozorskim maperom te aritmetika sistemskih poziva na probnoj datoteci od 1.8 GB i 300.000 objekata

Zašto PDF raspored poražava međuspremno čitanje

Tri strukturne činjenice oblikuju IO obrazac. Prvo, navigacija je vođena pomacima: tablica unakrsnih referenci mapira svaki broj objekta na apsolutnu poziciju bajta, i ništa ne zahtijeva da te pozicije budu poredane. Nakon godina inkrementalnih ažuriranja, objekt 4102 može sjediti na pomaku od 1.6 GB, dok objekt 4103 sjedi na 30 KB. Petlja unutar TFileStream pretvara svako dohvaćanje u Seek plus Read, odnosno u dvije tranzicije kernela, s međuspremnikom koji ne pridonosi ničemu jer je iduće dohvaćanje stotinama megabajta daleko

Drugo, tokovi objekata (ISO 32000-1 §7.5.7) pakiraju desetke ili stotine malih rječnika u jedan ispuhani spremnik. Dohvaćanje jednog rječnika stranice od 300 bajtova može značiti čitanje i napuhavanje klastera od 100 KB. S druge strane: objekti koji su zapisani zajedno obično se i čitaju zajedno, stoga međuspremnik dimenzioniran prema klasteru besplatno poslužuje sljedećih desetak dohvaćanja — što je najiskoristivija pravilnost u cijelom formatu

Treće, linearizacija. Linearizirana datoteka učitava unaprijed prvu stranicu i tablicu sa smjernicama kako bi je potrošači mogli čitati od naprijed prema natrag. Gigabajtne arhive gotovo nikada nisu linearizirane: linearizacija biva uništena istim inkrementalnim ažuriranjima i spajanjima koja su samu datoteku učinila velikom. Planirajte neprijateljski slučaj: duge skokove, bez redoslijeda, ulazak s kraja

Ispravljena 32-bitna priča

32-bitni Windows proces ima 2 GB korisničkog adresnog prostora, a MapViewOfFile s brojem bajtova postavljenim na nulu traži jednu kontinuiranu rezervaciju veličine same datoteke. Za ulaz od 2 GB takva rezervacija ne može uspjeti: nakon same EXE datoteke, raštrkanih DLL-ova i stogova dretvi, najveći slobodni kontinuirani blok u tipičnom 32-bitnom Delphi procesu leži negdje između 700 MB i 1.4 GB. Poziv završava s pogreškom ERROR_NOT_ENOUGH_MEMORY, što je isti zid na koji udara TMemoryStream.LoadFromFile, samo premješten s alocirane RAM memorije na rezervaciju adresnog prostora. Mapiranje pune datoteke nije nikakvo rješenje u 32-bitnom sustavu, već tek isti kvar prikriven API nazivima koji bolje zvuče

Rješenje se nalazi u razdvajanju dviju stvari koje mapiranje obavlja. CreateFileMapping kreira objekt odjeljka i uopće ne košta nikakav adresni prostor, kolika god datoteka bila. Samo MapViewOfFile troši adresni prostor, i ništa ga ne tjera da mapira cijeli odjeljak: on prima 64-bitni početni pomak i duljinu prikaza. Kreirajte odjeljak jednom, mapirajte prikaz od 64 do 256 MB preko regije koja se parsira, te odmapirajte prije nastavka pomicanja: trošak adresnog prostora jednak je jednom prozoru, a ne cijeloj datoteci. Postoji jedno ograničenje: pomaci prikaza moraju biti višekratnici od SYSTEM_INFO.dwAllocationGranularity, što u praksi iznosi 64 KB, pa se tako zahtjev za pomak na 1.000.000 zaokružuje naniže na 983.040, dok se pozivateljev pokazivač prilagođava unaprijed za nastalu razliku

Maper s pomičnim prozorom u Delphiju

Klasa u nastavku omotava cjelokupnu disciplinu: jedan objekt odjeljka, jedan živi prikaz, ponovno usklađivanje granularnosti te čitanja koja prelaze granicu prozora, pri čemu se to rješava povećanjem tog jednog prikaza umjesto šivanjem dva odvojena

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 čitavu težinu. Brza staza na vrhu Map vraća pokazivač bez tranzicije kernela onda kada se zatraženi raspon već nalazi unutar živog prikaza; zahvaljujući grupiranju tokova objekata to je uobičajen slučaj i upravo onaj iz kojeg proizlaze uštede. Uz to, zahtjev koji se proteže izvan kraja zadanog prozora povećava MapSize za taj jedan prikaz umjesto da ih šiva dva, što održava ReadBytes rješenjem u jednom redu i oslobađa pozivatelje potrebe za petljama s djelomičnim čitanjem

Veličina prozora oprašta pogreške kod ugađanja: na 64 MB potpuni prolazak kroz datoteku od 1.8 GB donosi 29 prikaza, na 256 MB donosi 8, ali svaku takvu rezervaciju teže je smjestiti u fragmentiranom 32-bitnom prostoru, dok se ispod oko 16 MB datoteke zasićene skokovima remapiraju dovoljno često da to postane uočljivo. Bilo gdje u rasponu od 64 do 256 MB, mapirani promet je tek statistički šum

Brojanje sistemskih poziva

A sada aritmetika. Testna datoteka: 1.8 GB, 300.000 neizravnih objekata u prosjeku s oko 600 bajtova korisnog opterećenja. Parser po objektu dohvaća svakoga pomoću SetFilePointerEx plus 4 KB dugačkim ReadFile pozivom: 600.000 tranzicija kernela. Keširani sistemski poziv za čitanje odradi se otprilike za 1.5 μs na trenutnom x64 hardveru, tako da je to 600.000 × 1.5 μs ≈ 0.9 sekundi čistog preopterećenja kernela i to prije parsiranja ijednog jedinog bajta — što je najbolji mogući slučaj u kojem je predmemorija topla. Ako je hladna, svaki je skok operacija na uređaju: uz ~20 μs efektivne latencije za NVMe nasumična čitanja po 4 KB, 300.000 njih košta oko 6 sekundi vremena uređaja; a na SATA klasi pohrane, na to odu minute

Osim toga, ova čitanja premještaju krive podatke: 300.000 × 4 KB gura 1.2 GB kroz korisničke međuspremnike kako bi isporučilo približno 180 MB korisnog opterećenja — šesterostruko povećanje, a svaki bajt je kopiran iz kernela prema korisniku

Međuspremnik za unaprijedno čitanje dimenzioniran prema klasterima tokova objekata prvo je doista pošteno poboljšanje: jedno čitanje od 256 KB po klasteru, umjesto jednog po objektu, smanjuje broj prijelaza za jedan do dva reda veličine. To je također i pravi alat za mjesta na kojima je mapiranje nespretno, što se najčešće odnosi na mrežna dijeljenja

Prozorski maper ide i dalje. Puni prolaz iziskuje 29 MapViewOfFile i 29 UnmapViewOfFile poziva, što je 58 eksplicitnih tranzicija naspram prijašnjih 600.000. Pravo xref-vođeno parsiranje nije čisti linearni prolaz, ali brzi put apsorbira svaki dohvat unutar živog prozora; prolaz indeksiranja metapodataka preko testne arhive smirio se na nekoliko stotina remapiranja. Samo mapiranje ne uklanja posao kernela: pretvara eksplicitne sistemske pozive u stranice s pogreškama koje upravitelj memorijom rješava u klasterima s više stranica, ravno iz predmemorije datoteke bez ikakvog kopiranja u korisnički prostor, dok regije koje nikada nisu ni dotaknute ne koštaju apsolutno ništa. Ukupno gledano, od početka do kraja, prolaz za indeksiranje pao je sa 23 s za hladni i 7.1 s za topli prolaz uz čitanja po pojedinom objektu, na 6.5 s za hladni i 1.9 s za topli prolaz uz pomoć mapera; ono što preostaje odnosi se na zlib inflate, a ne više na IO

Gdje se uklapa FILE_FLAG_NO_BUFFERING

FILE_FLAG_NO_BUFFERING zaobilazi sistemsku predmemoriju u zamjenu za čvrsta pravila poravnanja: pomaci, duljine i adrese međuspremnika su poravnati sa sektorima. Zarađuje svoje mjesto na sekvencijalnim poslovima iz jednog prolaza koji bi inače preplavili predmemoriju bajtovima koje nitko nikada ne čita dvaput — npr. serijska reserijalizacija koja prepisuje cjelokupnu arhivu ili prolaz linearizacije preko konačnog izlaza. S 4 do 8 MB poravnatim međuspremnicima približava se pojasnoj širini sekvencijalnog uređaja bez onečišćenja same predmemorije

Potpuno je pogrešan izbor za parsiranje. Nasumični xref skokovi preko nepredmemoriranog handlea pretvaraju svaki pokušaj dohvata rječnika od 300 bajtova u potpuno fizičko čitanje pri čemu nema predmemorije koja bi upila onaj drugi posjet — a parsiranje PDF-a konstantno nanovo posjećuje regije jer se različite stranice razrješavaju u iste tokove objekata. Nepredmemorirani IO idealan je za sekvencijalno prepisivanje, dok za nasumično parsiranje služi mapirani ili predmemorirani IO; zastavica se dodjeljuje po pojedinačnom handleu, pa stoga jedan cjevovod može imati i jedno i drugo nad istom datotekom

64 bita, radni skupovi i strana za pisanje

U 64-bitnom izdanju nestaje sav prigovor oko adresnog prostora: jednostavno proslijedite veličinu datoteke kao prozor i navedena klasa iznad degradirat će u jedinstveno mapiranje cjelokupnog dokumenta. Kvaka koja leži unutar dugotrajnih servisa: stranice samo za čitanje koje su potpomognute datotekama ne naplaćuju commit, pa commit brojači ostaju mirni, ali se zato svaka dotaknuta stranica pridružuje radnom skupu; ako parsirate većinu od tih 1.8 GB, i vaš će radni skup narasti u jednakoj mjeri, usput izbacujući sve ostalo. Ograničeni prozori postavljaju gornji limit na tu brojku, stoga pomični obrazac ostaje ispravan standardni izbor čak i tamo gdje je adresni prostor potpuno slobodan

Na strani za pisanje, najjeftiniji IO je onaj IO koji nikada nije ni izdan. PDF-ov mehanizam inkrementalnog ažuriranja (ISO 32000-1 §7.5.6) dodaje promijenjene objekte kao i novi odjeljak unakrsnih referenci odmah nakon originalnih bajtova, koji se nikada ne pomiču. Stavljanje pečata na jednu stranicu na arhivu od 1.8 GB priključit će desetke kilobajta; ali će potpuno prepisivanje premjestiti čitavih 1.8 GB, što razdvaja ova dva rješenja na pet reda veličine, dok je dodavanje na kraj čisti sekvencijalni izlaz s kraja datoteke

Gdje se uklapaju losLab biblioteke

Obje losLabove PDF biblioteke isporučuju takvu disciplinu kao API površinu. HotPDF Direct File API čita broj stranica i strukturu preko datotečnog handlea, bez same izgradnje hijerarhije objekata, zatim kopira i dešifrira na datotečnoj razini, a zapisuje izmijenjene razlike korištenjem naredbe BeginIncrementalUpdate — što pak predstavlja upakiranu strategiju navedenog dodavanja na kraj. PDFlibPas ide istim tim smjerom sa svojim podslojem izravnog pristupa: s čitačem toka koji šeta tablicom unakrsnih referenci direktno na samom mjestu, lijeno dohvaća objekte, ekstrahira raspone stranica na relaciji datoteka na datoteku i trajno sprema uređivanja kao inkrementalne revizije. Ako pak pišete vlastiti parser, sama maper klasa je vaša za uzimanje; ako pak pokrećete vlastiti dokumentni cjevovod, prepustite onda to radije biblioteci koja će brinuti za pošteno stanje vašeg prozora

Napomena: Optimizirano upravljanje IO operacijama za dokumente u gigabajtnim omjerima ugrađeno je izravno u HotPDF VCL Component za jezike Delphi i C++Builder