גרף התלויות של HotXLS: אינדוקס פלטים של נוסחאות מערך

‏HotXLS 2.383.1, ספריית ה-Excel הילידית ל-Delphi ול-C++Builder, בונה קשתות תלות של נוסחאות דרך אינדקס מרווחי פלט: צמתי הנוסחאות נשארים ממוינים לפי תא עוגן, ועץ segment שמחזיק את שורת הפלט הגדולה (OutRow2) של כל תת-עץ מאפשר ל-TXLSDepGraph.BuildEdges לדלג על בלוקים שלמים של נוסחאות שלא יכולות להגיע לטווח מופנה. על חוברת Win32 עם כ-100,000 נוסחאות, חישוב חוזר כפוי צנח מ-18.488 שניות ל-102–109 מילישניות

אף אחד לא עושה profiling לגרף התלויות עד שעבודת אצווה שנהגה לקחת שנייה מתחילה לקחת עשרים. הגרף נבנה מחדש בכל פעם שטופולוגיית הנוסחאות משתנה — ה-Recalculate הראשון אחרי טעינה או יצירה של חוברת, או כל מעבר אחרי שהגרף נפסל — וב-trace שלפני התיקון אותו מעבר ראשון לבד לקח 16,074 ms. ההערכה מעולם לא הייתה הבעיה; להחליט מי תלוי במי הייתה

למה חישוב חוזר של 100,000 נוסחאות לקח 18 שניות?

בונה הקשתות הישן היה ריבועי במספר הנוסחאות בגיליון. עבור כל טווח תלות, BuildEdges ביצע חיפוש בינארי אחר חלון של צמתים מועמדים ואז בדק כל אחד עם RangeIntersectsOutput, והחלון הזה התחיל בראש הגיליון המופנה ממש. מפתחות הצמתים מגיעים מ-XLSDepMakeKey, שאורז את אינדקס הגיליון החל מסיבית 34, את השורה בסיביות 14–33, ואת העמודה בסיביות 0–13, כך שהחסם התחתון (Sheet1, 0, 0) היה פירושו "כל נוסחה משורה 1 ומטה עד לתחתית הטווח המופנה"

