Optymalizacja wydajności wejścia/wyjścia (IO) dla przetwarzania gigabajtowych plików PDF

Pierwszy użyteczny odczyt parsera PDF znajduje się na niewłaściwym końcu pliku. Format umieszcza wskaźnik startxref w ostatnich bajtach, więc przetwarzanie archiwum o rozmiarze 1,8 GB rozpoczyna się od przeskoczenia na koniec, odczytania jednego kilobajta, a następnie skoku w miejsce, gdzie według tabeli odsyłaczy (cross-reference) znajduje się katalog dokumentu. Od tego momentu parsowanie to błądzenie losowe po całym zakresie bajtów. Wszystko to, w czym buforowane wejście/wyjście (IO) jest dobre — sekwencyjny odczyt z wyprzedzeniem za wskaźnikiem pliku — jest ukierunkowane na obciążenie, którego PDF po prostu nie ma

Pierwsza wersja tego artykułu twierdziła, że plik zmapowany w pamięci (memory-mapped file) rozwiązuje problem braku pamięci w architekturze 32-bitowej, na który natrafia TMemoryStream przy wejściu wielkości 2 GB. To twierdzenie jest błędne, a powód, dla którego jest błędne, wskazuje na prawdziwe rozwiązanie: przesuwne okno mapowania. Poniżej przedstawiono wzorzec dostępu, poprawioną 32-bitową historię wraz z kompilowalnym oknem mapowania oraz arytmetykę wywołań systemowych dla pliku testowego o rozmiarze 1,8 GB z 300 000 obiektów

Dlaczego układ PDF pokonuje buforowane odczyty

Trzy fakty strukturalne kształtują wzorzec IO. Po pierwsze, nawigacja jest oparta na offsetach: tabela odsyłaczy mapuje każdy numer obiektu na bezwzględną pozycję w bajtach i nic nie wymaga, aby te pozycje były uporządkowane. Po latach przyrostowych aktualizacji obiekt 4102 może znajdować się pod offsetem 1,6 GB, podczas gdy obiekt 4103 pod offsetem 30 KB. Pętla TFileStream zamienia każde pobranie w operację Seek plus Read, czyli dwa przejścia jądra (kernel transitions), z buforem, który nic nie wnosi, ponieważ kolejne pobranie jest setki megabajtów dalej

Po drugie, strumienie obiektów (ISO 32000-1 §7.5.7) pakują dziesiątki lub setki małych słowników do jednego skompresowanego kontenera (deflate). Pobranie jednego 300-bajtowego słownika strony może oznaczać odczytanie i dekompresję klastra o rozmiarze 100 KB. Druga strona medalu: obiekty zapisywane razem mają tendencję do bycia odczytywanymi razem, więc bufor o rozmiarze klastra obsługuje kilkanaście kolejnych pobrań za darmo — jest to najbardziej użyteczna prawidłowość w tym formacie

Po trzecie, linearyzacja. Zlinearyzowany plik umieszcza na początku pierwszą stronę i tabelę wskazówek (hint table), dzięki czemu konsumenci mogą czytać go od początku do końca. Gigabajtowe archiwa prawie nigdy nie są zlinearyzowane: linearyzację niszczą te same przyrostowe aktualizacje i łączenia plików, które sprawiły, że stał się on duży. Zaplanuj działanie dla najgorszego scenariusza: długie skoki, brak uporządkowania, wejście od końca pliku

32-bitowa historia, poprawiona

Proces w 32-bitowym systemie Windows dysponuje 2 GB przestrzeni adresowej użytkownika, a wywołanie MapViewOfFile z liczbą bajtów równą zero żąda ciągłej rezerwacji o rozmiarze pliku. W przypadku pliku wejściowego o wielkości 2 GB rezerwacja ta nie ma szans powodzenia: po załadowaniu pliku EXE, rozproszonych bibliotek DLL i stosów wątków, największy wolny ciągły blok w typowym 32-bitowym procesie Delphi wynosi od 700 MB do 1,4 GB. Wywołanie kończy się błędem ERROR_NOT_ENOUGH_MEMORY; jest to ta sama bariera, z którą zderza się TMemoryStream.LoadFromFile, jedynie przeniesiona z zaalokowanej pamięci RAM do rezerwacji przestrzeni adresowej. Mapowanie całego pliku nie jest rozwiązaniem w środowisku 32-bitowym, to po prostu ten sam błąd ukryty pod lepiej brzmiącymi nazwami API

