Dependency graph HotXLS: đánh chỉ mục output array formula

HotXLS 2.383.1, thư viện Excel native cho Delphi và C++Builder, dựng các cạnh phụ thuộc công thức qua một chỉ mục khoảng output: các node công thức vẫn được sắp theo ô anchor, và một segment tree giữ dòng output lớn nhất (OutRow2) của mỗi subtree cho phép TXLSDepGraph.BuildEdges bỏ qua cả khối công thức không thể với tới một range được tham chiếu. Trên một workbook Win32 với cỡ 100.000 công thức, recalc cưỡng bức rơi từ 18,488 giây xuống 102–109 mili giây

Chẳng ai profile dependency graph cho tới khi một batch job từng tốn một giây bắt đầu tốn hai mươi. Graph được dựng lại bất cứ khi nào topology công thức đổi — lần Recalculate đầu sau khi nạp hay sinh một workbook, hoặc bất kỳ lượt nào sau khi graph bị vô hiệu — và trong trace trước khi sửa, riêng lượt đầu tiên đã tốn 16,074 ms. Phần đánh giá chưa bao giờ là vấn đề; phần quyết định ai phụ thuộc vào ai mới là

Vì sao recalc 100.000 công thức tốn 18 giây?

Builder cạnh cũ có độ phức tạp bậc hai theo số công thức trên một sheet. Với mọi dependency range, BuildEdges tìm nhị phân một cửa sổ các node ứng viên rồi thử từng cái bằng RangeIntersectsOutput, và cửa sổ đó khởi đầu ngay từ đỉnh của sheet được tham chiếu. Key của node đến từ XLSDepMakeKey, gói chỉ mục sheet từ bit 34 trở lên, dòng vào bit 14–33, và cột vào bit 0–13, nên cận dưới (Sheet1, 0, 0) nghĩa là “mọi công thức từ dòng 1 xuống đáy của range được tham chiếu”

