گراف وابستگی HotXLS: اندیس‌گذاری خروجی‌های array formula

HotXLS 2.383.1، کتابخانهٔ بومی Excel برای Delphi و C++Builder، یال‌های وابستگی فرمول‌ها را از طریق یک output-interval index می‌سازد: گره‌های فرمول بر اساس سلول لنگر مرتب می‌مانند، و یک segment tree که بزرگ‌ترین ردیف خروجی (OutRow2) هر زیردرخت را نگه می‌دارد به TXLSDepGraph.BuildEdges اجازه می‌دهد کل بلوک‌های فرمولی را که نمی‌توانند به بازهٔ ارجاع‌شده برسند از قلم بیندازد. روی یک ورک‌بوک Win32 با حدود 100,000 فرمول، recalculation اجباری از 18.488 ثانیه به 102–109 میلی‌ثانیه افت کرد

هیچ‌کس گراف وابستگی را profile نمی‌کند تا وقتی که یک batch job که قبلاً یک ثانیه طول می‌کشید بیست ثانیه‌ای شود. گراف هر بار که توپولوژی فرمول‌ها عوض شود از نو ساخته می‌شود — اولین Recalculate بعد از لود یا تولید ورک‌بوک، یا هر پاس بعد از invalid شدن گراف — و در trace قبل از fix، همین پاس اول به‌تنهایی 16074 میلی‌ثانیه طول کشید. ارزیابی هرگز مشکل نبود؛ تصمیم‌گیری اینکه چه کسی به چه کسی وابسته است مشکل بود

چرا recalculation کردن 100,000 فرمول 18 ثانیه طول می‌کشید؟

edge builder قدیمی به تعداد فرمول‌های یک sheet درجهٔ دو بود. برای هر بازهٔ وابستگی، BuildEdges یک پنجرهٔ گره‌های کاندید را binary search می‌کرد و بعد هر کدام را با RangeIntersectsOutput می‌آزمود، و آن پنجره از همان بالای sheet ارجاع‌شده شروع می‌شد. کلیدهای گره از XLSDepMakeKey می‌آیند که اندیس sheet را از بیت 34 به بالا، ردیف را در بیت‌های 14 تا 33 و ستون را در بیت‌های 0 تا 13 می‌چیند، پس کران پایین (Sheet1, 0, 0) یعنی «هر فرمولی از ردیف 1 تا انتهای بازهٔ ارجاع‌شده»

// قبل از 2.383.1 - TXLSDepGraph.BuildEdges، برای بازهٔ وابستگی r از گره d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // بالای sheet
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...دو binary search روی FNodeOrder پنجرهٔ [i, Lo) را می‌سازند...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // یال hard یا یال LookupScan، با dedup از طریق EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

fixture کارایی که این را لو داد یک مدل آبشاری معمولی است: A2:A50000 هر کدام یکی به سلول بالای خودشان اضافه می‌کنند، و B1:B50000 هر کدام همسایهٔ ستون A را دو برابر می‌کنند. پس ارجاعی به ردیف r حدود 2r کاندید را از آزمون مستطیل عبور می‌داد، بنابراین یک build تکی گراف در مرتبهٔ پنج میلیارد بررسی تقاطع انجام می‌داد — تخمین سرانگشتی، ولی با 18.5 ثانیه روی ساعت جور درمی‌آید. هر بررسی می‌گفت «نه» جز یکی دو تا

چرا edge builder نمی‌تواند جستجو را از ردیف ارجاع‌شده شروع کند؟

