Graphe de dépendances HotXLS : index des sorties de formules

HotXLS 2.383.1, la bibliothèque Excel native pour Delphi et C++Builder, construit les arêtes de dépendances des formules via un index des intervalles de sortie : les nœuds de formules restent triés par cellule d'ancrage, et un segment tree gardant la plus grande rangée de sortie (OutRow2) de chaque sous-arbre permet à TXLSDepGraph.BuildEdges de sauter des blocs entiers de formules qui ne peuvent pas atteindre une plage référencée. Sur un classeur Win32 d'environ 100 000 formules, le recalcul forcé est tombé de 18,488 secondes à 102–109 millisecondes

Personne ne profile le graphe de dépendances jusqu'au jour où un traitement par lots qui prenait une seconde en prend vingt. Le graphe est reconstruit chaque fois que la topologie des formules change — le premier Recalculate après le chargement ou la génération d'un classeur, ou toute passe après invalidation du graphe — et dans la trace d'avant correctif, cette première passe seule prenait 16 074 ms. L'évaluation n'a jamais été le problème ; décider qui dépend de qui l'était

Pourquoi le recalcul de 100 000 formules prenait-il 18 secondes ?

L'ancien constructeur d'arêtes était quadratique dans le nombre de formules d'une feuille. Pour chaque plage de dépendance, BuildEdges cherchait par dichotomie une fenêtre de nœuds candidats puis testait chacun avec RangeIntersectsOutput, et cette fenêtre partait du tout haut de la feuille référencée. Les clés de nœuds viennent de XLSDepMakeKey, qui emballe l'index de feuille dans les bits 34 et au-delà, la rangée dans les bits 14–33 et la colonne dans les bits 0–13, si bien que la borne basse (Sheet1, 0, 0) signifiait chaque formule depuis la rangée 1 jusqu'au bas de la plage référencée