// Trước 2.383.1 - TXLSDepGraph.BuildEdges, với dependency range r của node d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // đỉnh của sheet
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...hai phép tìm kiếm nhị phân trên FNodeOrder cho ra cửa sổ [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard edge hay LookupScan edge, khử trùng lặp qua EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Fixture hiệu năng phơi bày chuyện này là một model lan truyền tầm thường: A2:A50000 mỗi ô cộng thêm một vào ô phía trên, và B1:B50000 mỗi ô nhân đôi hàng xóm ở cột A. Một tham chiếu tới dòng r vì thế kéo cỡ 2r ứng viên đi qua phép thử hình chữ nhật, nên một lần dựng graph thực hiện vào khoảng năm tỷ phép kiểm giao — ước lượng vớ vỉ trên giấy nháp, nhưng nó khớp với 18,5 giây trên đồng hồ. Mọi phép kiểm đều trả lời “không” ngoài một hay hai cái

Vì sao builder cạnh không thể bắt đầu tìm kiếm tại dòng được tham chiếu?

Vì một array formula neo phía trên một range có thể sở hữu các ô nằm bên trong nó. Mỗi TXLSDepNode mô tả một hình chữ nhật output từ anchor (Row, Col) tới (OutRow2, OutCol2), và một CSE array formula nhận đúng một node cho toàn bộ hình chữ nhật của nó, như bài về recalc tăng dần và dependency graph đã giải thích. Một root neo tại A1 phủ A1:A10 vẫn phải nhận một cạnh từ một công thức chỉ đọc A5; bắt đầu tìm nhị phân tại dòng 5 thì cạnh đó lặng lẽ biến mất, nghĩa là một giá trị cache cũ nằm trong báo cáo đã giao thay vì một báo cáo chậm. Truy vấn thật ra là hai phía — anchor tại hoặc trước Row2, output với tới ít nhất Row1 — và một thứ tự sắp duy nhất không thể trả lời cả hai nửa. Kết quả nhiều ô cũng xuất hiện trong các workbook hiện đại, và bài về dynamic array spill formula trình bày các range spill hành xử thế nào trong HotXLS

Một segment tree các dòng output cực đại

HotXLS giữ phép sắp theo anchor cho cận trên và thêm một segment tree có bổ sung cho cận dưới. BuildNodeIndex sắp FNodeOrder theo key node như cũ, rồi BuildMaxOutRowTree đổ FNodeMaxOutRow2 (cấp phát bốn phần tử mỗi node) bằng OutRow2 lớn nhất tìm thấy dưới mỗi subtree. QueryNodeTree chỉ đi xuống bên trong cửa sổ key và bỏ rơi bất kỳ subtree nào có dòng output cực đại nằm trên FRanges[r].Row1, vì chẳng công thức nào trong đó với tới được các dòng được tham chiếu. Các lá sống sót vẫn đi qua phép thử RangeIntersectsOutput đầy đủ, nên khoảng sheet và cột được kiểm đúng như trước

// TXLSDepGraph.BuildNodeIndex / BuildEdges từ 2.383.1 (rút gọn nhẹ)
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
  // ngoài cửa sổ key, hoặc không output nào trong subtree này với tới 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
      // không đổi: khử EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // subtree trái trước
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // giữ thứ tự cũ
end;

Đệ quy trái-trước-phải không phải một lựa chọn phong cách. Các lá sống sót được viếng thăm đúng theo thứ tự mà vòng lặp while cũ từng làm, nên các mảng Dependents và Precedents được đổ theo cùng một chuỗi và thứ tự topo vẫn tất định. Điều tương tự giữ cho hai loại cạnh: một hard edge được ghi trước vẫn khử một LookupScan edge đến sau cho cùng một cặp, còn một scan edge được ghi trước hard edge thì giữ nguyên chỗ của nó — đúng sự phân biệt ngăn các lookup range sinh ra circular reference ảo. Theo mỗi tham chiếu, chi phí rơi từ kích thước cửa sổ xuống O((k + 1) log n), với k là số công thức mà output thật sự với tới các dòng được tham chiếu

Chỉ mục output bảo đảm gì, và được kiểm chứng ra sao?

TXLSDepGraph cho ra cùng các cạnh theo cùng thứ tự như trước, và thuộc tính mới EdgeCandidateChecks đếm xem lần dựng gần nhất thật sự thử bao nhiêu hình chữ nhật output, nên lời khẳng định đo lường được chứ không phải khẩu hiệu. Test hồi quy EdgeBuildDeepChainsCheckOneCandidatePerDependency dựng các chuỗi tham chiếu điểm 1.024 và 100.000 node, chèn theo thứ tự ngược để ép phép sắp không gian, và khẳng định đúng N − 1 phép kiểm — 99.999 cho chuỗi dài — cùng thứ tự precedent, dependent và topo kỳ vọng cho mọi node. Các test đồng hành phủ root array được chèn lộn xộn vắt qua nhiều sheet span, tham chiếu hard và lookup-scan trùng nhau (10 phép kiểm, với các luật khử nêu trên), và một lần dựng lại sau AddNode, cái xóa cờ sắp để lần BuildEdges hay NodeIndexOf kế tiếp dựng lại tree và reset bộ đếm thay vì cộng dồn

Kết quả đo được: từ 18,5 giây xuống cỡ 0,1 giây

Trace Win32 trước khi sửa, được giữ lại trong baseline hiệu năng của dự án cho phiên bản 2.383.0, ghi nhận hai lần recalc cưỡng bức 18.488 ms và 19.578 ms. Sau khi đánh chỉ mục, ba lượt chạy focus nối tiếp mỗi kiến trúc đo được 102,332–109,429 ms trên Win32 và 116,990–133,995 ms trên Win64, nhanh hơn cỡ 170 đến 180 lần trên Win32; không có baseline Win64 trước khi sửa nào được ghi lại, nên không có lời khẳng định tăng tốc Win64 nào. Các lượt chạy đó vượt gate hiện có giữ một audit recalc chỉ đọc trong vòng 1,35 lần một recalc cưỡng bức. Số tuyệt đối phụ thuộc máy và tải của nó, nên hãy tái hiện workload trên phần cứng của bạn trước khi trích dẫn

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                     // chuỗi 49.999 mắt xích trong cột A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 dependent trong cột B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // lần gọi đầu dựng graph
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Chỉ mục output ngừng giúp ở đâu?

Tree chỉ tỉa theo dòng, và điều đó để lại vài giới hạn trung thực đáng biết trước khi bạn thiết kế một model rất lớn xoay quanh nó

• Trượt cột vẫn phải trả giá tại các lá: 2.626 công thức phủ A100:Z200 đều với tới dòng 100, nên một tham chiếu tới AA100:AA200 phải thử từng cái trước khi từ chối
• Các tham chiếu rộng như range nguyên cột thật sự có rất nhiều precedent; chỉ mục xóa các phép kiểm lãng phí chứ không xóa cạnh thật, và dựng những cạnh đó vẫn tỉ lệ với số của chúng
• Với các tham chiếu vắt qua nhiều sheet, cực đại được lưu bỏ qua sheet, nên các công thức trên sheet trung gian có output sâu vẫn lọt tới phép thử lá; kết quả vẫn đúng, chỉ có việc tỉa yếu hơn
• Tree tốn bốn số nguyên mỗi node công thức, cỡ 1,6 MB cho 100.000 node, và bất kỳ AddNode nào cũng vô hiệu nó, nên thay đổi topology trả giá một lần sắp lại O(n log n) trọn vẹn cộng một lần dựng tree O(n) ở lần dựng cạnh kế tiếp

Cùng hình dáng bậc hai trong việc clone tên report-band

Phiên bản 2.383.2 sửa một vấn đề anh em trong TXLSXDefinedNames.UniqueCloneName: mọi defined name được sao chép đều khởi động lại việc tìm hậu tố tại _2, nên các bản sao report-band lặp lại phình theo bậc hai về phép tra tên. Chỉ mục tên có scope giờ giữ một gợi ý hậu tố theo từng base name, từng scope và kiểm lại ứng viên được trả về cuối cùng, vì bên gọi có thể không add nó thật; xóa, đổi tên hay đổi scope một tên làm vô hiệu chỉ mục, trả lại kiểu đặt tên lấy cái đầu còn trống. Trong bộ test hồi quy, 1.024 clone nối tiếp cần 5.088 phép tra ứng viên và bốn base name xen kẽ cần 5.039, trong khi cực tiểu benchmark report rơi từ cỡ 240 ms xuống 18–20 ms. Bản thân gate định thời report-band vẫn chưa ổn định — ba trong sáu lượt chạy vượt tỉ lệ 1,05 của nó trong lần thử đầu sau khi sửa — và lịch sử hiệu năng giữ những lần thất bại đó trên giấy chứ không tinh chỉnh ngưỡng cho tới khi nó qua

Nếu ứng dụng Delphi hay C++Builder của bạn sinh hay recalc các workbook Excel lớn, HotXLS Excel component cho Delphi và C++Builder mang dependency graph có chỉ mục này trong engine recalc cho cả hai lớp workbook classic lẫn XLSX