بهینه‌سازی کارایی IO برای پردازش PDF در مقیاس گیگابایت

اولین خوانش واقعاً مفید در یک PDF در بدترین جای فایل قرار دارد. قالب، اشاره‌گر startxref را در بایت‌های پایانی می‌گذارد، بنابراین پردازش یک آرشیو 1.8 گیگابایتی با یک seek به انتهای فایل، یک خوانش یک کیلوبایتی و سپس یک پرش به جایی شروع می‌شود که جدول ارجاع متقاطع می‌گوید کاتالوگ سند آنجاست. از آن نقطه به بعد، پارس کردن به یک راه‌پیمایی تصادفی در سراسر بازه بایت‌ها تبدیل می‌شود. هر چیزی که IO بافرشده در آن خوب است، یعنی read-ahead ترتیبی پشت اشاره‌گر فایل، برای باری طراحی شده است که PDF اصولاً ندارد

نسخه نخست این مقاله ادعا می‌کرد فایل memory-mapped می‌تواند خطای کمبود حافظه سی‌ودوبیتی را که TMemoryStream روی ورودی 2 گیگابایتی می‌بیند حل کند. این ادعا نادرست بود و دقیقاً همین نقطه خطا به راه‌حل واقعی اشاره می‌کند: پنجره نگاشت لغزان. در ادامه الگوی دسترسی، روایت اصلاح‌شده برای سی‌ودوبیتی با یک windowed mapper قابل کامپایل، و حساب‌وکتاب syscallها روی یک فایل آزمایشی 1.8 گیگابایتی با 300000 شیء را می‌بینید

چرا چیدمان PDF خوانش بافرشده را شکست می‌دهد

سه واقعیت ساختاری الگوی IO را شکل می‌دهند. اول اینکه ناوبری مبتنی بر offset است: جدول ارجاع متقاطع هر شماره شیء را به یک موقعیت مطلق بایت نگاشت می‌کند و هیچ چیزی این موقعیت‌ها را مجبور به مرتب بودن نمی‌کند. بعد از سال‌ها به‌روزرسانی افزایشی، شیء 4102 می‌تواند در offset برابر با 1.6 گیگابایت باشد، در حالی که شیء 4103 در 30 کیلوبایت نشسته است. یک حلقه TFileStream هر واکشی را به یک Seek به‌علاوه یک Read تبدیل می‌کند، یعنی دو انتقال هسته، با بافری که هیچ کمکی نمی‌کند چون واکشی بعدی صدها مگابایت دورتر است

دوم، object streamها طبق ISO 32000-1 §7.5.7 ده‌ها یا صدها دیکشنری کوچک را در یک container فشرده‌شده جمع می‌کنند. واکشی یک page dictionary سیصدبایتی می‌تواند به معنی خواندن و inflate کردن یک خوشه 100 کیلوبایتی باشد. روی دیگر ماجرا این است که اشیائی که با هم نوشته شده‌اند معمولاً با هم هم خوانده می‌شوند، بنابراین بافری که به اندازه خوشه باشد، دوازده واکشی بعدی را تقریباً رایگان پوشش می‌دهد و این بهره‌بردنی‌ترین نظم موجود در این قالب است

سوم، linearization است. یک فایل linearized صفحه اول و جدول hint را جلو می‌آورد تا مصرف‌کننده بتواند فایل را از ابتدا به انتها بخواند. آرشیوهای گیگابایتی تقریباً هیچ‌وقت linearized نیستند، چون همان به‌روزرسانی‌های افزایشی و mergeهایی که فایل را بزرگ کرده‌اند، linearization را هم از بین برده‌اند. برای حالت بدبینانه برنامه‌ریزی کنید: پرش‌های بلند، بدون ترتیب، و ورود از انتهای فایل

روایت سی‌ودوبیتی، با اصلاح لازم

