Grafo de dependências do HotXLS: indexando saídas de matriz

O HotXLS 2.383.1, biblioteca Excel nativa para Delphi e C++Builder, constrói arestas de dependência de fórmulas por meio de um índice de intervalos de saída: os nós de fórmula continuam ordenados pela célula âncora, e uma segment tree que guarda a maior linha de saída (OutRow2) de cada subárvore deixa o TXLSDepGraph.BuildEdges pular blocos inteiros de fórmulas que não podem alcançar um intervalo referenciado. Numa pasta de trabalho Win32 com cerca de 100.000 fórmulas, o recálculo forçado caiu de 18,488 segundos para 102–109 milissegundos

Ninguém profile o grafo de dependências até um job em lote que levava um segundo começar a levar vinte. O grafo é reconstruído sempre que a topologia de fórmulas muda — o primeiro Recalculate depois de carregar ou gerar uma pasta de trabalho, ou qualquer passada depois de o grafo ter sido invalidado — e no trace de antes da correção só essa primeira passada levava 16.074 ms. Avaliar nunca foi o problema; decidir quem depende de quem é que era

Por que recalcular 100.000 fórmulas levava 18 segundos?

O construtor de arestas antigo era quadrático no número de fórmulas de uma planilha. Para cada intervalo de dependência, o BuildEdges fazia busca binária numa janela de nós candidatos e então testava cada um com RangeIntersectsOutput, e essa janela começava no topo da planilha referenciada. As chaves dos nós vêm do XLSDepMakeKey, que empacota o índice da planilha a partir do bit 34 para cima, a linha nos bits 14–33, e a coluna nos bits 0–13, então o limite inferior (Sheet1, 0, 0) significava "toda fórmula da linha 1 até o fim do intervalo referenciado"

