Gigabaitų apimties PDF apdorojimo IO našumo optimizavimas

Pirmasis naudingas PDF analizatoriaus skaitymas yra netinkamame failo gale. Formatas patalpina startxref rodyklę paskutiniuose baituose, todėl 1,8 GB archyvo apdorojimas pradedamas perėjimu į pabaigą, vieno kilobaito nuskaitymu, o po to šuoliu ten, kur, pasak kryžminių nuorodų lentelės (cross-reference table), yra dokumentų katalogas. Nuo ten analizė yra atsitiktinis vaikščiojimas po visą baitų diapazoną. Viskas, ką gerai atlieka buferinis IO — nuoseklus išankstinis skaitymas už failo rodyklės — yra skirta darbo krūviui, kurio PDF neturi

Pirmojoje šio straipsnio versijoje buvo teigiama, kad į atmintį atvaizduotas (memory-mapped) failas išsprendžia 32 bitų atminties trūkumo klaidą, su kuria TMemoryStream susiduria esant 2 GB įvesčiai. Šis teiginys yra klaidingas, ir jo klaidingumas nurodo į tikrąjį sprendimą: slankiojantį atvaizdavimo langą (sliding mapping window). Toliau pateikiamas prieigos modelis, pataisyta 32 bitų istorija su kompiliuojamu langų atvaizduokliu ir sistemos iškvietimų (syscall) aritmetika 1,8 GB, 300 000 objektų bandomajame faile

Kodėl PDF išdėstymas įveikia buferizuotą skaitymą

Trys struktūriniai faktai formuoja IO modelį. Pirma, navigacija yra pagrįsta poslinkiais (offset-driven): kryžminių nuorodų lentelė susieja kiekvieno objekto numerį su absoliučia baito pozicija, ir niekas nereikalauja, kad šios pozicijos būtų surūšiuotos. Po kelerių metų laipsniškų atnaujinimų 4102 objektas gali būti ties 1,6 GB poslinkiu, o 4103 objektas – ties 30 KB. TFileStream ciklas kiekvieną gavimą paverčia Seek ir Read, dviem branduolio perėjimais (kernel transitions), su buferiu, kuris neduoda jokios naudos, nes kitas gavimas yra už šimtų megabaitų

Antra, objektų srautai (ISO 32000-1 §7.5.7) sutalpina dešimtis ar šimtus mažų žodynų į vieną suspaustą (deflated) konteinerį. Vieno 300 baitų puslapio žodyno gavimas gali reikšti 100 KB klasterio skaitymą ir išskleidimą (inflating). Kita pusė: kartu įrašyti objektai paprastai skaitomi kartu, todėl klasterio dydžio buferis nemokamai aptarnauja kitą tuziną gavimų — labiausiai išnaudojamas formato dėsningumas

Trečia, linearizacija. Linearizuotas failas iš anksto įkelia pirmąjį puslapį ir užuominų lentelę (hint table), kad vartotojai galėtų jį skaityti nuo pradžios iki pabaigos. Gigabaitų apimties archyvai beveik niekada nebūna linearizuoti: linearizaciją sunaikina tie patys laipsniški atnaujinimai ir sujungimai, dėl kurių failas tapo didelis. Planuokite atšiauriam atvejui: ilgi šuoliai, jokios tvarkos, įvedimas nuo uodegos

32 bitų istorija, pataisyta

32 bitų „Windows“ procesas turi 2 GB vartotojo adresų srities, o MapViewOfFile su nuliniu baitų skaičiumi prašo vienos nepertraukiamos failo dydžio rezervacijos. Esant 2 GB įvesčiai ši rezervacija negali pavykti: po EXE, išsklaidytų DLL ir gijų stekų (thread stacks), didžiausias laisvas nepertraukiamas blokas tipiniame 32 bitų „Delphi“ procese yra kažkur tarp 700 MB ir 1,4 GB. Iškvietimas nepavyksta su ERROR_NOT_ENOUGH_MEMORY, ta pačia siena, į kurią atsitrenkia TMemoryStream.LoadFromFile, tik perkelta iš patvirtintos RAM į adresų srities rezervaciją. Viso failo atvaizdavimas nėra išeitis 32 bitų sistemose, tai tiesiog ta pati nesėkmė po geriau skambančiais API pavadinimais

