HotXLS: index output ของ array formula ใน dependency graph

HotXLS 2.383.1 ไลบรารี Excel เนทีฟสำหรับ Delphi และ C++Builder สร้าง edge ของ dependency ระหว่างสูตรผ่าน output-interval index: node ของสูตรยังเรียงตาม anchor cell อยู่ และ segment tree ที่ถือแถว output ที่มากที่สุด (OutRow2) ของ subtree ทุกต้นทำให้ TXLSDepGraph.BuildEdges ข้ามก้อนสูตรทั้งก้อนที่ไม่มีทางไปถึง range ที่ถูกอ้างถึงได้ บนเวิร์กบุ๊ก Win32 ที่มีสูตรราว 100,000 ตัว การบังคับ recalc ลดจาก 18.488 วินาทีเหลือ 102–109 มิลลิวินาที

ไม่มีใคร profile dependency graph หรอก จนกระทั่ง batch job ที่เคยใช้เวลาแค่วินาทีเดียวเริ่มใช้ยี่สิบวินาที graph จะถูกสร้างใหม่ทุกครั้งที่ topology ของสูตรเปลี่ยน — Recalculate ครั้งแรกหลังโหลดหรือสร้างเวิร์กบุ๊ก หรือรอบใด ๆ หลัง graph ถูกทำให้เป็นโมฆะ — และใน trace ก่อนแก้ รอบแรกรอบเดียวใช้ไป 16,074 ms การประเมินผลไม่เคยเป็นปัญหา สิ่งที่เป็นคือการตัดสินว่าใครพึ่งพาใคร

ทำไมการ recalc สูตร 100,000 ตัวถึงใช้เวลา 18 วินาที

ตัวสร้าง edge ตัวเก่ามีต้นทุนเป็นกำลังสองตามจำนวนสูตรบนชีต สำหรับ dependency range ทุกช่วง BuildEdges binary search หา window ของ node ผู้เข้าชิง แล้วทดสอบทีละตัวด้วย RangeIntersectsOutput โดย window นั้นเริ่มตั้งแต่บนสุดของชีตที่ถูกอ้างถึงเลย key ของ node มาจาก XLSDepMakeKey ซึ่ง pack sheet index ตั้งแต่ bit 34 ขึ้นไป, แถวลง bits 14–33 และคอลัมน์ลง bits 0–13 lower bound (Sheet1, 0, 0) จึงหมายถึง "ทุกสูตรตั้งแต่แถว 1 ลงไปจนถึงก้นของ range ที่ถูกอ้างถึง"

