HotXLS:n riippuvuusgraafi indeksoi taulukkokaavojen tulokset

HotXLS 2.383.1, natiivi Excel-kirjasto Delphille ja C++Builderille, rakentaa kaavojen riippuvuussärmet tulostusväli-indeksin kautta: kaavasolmut pysyvät lajiteltuina ankkurisolun mukaan, ja segmenttipuu joka pitää sisällään jokaisen alipuun suurimman tulostusrivin (OutRow2) antaa TXLSDepGraph.BuildEdgesin ohittaa kokonaisia kaavablokkeja jotka eivät ulotu viitattuun alueeseen. Win32-työkirjassa jossa on noin 100 000 kaavaa, pakotettu uudelleenlaskenta putosi 18,488 sekunnista 102–109 millisekuntiin

Kukaan ei profiloi riippuvuusgraafia ennen kuin eräajo joka ennen vei sekunnin alkaa viedä kaksikymmentä. Graafi rakennetaan uudelleen aina kun kaavatopologia muuttuu — ensimmäinen Recalculate työkirjan lataamisen tai generoinnin jälkeen, tai mikä tahansa kierros graafin mitätöinnin jälkeen — ja korjausta edeltävässä jäljityksessä pelkästään se ensimmäinen kierros vei 16 074 ms. Evaluointi ei ollut koskaan ongelma; sen päättäminen kuka riippuu kenestäkin oli

Miksi 100 000 kaavan uudelleenlaskenta vei 18 sekuntia?

Vanha särmärakentaja oli neliöllinen sheetin kaavamäärän suhteen. Jokaiselle riippuvuusalueelle BuildEdges teki binäärihaun kandidaattisolmujen ikkunalle ja testasi sitten jokaisen RangeIntersectsOutputilla, ja se ikkuna alkoi viitatun sheetin ihan yläosalta. Solmuavaimet tulevat XLSDepMakeKeyista joka pakkaa sheet-indeksin bitistä 34 ylöspäin, rivin biteille 14–33 ja sarakkeen biteille 0–13, joten alaraja (Sheet1, 0, 0) tarkoitti ”jokaisen kaavan riviltä 1 alas viitatun alueen pohjaan”