یک پردازه Windows سی‌ودوبیتی 2 گیگابایت فضای آدرس کاربر دارد و MapViewOfFile با تعداد بایت صفر درخواست یک رزرو پیوسته به اندازه کل فایل را می‌دهد. برای ورودی 2 گیگابایتی این رزرو نمی‌تواند موفق شود: بعد از EXE، DLLهای پراکنده و stackهای thread، بزرگ‌ترین بلوک آزاد پیوسته در یک پردازه معمولی Delphi سی‌ودوبیتی جایی بین 700 مگابایت تا 1.4 گیگابایت قرار می‌گیرد. فراخوانی با ERROR_NOT_ENOUGH_MEMORY شکست می‌خورد؛ همان دیواری که TMemoryStream.LoadFromFile به آن می‌خورد، فقط این بار از RAM متعهدشده به رزرو فضای آدرس منتقل شده است. نگاشت کل فایل در سی‌ودوبیتی هیچ درمانی نیست و فقط همان شکست را پشت نام‌های API خوش‌آهنگ‌تر پنهان می‌کند

راه‌حل این است که دو کاری را که نگاشت انجام می‌دهد از هم جدا کنیم. CreateFileMapping شیء section را می‌سازد و فارغ از اندازه فایل هیچ هزینه‌ای در فضای آدرس ندارد. فقط MapViewOfFile فضای آدرس خرج می‌کند و هیچ چیزی آن را مجبور نمی‌کند کل section را نگاشت کند: این تابع یک offset آغاز 64 بیتی و یک طول view می‌گیرد. section را یک‌بار بسازید، یک view بین 64 تا 256 مگابایت روی ناحیه در حال پارس نگاشت کنید و پیش از لغزاندن آن را unmap کنید: هزینه فضای آدرس یک پنجره است، نه یک فایل کامل. یک محدودیت هم وجود دارد: offsetهای view باید مضربی از SYSTEM_INFO.dwAllocationGranularity باشند که در عمل 64 کیلوبایت است، بنابراین درخواست برای offset برابر با 1000000 به 983040 گرد می‌شود و اشاره‌گر فراخواننده به اندازه اختلاف به جلو تنظیم می‌شود

یک mapper پنجره لغزان در Delphi

کلاس زیر تمام این انضباط را بسته‌بندی می‌کند: یک section object، یک view زنده، هم‌ترازی دوباره با granularity، و خوانش‌هایی که از مرز پنجره عبور می‌کنند با بزرگ کردن همان view واحد مدیریت می‌شوند، نه با وصله کردن دو view جداگانه

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;

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;

دو جزئیات بار اصلی را تحمل می‌کنند. مسیر سریع در ابتدای Map وقتی بازه درخواستی از قبل داخل view زنده قرار دارد، بدون هیچ انتقالی به هسته فقط یک اشاره‌گر برمی‌گرداند. به لطف خوشه‌بندی object streamها، همین حالت مسیر غالب است و بخش اصلی صرفه‌جویی از همین‌جا می‌آید. همچنین اگر درخواست از انتهای پنجره پیش‌فرض عبور کند، به‌جای وصله کردن دو view، فقط MapSize برای همان view بزرگ می‌شود و در نتیجه ReadBytes یک خط ساده می‌ماند و فراخواننده هم وارد حلقه‌های partial-read نمی‌شود

اندازه پنجره یک پیچ تنظیم forgiving است: با 64 مگابایت، یک sweep کامل روی فایل 1.8 گیگابایتی به 29 view نیاز دارد؛ با 256 مگابایت این عدد به 8 می‌رسد، اما هر رزرو در فضای آدرس تکه‌تکه‌شده سی‌ودوبیتی سخت‌تر جا می‌گیرد؛ و زیر حدود 16 مگابایت، فایل‌های پرجهش آن‌قدر remap می‌شوند که اثرش محسوس می‌شود. در هرجای بازه 64 تا 256 مگابایت، ترافیک نگاشت عملاً نویز آماری است

شمارش syscallها

