Graf odvisnosti HotXLS: indeks izhodov matričnih formul

HotXLS 2.383.1, izvorna knjižnica Excel za Delphi in C++Builder, gradi povezave odvisnosti formul prek indeksa izhodnih intervalov: vozlišča formul ostanejo razvrščena po sidrni celici, segmentno drevo, ki hrani največjo izhodno vrstico (OutRow2) vsakega poddrevesa, pa TXLSDepGraph.BuildEdges omogoči preskočiti cele bloke formul, ki do sklicanega obsega ne morejo doseči. Pri delovnem zvezku Win32 s približno 100.000 formulami je vsiljeni preračun padel iz 18,488 sekunde na 102–109 milisekund

Nihče ne profilira grafa odvisnosti, dokler paketno opravilo, ki je prej vzelo sekundo, ne začne jemati dvajset. Graf se znova zgradi vsakič, ko se spremeni topologija formul — prvi Recalculate po nalaganju ali ustvarjanju delovnega zvezka ali kateri koli prehod, potem ko je bil graf razveljavljen — v sledi pred popravkom pa je ta prvi prehod sam vzel 16.074 ms. Ovrednotenje nikoli ni bilo težava; težava je bila odločiti, kdo je odvisen od koga

Zakaj je preračun 100.000 formul vzel 18 sekund?

Stari graditelj povezav je bil kvadraten glede na število formul na listu. Za vsak obseg odvisnosti je BuildEdges z dvojiškim iskanjem poiskal okno kandidatskih vozlišč in nato vsako preizkusil s RangeIntersectsOutput, okno pa se je začelo kar na samem vrhu sklicanega lista. Ključi vozlišč prihajajo iz XLSDepMakeKey, ki indeks lista spravi od bita 34 navzgor, vrstico v bite 14–33 in stolpec v bite 0–13, zato je spodnja meja (Sheet1, 0, 0) pomenila »vse formule od vrstice 1 navzdol do dna sklicanega obsega«