Rozwiązaniem jest rozdzielenie dwóch rzeczy, które wykonuje mapowanie. CreateFileMapping tworzy obiekt sekcji i nie kosztuje w ogóle przestrzeni adresowej, niezależnie od rozmiaru pliku. Tylko MapViewOfFile zużywa przestrzeń adresową i nic nie zmusza do zmapowania całej sekcji: wywołanie przyjmuje 64-bitowy offset początkowy i długość widoku. Utwórz sekcję raz, zmapuj widok o wielkości 64 do 256 MB na obszar, który jest parsowany, a przed przesunięciem zdejmij mapowanie (unmap): kosztem w przestrzeni adresowej jest jedno okno, a nie jeden plik. Z jednym ograniczeniem: offsety widoku muszą być wielokrotnościami SYSTEM_INFO.dwAllocationGranularity, w praktyce 64 KB, więc żądanie dla offsetu 1 000 000 zostanie zaokrąglone w dół do 983 040, a wskaźnik wywołującego zostanie przesunięty do przodu o tę różnicę

Przesuwne okno mapowania (sliding-window mapper) w Delphi

Poniższa klasa opakowuje całą tę dyscyplinę: jeden obiekt sekcji, jeden aktywny widok, wyrównywanie do ziarnistości (granularity) oraz odczyty przecinające granicę okna, które są obsługiwane poprzez powiększenie tego pojedynczego widoku zamiast łączenia dwóch

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;

Dwa szczegóły niosą ze sobą największe korzyści. Szybka ścieżka (fast path) na początku metody Map zwraca wskaźnik bez przejścia jądra, gdy żądany zakres znajduje się już w aktywnym widoku; dzięki klastrowaniu w strumieniach obiektów jest to najczęstszy przypadek i źródło oszczędności. Z kolei żądanie przekraczające koniec domyślnego okna powiększa MapSize dla tego jednego widoku zamiast łączyć dwa, co utrzymuje metodę ReadBytes jako jednolinijkową, a wywołujących zwalnia z konieczności tworzenia pętli dla częściowych odczytów

Rozmiar okna to elastyczne pokrętło: przy 64 MB pełne przejście przez plik o rozmiarze 1,8 GB wymaga 29 widoków, przy 256 MB zaledwie 8, ale każdą rezerwację trudniej jest umieścić w sfragmentowanej 32-bitowej przestrzeni, z kolei poniżej około 16 MB pliki obfitujące w skoki wymuszają remapowanie na tyle często, że staje się to zauważalne. W przedziale od 64 do 256 MB ruch związany z mapowaniem to zaledwie szum statystyczny

Liczenie wywołań systemowych

A teraz matematyka. Plik testowy: 1,8 GB, 300 000 obiektów pośrednich, z których każdy przenosi średnio około 600 bajtów ładunku (payload). Parser działający obiekt po obiekcie pobiera każdy z nich za pomocą SetFilePointerEx plus 4 KB ReadFile: 600 000 przejść jądra. Na nowoczesnym sprzęcie x64 wywołanie systemowe buforowanego odczytu zajmuje (round-trip) około 1,5 μs, co daje 600 000 × 1,5 μs ≈ 0,9 sekundy czystego narzutu systemowego przed przeparsowaniem choćby jednego bajta — i to jest najlepszy scenariusz przy ciepłym cache'u. Na "zimno", każdy skok jest operacją na urządzeniu: przy efektywnym opóźnieniu ~20 μs dla losowych odczytów 4 KB z nośnika NVMe, 300 000 takich operacji kosztuje około 6 sekund czasu urządzenia; w przypadku pamięci masowej klasy SATA są to już minuty

Te odczyty przenoszą również niewłaściwe dane: 300 000 × 4 KB przepycha 1,2 GB przez bufory użytkownika, aby dostarczyć zaledwie około 180 MB ładunku — to sześciokrotne powielenie (amplifikacja), a każdy z tych bajtów jest kopiowany z jądra do przestrzeni użytkownika