Sprendimas yra atskirti du dalykus, kuriuos atlieka atvaizdavimas. CreateFileMapping sukuria sekcijos objektą ir visai nekainuoja adresų srities, nepriklausomai nuo failo dydžio. Tik MapViewOfFile naudoja adresų sritį, ir niekas neverčia jos atvaizduoti visos sekcijos: ji priima 64 bitų pradinį poslinkį ir rodinio (view) ilgį. Sukurkite sekciją vieną kartą, atvaizduokite nuo 64 iki 256 MB rodinį virš analizuojamos srities, atšaukite atvaizdavimą (unmap) prieš slinkdami toliau: adresų srities kaina yra vienas langas, o ne vienas failas. Vienas apribojimas: rodinio poslinkiai turi būti SYSTEM_INFO.dwAllocationGranularity kartotiniai, praktikoje 64 KB, todėl užklausa dėl 1 000 000 poslinkio apvalinama žemyn iki 983 040, o skambinančiojo rodyklė (pointer) pakoreguojama į priekį per skirtumą

Slankiojančio lango atvaizduoklis programoje „Delphi“

Žemiau esanti klasė apjungia visą discipliną: vienas sekcijos objektas, vienas gyvas rodinys (live view), granuliarumo (granularity) derinimas ir skaitymai, peržengiantys lango ribą, apdorojami padidinant tą vieną rodinį, užuot sujungiant du

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;

Dvi detalės turi didžiausią svorį. Greitasis kelias (fast path) Map viršuje grąžina rodyklę be branduolio perėjimo, kai prašomas diapazonas jau yra gyvame rodinyje; dėl objektų srautų klasterizavimo tai yra dažnas atvejis ir būtent čia atsiranda sutaupymai. O užklausa, apimanti numatytojo lango pabaigą, padidina MapSize tam vienam rodiniui, užuot sujungusi du, todėl ReadBytes išlieka vienos eilutės funkcija, o iškviečiantiems nereikia naudoti dalinio skaitymo (partial-read) ciklų

Lango dydis yra atlaidus nustatymas: esant 64 MB, pilnas 1,8 GB failo nuskaitymas yra 29 rodiniai, esant 256 MB - 8, tačiau kiekvieną rezervaciją sunkiau patalpinti suskaidytoje 32 bitų erdvėje, o esant mažiau nei maždaug 16 MB failams su daug šuolių peratvaizduojama pakankamai dažnai, kad tai būtų pastebima. Bet kur 64–256 MB diapazone atvaizdavimo srautas (map traffic) yra statistinis triukšmas

Sistemos iškvietimų (syscalls) skaičiavimas

Dabar aritmetika. Bandomasis failas: 1,8 GB, 300 000 netiesioginių objektų, kurių naudingo krovimo (payload) vidurkis yra apie 600 baitų. Kiekvieno objekto analizatorius gauna kiekvieną iš jų naudodamas SetFilePointerEx ir 4 KB ReadFile: 600 000 branduolio perėjimų. Talpykloje esantis (cached) skaitymo sistemos iškvietimas dabartinėje x64 aparatinėje įrangoje užtrunka maždaug 1,5 μs, tad tai yra 600 000 × 1,5 μs ≈ 0,9 sekundės gryno branduolio pridėtinio laiko prieš analizuojant nors vieną baitą — geriausias atvejis su įšilusia talpykla (warm-cache). Su šalta talpykla (cold), kiekvienas šuolis yra įrenginio operacija: esant ~20 μs efektyviajai NVMe 4 KB atsitiktinių skaitymų gaišties trukmei, 300 000 iš jų kainuoja apie 6 sekundes įrenginio laiko; SATA klasės saugyklose – minutes

Skaitymai taip pat perkelia netinkamus duomenis: 300 000 × 4 KB praleidžia 1,2 GB per vartotojo buferius, kad pristatytų maždaug 180 MB naudingo krovimo — šešis kartus padidintas (six-fold amplification), kiekvienas baitas nukopijuojamas iš branduolio vartotojui

Išankstinio skaitymo (read-ahead) buferis, kurio dydis pritaikytas objektų srauto klasteriams, yra pirmas tikras patobulinimas: vienas 256 KB skaitymas vienam klasteriui vietoj vieno kiekvienam objektui sumažina perėjimų skaičių viena ar dviem eilėmis. Tai taip pat tinkamas įrankis ten, kur atvaizdavimas yra nepatogus, paprastai tinklo bendriniuose diskuose (network shares)

Langų atvaizduoklis (windowed mapper) eina dar toliau. Pilnas nuskaitymas yra 29 MapViewOfFile ir 29 UnmapViewOfFile iškvietimai, 58 aiškūs perėjimai prieš 600 000. Tikra xref valdoma analizė nėra švarus nuskaitymas, tačiau greitasis kelias sugeria kiekvieną gavimą gyvo lango viduje; metaduomenų indeksavimo (metadata-indexing) perėjimas bandomajame archyve nusistovėjo ties keliais šimtais peratvaizdavimų. Atvaizdavimas nepašalina branduolio darbo: jis paverčia aiškius sistemos iškvietimus (syscalls) puslapių klaidomis (page faults), kurias atminties tvarkyklė išsprendžia kelių puslapių klasteriais, tiesiai iš failų talpyklos be kopijavimo vartotojo erdvėje, o niekada neliesti regionai nieko nekainuoja. Nuo pradžios iki pabaigos indeksavimo perėjimas nuo 23 s (šalta) ir 7,1 s (įšilusi) su kiekvieno objekto skaitymais sumažėjo iki 6,5 s (šalta) ir 1,9 s (įšilusi) su atvaizduokliu; tai, kas liko, yra zlib išskleidimas, o ne IO