// Avant 2.383.1 - TXLSDepGraph.BuildEdges, pour la plage de dépendance r du nœud d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // haut de la feuille
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...deux recherches dichotomiques sur FNodeOrder produisent la fenêtre [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // arête dure ou arête LookupScan, dédupliquée via EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Le gabarit de performance qui a exposé cela est un modèle en cascade ordinaire : A2:A50000 ajoute chacun un à la cellule du dessus, et B1:B50000 double chacun son voisin en colonne A. Une référence à la rangée r traînait donc environ 2r candidats à travers le test rectangle, si bien qu'une seule construction du graphe effectuait de l'ordre de cinq milliards de tests d'intersection — une estimation au dos de l'enveloppe, mais elle colle aux 18,5 secondes au chronomètre. Chaque test répondait non, sauf un ou deux

Pourquoi le constructeur d'arêtes ne peut-il pas partir de la rangée référencée ?

Parce qu'une formule matricielle ancrée au-dessus d'une plage peut posséder des cellules à l'intérieur de celle-ci. Chaque TXLSDepNode décrit un rectangle de sortie depuis son ancre (Row, Col) jusqu'à (OutRow2, OutCol2), et une formule matricielle CSE obtient un nœud pour tout son rectangle, comme l'explique l'article sur le recalcul incrémental et le graphe de dépendances. Une racine ancrée en A1 qui remplit A1:A10 doit quand même recevoir une arête d'une formule qui ne lit que A5 ; partir de la rangée 5 dans la recherche dichotomique et cette arête disparaît silencieusement, ce qui signifie une valeur en cache périmée dans un rapport livré au lieu d'un rapport lent. La requête est en réalité bilatérale — ancre à ou avant Row2, sortie atteignant au moins Row1 — et un seul ordre de tri ne peut pas répondre aux deux moitiés. Les résultats multi-cellules apparaissent aussi dans les classeurs modernes, et l'article sur les formules à débordement de tableau dynamique couvre le comportement des plages débordées dans HotXLS

Un segment tree des rangées de sortie maximales

HotXLS garde le tri par ancre pour la borne haute et ajoute un segment tree augmenté pour la borne basse. BuildNodeIndex trie FNodeOrder par clé de nœud comme avant, puis BuildMaxOutRowTree remplit FNodeMaxOutRow2 (alloué à quatre entrées par nœud) avec le plus grand OutRow2 trouvé sous chaque sous-arbre. QueryNodeTree ne descend qu'à l'intérieur de la fenêtre de clés et abandonne tout sous-arbre dont la rangée de sortie maximale se situe au-dessus de FRanges[r].Row1, parce qu'aucune formule qu'il contient ne peut atteindre les rangées référencées. Les nœuds feuilles qui survivent passent quand même par le test complet RangeIntersectsOutput, si bien que les étendues de feuilles et les colonnes sont vérifiées exactement comme avant

// TXLSDepGraph.BuildNodeIndex / BuildEdges depuis 2.383.1 (légèrement condensé)
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
  // hors de la fenêtre de clés, ou aucune sortie de ce sous-arbre n'atteint 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
      // inchangé : suppression EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // sous-arbre gauche d'abord
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // conserve l'ancien ordre
end;

La récursion gauche-avant-droite n'est pas un choix de style. Les feuilles survivantes sont visitées exactement dans l'ordre où l'ancienne boucle while les visitait, si bien que les tableaux Dependents et Precedents sont remplis dans la même séquence et l'ordre topologique reste déterministe. Il en va de même pour les deux sortes d'arêtes : une arête dure enregistrée en premier supprime toujours une arête LookupScan ultérieure pour la même paire, tandis qu'une arête de scan enregistrée avant une arête dure garde sa place — la distinction qui empêche les plages de recherche de produire de fausses références circulaires. Par référence, le coût passe de la taille de la fenêtre à O((k + 1) log n), où k est le nombre de formules dont la sortie atteint réellement les rangées référencées

Que garantit l'index de sorties, et comment est-il vérifié ?

TXLSDepGraph produit les mêmes arêtes dans le même ordre qu'avant, et la nouvelle propriété EdgeCandidateChecks compte combien de rectangles de sortie la construction la plus récente a réellement testés, si bien que l'affirmation est mesurable plutôt que rhétorique. Le test de régression EdgeBuildDeepChainsCheckOneCandidatePerDependency construit des chaînes de références ponctuelles de 1 024 et 100 000 nœuds, insérées en ordre inverse pour forcer le tri spatial, et affirme exactement N − 1 tests — 99 999 pour la longue chaîne — plus l'ordre topologique et les précédents et dépendants attendus pour chaque nœud. Des tests compagnons couvrent des racines matricielles insérées en désordre à travers des étendues de feuilles, des références dupliquées dures et lookup-scan (10 tests, avec les règles de suppression ci-dessus), et une reconstruction après AddNode, qui efface le drapeau de tri pour que le prochain BuildEdges ou NodeIndexOf reconstruise l'arbre et remette le compteur à zéro au lieu de l'accumuler

Résultats mesurés : de 18,5 secondes à environ 0,1 seconde

La trace Win32 d'avant correctif, conservée dans la baseline de performance du projet pour la version 2.383.0, enregistrait deux recalculs forcés de 18 488 ms et 19 578 ms. Après indexation, trois exécutions focalisées en série par architecture ont mesuré 102,332–109,429 ms sur Win32 et 116,990–133,995 ms sur Win64, soit environ 170 à 180 fois plus rapide sur Win32 ; aucune baseline Win64 d'avant correctif n'a été enregistrée, donc aucun gain Win64 n'est revendiqué. Les mêmes exécutions ont passé le garde-fou existant qui maintient un audit de recalcul en lecture seule dans un facteur 1,35 d'un recalcul forcé. Les chiffres absolus dépendent de la machine et de sa charge, alors reproduisez la charge de travail sur votre propre matériel avant de les citer

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                     // chaîne de 49 999 maillons en colonne A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 dépendants en colonne B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // le premier appel construit le graphe
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Où l'index de sorties cesse-t-il d'aider ?

L'arbre élague sur les rangées seulement, et cela laisse quelques limites honnêtes à connaître avant de concevoir un très grand modèle autour

• Les ratés de colonnes se paient toujours aux feuilles : les 2 626 formules remplissant A100:Z200 atteignent tous la rangée 100, si bien qu'une référence à AA100:AA200 teste chacune avant de la rejeter
• Les références larges comme des colonnes entières ont vraiment beaucoup de précédents ; l'index supprime les tests gaspillés, pas les vraies arêtes, et construire ces arêtes reste proportionnel à leur nombre
• Pour les références qui s'étendent sur plusieurs feuilles, le maximum stocké ignore la feuille, si bien que les formules des feuilles intermédiaires à sorties profondes arrivent au test feuille ; les résultats restent corrects, seul l'élagage est plus faible
• L'arbre coûte quatre entiers par nœud de formule, environ 1,6 Mo pour 100 000 nœuds, et tout AddNode l'invalide, si bien que les changements de topologie paient un re-tri complet en O(n log n) plus une construction d'arbre en O(n) à la prochaine construction d'arêtes

La même forme quadratique dans le clonage des noms de bandes de rapport

La version 2.383.2 a corrigé un problème jumeau dans TXLSXDefinedNames.UniqueCloneName : chaque nom défini copié reprenait sa recherche de suffixe à _2, si bien que les copies répétées de bandes de rapport croissaient de façon quadratique en recherches de noms. L'index de noms scopés garde désormais un indice de suffixe par nom de base et par portée et revérifie le dernier candidat renvoyé, parce que l'appelant peut très bien ne pas l'ajouter ; supprimer, renommer ou changer la portée d'un nom invalide l'index, ce qui restaure le nommage premier-disponible. Dans la suite de régression, 1 024 clones séquentiels demandent 5 088 recherches de candidats et quatre noms de base alternés en demandent 5 039, tandis que les minima du gabarit de rapport sont tombés d'environ 240 ms à 18–20 ms. Le garde-fou de chronométrage des bandes de rapport lui-même reste instable — trois exécutions sur six dépassaient son ratio de 1,05 à la première tentative d'après correctif — et l'historique de performance garde ces échecs enregistrés au lieu d'ajuster le seuil jusqu'à ce qu'il passe

Si votre application Delphi ou C++Builder génère ou recalcule de grands classeurs Excel, le composant Excel HotXLS pour Delphi et C++Builder livre ce graphe de dépendances indexé dans son moteur de recalcul, pour ses classes de classeurs classiques comme XLSX