Bufor typu read-ahead dopasowany rozmiarem do klastrów strumieni obiektów to pierwsze prawdziwe ulepszenie: jeden odczyt 256 KB na klaster zamiast jednego na obiekt zmniejsza liczbę przejść (kernel transitions) o jeden lub dwa rzędy wielkości. Jest to także odpowiednie narzędzie w sytuacjach, gdzie mapowanie sprawia trudności, najczęściej w przypadku udziałów sieciowych

Przesuwne okno mapowania idzie jeszcze dalej. Pełne przejście pliku to 29 wywołań MapViewOfFile i 29 UnmapViewOfFile, czyli 58 jawnych przejść jądra w porównaniu z 600 000. Prawdziwe parsowanie sterowane odsyłaczami (xref) nie jest czystym ciągłym przebiegiem, ale szybka ścieżka (fast path) amortyzuje każde pobranie w ramach aktywnego okna; przejście indeksujące metadane w archiwum testowym zatrzymało się na kilkuset remapowaniach. Mapowanie nie eliminuje pracy po stronie jądra: przekształca jawne wywołania systemowe w błędy braku strony (page faults), które menedżer pamięci rozwiązuje za pomocą klastrów wielostronicowych prosto z pamięci podręcznej plików, bez konieczności kopiowania do przestrzeni użytkownika, przy czym nienaruszane obszary nie generują kosztów. Od początku do końca faza indeksowania spadła z 23 s dla "zimnego" środowiska i 7,1 s przy ciepłym cache dla odczytów per obiekt do odpowiednio 6,5 s i 1,9 s przy użyciu obiektu mapującego; to co pozostało to dekompresja zlib (inflate), a nie wejście/wyjście (IO)

Gdzie pasuje FILE_FLAG_NO_BUFFERING

FILE_FLAG_NO_BUFFERING omija pamięć podręczną (cache) systemu w zamian za rygorystyczne zasady wyrównywania (alignment): offsety, długości bloków i adresy buforów muszą być wyrównane do sektorów. Przydaje się on w operacjach sekwencyjnych (o pojedynczym przebiegiem), które w przeciwnym razie zalałyby pamięć podręczną bajtami, których nikt więcej nie odczyta — jak na przykład re-serializacja wsadowa, która przepisuje całe archiwum, lub przebieg linearyzacji zapisanego na dysku pliku końcowego. Dzięki zrównanym buforom o rozmiarach od 4 do 8 MB, uzyskuje ono przepustowość niemal zbliżoną do sekwencyjnej nośnika, nie zaśmiecając pamięci podręcznej

W celach analizy zawartości (parsing) dokumentu to jest dokładnie błędne założenie. Losowe skoki na podstawie tabeli xref poprzez uchwyt niezbuforowany sprawiają, iż każde nawet najmniejsze pobranie słownika o długości 300 bajtów jest de facto wprost u źródła natychmiastowym wariantem czystego odczytu sprzętowego pozbawionym bufora który byłby np. gotów na użytek drugiej wizyty (z kolejnym zapytaniem o te dane) — podczas gdy parser PDF nawiedza dany obszar dokumentu stale i z częstotliwością, w szczególności ze względu na liczne strony mogące trafiać do tych samych strumieni obiektów (object streams). Wejście/wyjście (IO) pozbawione bufora najlepiej posłuży wyłącznie operacjom na bazie czystego zapisu z reguły sekwencyjnego przepisywania na nowo (sequential rewrite), natomiast przy losowym przetwarzaniu należy zdecydować się na wersje pod kątem dostępu mapowanego czy chociaż ujęcia buforowania; flaga wywoływana jest przypisana na uchwyt systemowy, można więc chociażby posiadać bezproblemowo te rzeczone dwa typy operacji działające tu w jednym potoku obsługi konkretnie ujętego pliku źródłowego

Architektura 64-bitowa, zbiory robocze oraz po stronie zapisu