چون یک array formula که بالای یک بازه لنگر شده می‌تواند سلول‌هایی داخلش را مالک باشد. هر TXLSDepNode یک مستطیل خروجی را از لنگر خودش (Row، Col) تا (OutRow2، OutCol2) توصیف می‌کند، و یک array formula از نوع CSE برای کل مستطیلش یک گره می‌گیرد، همان‌طور که مقالهٔ recalculation افزایشی و گراف وابستگی توضیح می‌دهد. ریشه‌ای که در A1 لنگر شده و A1:A10 را پر می‌کند باز هم باید یالی از فرمولی که فقط A5 را می‌خواند بگیرد؛ binary search را از ردیف 5 شروع کنید و آن یال بی‌سروصدا گم می‌شود، که یعنی یک مقدار کش‌شدهٔ کهنه در گزارشی که ارسال می‌شود به‌جای یک گزارش کند. کوئری واقعاً دو طرفه است — لنگر در یا قبل از Row2، خروجی که دست‌کم به Row1 برسد — و یک ترتیب مرتب‌سازی تکی نمی‌تواند هر دو نیمه را جواب دهد. نتایج چند-سلولی در ورک‌بوک‌های مدرن هم پیدا می‌شوند، و مقالهٔ فرمول‌های dynamic array spill پوشش می‌دهد بازه‌های spilled در HotXLS چطور رفتار می‌کنند

یک segment tree از بیشترین ردیف‌های خروجی

HotXLS مرتب‌سازی لنگر را برای کران بالا نگه می‌دارد و برای کران پایین یک segment tree تقویت‌شده اضافه می‌کند. BuildNodeIndex FNodeOrder را همان‌طور که قبلاً با کلید گره مرتب می‌کرد، بعد BuildMaxOutRowTree مقدار FNodeMaxOutRow2 (به اندازهٔ چهار مدخل به‌ازای هر گره تخصیص‌یافته) را با بزرگ‌ترین OutRow2 پیدا شده زیر هر زیردرخت پر می‌کند. QueryNodeTree فقط داخل پنجرهٔ کلید پایین می‌رود و هر زیردرختی که بیشترین ردیف خروجی‌اش بالای FRanges[r].Row1 باشد را رها می‌کند، چون هیچ فرمولی داخلش نمی‌تواند به ردیف‌های ارجاع‌شده برسد. برگ‌هایی که زنده می‌مانند همچنان آزمون کامل RangeIntersectsOutput را می‌روند، پس spanهای sheet و ستون‌ها دقیقاً مثل قبل چک می‌شوند

// 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 همان یال‌های قبلی را در همان ترتیب تولید می‌کند، و property جدید EdgeCandidateChecks می‌شمارد که آخرین build واقعاً چند مستطیل خروجی را آزموده، پس ادعا قابل اندازه‌گیری است نه شعاری. تست رگرسیون EdgeBuildDeepChainsCheckOneCandidatePerDependency زنجیره‌های ارجاع نقطه‌ای با 1024 و 100,000 گره می‌سازد، به ترتیب معکوس درج می‌کند تا مرتب‌سازی فضایی تحمیل شود، و دقیقاً N منهای 1 بررسی را اظهار می‌کند — 99,999 برای زنجیرهٔ بلند — به‌علاوهٔ ترتیب مورد انتظار precedent و dependent و توپولوژیک برای هر گره. تست‌های همراه زنجیره‌های ریشهٔ array را که بیرون از ترتیب در spanهای sheet درج شده‌اند، ارجاع‌های تکراری hard و lookup-scan را (10 بررسی، با قواعد سرکوب بالا)، و rebuild بعد از AddNode را پوشش می‌دهند، که پرچم مرتب‌سازی را پاک می‌کند تا BuildEdges یا NodeIndexOf بعدی درخت را از نو بسازد و شمارنده را reset کند نه اینکه رویش جمع بزند

نتایج اندازه‌گیری‌شده: از 18.5 ثانیه به حدود 0.1 ثانیه

trace قبل از fix روی Win32، که در baseline کارایی پروژه برای نسخهٔ 2.383.0 نگه داشته شده، دو recalculation اجباری 18488 و 19578 میلی‌ثانیه‌ای ثبت کرده بود. بعد از اندیس‌گذاری، سه اجرای سریالی متمرکز به‌ازای هر معماری روی Win32 بین 102.332 تا 109.429 میلی‌ثانیه و روی Win64 بین 116.990 تا 133.995 میلی‌ثانیه اندازه گرفت، یعنی حدود 170 تا 180 برابر سریع‌تر روی Win32؛ baseline قبل از fix روی Win64 ثبت نشده بود، پس ادعای speedup روی Win64 نمی‌کنیم. همان اجراها گیت موجودی را که ممیزی recalculation فقط‌خواندنی را در 1.35 برابر یک recalculation اجباری نگه می‌دارد پاس کردند. اعداد مطلق به ماشین و بارش وابسته‌اند، پس قبل از نقل کردنشان روی سخت‌افزار خودتان بازتولیدشان کنید

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;

