HotXLS beroendegraf: indexering av matrisformlers utdata

HotXLS 2.383.1, det nativa Excel-biblioteket för Delphi och C++Builder, bygger formelberoendekanter genom ett utdataintervallindex: formelnoder förblir sorterade efter ankarcell, och ett segmentträd som håller den största utdataraden (OutRow2) för varje delträd låter TXLSDepGraph.BuildEdges hoppa över hela block av formler som inte kan nå ett refererat område. På en Win32-arbetsbok med omkring 100 000 formler föll den framtvingade omräkningen från 18,488 sekunder till 102–109 millisekunder

Ingen profilerar beroendegrafen förrän ett batchjobb som brukade ta en sekund börjar ta tjugo. Grafen byggs om närhelst formeltopologin ändras — första Recalculate efter att en arbetsbok laddats eller genererats, eller varje körning efter att grafen ogiltigförklarats — och i spåret före fixen tog den första körningen ensam 16 074 ms. Evalueringen var aldrig problemet; att avgöra vem som beror på vem var det

Varför tog omräkningen av 100 000 formler 18 sekunder?

Den gamla kantbyggaren var kvadratisk i antalet formler på ett blad. För varje beroendeområde gjorde BuildEdges en binärsökning efter ett fönster av kandidatnoder och testade sedan var och en med RangeIntersectsOutput, och det fönstret började allra högst upp på det refererade bladet. Nodnycklarna kommer från XLSDepMakeKey, som packar bladindex från bit 34 och uppåt, raden i bitarna 14–33 och kolumnen i bitarna 0–13, så nedre gränsen (Sheet1, 0, 0) betydde "varje formel från rad 1 ner till botten av det refererade området"