// Antes da 2.383.1 - TXLSDepGraph.BuildEdges, para o intervalo de dependência r do nó d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // topo da planilha
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...duas buscas binárias sobre FNodeOrder produzem a janela [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // aresta dura ou aresta LookupScan, deduplicada via EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

O fixture de performance que expôs isso é um modelo em cascata banal: A2:A50000 cada uma soma um à célula de cima, e B1:B50000 cada uma dobra a vizinha na coluna A. Uma referência à linha r portanto arrastava cerca de 2r candidatos pelo teste de retângulo, então uma única construção do grafo fazia na casa de cinco bilhões de checagens de interseção — uma estimativa de guardanapo, mas que bate com os 18,5 segundos no relógio. Toda checagem dizia "não", exceto uma ou duas

Por que o construtor de arestas não pode começar a busca na linha referenciada?

Porque uma fórmula de matriz ancorada acima de um intervalo pode ser dona de células dentro dele. Cada TXLSDepNode descreve um retângulo de saída da âncora dele (Row, Col) até (OutRow2, OutCol2), e uma fórmula de matriz CSE ganha um nó para o retângulo inteiro, como explica o artigo sobre recálculo incremental e o grafo de dependências. Uma raiz ancorada em A1 que preenche A1:A10 ainda precisa receber uma aresta de uma fórmula que lê só A5; comece a busca binária na linha 5 e essa aresta desaparece em silêncio, o que significa um valor em cache obsoleto num relatório entregue em vez de um relatório lento. A consulta é realmente de dois lados — âncora em ou antes de Row2, saída alcançando pelo menos Row1 — e uma única ordem de ordenação não responde às duas metades. Resultados de múltiplas células aparecem em pastas de trabalho modernas também, e o artigo sobre fórmulas de spill de dynamic array cobre como intervalos spilled se comportam no HotXLS

Uma segment tree de linhas de saída máximas

O HotXLS mantém a ordenação por âncora para o limite superior e adiciona uma segment tree aumentada para o limite inferior. O BuildNodeIndex ordena o FNodeOrder pela chave do nó como antes, então o BuildMaxOutRowTree preenche o FNodeMaxOutRow2 (alocado com quatro entradas por nó) com a maior OutRow2 encontrada sob cada subárvore. O QueryNodeTree desce só dentro da janela de chaves e abandona qualquer subárvore cuja linha de saída máxima esteja acima de FRanges[r].Row1, porque nenhuma fórmula nela alcança as linhas referenciadas. As folhas que sobrevivem ainda passam pelo teste completo de RangeIntersectsOutput, então spans de planilha e colunas são checados exatamente como antes

// TXLSDepGraph.BuildNodeIndex / BuildEdges desde a 2.383.1 (levemente condensado)
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
  // fora da janela de chaves, ou nenhuma saída nesta subárvore alcança 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
      // inalterado: supressão EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // subárvore esquerda primeiro
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // mantém a ordem antiga
end;

A recursão esquerda-antes-de-direita não é uma escolha de estilo. As folhas sobreviventes são visitadas exatamente na ordem em que o loop while antigo as visitava, então os arrays Dependents e Precedents são preenchidos na mesma sequência e a ordem topológica continua determinística. O mesmo vale para os dois tipos de aresta: uma aresta dura gravada primeiro ainda suprime uma aresta LookupScan posterior do mesmo par, enquanto uma aresta de scan gravada antes de uma dura mantém seu lugar — a distinção que impede intervalos de lookup de produzirem referências circulares falsas. Por referência, o custo cai do tamanho da janela para O((k + 1) log n), em que k é o número de fórmulas cuja saída realmente alcança as linhas referenciadas

O que o índice de saída garante, e como isso é verificado?

O TXLSDepGraph produz as mesmas arestas na mesma ordem de antes, e a nova propriedade EdgeCandidateChecks conta quantos retângulos de saída a construção mais recente testou de fato, então a afirmação é mensurável em vez de retórica. O teste de regressão EdgeBuildDeepChainsCheckOneCandidatePerDependency constrói cadeias de referências pontuais de 1.024 e 100.000 nós, inseridos em ordem reversa para forçar a ordenação espacial, e assevera exatamente N − 1 checagens — 99.999 para a cadeia longa — além da ordem esperada de precedentes, dependentes e topológica para todo nó. Testes companheiros cobrem raízes de matriz inseridas fora de ordem através de spans de planilhas, referências duplicadas duras e de lookup-scan (10 checagens, com as regras de supressão acima), e uma reconstrução depois de AddNode, que limpa a flag de ordenação para que o próximo BuildEdges ou NodeIndexOf reconstrua a árvore e zere o contador em vez de acumulá-lo

Resultados medidos: de 18,5 segundos para cerca de 0,1 segundo

O trace Win32 de antes da correção, mantido na baseline de performance do projeto para a versão 2.383.0, registrou dois recálculos forçados de 18.488 ms e 19.578 ms. Depois da indexação, três execuções focais em série por arquitetura mediram 102,332–109,429 ms no Win32 e 116,990–133,995 ms no Win64, cerca de 170 a 180 vezes mais rápido no Win32; nenhuma baseline Win64 de antes da correção foi registrada, então nenhum ganho de velocidade no Win64 é reivindicado. As mesmas execuções passaram no gate existente que mantém uma auditoria de recálculo somente leitura dentro de 1,35 vez de um recálculo forçado. Números absolutos dependem da máquina e da carga dela, então reproduza a carga de trabalho no seu próprio hardware antes de citá-los

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                     // cadeia de 49.999 elos na coluna A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 dependentes na coluna B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // a primeira chamada constrói o grafo
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Onde o índice de saída para de ajudar?

A árvore poda só por linhas, e isso deixa alguns limites honestos que valem conhecer antes de desenhar um modelo muito grande em cima dela

• Erros de coluna ainda são pagos nas folhas: as 2.626 fórmulas que preenchem A100:Z200 todas alcançam a linha 100, então uma referência a AA100:AA200 testa cada uma antes de rejeitá-la
• Referências largas, como intervalos de coluna inteira, genuinamente têm muitos precedentes; o índice remove checagens desperdiçadas, não arestas reais, e construir essas arestas continua proporcional ao número delas
• Para referências que atravessam várias planilhas, o máximo armazenado ignora a planilha, então fórmulas em planilhas intermediárias com saídas profundas chegam ao teste de folha; os resultados continuam corretos, só a poda é mais fraca
• A árvore custa quatro inteiros por nó de fórmula, cerca de 1,6 MB para 100.000 nós, e qualquer AddNode a invalida, então mudanças de topologia pagam uma re-ordenação O(n log n) completa mais uma construção de árvore O(n) na próxima construção de arestas

A mesma forma quadrática na clonagem de nomes de report-band

A versão 2.383.2 corrigiu um problema irmão no TXLSXDefinedNames.UniqueCloneName: todo nome definido copiado reiniciava a busca de sufixo dele em _2, então cópias repetidas de report-band cresciam quadraticamente em lookups de nomes. O índice de nomes com escopo agora mantém uma dica de sufixo por nome base, por escopo, e recheca o último candidato devolvido, porque quem chama pode não adicioná-lo de fato; apagar, renomear ou mudar o escopo de um nome invalida o índice, o que restaura a nomenclatura de primeiro disponível. Na suíte de regressão, 1.024 clones sequenciais precisam de 5.088 lookups de candidatos e quatro nomes base alternantes precisam de 5.039, enquanto os mínimos do benchmark de relatório caíram de cerca de 240 ms para 18–20 ms. O gate de timing do report-band em si ainda não está estável — três de seis execuções excederam a razão de 1,05 dele na primeira tentativa pós-correção — e o histórico de performance mantém essas falhas em registro em vez de calibrar o limiar até passar

Se sua aplicação Delphi ou C++Builder gera ou recalcula pastas de trabalho Excel grandes, o componente Excel HotXLS para Delphi e C++Builder traz esse grafo de dependências indexado no motor de recálculo para as classes de pasta de trabalho clássica e XLSX