Kur tinka FILE_FLAG_NO_BUFFERING

FILE_FLAG_NO_BUFFERING aplenkia sistemos talpyklą mainais į griežtas lygiavimo taisykles: poslinkiai, ilgiai ir buferio adresai sulygiuoti pagal sektorius (sector-aligned). Tai atsiperka vieno perėjimo nuosekliuose (single-pass sequential) darbuose, kurie kitaip užtvindytų talpyklą baitais, kurių niekas neskaito du kartus — paketinis pakartotinis serializavimas (batch re-serialization), kuris perrašo visą archyvą, arba linearizacijos perėjimas per baigtą išvestį. Naudojant nuo 4 iki 8 MB sulygiuotus buferius, tai priartėja prie įrenginio nuoseklaus pralaidumo neužteršiant talpyklos

Tai visiškai netinka analizei. Atsitiktiniai xref šuoliai per nebuferizuotą rankeną (unbuffered handle) kiekvieną 300 baitų žodyno gavimą paverčia visišku fiziniu skaitymu, be talpyklos, kuri sugertų antrąjį apsilankymą — o PDF analizė nuolat grįžta į regionus, nes skirtingi puslapiai išsprendžiami į tuos pačius objektų srautus. Nebuferizuotas IO skirtas nuosekliam perrašymui, atvaizduotas arba talpykloje esantis IO — atsitiktinei analizei; vėliavėlė (flag) yra priskiriama rankenai (per-handle), todėl vienas konvejeris (pipeline) gali išlaikyti abu tame pačiame faile

64 bitų, darbiniai rinkiniai (working sets) ir rašymo pusė

64 bitų versijoje adresų srities prieštaravimas išnyksta: perduokite failo dydį kaip langą ir aukščiau esanti klasė išsigimsta į vieną pilną atvaizdavimą. Kabliukas ilgai veikiančiose paslaugose (long-running services): tik skaitymui skirti failais palaikomi (file-backed) puslapiai nereikalauja patvirtinimo (commit), todėl patvirtinimų skaitikliai išlieka ramūs, tačiau kiekvienas paliestas puslapis prisijungia prie darbinio rinkinio (working set); išanalizuokite didžiąją dalį 1,8 GB ir darbinis rinkinys išaugs atitinkamai, išstumdamas visa kita. Apriboti langai nustato tam lubas, todėl slankiojantis modelis išlieka teisingu numatytuoju pasirinkimu net ir ten, kur adresų sritis yra laisva

Rašymo pusėje pigiausias IO yra IO, kuris niekada neišduodamas. PDF laipsniško atnaujinimo mechanizmas (ISO 32000-1 §7.5.6) prideda pakeistus objektus ir naują kryžminių nuorodų sekciją po pradinių baitų, kurie niekada nejuda. Vieno puslapio įspaudas 1,8 GB archyve prideda dešimtis kilobaitų; pilnas perrašymas perkelia visus 1,8 GB, penkiomis eilėmis skiriasi, o pridėjimas (append) yra grynai nuosekli išvestis (sequential output) uodegoje

Kur tinka „losLab“ bibliotekos

Abi „losLab“ PDF bibliotekos pateikia šią discipliną kaip API paviršių. HotPDF Direct File API per failo rankeną nuskaito puslapių skaičių ir struktūrą nesudarydama objektų medžio, kopijuoja ir dešifruoja failo lygmeniu bei rašo skirtumus (deltas) per BeginIncrementalUpdate — aukščiau aprašyta tik pridedama (append-only) strategija, supakuota. „PDFlibPas“ eina tuo pačiu keliu su savo tiesioginės prieigos (Direct Access) sluoksniu: srautinis skaitytuvas (streaming reader), kuris vietoje pereina kryžminių nuorodų lentelę, vangiai (lazily) gauna objektus, ištraukia puslapių diapazonus iš failo į failą ir išsaugo pakeitimus kaip laipsniškas revizijas. Jei rašote savo analizatorių, atvaizduoklio klasė skirta jums; jei vykdote dokumentų konvejerį (pipeline), leiskite bibliotekai išlaikyti langą teisingą

Pastaba: Optimizuotas IO apdorojimas gigabaitų apimties dokumentams yra įmontuotas tiesiai į HotPDF VCL Component skirtą Delphi ir C++Builder