// Pred 2.383.1 - TXLSDepGraph.BuildEdges, za obseg odvisnosti r vozlišča d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // vrh lista
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...dvojiški iskanji po FNodeOrder ustvarita okno [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // trda povezava ali povezava LookupScan, brez dvojnikov prek EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Preskusna nastavitev, ki je to izkopala, je običajen kaskadni model: A2:A50000 vsaka prišteje eno celici zgoraj, B1:B50000 pa vsaka podvoji soseda v stolpcu A. Sklic na vrstico r je zato skozi preizkus pravokotnika vlekel približno 2r kandidatov, en sama gradnja grafa pa je naredila reda pet milijard preizkusov presekanja — ocena iz rokava, a se ujema s 18,5 sekunde na uri. Vsak preizkus je rekel »ne«, razen enega ali dveh

Zakaj graditelj povezav ne more začeti iskanja pri sklicani vrstici?

Ker matrična formula, zasidrana nad obsegom, lahko lasti celice znotraj njega. Vsako TXLSDepNode opisuje izhodni pravokotnik od svojega sidra (Row, Col) do (OutRow2, OutCol2), CSE matrična formula pa dobi eno vozlišče za celoten svoj pravokotnik, kot razlaga članek o inkrementalnem preračunu in grafu odvisnosti. Koren, zasidran v A1, ki zapolni A1:A10, mora še vedno dobiti povezavo od formule, ki bere le A5; začnete li dvojiško iskanje pri vrstici 5, ta povezava tiho izgine, kar pomeni zastarelo predpomnjeno vrednost v poslanem poročilu namesto počasnega. Poizvedba je pravzaprav dvostranska — sidro pri ali pred Row2, izhod, ki doseže vsaj Row1 — en sam vrstni red razvrščanja pa ne more odgovoriti na obe polovici. Večcelični rezultati se pojavljajo tudi v sodobnih delovnih zvezkih, članek o formulah prelivanja dinamičnih matrik pa pokriva, kako se preliti obsegi obnesejo v HotXLS

Segmentno drevo največjih izhodnih vrstic

HotXLS obdrži razvrščanje po sidru za zgornjo mejo in doda obogajano segmentno drevo za spodnjo mejo. BuildNodeIndex razvrsti FNodeOrder po ključu vozlišča kot prej, nato BuildMaxOutRowTree napolni FNodeMaxOutRow2 (dodeljeno s štirimi vnosi na vozlišče) z največjim OutRow2, najdenim pod vsakim poddrevesom. QueryNodeTree spusti le znotraj okna ključev in opusti vsako poddrevo, katerega največja izhodna vrstica leži nad FRanges[r].Row1, ker nobena formula vanj ne more doseči sklicanih vrstic. Listi, ki preživijo, še vedno gredo skozi celoten preizkus RangeIntersectsOutput, tako da so razponi listov in stolpci preverjeni točno kot prej

// TXLSDepGraph.BuildNodeIndex / BuildEdges od 2.383.1 (rahlo skrčeno)
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
  // zunaj okna ključev ali noben izhod v tem poddrevesu ne doseže 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
      // nespremenjeno: potlačitev EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // najprej levo poddrevo
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // obdrži stari vrstni red
end;

Rekurzija levo-pred-desno ni stilska izbira. Preživeli listi so obiskani v točno tistem vrstnem redu, v katerem jih je obiskala stara zanka while, tabeli Dependents in Precedents sta zato napolnjeni v istem zaporedju in topološki vrstni red ostane determinističen. Enako velja za dve vrsti povezav: trda povezava, zabeležena prva, še vedno potlači poznejšo povezavo LookupScan za isti par, povezava pregledovanja, zabeležena pred trdo, pa obdrži svoje mesto — tista razlika, ki preprečuje, da bi obsegi iskanja ustvarjali lažne krožne sklice. Na sklic se strošek zniža iz velikosti okna na O((k + 1) log n), kjer je k število formul, katerih izhod dejansko doseže sklicane vrstice

Kaj zagotavlja izhodni indeks in kako je preverjen?

TXLSDepGraph daje iste povezave v istem vrstnem redu kot prej, nova lastnost EdgeCandidateChecks pa šteje, koliko izhodnih pravokotnikov je zadnja gradnja dejansko preizkusila, zato je trditev merljiva in ne retorična. Regresijski test EdgeBuildDeepChainsCheckOneCandidatePerDependency gradi verige točkovnih sklicev s 1.024 in 100.000 vozlišči, vstavljenimi v obratnem vrstnem redu, da vsili prostorsko razvrščanje, in zagotovi točno N − 1 preizkusov — 99.999 za dolgo verigo — plus pričakovani predhodnik, odvisnik in topološki vrstni red za vsako vozlišče. Spremljajoči testi pokrivajo korene matrik, vstavljene neurejeno čez razpone listov, podvojene trde sklice in sklice pregledovanja (10 preizkusov, s pravili potlačitve zgoraj) in znovogradnjo po AddNode, ki počisti zastavico razvrščanja, tako da naslednji BuildEdges ali NodeIndexOf drevo znova zgradi in števec ponastavi, namesto da bi ga kopičil

Izmerjeni rezultati: iz 18,5 sekunde na približno 0,1 sekunde

Sled pred popravkom za Win32, shranjena v izhodiščni meritvi zmogljivosti projekta za različico 2.383.0, je zabeležila dva vsiljena preračuna, 18.488 ms in 19.578 ms. Po indeksiranju so tri zaporedne osredotočene zagone na arhitekturo merili 102,332–109,429 ms na Win32 in 116,990–133,995 ms na Win64, približno 170- do 180-krat hitreje na Win32; izhodiščna meritev Win64 pred popravkom ni bila zabeležena, zato pospešitev Win64 ni trjena. Ista zagona sta prestala obstoječo pregrado, ki revizijo preračuna samo za branje drži znotraj 1,35-kratnika vsiljenega preračuna. Absolutne številke so odvisne od strojne opreme in njene obremenitve, zato delovno obremenitev ponovite na svoji strojni opremi, preden jih navedete

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                     // veriga s 49.999 povezavami v stolpcu A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 odvisnikov v stolpcu B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // prvi klic zgradi graf
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Kje indeks izhodov preneha pomagati?

Drevo obrezuje le po vrsticah, kar pusti nekaj iskrenih omejitev, vrednih poznavanja, preden zasnrete zelo velik model okoli njega

• Zgrešitve po stolpcih se še vedno plačajo na listih: 2.626 formul, ki zapolnjuje A100:Z200, vse doseže vrstico 100, zato jih sklic na AA100:AA200 preizkusi vsako, preden jo zavrne
• Široki sklici, kot so obsegi celih stolpcev, resnično imajo veliko predhodnikov; indeks odstrani potratenjene preizkuse in ne pravih povezav, gradnja teh povezav pa je še vedno sorazmerna z njihovim številom
• Pri sklicih, ki segajo čez več listov, shrani shranjeni maksimum brez upoštevanja lista, zato formule na vmesnih listih z globokimi izhodi dosežejo preizkus listov; rezultati ostanejo pravilni, le obrezovanje je šibkejše
• Drevo stane štiri cela števila na vozlišče formule, približno 1,6 MB za 100.000 vozlišč, vsak AddNode pa ga razveljavi, zato spremembe topologije plačajo polno ponovno razvrščanje O(n log n) plus gradnjo drevesa O(n) ob naslednji gradnji povezav

Ista kvadratna oblika pri kloniranju imen pasov poročil

Različica 2.383.2 je popravila sorodni problem v TXLSXDefinedNames.UniqueCloneName: vsako kopirano definirano ime je ponovno začelo iskanje pripone pri _2, zato so se ponavljajoče kopije pasov poročil kvadratno razraščale v iskanjih imen. Indeks obseženih imen zdaj hrani namig pripone na ime osnove in na obseg ter znova preveri zadnjega vrnjenega kandidata, ker ga klicnik morda sploh ne doda; brisanje, preimenovanje ali prestavitev imena v drug obseg razveljavi indeks, kar obnovi poimenovanje po prvi prosti. V regresijski zbirki potrebuje 1.024 zaporednih klonov 5.088 iskanj kandidatov in štiri izmenične osnovne imene 5.039, minimumi merila poročil pa so padli s približno 240 ms na 18–20 ms. Časovna pregrada pasov poročil sama še vedno ni stabilna — trije od šestih zagonov so v prvem poskusu po popravku presegli njeno razmerje 1,05 — zgodovina zmogljivosti pa te neuspehe ohranja na zapisu, namesto da bi prag nastavljala, dokler ne gre skozi

Če Vaša aplikacija za Delphi ali C++Builder ustvarja ali preračunava velike delovne zvezke Excel, ta indeksirani graf odvisnosti pošilja komponenta Excel HotXLS za Delphi in C++Builder v svojem pogonu za preračun za oba razreda delovnih zvezkov, klasičnega in XLSX