حالا سراغ حساب‌وکتاب برویم. فایل آزمایشی: 1.8 گیگابایت، 300000 شیء غیرمستقیم با میانگین حدود 600 بایت payload. یک parser شیء-به-شیء هر مورد را با یک SetFilePointerEx و یک ReadFile چهارهزاربایتی واکشی می‌کند: 600000 انتقال به هسته. یک syscall خوانش با کش روی سخت‌افزار x64 امروزی تقریباً 1.5 میکروثانیه رفت‌وبرگشت دارد، پس 600000 × 1.5 μs حدود 0.9 ثانیه سربار خالص هسته است، آن هم پیش از پارس شدن حتی یک بایت و در بهترین حالت cache-warm. در حالت cold، هر پرش یک عملیات روی دستگاه است: با latency مؤثر حدود 20 میکروثانیه برای خوانش تصادفی 4 کیلوبایتی NVMe، همین 300000 پرش حدود 6 ثانیه زمان دستگاه می‌بلعد و روی ذخیره‌سازهای کلاس SATA به دقیقه‌ها می‌رسد

خود خوانش‌ها هم داده اشتباه را جابه‌جا می‌کنند: 300000 × 4 کیلوبایت برابر با 1.2 گیگابایت داده را از بافرهای کاربر عبور می‌دهد تا فقط حدود 180 مگابایت payload تحویل دهد، یعنی شش برابر amplification و کپی شدن تک‌تک بایت‌ها از هسته به کاربر

یک read-ahead buffer که به اندازه خوشه‌های object stream تنظیم شده باشد، اولین بهبود صادقانه است: یک خوانش 256 کیلوبایتی برای هر خوشه به‌جای یک خوانش برای هر شیء، تعداد انتقال‌ها را یک تا دو مرتبه بزرگی کاهش می‌دهد. این راه‌حل همچنین در جاهایی که نگاشت سخت است، معمولاً روی اشتراک‌های شبکه، ابزار درست‌تری است

mapper پنجره لغزان یک قدم جلوتر می‌رود. یک sweep کامل فقط 29 فراخوانی MapViewOfFile و 29 فراخوانی UnmapViewOfFile دارد، یعنی 58 انتقال صریح در برابر 600000 انتقال. یک parse واقعی مبتنی بر xref البته sweep تمیز نیست، اما مسیر سریع هر واکشی داخل پنجره زنده را جذب می‌کند. در یک گذر نمایه‌سازی metadata روی همین آرشیو آزمایشی، تعداد remapها به چندصد مورد رسید. نگاشت کار هسته را حذف نمی‌کند؛ syscallهای صریح را به page faultهایی تبدیل می‌کند که memory manager آن‌ها را در خوشه‌های چندصفحه‌ای و مستقیماً از file cache، بدون کپی در فضای کاربر، حل می‌کند و نواحی‌ای هم که هرگز لمس نمی‌شوند هیچ هزینه‌ای ندارند. نتیجه سرتاسری این بود که گذر نمایه‌سازی از 23 ثانیه cold و 7.1 ثانیه warm با خوانش‌های شیء-به-شیء، به 6.5 ثانیه cold و 1.9 ثانیه warm با mapper رسید و آنچه باقی ماند zlib inflate بود، نه IO

جایگاه FILE_FLAG_NO_BUFFERING

FILE_FLAG_NO_BUFFERING با کنار زدن system cache در ازای قواعد سخت‌گیرانه هم‌ترازی کار می‌کند: offsetها، طول‌ها و آدرس بافرها همگی باید sector-aligned باشند. این پرچم در کارهای ترتیبی تک‌گذر که در غیر این صورت cache را با بایت‌هایی که دوباره خوانده نمی‌شوند پر می‌کنند ارزشمند است، مثل re-serialization دسته‌ای که کل آرشیو را بازنویسی می‌کند یا یک گذر linearization روی خروجی نهایی. با بافرهای هم‌تراز 4 تا 8 مگابایتی می‌تواند بدون آلوده کردن کش به پهنای باند ترتیبی دستگاه نزدیک شود

