Grafo de dependências: indexar saídas de matriz no HotXLS

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

Ninguém faz profiling ao grafo de dependências até que um job em lote que levava um segundo comece a levar vinte. O grafo é reconstruído sempre que a topologia de fórmulas muda — o primeiro Recalculate depois de carregar ou gerar um livro, ou qualquer passagem depois de o grafo ter sido invalidado — e no trace anterior à correção só essa primeira passagem levou 16 074 ms. A avaliação nunca foi o problema; decidir quem depende de quem é que era

Porque é 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 folha. Para cada intervalo de dependência, o BuildEdges fazia uma pesquisa binária de uma janela de nós candidatos e depois testava cada um com o RangeIntersectsOutput, e essa janela começava mesmo no topo da folha referenciada. As chaves dos nós vêm do XLSDepMakeKey, que empacota o índice da folha a partir do bit 34 para cima, a linha nos bits 14–33, e a coluna nos bits 0–13, pelo que o limite inferior (Sheet1, 0, 0) significava «toda a fórmula da linha 1 até ao fundo do intervalo referenciado»

// Antes de 2.383.1 - TXLSDepGraph.BuildEdges, para o intervalo de dependência r do nó d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // topo da folha
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...duas pesquisas 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 através de EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

O fixture de desempenho que expôs isto é um modelo em cascata vulgar: A2:A50000 somam cada um um à célula acima, e B1:B50000 duplicam cada um o vizinho na coluna A. Uma referência à linha r arrastava portanto cerca de 2r candidatos pelo teste do retângulo, pelo que uma única construção do grafo executava pela ordem de cinco mil milhões de verificações de interseção — uma estimativa de guardanapo, mas coincide com os 18,5 segundos no relógio. Todas as verificações diziam «não» exceto uma ou duas

Porque é que o construtor de arestas não pode começar a pesquisa na linha referenciada?

Porque uma fórmula de matriz ancorada acima de um intervalo pode possuir células dentro dele. Cada TXLSDepNode descreve um retângulo de saída da sua ancoragem (Row, Col) até (OutRow2, OutCol2), e uma fórmula de matriz CSE recebe um único nó para o seu retângulo inteiro, como explica o artigo sobre recálculo incremental e o grafo de dependências. Uma raiz ancorada em A1 que preencha A1:A10 tem de continuar a receber uma aresta de uma fórmula que leia apenas A5; comece a pesquisa binária na linha 5 e essa aresta desaparece em silêncio, o que significa um valor em cache obsoleto num relatório enviado em vez de um relatório lento. A consulta é realmente de dois lados — ancoragem em ou antes de Row2, saída a alcançar pelo menos Row1 — e uma única ordem de ordenação não consegue responder às duas metades. Os resultados de várias células também aparecem em livros modernos, e o artigo sobre fórmulas de spill de matriz dinâmica cobre como os intervalos spilled se comportam no HotXLS

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

O HotXLS mantém a ordenação por ancoragem para o limite superior e acrescenta uma segment tree aumentada para o limite inferior. O BuildNodeIndex ordena o FNodeOrder por chave de nó como antes, depois o BuildMaxOutRowTree preenche o FNodeMaxOutRow2 (alocado a quatro entradas por nó) com o maior OutRow2 encontrado sob cada subárvore. O QueryNodeTree desce apenas 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 consegue alcançar as linhas referenciadas. As folhas que sobrevivem ainda passam pelo teste completo do RangeIntersectsOutput, pelo que os intervalos de folhas e as colunas são verificados exatamente como antes

// TXLSDepGraph.BuildNodeIndex / BuildEdges desde 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 pela ordem por que o antigo ciclo while as visitava, pelo que as matrizes Dependents e Precedents são preenchidas pela mesma sequência e a ordem topológica continua determinística. O mesmo se aplica aos dois tipos de arestas: uma aresta dura registada primeiro continua a suprimir uma aresta LookupScan posterior para o mesmo par, enquanto uma aresta de scan registada antes de uma dura conserva o seu lugar — a distinção que impede os intervalos de lookup de produzir 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 garante o índice de saída, e como é verificado?

O TXLSDepGraph produz as mesmas arestas pela mesma ordem de antes, e a nova propriedade EdgeCandidateChecks conta quantos retângulos de saída a construção mais recente realmente testou, pelo que a afirmação é mensurável em vez de retórica. O teste de regressão EdgeBuildDeepChainsCheckOneCandidatePerDependency constrói cadeias de referências pontuais de 1024 e 100 000 nós, inseridas por ordem inversa para forçar a ordenação espacial, e afirma exatamente N − 1 verificações — 99 999 para a cadeia longa — mais a ordem de precedente, de dependente e topológica esperada para cada nó. Os testes acompanhantes cobrem raízes de matriz inseridas fora de ordem através de intervalos de folhas, referências duplicadas de aresta dura e de lookup-scan (10 verificações, 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 reponha o contador em vez de o acumular

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

O trace Win32 anterior à correção, retido na linha base de desempenho do projeto para a versão 2.383.0, registou 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 em Win32 e 116,990–133,995 ms em Win64, cerca de 170 a 180 vezes mais rápido em Win32; nenhuma linha base Win64 anterior à correção foi registada, pelo que não se afirma aceleração nenhuma em Win64. As mesmas execuções passaram o portão existente que mantém uma auditoria de recálculo só de leitura dentro de 1,35 vezes um recálculo forçado. Os números absolutos dependem da máquina e da sua carga, por isso reproduza a carga de trabalho no seu próprio hardware antes de os citar

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 deixa o índice de saída de ajudar?

A árvore poda apenas em linhas, e isso deixa alguns limites honestos que valem a pena conhecer antes de desenhar um modelo muito grande à volta dela

• As falhas de coluna continuam a pagar-se nas folhas: as 2626 fórmulas que preenchem A100:Z200 chegam todas à linha 100, pelo que uma referência a AA100:AA200 testa cada uma delas antes de a recusar
• Referências largas como intervalos de colunas inteiras genuinamente têm muitos precedentes; o índice remove verificações desperdiçadas, não arestas reais, e construir essas arestas continua proporcional ao seu número
• Para referências que atravessam várias folhas, o máximo guardado ignora a folha, pelo que fórmulas em folhas intermédias 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 invalida-a, pelo que mudanças de topologia pagam uma reordenação completa O(n log n) 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 bandas de relatório

A versão 2.383.2 corrigiu um problema irmão no TXLSXDefinedNames.UniqueCloneName: cada nome definido copiado recomeçava a sua pesquisa de sufixo em _2, pelo que cópias repetidas de bandas de relatório cresciam quadraticamente em pesquisas de nomes. O índice de nomes com âmbito guarda agora uma dica de sufixo por nome base e por âmbito, e reverifica o último candidato devolvido, porque quem chama pode não o adicionar de facto; apagar, renomear ou mudar o âmbito de um nome invalida o índice, o que repõe a nomenclatura do primeiro disponível. Na suite de regressão, 1024 clones sequenciais precisam de 5088 pesquisas de candidatos e quatro nomes base alternantes precisam de 5039, enquanto os mínimos do benchmark de relatórios caíram de cerca de 240 ms para 18–20 ms. O próprio portão de tempos da banda de relatório ainda não está estável — três de seis execuções excederam o seu rácio de 1,05 na primeira tentativa após a correção — e o histórico de desempenho mantém essas falhas registadas em vez de afinar o limiar até passar

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