אופטימיזציה של IO לעיבוד PDF בקנה מידה של ג'יגה-בייט ב-Delphi

הקריאה השימושית הראשונה של מנתח PDF נמצאת בקצה הלא נכון של הקובץ. הפורמט מציב את מצביע ה-startxref בבתים האחרונים, כך שעיבוד של ארכיון בנפח 1.8 GB מתחיל עם חיפוש (seek) אל הזנב, קריאה של קילובייט אחד, ואז קפיצה לכל מקום בו טבלת ההפניות המקורבות (cross-reference) אומרת שנמצא קטלוג המסמך. משם הניתוח הוא הליכה אקראית על פני כל טווח הבתים. כל מה שקלט/פלט (IO) במאגר (buffered) טוב בו - קריאה רציפה קדימה (read-ahead) מאחורי מצביע הקובץ - מכוון לעומס עבודה שאין ל-PDF

הגרסה הראשונה של מאמר זה טענה שקובץ ממופה בזיכרון (memory-mapped file) פותר את כשל הזיכרון (out-of-memory) של 32 סיביות ש-TMemoryStream נתקל בו בקלט של 2 GB. טענה זו שגויה, והאופן שבו היא שגויה מצביע על התיקון האמיתי: חלון מיפוי מחליק (sliding mapping window). להלן דפוס הגישה, סיפור ה-32 סיביות המתוקן עם מְמַפֶּה (mapper) חלונות הניתן להידור, ואריתמטיקת קריאות המערכת (syscall) על קובץ בדיקה בנפח 1.8 GB ו-300,000 אובייקטים

מדוע פריסת PDF מביסה קריאות במאגר

שלוש עובדות מבניות מעצבות את תבנית ה-IO. ראשית, הניווט מונחה היסט (offset-driven): טבלת ההפניות המקורבות ממפה כל מספר אובייקט למיקום בתים מוחלט, ושום דבר לא דורש שהמיקומים הללו יהיו מסודרים. אחרי שנים של עדכונים מצטברים, אובייקט 4102 יכול לשבת בהיסט של 1.6 GB בעוד אובייקט 4103 יושב ב-30 KB. לולאת TFileStream הופכת כל שליפה (fetch) ל-Seek בתוספת Read, שני מעברי ליבה (kernel transitions), עם מאגר שלא תורם כלום כי השליפה הבאה נמצאת במרחק של מאות מגה-בייטים

שנית, זרמי אובייקטים (ISO 32000-1 §7.5.7) אורזים עשרות או מאות מילונים קטנים לתוך מיכל מכווץ אחד. שליפה של מילון עמודים אחד של 300 בתים יכולה להיות קריאה וניפוח של אשכול בגודל 100 KB. הצד השני: אובייקטים שנכתבים יחד נוטים להיקרא יחד, לכן מאגר המותאם לגודל האשכול משרת את התריסר שליפות הבאות בחינם - הסדירות הניתנת לניצול ביותר בפורמט

שלישית, ליניאריזציה. קובץ שעבר ליניאריזציה טוען מראש את העמוד הראשון וטבלת רמזים כדי שצרכנים יוכלו לקרוא אותו מההתחלה לסוף. ארכיונים של ג'יגה-בייטים כמעט אף פעם לא עוברים ליניאריזציה: הליניאריזציה נהרסת על ידי אותם עדכונים מצטברים ומיזוגים שהפכו את הקובץ לגדול. תכננו למקרה העוין: קפיצות ארוכות, ללא סדר, כניסה מהזנב קודם

סיפור ה-32 סיביות, מתוקן

לתהליך של Windows ב-32 סיביות יש 2 GB של מרחב כתובות למשתמש, ו-MapViewOfFile עם ספירת בתים של אפס מבקש הזמנה רציפה אחת בגודל הקובץ. עבור קלט של 2 GB ההזמנה הזו לא יכולה להצליח: לאחר קובץ ה-EXE, קובצי DLL מפוזרים, ומחסניות הליכי משנה, הגוש הרציף החופשי הגדול ביותר בתהליך Delphi טיפוסי של 32 סיביות יושב איפשהו בין 700 MB ל-1.4 GB. הקריאה נכשלת עם ERROR_NOT_ENOUGH_MEMORY, אותו קיר ש-TMemoryStream.LoadFromFile נתקל בו, רק הועבר מזיכרון RAM שהוקצה להזמנת מרחב כתובות. מיפוי קובץ שלם אינו תיקון ב-32 סיביות, רק אותו כשל מאחורי שמות API שנשמעים טוב יותר

