HotXLS 의존성 그래프와 배열 수식 출력 인덱싱

Delphi와 C++Builder용 네이티브 Excel 라이브러리인 HotXLS 2.383.1은 출력 구간 인덱스로 수식 의존성 엣지를 만듭니다. 수식 노드는 앵커 셀 기준 정렬 상태를 유지하고, 모든 서브트리의 최대 출력 행(OutRow2)을 담은 세그먼트 트리가 참조 범위에 닿을 수 없는 수식 블록 전체를 TXLSDepGraph.BuildEdges가 건너뛰게 합니다. 수식 10만 개쯤 되는 Win32 통합 문서에서 강제 재계산은 18.488초에서 102–109밀리초로 떨어졌습니다

1초 걸리던 배치 작업이 20초를 잡아먹기 시작하기 전까지는 아무도 의존성 그래프를 프로파일하지 않습니다. 그래프는 수식 토폴로지가 바뀔 때마다 다시 만들어집니다. 통합 문서를 로드하거나 생성한 뒤 첫 Recalculate, 또는 그래프가 무효화된 뒤의 아무 패스가 그렇습니다. 수정 전 트레이스에서 첫 패스 하나가 16,074ms를 잡아먹었습니다. 평가는 원래 문제가 아니었고, 누가 누구에게 의존하는지 판정하는 일이 문제였습니다

수식 10만 개 재계산에 왜 18초나 걸렸을까요?

예전 엣지 빌더는 시트의 수식 개수에 대해 2차 복잡도였습니다. 의존성 범위마다 BuildEdges는 후보 노드 창을 이진 탐색한 다음 각각을 RangeIntersectsOutput으로 검사했는데, 그 창은 참조된 시트의 맨 위에서 시작했습니다. 노드 키는 XLSDepMakeKey에서 나오는데, 시트 인덱스를 비트 34 이상에, 행을 비트 14–33에, 열을 비트 0–13에 패킹하므로 하한 (Sheet1, 0, 0)은 "1행부터 참조 범위 끝까지의 모든 수식"을 뜻했습니다

// 2.383.1 이전 - TXLSDepGraph.BuildEdges, 노드 d의 의존성 범위 r에 대해
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;

이것을 드러낸 성능 픽스처는 평범한 캐스케이딩 모델입니다. A2:A50000은 각각 위 셀에 1을 더하고, B1:B50000은 각각 A열 이웃을 두 배로 만듭니다. 행 r에 대한 참조는 따라서 약 2r개의 후보를 사각형 검사에 끌어들였고, 그래프 빌드 한 번이 대략 50억 번의 교차 검사를 수행한 셈입니다. 간이 추정이지만 스톱워치의 18.5초와 들어맞습니다. 교차 검사는 한두 번을 빼면 전부 "교차 없음"이었습니다

엣지 빌더는 검색을 참조된 행에서 시작할 수 없을까요?

범위보다 위에 앵커된 배열 수식이 그 안의 셀을 소유할 수 있기 때문입니다. 각 TXLSDepNode는 앵커(Row, Col)부터 (OutRow2, OutCol2)까지의 출력 사각형을 기술하고, CSE 배열 수식은 자기 사각형 전체에 노드 하나를 받습니다. 증분 재계산과 의존성 그래프 글이 설명하듯이요. A1에 앵커되어 A1:A10을 채우는 루트는 A5만 읽는 수식에서 엣지를 받아야 합니다. 이진 탐색을 5행에서 시작하면 그 엣지가 조용히 사라지는데, 느린 대신 배포된 보고서에 낡은 캐시 값이 남는다는 뜻입니다. 질의는 실은 양면적입니다. 앵커는 Row2 이전이어야 하고 출력은 적어도 Row1에 닿아야 합니다. 하나의 정렬 순서로는 두 절반에 모두 답할 수 없습니다. 다중 셀 결과는 현대 통합 문서에도 나타나며, 동적 배열 spill 수식 글이 HotXLS에서 spill 범위가 어떻게 동작하는지 다룹니다