اندیس خروجی کجا دیگر کمک نمی‌کند؟

درخت فقط روی ردیف‌ها هرس می‌کند، و این چند سقف صادقانه‌ای باقی می‌گذارد که ارزش دارد قبل از طراحی یک مدل خیلی بزرگ روی آن بدانید

• از دست رفتن ستون‌ها همچنان در برگ‌ها پرداخت می‌شود: 2626 فرمولی که A100:Z200 را پر می‌کنند همه به ردیف 100 می‌رسند، پس ارجاعی به AA100:AA200 قبل از رد کردن هر کدامشان را می‌آزماید
• ارجاع‌های پهنی مثل بازه‌های تمام-ستون واقعاً precedentهای زیادی دارند؛ اندیس بررسی‌های هدررفته را حذف می‌کند نه یال‌های واقعی را، و ساختن آن یال‌ها همچنان متناسب با تعدادشان است
• برای ارجاع‌هایی که چند sheet را در بر می‌گیرند، بیشینهٔ ذخیره‌شده sheet را نادیده می‌گیرد، پس فرمول‌های sheetهای واسط با خروجی‌های عمیق به آزمون برگ می‌رسند؛ نتایج درست می‌مانند، فقط هرس ضعیف‌تر است
• درخت به‌ازای هر گره فرمول چهار عدد صحیح هزینه دارد، حدود 1.6 مگابایت برای 100,000 گره، و هر AddNode آن را نامعتبر می‌کند، پس تغییر توپولوژی یک مرتب‌سازی کامل O(n log n) به‌علاوهٔ یک ساخت درخت O(n) را در build بعدی یال پرداخت می‌کند

همان شکل درجهٔ دو در clone کردن نام‌های report-band

نسخهٔ 2.383.2 یک مشکل خواهر را در TXLSXDefinedNames.UniqueCloneName درست کرد: هر defined name کپی‌شده جستجوی پسوندش را از _2 از نو شروع می‌کرد، پس کپی‌های تکراری report-band در lookupهای نام به‌صورت درجهٔ دو رشد می‌کردند. اندیس نام اسکوپ‌دار حالا یک hint پسوند به‌ازای هر نام پایه و هر اسکوپ نگه می‌دارد و آخرین کاندید برگردانده‌شده را دوباره چک می‌کند، چون ممکن است فراخوان واقعاً آن را اضافه نکند؛ حذف یا تغییر نام یا تغییر اسکوپ یک نام اندیس را نامعتبر می‌کند، که نام‌گذاری اولین-موجود را برمی‌گرداند. در مجموعهٔ رگرسیون، 1024 clone متوالی به 5088 lookup کاندید و چهار نام پایه متناوب به 5039 نیاز دارند، در حالی که کمینه‌های benchmark گزارش از حدود 240 میلی‌ثانیه به 18–20 میلی‌ثانیه افت کرد. خود گیت زمان‌بندی report-band هنوز پایدار نیست — سه اجرا از شش اجرا در اولین تلاش بعد از fix از نسبت 1.05 عبور کردند — و تاریخ کارایی آن شکست‌ها را روی پرونده نگه می‌دارد به‌جای اینکه آستانه را تا پاس شدن تنظیم کند

اگر اپلیکیشن Delphi یا C++Builder شما ورک‌بوک‌های بزرگ اکسل تولید یا recalculation می‌کند، کامپوننت Excel HotXLS برای Delphi و C++Builder این گراف وابستگی اندیسی را در موتور recalculation هر دو کلاس ورک‌بوک کلاسیک و XLSX خودش ارسال می‌کند