HotXLS: grafo delle dipendenze e formule array indicizzate

HotXLS 2.383.1, la libreria Excel nativa per Delphi e C++Builder, costruisce gli archi di dipendenza delle formule tramite un indice degli intervalli di output: i nodi formula restano ordinati per cella di ancoraggio, e un segment tree che contiene la massima riga di output (OutRow2) di ogni sottoalbero permette a TXLSDepGraph.BuildEdges di saltare interi blocchi di formule che non possono raggiungere un range referenziato. In un workbook Win32 con circa 100.000 formule, il ricalcolo forzato è sceso da 18,488 secondi a 102–109 millisecondi

Nessuno fa profiling del grafo delle dipendenze finché un job batch che prima impiegava un secondo non inizia a impiegarne venti. Il grafo viene ricostruito ogni volta che la topologia delle formule cambia — il primo Recalculate dopo il caricamento o la generazione di un workbook, o qualunque passaggio dopo che il grafo è stato invalidato — e nella traccia pre-correzione quella prima passata da sola impiegava 16.074 ms. La valutazione non è mai stata il problema; decidere chi dipende da chi lo era

Perché ricalcolare 100.000 formule richiedeva 18 secondi?

Il vecchio costruttore di archi era quadratico rispetto al numero di formule su un foglio. Per ogni range di dipendenza, BuildEdges cercava per dicotomia una finestra di nodi candidati e poi testava ciascuno con RangeIntersectsOutput, e quella finestra partiva dal vertice del foglio referenziato. Le chiavi dei nodi vengono da XLSDepMakeKey, che impacchetta l'indice del foglio dal bit 34 in su, la riga nei bit 14–33 e la colonna nei bit 0–13, quindi il limite inferiore (Sheet1, 0, 0) significava "ogni formula dalla riga 1 fino al fondo del range referenziato"