// Före 2.383.1 - TXLSDepGraph.BuildEdges, för beroendeområde r hos nod d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // högst upp på bladet
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...två binärsökningar över FNodeOrder ger fönstret [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hård kant eller LookupScan-kant, deduplicerad via EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Prestandafixturen som avslöjade detta är en helt vanlig kaskadmodell: A2:A50000 lägger var och en ett till cellen ovanför, och B1:B50000 fördubblar var och en grannen i kolumn A. En referens till rad r släpade alltså omkring 2r kandidater genom rektangeltestet, så ett enda grafbygge utförde i storleksordningen fem miljarder skärningskontroller — en tumregeluppskattning, men den stämmer med de 18,5 sekunderna på klockan. Varje kontroll svarade "nej" utom en eller två

Varför kan kantbyggaren inte börja sökningen vid den refererade raden?

För att en matrisformel förankrad ovanför ett område kan äga celler inuti det. Varje TXLSDepNode beskriver en utdatarektangel från sitt ankare (Row, Col) till (OutRow2, OutCol2), och en CSE-matrisformel får en nod för hela sin rektangel, som artikeln om inkrementell omräkning och beroendegrafen förklarar. En rot förankrad vid A1 som fyller A1:A10 måste fortfarande få en kant från en formel som bara läser A5; börja binärsökningen vid rad 5 och den kanten försvinner tyst, vilket betyder ett inaktuellt cachat värde i en levererad rapport i stället för en långsam. Frågan är i själva verket tvåsidig — ankare på eller före Row2, utdata som når åtminstone Row1 — och en enda sorteringsordning kan inte besvara båda halvorna. Flercellsresultat dyker upp i moderna arbetsböcker också, och artikeln om dynamiska matrisformler med spill täcker hur spillda områden beter sig i HotXLS

Ett segmentträd över största utdatarader

HotXLS behåller ankarsorteringen för den övre gränsen och lägger till ett utökat segmentträd för den nedre. BuildNodeIndex sorterar FNodeOrder efter nodnyckel som tidigare, sedan fyller BuildMaxOutRowTree FNodeMaxOutRow2 (allokerat med fyra poster per nod) med den största OutRow2 som finns under varje delträd. QueryNodeTree går bara ner inuti nyckelfönstret och överger varje delträd vars största utdatarad ligger över FRanges[r].Row1, för ingen formel i det kan nå de refererade raderna. Löv som överlever går fortfarande igenom hela RangeIntersectsOutput-testet, så bladspann och kolumner kontrolleras precis som tidigare

// TXLSDepGraph.BuildNodeIndex / BuildEdges sedan 2.383.1 (lätt komprimerat)
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
  // utanför nyckelfönstret, eller ingen utdata i detta delträd når 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
      // oförändrat: EdgeStamp / ScanStamp-undertryckning, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // vänstra delträdet först
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // behåller den gamla ordningen
end;

Rekursionen vänster-före-höger är inte en stilfråga. Överlevande löv besöks i exakt den ordning den gamla while-loopen besökte dem, så arrayerna Dependents och Precedents fylls i samma sekvens och den topologiska ordningen förblir deterministisk. Detsamma gäller de två kanttyperna: en hård kant som registrerats först undertrycker fortfarande en senare LookupScan-kant för samma par, medan en skanningskant som registrerats före en hård behåller sin plats — distinktionen som hindrar uppslagsområden från att producera falska cirkulära referenser. Per referens sjunker kostnaden från fönstrets storlek till O((k + 1) log n), där k är antalet formler vars utdata faktiskt når de refererade raderna

Vad garanterar utdataindexet, och hur verifieras det?

TXLSDepGraph producerar samma kanter i samma ordning som tidigare, och den nya egenskapen EdgeCandidateChecks räknar hur många utdatarektanglar det senaste bygget faktiskt testade, så påståendet är mätbart snarare än retoriskt. Regressionstesten EdgeBuildDeepChainsCheckOneCandidatePerDependency bygger punktreferenskedjor med 1 024 och 100 000 noder, insatta i omvänd ordning för att tvinga fram den spatiala sorteringen, och assertar exakt N − 1 kontroller — 99 999 för den långa kedjan — plus förväntad föregångare, beroende och topologisk ordning för varje nod. Testerna runt omkring täcker matrisrötter insatta i oordning över bladspann, dublerade hårda och uppslagsskanningsreferenser (10 kontroller, med undertryckningsreglerna ovan), samt ett ombygge efter AddNode, som rensar sorteringsflaggan så att nästa BuildEdges eller NodeIndexOf bygger om trädet och nollställer räknaren i stället för att ackumulera den

Uppmätta resultat: från 18,5 sekunder till omkring 0,1 sekunder

Spåret före fixen, bevarat i projektets prestandabaslinje för version 2.383.0, registrerade två framtvingade omräkningar på 18 488 ms och 19 578 ms. Efter indexeringen mätte tre seriella fokuserade körningar per arkitektur 102,332–109,429 ms på Win32 och 116,990–133,995 ms på Win64, ungefär 170 till 180 gånger snabbare på Win32; ingen Win64-baslinje före fixen registrerades, så ingen Win64-acceleration hävdas. Samma körningar klarade den befintliga grinden som håller en skrivskyddad omräkningsgranskning inom 1,35 gånger en framtvingad omräkning. Absoluta tal beror på maskinen och dess last, så återupprepa arbetsbelastningen på din egen hårdvara innan du citerar dem

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                     // kedja med 49 999 länkar i kolumn A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 beroenden i kolumn B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // första anropet bygger grafen
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Var slutar utdataindexet hjälpa?

Trädet beskär bara på rader, och det lämnar några ärliga gränser värda att känna till innan du bygger en mycket stor modell runt det

• Kolumnmissar betalas fortfarande vid löven: de 2 626 formler som fyller A100:Z200 når alla rad 100, så en referens till AA100:AA200 testar var och en innan den avvisar den
• Breda referenser som helkolumnsområden har på riktigt många föregångare; indexet tar bort bortkastade kontroller, inte riktiga kanter, och att bygga de kanterna är fortfarande proportionellt mot deras antal
• För referenser som spänner över flera blad ignorerar det lagrade maximumet bladet, så formler på mellanliggande blad med djupa utdata når lövtestet; resultaten förblir korrekta, bara beskärningen blir svagare
• Trädet kostar fyra heltal per formelnod, omkring 1,6 MB för 100 000 noder, och varje AddNode ogiltigförklarar det, så topologiändringar betalar en full O(n log n)-omsortering plus ett O(n)-trädbygge vid nästa kantbygge

Samma kvadratiska form i kloning av rapportbandsnamn

Version 2.383.2 rättade ett syskonproblem i TXLSXDefinedNames.UniqueCloneName: varje kopierat definierat namn startade om sin suffixsökning vid _2, så upprepade rapportbandskopior växte kvadratiskt i namnuppslag. Indexet för avgränsade namn håller nu en suffixledtråd per basnamn och per omfattning och kontrollerar den sist returnerade kandidaten igen, för anroparen kanske inte faktiskt lägger till den; att ta bort, döpa om eller flytta ett namn till annan omfattning ogiltigförklarar indexet, vilket återställer först-tillgängliga-namngivningen. I regressionssviten behöver 1 024 sekventiella kloner 5 088 kandidatuppslag och fyra alternerande basnamn behöver 5 039, medan rapportbenchmarkens minima sjönk från omkring 240 ms till 18–20 ms. Tidsgrinden för rapportbandet själv är fortfarande inte stabil — tre av sex körningar överskred dess kvot 1,05 i första försöket efter fixen — och prestandahistoriken bevarar de misslyckandena i arkivet i stället för att finslipa tröskeln tills den går igenom

Genererar eller räknar om din Delphi- eller C++Builder-applikation stora Excel-arbetsböcker levererar HotXLS Excel-komponenten för Delphi och C++Builder denna indexerade beroendegraf i omräkningsmotorn för både sina klassiska och sina XLSX-arbetsboksklasser