W przypadku kompilacji 64-bitowej problem z przestrzenią adresową całkowicie znika: po przekazaniu rozmiaru pliku jako rozmiaru okna, powyższa klasa zostaje zredukowana do zwykłego wariantu rzędu pojedynczego zmapowania całego obszaru (single full mapping). Haczyk w przypadku długo działających usług: strony wsparte tylko do odczytu (read-only file-backed pages) wprawdzie nie powodują użycia zaangażowania (commit), dzięki czemu systemowe liczniki pozostają nienaruszone, aczkolwiek absolutnie każda odwiedzona przez skrypt strona natychmiast wraca (doczepiając do tzw. working set tj. roboczego zestawu systemu docelowego pulpitu); zdekodowanie dla rzędu przeważających obszarów objętości zasobu pokroju blisko ok. 1,8 GB drastycznie podniesie objętość tego zasobu, w konsekwencji eksmitując systemowo z niego niemal resztę wszelakich pozostałych zasobów. Określenie wąskich pułapów ustanawia "sufit", zatem rygor użycia okien o przesuwnym horyzoncie wzorca w dalszym ciągu należy do optymalnych mechanizmów wywoławczych - tak wręcz należy postąpić w większości wdrożeń nawet tam gdzie wariant przestrzeni wywoławczych dla puli systemowych wskaźników alokacji jest de facto wręcz pozornie niemal "od reki"

Z kolei patrząc od strony zapisu, najtańszym wejściem/wyjściem jest to I/O nigdy przez system nie podjęte. Mechanizm formatu PDF tzw. przyrostowej aktualizacji (ISO 32000-1 §7.5.6) na końcu samego dopisuje wyłącznie poddane re-edycji binarne obiekty dołączając równocześnie i drugą zrzuconą formę tablic z serii rzeczonej (cross-reference) bez ruszania ujętego oryginalnie na przestrzeni samego przodu ciągu źródłowych zrzutów binarnych bajtów. Pospolite stemplowanie dla choćby jednej z kart stron u góry opisywanego (o ok 1,8 GB rozmiarach objętościowych) repozytoriach dokłada góra najwyżej rozmiary z pułapu góra ledwie niewielkiej puli rzędu dosłownie kilkudziesięciu kilobajtów u źródła rzeczonego ogona. Całościowe przebicie i nadpisanie dokumentu to po raz wtóry mianowicie zjawisko ponownego przemieszczenia od podstaw bazy zasobów o rygorze wagowym ok. blisko 1,8 GB, co ewidentnie stanowi przepaść aż dobrych 5-ciu stopni rzędu u skali wielkości w samej swej definicji obciążeń, zatem i rzeczony "append" jest zatem wprost niczym wariacja strumienia sekwencyjnego tylko wyjściowego

Gdzie wpasowują się biblioteki losLab

Obie biblioteki udostępniane dla podmiotu losLab wyposażono u progu na bazie powierzchni warstwy API dla samego ułatwienia właśnie o takie opisywane od podstaw powołane tu już schematy systemowe. Wydzielony interfejs w opcji bezpośrednio pliku HotPDF Direct File API po prostu w trybie samej tylko oficjalnej rzeczonej otwartej usługi pod uchwyt systemowy podgląda same liczniki (zliczając tu chociażby same rozmiary dla np. liczników pod strony same w sobie czy ramy układu z ominięciem jakiejkolwiek uciążliwej powołanej alokacji czy parsingu na pełnym widoku drzew w obiekcie) operując zrzuconym dekretem po skopiowaniu go po samej kryptografii w dół, wywołując po wszystkim BeginIncrementalUpdate (celem naniesienia tzw. delt). Posiadany PDFlibPas zmierza pod wprost równoznacznie wyciągnięty wariant poprzez rzut własnej na tożsamych warunkach podyktowanej w bibliotece tzw. własnej struktury modułu tj. (Direct Access). Jeśli na rzecz samej firmy piszesz systemowo u swojego oprogramowania absolutnie autorski wariant silnika do ujęcia tego formatu miej wspomnianą klasę "do zmapowania" z progu swobodnie dla użytku; Jeśli jednak celujesz zrzut na pełen obieg procesu i potok obróbki pliku jako zadanie bazowe (niezależne procesowanie), pozwól powierzonej strukturze samej biblioteki "przypilnować za ciebie sufitów"

Uwaga: Zoptymalizowana obsługa wejścia/wyjścia (IO) dla gigabajtowych dokumentów jest wbudowana bezpośrednio w Komponent VCL HotPDF dla Delphi i C++Builder