התיקון הוא הפרדה של שני הדברים שמיפוי עושה. CreateFileMapping יוצר את אובייקט המקטע (section object) ולא עולה במרחב כתובות בכלל, לא משנה מה גודל הקובץ. רק MapViewOfFile צורך מרחב כתובות, ושום דבר לא מאלץ אותו למפות את כל המקטע: הוא מקבל היסט התחלתי של 64 סיביות ואורך תצוגה. צרו את המקטע פעם אחת, מפו תצוגה של 64 עד 256 MB מעל האזור המנותח, בטלו את המיפוי (unmap) לפני ההחלקה הלאה: עלות מרחב הכתובות היא חלון אחד, לא קובץ אחד. אילוץ אחד: היסטי תצוגה חייבים להיות כפולות של SYSTEM_INFO.dwAllocationGranularity, 64 KB בפועל, לכן בקשה להיסט 1,000,000 מעוגלת כלפי מטה ל-983,040 והמצביע של המתקשר מותאם קדימה לפי ההפרש

ממפה קבצים חלוני ב-Delphi

הכיתה להלן עוטפת את המשמעת כולה: אובייקט מקטע אחד, תצוגה חיה אחת, התאמה מחדש של הפירוט (granularity realignment), וקריאות שחוצות גבול של חלון המטופלות על ידי הגדלת אותה תצוגה אחת במקום תפירה של שתיים

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;

שני פרטים נושאים במשקל. הנתיב המהיר בחלק העליון של Map מחזיר מצביע ללא מעבר ליבה כאשר הטווח המבוקש כבר יושב בתוך התצוגה החיה; הודות לקיבוץ (clustering) של זרמי אובייקטים, זהו המקרה הנפוץ ושם נמצא החיסכון. ובקשה שחוצה את קצה חלון ברירת המחדל מגדילה את MapSize עבור התצוגה האחת הזו במקום לתפור שתיים, מה ששומר על ReadBytes כשורת קוד אחת ומשחרר את המתקשרים מלולאות של קריאה חלקית

גודל החלון הוא כפתור סלחני: ב-64 MB, סריקה מלאה של קובץ בנפח 1.8 GB היא 29 תצוגות, ב-256 MB זה 8 אבל כל הזמנה קשה יותר להצבה במרחב 32 סיביות מקוטע, ומתחת לכ-16 MB קבצים כבדי-קפיצות ממופים מחדש בתדירות שמורגשת. בכל מקום בטווח של 64 עד 256 MB, תעבורת המיפוי היא רעש סטטיסטי

ספירת קריאות המערכת (syscalls)

עכשיו האריתמטיקה. קובץ בדיקה: 1.8 GB, 300,000 אובייקטים עקיפים בממוצע של כ-600 בתים של מטען נתונים. מנתח לכל-אובייקט שולף כל אחד עם SetFilePointerEx בתוספת ReadFile של 4 KB: 600,000 מעברי ליבה. קריאת מערכת שנשמרה במטמון עושה סיבוב (round-trip) בכ-1.5 מיקרו-שניות (μs) בחומרת x64 נוכחית, כלומר 600,000 × 1.5 מיקרו-שניות ≈ 0.9 שניות של תקורת ליבה טהורה לפני ניתוח של בית בודד - המקרה הטוב ביותר עם מטמון חם. במצב קר, כל קפיצה היא פעולת התקן: בהשהיה (latency) יעילה של ~20 מיקרו-שניות לקריאות אקראיות של 4 KB ב-NVMe, 300,000 מהן עולות כ-6 שניות של זמן התקן; באחסון ברמת SATA, דקות

הקריאות גם מעבירות את הנתונים הלא נכונים: 300,000 × 4 KB דוחפים 1.2 GB דרך מאגרי המשתמש כדי לספק כ-180 MB של מטען נתונים - הגברה של פי שישה, כל בית מועתק מהליבה למשתמש

מאגר קריאה-קדימה המותאם לאשכולות זרמי האובייקטים הוא השיפור הכן הראשון: קריאה אחת של 256 KB לכל אשכול במקום אחת לכל אובייקט חותכת את ספירת המעברים בסדר גודל אחד עד שניים. זהו גם הכלי הנכון כאשר מיפוי הוא מסורבל, בדרך כלל בתיקיות רשת משותפות