اما برای parsing دقیقاً انتخاب اشتباهی است. پرش‌های تصادفی xref روی یک handle بدون بافر، هر واکشی دیکشنری سیصدبایتی را به یک خوانش کامل فیزیکی تبدیل می‌کند، بدون کشی که بازدید دوم را جذب کند، در حالی که parsing فایل PDF مدام به همان نواحی برمی‌گردد چون صفحات مختلف به همان object streamها resolve می‌شوند. IO بدون بافر برای بازنویسی ترتیبی، IO نگاشتی یا cache شده برای parse تصادفی؛ چون این پرچم per-handle است، یک pipeline می‌تواند هر دو را روی یک فایل نگه دارد

شصت‌وچهاربیتی، working set و سمت نوشتن

در build شصت‌وچهاربیتی ایراد فضای آدرس از بین می‌رود: اگر اندازه فایل را به عنوان اندازه پنجره بدهید، کلاس بالا عملاً به یک نگاشت کامل تبدیل می‌شود. اما در سرویس‌های بلندمدت یک نکته باقی می‌ماند: صفحه‌های فقط‌خواندنیِ پشت‌فایل commit مصرف نمی‌کنند، پس شمارنده‌های commit آرام می‌مانند، ولی هر صفحه‌ای که لمس شود وارد working set می‌شود. اگر بیشترِ فایل 1.8 گیگابایتی را parse کنید، working set هم تا همان حدود رشد می‌کند و بقیه چیزها را بیرون می‌راند. پنجره‌های محدود روی این رشد سقف می‌گذارند، بنابراین الگوی لغزان حتی جایی که فضای آدرس آزاد است هم پیش‌فرض درست باقی می‌ماند

در سمت نوشتن، ارزان‌ترین IO همان IOای است که اصلاً صادر نمی‌شود. سازوکار incremental update در PDF طبق ISO 32000-1 §7.5.6 اشیای تغییرکرده و یک بخش ارجاع متقاطع جدید را بعد از بایت‌های اصلی append می‌کند و بایت‌های قبلی هرگز جابه‌جا نمی‌شوند. اگر فقط یک صفحه را روی آرشیو 1.8 گیگابایتی stamp کنید، چند ده کیلوبایت append می‌شود؛ در حالی که بازنویسی کامل کل 1.8 گیگابایت را جابه‌جا می‌کند. این دو پنج مرتبه بزرگی فاصله دارند و append هم یک خروجی کاملاً ترتیبی در انتهای فایل است

جایگاه کتابخانه‌های losLab

هر دو کتابخانه PDF شرکت losLab این انضباط را در سطح API ارائه می‌کنند. HotPDF Direct File API بدون ساختن درخت شیء، تعداد صفحات و ساختار را از طریق file handle می‌خواند، کپی و decrypt را در سطح فایل انجام می‌دهد و deltaها را از طریق BeginIncrementalUpdate می‌نویسد؛ یعنی همان راهبرد append-only که بالاتر توضیح داده شد اما به‌صورت بسته‌بندی‌شده. PDFlibPas هم با لایه Direct Access همین مسیر را می‌رود: یک reader جریانی که جدول ارجاع متقاطع را درجا پیمایش می‌کند، اشیاء را lazy واکشی می‌کند، بازه‌های صفحه را از فایل به فایل استخراج می‌کند و ویرایش‌ها را به‌صورت بازبینی‌های افزایشی پایدار می‌سازد. اگر parser خودتان را می‌نویسید، کلاس mapper را بردارید و استفاده کنید؛ اگر هم یک pipeline سند اجرا می‌کنید، بگذارید کتابخانه این پنجره را صادق نگه دارد

نکته: رسیدگی به IO بهینه برای اسناد در مقیاس گیگابایت به‌صورت مستقیم در HotPDF VCL Component برای Delphi و C++Builder تعبیه شده است