최대 출력 행의 세그먼트 트리

HotXLS는 상한을 위해 앵커 정렬을 유지하고 하한을 위해 증강 세그먼트 트리를 더합니다. 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 엣지를 여전히 억제하고, hard 엣지보다 먼저 기록된 scan 엣지는 제 자리를 유지합니다. 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초로

버전 2.383.0의 프로젝트 성능 베이스라인에 남아 있는 수정 전 Win32 트레이스는 18,488ms와 19,578ms의 강제 재계산 두 번을 기록했습니다. 인덱싱 후에는 아키텍처당 세 번의 직렬 focused 런이 Win32에서 102.332–109.429ms, Win64에서 116.990–133.995ms를 측정했고, Win32에서 대략 170배에서 180배 빨라졌습니다. 수정 전 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                     // A열의 49,999 링크 체인
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // B열의 50,000개 dependent
      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;

출력 인덱스는 어디서부터 도움이 안 될까요?

트리는 행으로만 가지치기를 하므로, 아주 큰 모델을 이것 위에 설계하기 전에 알아 둘 만한 정직한 한계가 몇 개 남습니다

• 열 미스는 여전히 잎에서 지불됩니다. A100:Z200을 채우는 2,626개 수식은 전부 100행에 닿으므로, AA100:AA200 참조는 각각을 거부하기 전에 검사합니다
• 열 전체 범위 같은 넓은 참조는 실제로 precedent가 많습니다. 인덱스는 낭비되는 검사를 없애는 것이지 진짜 엣지를 없애는 게 아니고, 그 엣지를 만드는 비용은 여전히 개수에 비례합니다
• 여러 시트에 걸친 참조의 경우 저장된 최댓값은 시트를 무시하므로, 출력이 깊은 중간 시트의 수식은 잎 검사까지 도달합니다. 결과는 올바르고 가지치기만 약해집니다
• 트리는 수식 노드당 정수 네 개, 100,000노드면 약 1.6MB가 들고, AddNode가 하나라도 있으면 무효화됩니다. 토폴로지 변경은 다음 엣지 빌드에서 완전한 O(n log n) 재정렬과 O(n) 트리 빌드를 치릅니다

report-band 이름 복제에도 같은 2차 형태

버전 2.383.2는 TXLSXDefinedNames.UniqueCloneName의 형제 문제를 고쳤습니다. 복사된 정의 이름마다 접미사 검색이 _2에서 다시 시작되어, report-band 사본을 반복하면 이름 조회가 2차적으로 불어났습니다. 스코프 이름 인덱스는 이제 base 이름별, 스코프별 접미사 힌트를 유지하고 마지막으로 반환된 후보를 다시 검사합니다. 호출자가 실제로 추가하지 않을 수도 있기 때문입니다. 이름을 삭제하거나 이름을 바꾸거나 스코프를 옮기면 인덱스가 무효화되어 first-available 네이밍으로 돌아갑니다. 회귀 스위트에서 순차 클론 1,024개는 후보 조회 5,088회, 번갈아 나오는 base 이름 네 개는 5,039회가 필요하고, 보고서 벤치마크 최솟값은 대략 240ms에서 18–20ms로 떨어졌습니다. report-band 타이밍 게이트 자체는 여전히 불안정합니다. 수정 후 첫 시도에서 여섯 런 중 세 런이 1.05 비율을 넘었습니다. 성능 이력은 임계값이 통과할 때까지 조정하는 대신 그 실패들을 기록으로 남깁니다

Delphi나 C++Builder 애플리케이션이 큰 Excel 통합 문서를 생성하거나 재계산한다면, Delphi 및 C++Builder용 HotXLS Excel 컴포넌트의 재계산 엔진이 이 인덱싱된 의존성 그래프를 클래식과 XLSX 통합 문서 클래스 양쪽에 실어 제공합니다