// Prima della 2.383.1 - TXLSDepGraph.BuildEdges, per il range di dipendenza r del nodo d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // cima del foglio
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...due ricerche dicotomiche su FNodeOrder producono la finestra [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // arco hard o arco LookupScan, deduplicato tramite EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Il fixture di prestazioni che ha esposto il problema è un banale modello a cascata: A2:A50000 aggiunge uno alla cella sopra, e B1:B50000 raddoppia il vicino nella colonna A. Un riferimento alla riga r trascinava quindi circa 2r candidati attraverso il test del rettangolo, così una singola costruzione del grafo eseguiva nell'ordine di cinque miliardi di controlli di intersezione — una stima a spanne, ma torna con i 18,5 secondi sul cronometro. Ogni controllo diceva "no" tranne uno o due

Perché il costruttore di archi non può far partire la ricerca dalla riga referenziata?

Perché una formula array ancorata sopra un range può possedere celle al suo interno. Ogni TXLSDepNode descrive un rettangolo di output dal suo ancoraggio (Row, Col) fino a (OutRow2, OutCol2), e una formula array CSE riceve un nodo per l'intero rettangolo, come spiega l'articolo sul ricalcolo incrementale e il grafo delle dipendenze. Una radice ancorata su A1 che riempie A1:A10 deve comunque ricevere un arco da una formula che legge solo A5; fate partire la ricerca dicotomica dalla riga 5 e quell'arco sparisce in silenzio, il che significa un valore in cache stantio in un report consegnato invece di uno lento. La query è davvero a due lati — ancoraggio su o prima di Row2, output che arriva almeno a Row1 — e un solo ordinamento non può rispondere a entrambe le metà. I risultati multi-cella compaiono anche nei workbook moderni, e l'articolo sulle formule spill di dynamic array copre come si comportano i range spilled in HotXLS

Un segment tree delle massime righe di output

HotXLS conserva l'ordinamento per ancoraggio per il limite superiore e aggiunge un segment tree aumentato per il limite inferiore. BuildNodeIndex ordina FNodeOrder per chiave di nodo come prima, poi BuildMaxOutRowTree riempie FNodeMaxOutRow2 (allocato a quattro voci per nodo) con la massima OutRow2 trovata sotto ogni sottoalbero. QueryNodeTree scende solo dentro la finestra di chiavi e abbandona ogni sottoalbero la cui massima riga di output sta sopra FRanges[r].Row1, perché nessuna formula al suo interno può raggiungere le righe referenziate. Le foglie che sopravvivono passano comunque il test completo RangeIntersectsOutput, quindi spans di fogli e colonne vengono verificati esattamente come prima

// TXLSDepGraph.BuildNodeIndex / BuildEdges dalla 2.383.1 (leggermente condensato)
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
  // fuori dalla finestra di chiavi, oppure nessun output di questo sottoalbero raggiunge 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
      // invariato: soppressione EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // prima il sottoalbero sinistro
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // conserva il vecchio ordine
end;

La ricorsione sinistra-prima-di-destra non è una scelta di stile. Le foglie superstiti vengono visitate nell'esatto ordine in cui le visitava il vecchio loop while, quindi gli array Dependents e Precedents vengono riempiti nella stessa sequenza e l'ordine topologico resta deterministico. Vale lo stesso per le due specie di archi: un arco hard registrato prima sopprime ancora un successivo arco LookupScan per la stessa coppia, mentre un arco di scan registrato prima di uno hard conserva il suo posto — la distinzione che impedisce ai range di lookup di produrre falsi riferimenti circolari. Per riferimento, il costo scende dalla dimensione della finestra a O((k + 1) log n), dove k è il numero di formule il cui output raggiunge davvero le righe referenziate

Che cosa garantisce l'indice di output, e come viene verificato?

TXLSDepGraph produce gli stessi archi nello stesso ordine di prima, e la nuova proprietà EdgeCandidateChecks conta quanti rettangoli di output la costruzione più recente ha davvero testato, così l'affermazione è misurabile invece che retorica. Il test di regressione EdgeBuildDeepChainsCheckOneCandidatePerDependency costruisce catene di riferimenti puntuali da 1.024 e 100.000 nodi, inseriti in ordine inverso per forzare l'ordinamento spaziale, e asserisce esattamente N − 1 controlli — 99.999 per la catena lunga — più l'ordine atteso di precedenti, dipendenti e topologia per ogni nodo. I test companion coprono radici array inserite fuori ordine attraverso spans di fogli, riferimenti hard e lookup-scan duplicati (10 controlli, con le regole di soppressione di sopra), e una ricostruzione dopo AddNode, che azzera il flag di ordinamento così la successiva BuildEdges o NodeIndexOf ricostruisce l'albero e azzera il contatore invece di accumularlo

Risultati misurati: da 18,5 secondi a circa 0,1 secondi

La traccia Win32 pre-correzione, conservata nella baseline di prestazioni del progetto per la versione 2.383.0, registrava due ricalcoli forzati da 18.488 ms e 19.578 ms. Dopo l'indicizzazione, tre run seriali mirati per architettura hanno misurato 102,332–109,429 ms su Win32 e 116,990–133,995 ms su Win64, circa 170-180 volte più veloce su Win32; non è stata registrata alcuna baseline Win64 pre-correzione, quindi nessuno speedup Win64 viene rivendicato. Le stesse run hanno superato il gate esistente che tiene un audit di ricalcolo in sola lettura entro 1,35 volte un ricalcolo forzato. I numeri assoluti dipendono dalla macchina e dal suo carico, quindi riproducete il workload sul vostro hardware prima di citarli

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                     // catena di 49.999 anelli nella colonna A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 formule dipendenti nella colonna B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // la prima chiamata costruisce il grafo
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Dove l'indice di output smette di aiutare?

L'albero pota solo sulle righe, e questo lascia qualche limite onesto che vale la pena conoscere prima di progettare attorno un modello molto grande

• I mancati match di colonna si pagano comunque alle foglie: le 2.626 formule che riempiono A100:Z200 arrivano tutte alla riga 100, quindi un riferimento a AA100:AA200 le testa una per una prima di respingerle
• I riferimenti larghi come i range a intera colonna hanno davvero molti precedenti; l'indice toglie i controlli sprecati, non gli archi reali, e costruire quegli archi resta proporzionale al loro numero
• Per i riferimenti che attraversano più fogli, il massimo memorizzato ignora il foglio, quindi le formule sui fogli intermedi con output profondi arrivano al test delle foglie; i risultati restano corretti, è solo la potatura a essere più debole
• L'albero costa quattro interi per nodo formula, circa 1,6 MB per 100.000 nodi, e ogni AddNode lo invalida, così i cambi di topologia pagano un riordino completo O(n log n) più una costruzione dell'albero O(n) alla successiva costruzione degli archi

La stessa forma quadratica nella clonazione dei nomi dei report-band

La versione 2.383.2 ha corretto un problema gemello in TXLSXDefinedNames.UniqueCloneName: ogni nome definito copiato ripartiva la ricerca del suffisso da _2, così le copie ripetute di report-band crescevano quadraticamente nelle ricerche di nomi. L'indice dei nomi con scope ora conserva un hint di suffisso per nome base e per scope e riverifica l'ultimo candidato restituito, perché il chiamante potrebbe non aggiungerlo davvero; eliminare, rinominare o cambiare scope a un nome invalida l'indice, il che ripristina la nomenclatura primo-disponibile. Nella suite di regressione, 1.024 cloni sequenziali richiedono 5.088 ricerche di candidati e quattro nomi base alternati ne richiedono 5.039, mentre i minimi del benchmark dei report sono scesi da circa 240 ms a 18-20 ms. Il gate di timing dei report-band in sé non è ancora stabile — tre run su sei hanno superato il suo rapporto di 1,05 nel primo tentativo post-correzione — e la storia delle prestazioni registra quei fallimenti invece di ritoccare la soglia finché non passa

Se la vostra applicazione Delphi o C++Builder genera o ricalcola workbook Excel di grandi dimensioni, il componente Excel HotXLS per Delphi e C++Builder spedisce questo grafo delle dipendenze indicizzato nel motore di ricalcolo sia per le sue classi workbook classiche sia per quelle XLSX