הממפה החלוני מרחיק לכת. סריקה מלאה היא 29 קריאות MapViewOfFile ו-29 קריאות UnmapViewOfFile, 58 מעברים מפורשים לעומת 600,000. ניתוח אמיתי מונחה xref אינו סריקה נקייה, אך הנתיב המהיר סופג כל שליפה בתוך החלון החי; מעבר של אינדוקס מטא-נתונים על פני ארכיון הבדיקה התייצב על כמה מאות מיפויים מחדש. המיפוי אינו מסיר עבודת ליבה: הוא ממיר קריאות מערכת מפורשות לתקלות דף (page faults) שמנהל הזיכרון פותר באשכולות מרובי-דפים, היישר ממטמון הקבצים ללא עותק במרחב המשתמש, ואזורים שלעולם לא נוגעים בהם לא עולים כלום. מקצה לקצה, מעבר האינדוקס ירד מ-23 שניות במצב קר ו-7.1 שניות במצב חם עם קריאות לכל-אובייקט ל-6.5 שניות במצב קר ו-1.9 שניות במצב חם עם הממפה; מה שנותר הוא ניפוח zlib, לא IO

היכן משתלב FILE_FLAG_NO_BUFFERING

FILE_FLAG_NO_BUFFERING עוקף את המטמון של המערכת בתמורה לכללי יישור נוקשים: היסטים, אורכים וכתובות מאגר כולם מיושרים למגזר (sector-aligned). הוא מוכיח את יעילותו בעבודות רציפות במעבר יחיד שהיו מציפות את המטמון בבתים שאף אחד לא קורא פעמיים - סדריות-מחדש (re-serialization) באצווה שכותבת מחדש את כל הארכיון, או מעבר ליניאריזציה על פלט מוגמר. עם מאגרים מיושרים של 4 עד 8 MB הוא מתקרב לרוחב הפס הרציף של ההתקן ללא זיהום המטמון

זה בדיוק שגוי עבור ניתוח. קפיצות xref אקראיות דרך מאחיז (handle) ללא מאגר הופכות כל שליפת מילון של 300 בתים לקריאה פיזית מלאה ללא מטמון שיספוג את הביקור השני - וניתוח PDF מבקר מחדש באזורים ללא הרף, מכיוון שעמודים שונים נפתרים לאותם זרמי אובייקטים. IO ללא מאגר עבור השכתוב הרציף, IO ממופה או במטמון עבור הניתוח האקראי; הדגל הוא פר-מאחיז, כך שצינור עיבוד אחד יכול להחזיק את שניהם על אותו קובץ

64 סיביות, מערכי עבודה (working sets) וצד הכתיבה

בבנייה של 64 סיביות התנגדות מרחב הכתובות נעלמת: העבירו את גודל הקובץ כחלון והכיתה לעיל מתנוונת למיפוי מלא יחיד. הקאטש (catch) בשירותים שרצים זמן רב: דפים בגיבוי-קובץ לקריאה-בלבד אינם מחייבים חיוב commit, כך שמוני ה-commit נשארים רגועים, אך כל דף שנוגעים בו מצטרף למערך העבודה; נתחו את רוב ה-1.8 GB ומערך העבודה יגדל בהתאם, תוך פינוי כל השאר. חלונות תחומים שמים תקרה על כך, ולכן התבנית המחליקה נשארת ברירת המחדל הנכונה גם כאשר מרחב הכתובות פנוי

בצד הכתיבה, ה-IO הזול ביותר הוא זה שמעולם לא הופעל. מנגנון העדכון המצטבר של PDF (ISO 32000-1 §7.5.6) מצרף את האובייקטים שהשתנו וחלק חדש של טבלת הפניות מקורבות אחרי הבתים המקוריים, שלעולם אינם זזים. הטבעת עמוד אחד על ארכיון של 1.8 GB מצרפת עשרות קילובייטים; שכתוב מלא מזיז את כל ה-1.8 GB, חמישה סדרי גודל הפרש, והצירוף הוא פלט רציף טהור בזנב

היכן משתלבות ספריות losLab

שתי ספריות ה-PDF של losLab מספקות משמעת זו כשטח API. ה-HotPDF Direct File API קורא ספירות עמודים ומבנה דרך מאחיז קובץ מבלי לבנות את עץ האובייקטים, מעתיק ומפענח ברמת הקובץ, וכותב דלתאות דרך BeginIncrementalUpdate - אסטרטגיית ה-append-only לעיל, ארוזה. PDFlibPas נוקטת באותו מסלול עם שכבת ה-Direct Access שלה: קורא מוזרם שעובר על טבלת ההפניות המקורבות במקום, שולף אובייקטים בעצלות, מחלץ טווחי עמודים מקובץ לקובץ, ושומר עריכות כתיקונים מצטברים. אם אתם כותבים מנתח משלכם, כיתת הממפה שלכם לקחת; אם אתם מריצים צינור עיבוד מסמכים, תנו לספרייה לשמור על החלון ישר

הערה: טיפול מותאם בקלט/פלט עבור מסמכים בקנה מידה של ג'יגה-בייט מובנה ישירות ב-רכיב VCL של HotPDF עבור Delphi ו-C++Builder