// Ennen 2.383.1 - TXLSDepGraph.BuildEdges, solmun d riippuvuusalueelle r
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // sheetin yläosa
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...kaksi binäärihakua FNodeOrderin yli tuottaa ikkunan [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // kova särmä tai LookupScan-särmä, deduplikoitu EdgeStamp / ScanStamp kautta
  end;
  Inc(i);
end;

Suorituskykyfixture joka paljasti tämän on tavallinen kaskadimalli: A2:A50000 lisäävät kussakin yhden yläpuoliseen soluun, ja B1:B50000 kaksinkertaistavat kussakin A-sarakkeen naapurin. Viittaus riviin r raahasi siksi noin 2r kandidaattia suorakulmatestin läpi, joten yksi graafin rakennus teki suuruusluokaltaan viisi miljardia leikkautustarkistusta — takapaperiarvio, mutta se osuu yhteen kellossa näkyvän 18,5 sekunnin kanssa. Jokainen tarkistus sanoi ”ei” paitsi yksi tai kaksi

Miksi särmärakentaja ei voi aloittaa haun viitatulta riviltä?

Siksi että alueen yläpuolelle ankkuroitunut taulukkokaava voi omistaa sen sisällä olevia soluja. Jokainen TXLSDepNode kuvaa tulossuorakulmion ankkuristaan (Row, Col) kohtaan (OutRow2, OutCol2), ja CSE-taulukkokaava saa yhden solmun koko suorakulmiolleen, kuten artikkeli inkrementaalisesta uudelleenlaskennasta ja riippuvuusgraafista selittää. Juuri joka on ankkuroitu A1een ja täyttää A1:A10n on silti saatava särmä kaavasta joka lukee vain A5:n; aloita binäärihaku rivistä 5 ja se särmä katoaa hiljaisesti, mikä tarkoittaa vanhentunutta välimuistiarvoa toimitetussa raportissa hitaan sijaan. Kysely on oikeasti kaksisuuntainen — ankkuri kohdassa tai ennen Row2:a, tulostus ulottuen vähintään Row1:in — eikä yksi lajittelujärjestys voi vastata molempia puoliskoja. Monisoluiset tulokset ilmestyvät myös moderneihin työkirjoihin, ja artikkeli dynaamisten taulukoiden spill-kaavoista kattaa miten spill-alueet käyttäytyvät HotXLS:ssä

Segmenttipuu suurimmista tulostusriveistä

HotXLS pitää ankkurilajittelun ylärajalle ja lisää täydennetyn segmenttipuun alarajalle. BuildNodeIndex lajittelee FNodeOrderin solmuavaimen mukaan kuten ennenkin, sitten BuildMaxOutRowTree täyttää FNodeMaxOutRow2in (varattuna neljä merkintää solmua kohti) jokaisen alipuun alta löytyneellä suurimmalla OutRow2lla. QueryNodeTree laskeutuu vain avainikkunan sisällä ja hylkää jokaisen alipuun jonka suurin tulostusrivi on FRanges[r].Row1in yläpuolella, koska yksikään sen kaava ei ulotu viitattuihin riveihin. Selviävät lehdet käyvät silti läpi koko RangeIntersectsOutput-testin, joten sheet-välit ja sarakkeet tarkistetaan täsmälleen kuten ennen

// TXLSDepGraph.BuildNodeIndex / BuildEdges versiosta 2.383.1 alkaen (kevyesti tiivistetty)
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
  // avainikkunan ulkopuolella, tai yksikään tämän alipuun tulostus ei ulotu Row1:in
  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
      // ennallaan: EdgeStamp / ScanStamp -vaimennus, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // vasen alipuu ensin
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // säilyttää vanhan järjestyksen
end;

Vasen-ennen-oikeaa -rekursio ei ole tyylikysymys. Selviävät lehdet vieraillaan täsmälleen siinä järjestyksessä jossa vanha while-silmukka ne vieraili, joten Dependents- ja Precedents-aulokot täyttyvät samassa järjestyksessä ja topologinen järjestys pysyy deterministisenä. Sama pätee kahteen särmälajiin: ensin kirjattu kova särmä vaimentaa edelleen myöhemmän LookupScan-särmän samalle parille, kun taas kovan edellä kirjattu skannaussärmä pitää paikkansa — se ero joka estää lookup-alueita tuottamasta epätosia kehätviittauksia. Viittausta kohti kustannus putoaa ikkunan koosta O((k + 1) log n) -muotoon, jossa k on niiden kaavojen määrä joiden tulostus oikeasti ulottuu viitattuihin riveihin

Mitä tulostusindeksi takaa ja miten se varmistetaan?

TXLSDepGraph tuottaa samat särmät samassa järjestyksessä kuin ennen, ja uusi EdgeCandidateChecks-ominaisuus laskee kuinka monta tulossuorakulmiota viimeisin rakennus oikeasti testasi, joten väite on mitattava eikä retorinen. Regressiotesti EdgeBuildDeepChainsCheckOneCandidatePerDependency rakentaa pisteviittausketjut 1 024 ja 100 000 solmusta, lisättynä käänteisessä järjestyksessä pakottaakseen spatiaalisen lajittelun, ja vaatii täsmälleen N − 1 tarkistusta — 99 999 pitkälle ketjulle — sekä odotetut precedent-, dependent- ja topologiset järjestykset jokaiselle solmulle. Mukana kulkevat testit kattavat järjestyksen ulkopuolella lisätyt taulukkojuuret sheet-välien yli, tuplakovat ja lookup-scan-viittaukset (10 tarkistusta, yllä olevilla vaimennussäännöillä) sekä rakennuksen uudelleen AddNodein jälkeen, joka tyhjentää lajittelulipun joten seuraava BuildEdges tai NodeIndexOf rakentaa puun uudelleen ja nollaa laskurin sen kasaamisen sijaan

Mitkatut tulokset: 18,5 sekunnista noin 0,1 sekuntiin

Korjauksen edeltävä Win32-jäljitys, säilytetty projektin suorituskykybaselinenä versiolle 2.383.0, kirjasi kaksi pakotettua uudelleenlaskentaa 18 488 ms ja 19 578 ms. Indeksoinnin jälkeen kolme peräkkäistä kohdistettua ajoa arkkitehtuuria kohti mittasi 102,332–109,429 ms Win32:lla ja 116,990–133,995 ms Win64:lla, noin 170–180 kertaa nopeammin Win32:lla; korjauksen edeltävää Win64-baselinea ei kirjattu, joten Win64-kiihtyvyyttä ei väitetä. Samat ajot läpäisivät olemassa olevan portin joka pitää vain lukevan uudelleenlaskennan auditoinnin 1,35 kertaa pakotetun uudelleenlaskennan sisällä. Absoluuttiset luvut riippuvat koneesta ja sen kuormasta, joten toista kuorma omalla laitteistollesi ennen kuin lainaat niitä

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                     // 49 999 linkin ketju sarakkeessa A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 riippuvaista sarakkeessa B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // ensimmäinen kutsu rakentaa graafin
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Missä tulostusindeksi lopettaa auttamisen?

Puu karsii vain riveillä, ja se jättää muutaman rehellisen rajan jotka kannattaa tuntea ennen kuin suunnittelet sen ympärille hyvin suurta mallia

• Sarakkeiden ohi menot maksetaan yhä lehdissä: 2 626 kaavaa jotka täyttävät A100:Z200:n ulottuvat kaikki riville 100, joten viittaus AA100:AA200:een testaa jokaisen niistä ennen hylkäämistä
• Leveät viittaukset kuten kokonaisen sarakkeen alueet oikeasti omaavat monta edeltäjää; indeksi poistaa hukkatarkistuksia, ei oikeita särmäitä, ja niiden särmien rakentaminen on yhä verrannollinen niiden määrään
• Useita sheetejä ylittävillä viittauksilla tallennettu maksimi ohittaa sheetin, joten välisheettien kaavat syvillä tulostuksilla päätyvät lehtitestiin; tulokset pysyvät oikeina, vain karsinta on heikompaa
• Puu maksaa neljä kokonaislukua kaavasolmua kohti, noin 1,6 MB 100 000 solmulle, ja mikä tahansa AddNode mitätöi sen, joten topologian muutokset maksavat täyden O(n log n) -uudelleenlajittelun plus O(n)-puun rakennuksen seuraavassa särmärakennuksessa

Sama neliöllinen muoto raporttinauhojen nimikloonaamisessa

Versio 2.383.2 korjasi sisarongelman TXLSXDefinedNames.UniqueCloneNameissa: jokainen kopioitu määritelty nimi käynnisti jälkiliitehaun uudelleen kohdasta _2, joten toistuvat raporttinauhakopiot kasvoivat neliöllisesti nimihauissa. Skoopattujen nimien indeksi pitää nyt perusnimen ja skoopen mukaan pidettävää jälkiliitevihjettä ja tarkistaa viimeksi palautetun kandidaatin uudelleen, koska kutsuja ei välttämättä oikeastaan lisää sitä; nimen poistaminen, uudelleennimeäminen tai reskopaaminen mitätöi indeksin, mikä palauttaa ensimmäisen vapaan nimeämisen. Regressiopaketissa 1 024 peräkkäistä kloonaa tarvitsee 5 088 kandidaattihakua ja neljä vuorottelevaa perusnimeä 5 039, kun taas raporttibenchmarkin minimiarvot putosivat noin 240 ms:stä 18–20 ms:een. Raporttinauhojen ajoitusportti itsessään on yhä epävakaa — kolme kuudesta ajosta ylitti sen 1,05-suhteen ensimmäisessä korjauksen jälkeisessä yrityksessä — ja suorituskykyhistoria pitää ne epäonnistumiset kirjattuina sen sijaan että kynnystä viritettäisiin kunnes se läpäistään

Jos Delphi- tai C++Builder-sovelluksesi generoi tai laskee uudelleen suuria Excel-työkirjoja, Delphille ja C++Builderille tarkoitettu HotXLS Excel -komponentti toimittaa tämän indeksoidun riippuvuusgraafin uudelleenlaskentamoottorissaan molemmissa työkirjaluokissaan, klassisessa ja XLSX:ssä