// ก่อน 2.383.1 - TXLSDepGraph.BuildEdges, สำหรับ dependency range r ของ node d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // บนสุดของชีต
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...binary search สองครั้งบน FNodeOrder ให้ window [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard edge หรือ LookupScan edge, กันซ้ำผ่าน EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

เฟสเตอร์ที่เผยตัวนี้คือโมเดล cascade ธรรมดา: A2:A50000 แต่ละเซลล์บวกหนึ่งจากเซลล์ข้างบน และ B1:B50000 แต่ละเซลล์คูณสองเพื่อนบ้านในคอลัมน์ A การอ้างถึงแถว r จึงลากผู้เข้าชิงราว 2r ตัวผ่านการทดสอบสี่เหลี่ยม การสร้าง graph หนึ่งครั้งจึงทำการตรวจการตัดกันในระดับห้าพันล้านครั้ง — ประมาณการแบบคำนวณบนซองจดหมาย แต่มันเข้าคู่กับตัวเลข 18.5 วินาทีบนหน้าปัดพอดี ทุกการตรวจตอบ "ไม่" ยกเว้นหนึ่งหรือสองครั้ง

ทำไมตัวสร้าง edge ถึงเริ่มค้นที่แถวที่ถูกอ้างถึงไม่ได้

เพราะ array formula ที่ยึด anchor อยู่เหนือ range หนึ่งก็สามารถเป็นเจ้าของเซลล์ข้างใน range นั้นได้ TXLSDepNode แต่ละตัวบรรยายสี่เหลี่ยม output จาก anchor (Row, Col) ไปจนถึง (OutRow2, OutCol2) และ array formula แบบ CSE จะได้ node เดียวสำหรับสี่เหลี่ยมทั้งอัน ดังที่บทความเรื่องการ recalc แบบขั้นบันไดกับ dependency graph อธิบาย รากที่ยึดที่ A1 แล้วเติม A1:A10 ยังต้องได้รับ edge จากสูตรที่อ่านแค่ A5 อยู่ดี ถ้าเริ่ม binary search ที่แถว 5 edge นั้นจะหายไปเงียบ ๆ ซึ่งหมายถึงค่า cache ที่ค้างเก่าในรายงานที่ส่งออกไปแล้ว แทนที่จะแค่ช้า คำถามนี้จริง ๆ เป็นสองข้าง — anchor ที่ Row2 หรือเหนือกว่า, output ที่ไปถึงอย่างน้อย Row1 — และลำดับการเรียงตัวเดียวตอบสองครึ่งนี้ไม่ได้ ผลลัพธ์หลายเซลล์ก็โผล่ในเวิร์กบุ๊กสมัยใหม่ด้วย และบทความเรื่อง dynamic array spill formula อธิบายว่า spill range ทำงานอย่างไรใน HotXLS

segment tree ของแถว output สูงสุด

HotXLS เก็บการเรียงตาม anchor ไว้สำหรับ upper bound และเพิ่ม segment tree แบบ augmented สำหรับ lower bound BuildNodeIndex เรียง FNodeOrder ตาม node key เหมือนเดิม จากนั้น BuildMaxOutRowTree เติม FNodeMaxOutRow2 (จัดสรรที่สี่ entry ต่อ node) ด้วย OutRow2 ที่ใหญ่ที่สุดที่พบใต้ subtree แต่ละต้น QueryNodeTree ลงลึกเฉพาะภายใน key window และทิ้ง subtree ใดก็ตามที่แถว output สูงสุดของมันอยู่เหนือ FRanges[r].Row1 เพราะไม่มีสูตรในนั้นไปถึงแถวที่ถูกอ้างถึงได้ ใบที่รอดยังต้องผ่านการทดสอบ RangeIntersectsOutput เต็มรูปแบบ การเช็ก sheet span กับคอลัมน์จึงเป๊ะเหมือนเดิมทุกอย่าง

// 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
  // อยู่นอก key window หรือไม่มี output ใน subtree นี้ไปถึง 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);           // subtree ซ้ายก่อน
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // รักษาลำดับเดิม
end;

การเวียนเกิดแบบซ้ายก่อนขวาไม่ใช่เรื่องสไตล์ ใบที่รอดจะถูกเยี่ยมตามลำดับเป๊ะ ๆ กับที่ลูป while ตัวเก่าเคยเยี่ยม array Dependents กับ Precedents จึงถูกเติมตามลำดับเดิมและ topological order ก็ยัง deterministic กฎเดียวกันใช้กับ edge สองชนิด: hard edge ที่ถูกจดก่อนยังกด LookupScan edge ที่มาทีหลังของคู่เดียวกัน ส่วน scan edge ที่ถูกจดก่อน hard edge ก็คงที่ของมัน — ความต่างนี้แหละที่กันไม่ให้ lookup range ผลิตcircular reference ปลอม ต่อการอ้างอิงหนึ่งครั้ง ต้นทุนลดจากขนาดของ window เหลือ O((k + 1) log n) โดย k คือจำนวนสูตรที่ output จริง ๆ ไปถึงแถวที่ถูกอ้างถึง

output index การันตีอะไร และตรวจยืนยันอย่างไร

TXLSDepGraph ผลิต edge ชุดเดิมตามลำดับเดิม และ property ใหม่ EdgeCandidateChecks นับว่าการสร้างล่าสุดทดสอบสี่เหลี่ยม output ไปจริงกี่ตัว คำกล่าวอ้างนี้จึงวัดได้ ไม่ใช่คำโปรย regression test EdgeBuildDeepChainsCheckOneCandidatePerDependency สร้างห่วงโซ่ point reference ขนาด 1,024 กับ 100,000 node โดย insert ย้อนลำดับเพื่อบังคับการเรียงเชิงพื้นที่ แล้ว assert ว่าเช็กพอดี N − 1 ครั้ง — 99,999 สำหรับห่วงโซ่ยาว — พร้อมลำดับ precedent, dependent และ topological ที่คาดหวังของ node ทุกตัว เทสต์คู่สายครอบ array root ที่ insert สลับลำดับคนละ sheet span, reference แบบ hard กับ lookup-scan ที่ซ้ำกัน (10 ครั้ง พร้อมกฎการกดข้างบน) และการสร้างใหม่หลัง AddNode ซึ่งล้าง sort flag เพื่อให้ BuildEdges หรือ NodeIndexOf ครั้งถัดไปสร้าง tree ใหม่และรีเซ็ตตัวนับ แทนที่จะบวกสะสม

ผลที่วัดได้: จาก 18.5 วินาทีเหลือประมาณ 0.1 วินาที

trace ก่อนแก้ฝั่ง Win32 ที่เก็บไว้ใน performance baseline ของโปรเจกต์รุ่น 2.383.0 บันทึกการบังคับ recalc สองรอบได้ 18,488 ms กับ 19,578 ms หลังทำ index รันแบบโฟกัสต่อเนื่องสามรอบต่อสถาปัตยกรรม วัดได้ 102.332–109.429 ms บน Win32 และ 116.990–133.995 ms บน Win64 เร็วขึ้นราว 170 ถึง 180 เท่าบน Win32 ส่วน baseline ก่อนแก้บน Win64 ไม่เคยถูกบันทึก จึงไม่อ้างสิทธิ์ความเร็วบน Win64 รอบเดียวกันนี้ผ่าน gate เดิมที่บังคับให้การ audit แบบ read-only ของการคำนวณใหม่อยู่ใน 1.35 เท่าของการบังคับ recalc ตัวเลขสัมบูรณ์ขึ้นกับเครื่องกับโหลดของมัน จงทำซ้ำ workload นี้บนฮาร์ดแวร์ของคุณเองก่อนจะไปอ้างถึงมัน

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                     // dependent 50,000 ตัวในคอลัมน์ B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // การเรียกครั้งแรกสร้าง graph
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

output index หยุดช่วยตรงไหน

tree ตัดกิ่งเฉพาะด้านแถว และนั่นทิ้งขีดจำกัดสองสามข้อที่ควรรู้ไว้ก่อนคุณจะออกแบบโมเดลใหญ่มาก ๆ ยึดมันเป็นหลัก

• การพลาดที่คอลัมน์ยังจ่ายที่ใบอยู่: สูตร 2,626 ตัวที่เติม A100:Z200 ทุกตัวไปถึงแถว 100 การอ้างถึง AA100:AA200 จึงต้องทดสอบพวกมันทีละตัวก่อนปฏิเสธ
• reference กว้าง ๆ อย่าง range ทั้งคอลัมน์มี precedent เยอะจริง ๆ ตามธรรมชาติ index ตัดการตรวจที่เส็งเปล่า ไม่ได้ตัด edge ของจริง และการสร้าง edge พวกนั้นก็ยังแปรผันตามจำนวนของมัน
• สำหรับ reference ที่กินหลายชีต ค่าสูงสุดที่เก็บไว้ไม่สนใจชีต สูตรบนชีตระหว่างกลางที่มี output ลึก ๆ จึงรอดไปถึงการทดสอบที่ใบ ผลลัพธ์ยังถูกต้อง เพียงแต่การตัดกิ่งอ่อนลง
• tree กินจำนวนเต็มสี่ตัวต่อ node สูตร ประมาณ 1.6 MB สำหรับ 100,000 node และ AddNode ใด ๆ ก็ทำให้เป็นโมฆะ การเปลี่ยน topology จึงจ่ายการเรียงใหม่เต็มรูปแบบ O(n log n) บวกการสร้าง tree O(n) ที่การสร้าง edge ครั้งถัดไป

รูปทรงกำลังสองแบบเดิมในการ clone ชื่อ report band

รุ่น 2.383.2 แก้ปัญหาพี่น้องใน TXLSXDefinedNames.UniqueCloneName: defined name ที่ถูก copy ทุกตัวเริ่มค้น suffix ใหม่ที่ _2 การ copy report band ซ้ำ ๆ จึงโตเป็นกำลังสองในการค้นหาชื่อ index ของ scoped name ตอนนี้เก็บ suffix hint ต่อชื่อฐาน ต่อ scope แล้วเช็กซ้ำผู้เข้าชิงตัวสุดท้ายที่คืนไป เพราะผู้เรียกอาจไม่ได้เพิ่มมันจริง ๆ การลบ เปลี่ยนชื่อ หรือย้าย scope ของชื่อจะทำ index เป็นโมฆะ ซึ่งคืนการตั้งชื่อแบบเลือกตัวแรกที่ว่าง ในชุด regression การ clone ต่อเนื่อง 1,024 ตัวต้องค้นผู้เข้าชิง 5,088 ครั้ง ชื่อฐานสลับกันสี่ตัวต้องการ 5,039 ครั้ง ขณะที่ค่าต่ำสุดของ benchmark รายงานลดจากราว 240 ms เหลือ 18–20 ms gate จับเวลา report band เองก็ยังไม่นิ่ง — รอบแรกหลังแก้ หกครั้งมีสามครั้งเกิน ratio 1.05 — และประวัติ performance ก็เก็บความล้มเหลวพวกนั้นไว้ตามจริง แทนที่จะไปหมุนเกณฑ์จนกว่ามันจะผ่าน

ถ้าแอปพลิเคชัน Delphi หรือ C++Builder ของคุณสร้างหรือคำนวณเวิร์กบุ๊ก Excel ขนาดใหญ่ HotXLS Excel component สำหรับ Delphi และ C++Builder ส่ง dependency graph แบบ index นี้มาใน recalculation engine ของทั้งคลาสเวิร์กบุ๊กคลาสสิกและ XLSX