// לפני 2.383.1 — TXLSDepGraph.BuildEdges, עבור טווח תלות r של צומת d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // ראש הגיליון
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...שני חיפושים בינאריים על FNodeOrder מניבים את החלון [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // קשת hard או קשת LookupScan, מנוטרלות כפילויות דרך EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

רתמת הביצועים שחשפה את זה היא מודל cascade רגיל לחלוטין: A2:A50000 כל אחד מוסיף אחד לתא שמעליו, ו-B1:B50000 כל אחד מכפיל את השכן בעמודה A. הפניה לשורה r גררה אם כך כ-2r מועמדים דרך בדיקת המלבן, כך שבניית גרף אחת ביצעה בסדר גודל של חמישה מיליארד בדיקות חיתוך — הערכה גסה על נייר, אבל היא מתיישרת עם 18.5 השניות על השעון. כל בדיקה ענתה "לא" חוץ מאחת-שתיים

למה בונה הקשתות לא יכול להתחיל את החיפוש בשורה המופנית?

כי נוסחת מערך שמעוגנת מעל טווח יכולה להחזיק בעלות על תאים בתוכו. כל TXLSDepNode מתאר מלבן פלט מהעוגן שלו (Row, Col) ועד (OutRow2, OutCol2), ונוסחת מערך CSE מקבלת צומת אחד למלבן שלמה שלה, כפי שהמאמר על חישוב חוזר מצטבר וגרף התלויות מסביר. שורש שמעוגן ב-A1 וממלא את A1:A10 חייב עדיין לקבל קשת מנוסחה שקוראת רק את A5; התחל את החיפוש הבינארי בשורה 5 והקשת הזו נעלמת בשקט, מה שאומר ערך מטמון מיושן בדוח שנשלח ללקוח במקום דוח איטי. השאילתה היא באמת דו-צדדית — עוגן ב-Row2 או לפניו, פלט שמגיע לפחות עד Row1 — וסדר מיון יחיד לא יכול לענות על שני החצאים. תוצאות מרובות תאים מופיעות גם בחוברות מודרניות, והמאמר על נוסחאות spill של מערכים דינמיים מכסה איך טווחים נשפכים מתנהגים ב-HotXLS

עץ segment של שורות פלט מקסימליות

‏HotXLS משאיר את מיון העוגנים עבור החסם העליון ומוסיף עץ segment מועשר עבור החסם התחתון. BuildNodeIndex ממיין את FNodeOrder לפי מפתח צומת כקודם, ואז BuildMaxOutRowTree ממלא את FNodeMaxOutRow2 (מוקצה בארבע כניסות לצומת) עם ה-OutRow2 הגדול ביותר שנמצא תחת כל תת-עץ. QueryNodeTree יורד רק בתוך חלון המפתחות ונוטש כל תת-עץ ששורת הפלט המקסימלית שלו נמצאת מעל FRanges[r].Row1, כי אף נוסחה בו לא יכולה להגיע לשורות המופנות. עלים ששרדו עדיין עוברים את בדיקת RangeIntersectsOutput המלאה, כך שטווחי גיליונות ועמודות נבדקים בדיוק כמו קודם

// TXLSDepGraph.BuildNodeIndex / BuildEdges מאז 2.383.1 (מעט מקוצר)
procedure BuildMaxOutRowTree(ATreeIndex, ALeft, ARight: Integer);
var
  Mid: Integer;
begin
  if ALeft = ARight then
  begin
    FNodeMaxOutRow2[ATreeIndex] := FNodes[FNodeOrder[ALeft]].OutRow2;
    Exit;
  end;
  Mid := (ALeft + ARight) shr 1;
  BuildMaxOutRowTree(ATreeIndex * 2, ALeft, Mid);
  BuildMaxOutRowTree(ATreeIndex * 2 + 1, Mid + 1, ARight);
  FNodeMaxOutRow2[ATreeIndex] := Max(FNodeMaxOutRow2[ATreeIndex * 2],
    FNodeMaxOutRow2[ATreeIndex * 2 + 1]);
end;

procedure QueryNodeTree(ATreeIndex, ALeft, ARight, ALower, AUpper: Integer);
var
  Split: Integer;
begin
  // מחוץ לחלון המפתחות, או שאף פלט בתת-עץ הזה לא מגיע ל-Row1
  if (ARight < ALower) or (ALeft >= AUpper) or
     (FNodeMaxOutRow2[ATreeIndex] < FRanges[r].Row1) then
    Exit;
  if ALeft = ARight then
  begin
    Inc(FEdgeCandidateChecks);
    if RangeIntersectsOutput(FRanges[r], FNodes[FNodeOrder[ALeft]]) then
    begin
      // ללא שינוי: דיכוי EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // תת-עץ שמאלי קודם
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // שומר על הסדר הישן
end;

הרקורסיה שמאל-לפני-ימין אינה בחירה סגנונית. עלים ששרדו מבוקרים בדיוק בסדר שבו הלולאת while הישנה ביקרה אותם, כך שמערכי Dependents ו-Precedents מתמלאים באותו רצף והסדר הטופולוגי נשאר דטרמיניסטי. אותו דבר נכון לשני סוגי הקשתות: קשת hard שנרשמה ראשונה עדיין מדכאת קשת LookupScan מאוחרת עבור אותו זוג, בזמן שקשת scan שנרשמה לפני קשת hard שומרת על מקומה — ההבחנה שמונעת מטווחי lookup לייצר הפניות מעגליות כוזבות. לכל הפניה, העלות צונחת מגודל החלון ל-O((k + 1) log n), כאשר k הוא מספר הנוסחאות שהפלט שלהן באמת מגיע לשורות המופנות

מה אינדקס הפלט מבטיח, ואיך זה מאומת?

‏TXLSDepGraph מפיק את אותן קשתות באותו סדר כמו קודם, והמאפיין החדש EdgeCandidateChecks סופר כמה מלבני פלט הבנייה האחרונה באמת בדקה, כך שהטענה ניתנת למדידה ולא רטורית. בדיקת הרגרסיה EdgeBuildDeepChainsCheckOneCandidatePerDependency בונה שרשראות הפניות נקודתיות של 1,024 ו-100,000 צמתים, שהוכנסו בסדר הפוך כדי לכפות את המיון המרחבי, ומאמתת בדיוק N − 1 בדיקות — 99,999 עבור השרשרת הארוכה — בתוספת הסדר הצפוי של precedent, dependent וטופולוגיה לכל צומת. בדיקות נלוות מכסות שורשי מערך שהוכנסו שלא בסדר על פני טווחי גיליונות, הפניות hard ו-lookup-scan כפולות (10 בדיקות, עם כללי הדיכוי שלמעלה), ובנייה מחדש אחרי AddNode, שמנקה את דגל המיון כך ש-BuildEdges או NodeIndexOf הבאים בונים את העץ מחדש ומאפסים את המונה במקום לצבור אותו

תוצאות נמדדות: מ-18.5 שניות לכ-0.1 שניות

ה-trace של Win32 לפני התיקון, שנשמר בקו הבסיס של ביצועי הפרויקט עבור גרסה 2.383.0, תיעד שני חישובים חוזרים כפויים של 18,488 ms ו-19,578 ms. אחרי האינדוקס, שלוש ריצות focused סדרתיות לכל ארכיטקטורה מדדו 102.332–109.429 ms ב-Win32 ו-116.990–133.995 ms ב-Win64, בערך פי 170 עד 180 מהר יותר ב-Win32; לא נרשם קו בסיס של Win64 לפני התיקון, ולכן לא נטענת האצה ל-Win64. אותן ריצות עברו את השער הקיים שמחזיק ביקורת חישוב חוזר לקריאה בלבד בתוך 1.35 מחישוב חוזר כפוי. המספרים המוחלטים תלויים במכונה ובעומס שלה, אז שחזרו את עומס העבודה על החומרה שלכם לפני שאתם מצטטים אותם

uses
  System.SysUtils, System.Diagnostics, lxHandle;

procedure TimeChainRecalc;
var
  Wb: TXLSWorkbook;
  Sh: TXLSWorksheet;
  I, Failed: Integer;
  Watch: TStopwatch;
begin
  Wb := TXLSWorkbook.Create;
  try
    Sh := Wb.Sheets.Add;
    Sh.Cells[1, 1].Value := 1;
    for I := 2 to 50000 do                     // שרשרת של 49,999 חוליות בעמודה A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50,000 תלויים בעמודה B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // הקריאה הראשונה בונה את הגרף
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

איפה אינדקס הפלט מפסיק לעזור?

העץ גוזם על שורות בלבד, וזה משאיר כמה מגבלות כנות שכדאי להכיר לפני שאתה בונה סביבו מודל ענק

• פספוסי עמודה עדיין משולמים בעלים: 2,626 הנוסחאות שממלאות את A100:Z200 כולן מגיעות לשורה 100, כך שהפניה ל-AA100:AA200 בודקת כל אחת מהן לפני שהיא דוחה אותה
• הפניות רחבות כמו טווחי עמודה שלמה באמת מחזיקות הרבה precedents; האינדקס מסיר בדיקות מבוזבזות, לא קשתות אמיתיות, ובניית הקשתות האלה עדיין פרופורציונלית למספרן
• עבור הפניות שחוצות כמה גיליונות, המקסימום השמור מתעלם מהגיליון, כך שנוסחאות בגיליונות הביניים עם פלטים עמוקים מגיעות לבדיקת העלים; התוצאות נשארות נכונות, רק הגיזום חלש יותר
• העץ עולה ארבעה מספרים שלמים לכל צומת נוסחה, כ-1.6 MB עבור 100,000 צמתים, וכל AddNode פוסל אותו, כך ששינויי טופולוגיה משלמים מיון מחדש מלא של O(n log n) בתוספת בניית עץ של O(n) בבניית הקשתות הבאה

אותה צורה ריבועית בשיבוט שמות של report-band

גרסה 2.383.2 תיקנה בעיה אחות ב-TXLSXDefinedNames.UniqueCloneName: כל שם מוגדר שהועתק התחיל מחדש את חיפוש הסיומת ב-_2, כך שהעתקות report-band חוזרות ונשנות גדלו ריבועית בחיפושי שמות. אינדקס השמות הממוקפים שומר כעת רמז סיומת לכל שם בסיס ולכל scope, ובודק מחדש את המועמד האחרון שהוחזר, כי ייתכן שהקורא לא יוסיף אותו בפועל; מחיקה, שינוי שם או שינוי scope של שם פוסלים את האינדקס, מה שמחזיר שמות של ראשון-פנוי. בסוויטת הרגרסיה, 1,024 שיבוטים סדרתיים זקוקים ל-5,088 חיפושי מועמדים וארבעה שמות בסיס מתחלפים זקוקים ל-5,039, בזמן שמינימומי מדד ה-report צנחו מכ-240 ms ל-18–20 ms. שער התזמון של report-band עצמו עדיין לא יציב — שלוש מתוך שש ריצות חרגו מהיחס 1.05 שלו בניסיון הראשון אחרי התיקון — והיסטוריית הביצועים שומרת את הכישלונות האלה ברשומה במקום לכייל את הסף עד שיעבור

אם היישום שלכם ב-Delphi או ב-C++Builder מייצר או מחשב מחדש חוברות Excel גדולות, רכיב ה-Excel של HotXLS עבור Delphi ו-C++Builder משלח את גרף התלויות המאונדקס הזה בתוך מנוע החישוב החוזר עבור שתי מחלקות החוברות שלו, הקלאסית וה-XLSX