HotXLS függőséggráf: tömbképletek kimeneteinek indexelése

A HotXLS 2.383.1, a natív Excel könyvtár Delphihez és C++Builderhez, kimeneti intervallumindexen keresztül építi a képletfüggőségi éleket: a képletcsomópontok horgonycella szerint rendezve maradnak, és a minden részfának a legnagyobb kimeneti sorát (OutRow2) tároló szegmenfa lehetővé teszi, hogy a TXLSDepGraph.BuildEdges átugorja azokat a képletblokkokat, amelyek nem érhetik el a hivatkozott tartományt. Egy nagyjából 100 000 képletet hordozó Win32 munkafüzetnél a kényszerített újraszámolás 18,488 másodpercről 102–109 milliszekundumra esett

Senki nem profilozza a függőséggráfot, addig, míg egy eddig egy másodpercig futó kötegelt feladat húszat nem kezd el venni. A gráf minden alkalommal újraépül, amikor a képlet topológiája változik — az első Recalculate egy munkafüzet betöltése vagy generálása után, illetve bármely menet, miután a gráf érvénytelenné vált —, és a javítás előtti trace-ben már ez az első menet is 16 074 ms-ot vett el. A kiértékelés soha nem volt a probléma; az, hogy eldöntsék, ki kitől függ, az volt

Miért vett el 18 másodpercet 100 000 képlet újraszámolása?

A régi élépítő a munkalap képleteinek darabszámában kvadratikus volt. Minden függőségi tartományra a BuildEdges binárisan kereste meg a jelöltcsomópontok ablakát, majd mindegyiket a RangeIntersectsOutput-tal tesztelte, és ez az ablak a hivatkozott munkalap legtetejénél kezdődött. A csomópontkulcsok a XLSDepMakeKey-ből jönnek, amely a munkalapindexet a 34. bit fölé, a sort a 14–33. bitekbe, az oszlopot a 0–13. bitekbe csomagolja, így az alsó határ, a (Sheet1, 0, 0), azt jelentette: minden képlet az 1. sortól a hivatkozott tartomány aljáig

// 2.383.1 előtt — TXLSDepGraph.BuildEdges, a d csomópont r függőségi tartományára
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // a munkalap teteje
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...két bináris keresés az FNodeOrder felett adja az [i, Lo) ablakot...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // kemény él vagy LookupScan él, EdgeStamp / ScanStamp útján deduplikálva
  end;
  Inc(i);
end;

Az ezt leleplező teljesítményfixtúra egy hétköznapi kaszkádmodell: az A2:A50000 mindegyike eggyel növeli a felette lévő cellát, a B1:B50000 mindegyike pedig megduplázza az A oszlopbeli szomszédját. Egy az r. sorra hivatkozás ezért nagyjából 2r jelöltet húzott végig a téglalapteszten, így egyetlen gráfépítés ötmilliárd metszésellenőrzés nagyságrendjét végezte el — borítékra írt becslés, de egyezik az órán álló 18,5 másodperccel. Minden ellenőrzés „nem"-et mondott, egy vagy két kivételével

Miért nem kezdheti az élépítő a keresést a hivatkozott sornál?

Mert egy tartomány felett horgonyzott tömbképlet birtokolhat cellákat belül is. Minden TXLSDepNode egy kimeneti téglalapot ír le a horgonyától (Row, Col) a (OutRow2, OutCol2) koordinátáig, és egy CSE tömbképlet a teljes téglalapjára kap egy csomópontot, ahogy az a növekményes újraszámolásról és a függőséggráfról szóló cikk is kifejti. Az A1-nél horgonyzó, az A1:A10-et kitöltő gyökérnek is élt kell kapnia egy olyan képlettől, amely csak az A5-öt olvassa; ha a bináris keresés az 5. sornál indul, az él csendben eltűnik, ami kiszállított jelentésben elavult gyorsítótár-értéket jelent egy lassú helyett. A lekérdezés valójában kétoldalú — horgony a Row2-n vagy azelőtt, kimenet elérve legalább a Row1-et —, és egyetlen rendezési sorrend nem tudja mindkét felét megválaszolni. A többcellás eredmények a modern munkafüzetekben is felbukkannak, a dinamikus tömb spill képletekről szóló cikk pedig bemutatja, hogyan viselkednek a kifolyó tartományok a HotXLS-ben

Szegmenfa a maximális kimenetsorokból

A HotXLS megtartja a horgonyrendezést a felső határhoz, és egy kiegészített szegmenfát ad hozzá az alsó határhoz. A BuildNodeIndex a FNodeOrder-t a régi módon csomópontkulcs szerint rendezi, a BuildMaxOutRowTree pedig feltölti a FNodeMaxOutRow2-öt (csomópontonként négy bejegyzésre foglalva) minden részfában talált legnagyobb OutRow2-vel. A QueryNodeTree csak a kulcsablakon belül ereszkedik, és felad minden részfát, amelynek maximális kimenetsora a FRanges[r].Row1 fölött van, mert benne egyetlen képlet sem érheti el a hivatkozott sorokat. A túlélő levelek mindegyike továbbra is átmegy a teljes RangeIntersectsOutput teszten, így a munkalapterjedelmek és az oszlopok pontosan a régi módon ellenőrződnek

// TXLSDepGraph.BuildNodeIndex / BuildEdges 2.383.1 óta (enyhén sűrítve)
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
  // a kulcsablakon kívül, vagy ebben a részfában egyetlen kimenet sem éri el a Row1-et
  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
      // változatlan: EdgeStamp / ScanStamp elnyomás, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // először a bal részfa
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // megtartja a régi sorrendet
end;

A bal-előbb-jobb rekurzió nem stílusbeli választás. A túlélő levelek pontosan abban a sorrendben kerülnek felkeresésre, ahogy a régi while ciklus tette, így a Dependents és Precedents tömbök ugyanabban a sorrendben töltődnek, és a topológiai sorrend determinisztikus marad. Ugyanez érvényes a két élfajtára: a korábban rögzített kemény él továbbra is elnyomja ugyanannak a párnak egy későbbi LookupScan élét, míg a kemény él előtt rögzített scan él megtartja a helyét — ez az a különbségtétel, amely megakadályozza, hogy a lookup tartományok hamis körkörös hivatkozásokat termeljenek. Hivatkozásonként a költség az ablak méretéről O((k + 1) log n)-re esik, ahol k azoknak a képleteknek a száma, amelyek kimenete ténylegesen eléri a hivatkozott sorokat

Mit garantál a kimeneti index, és hogyan ellenőrzik?

A TXLSDepGraph ugyanazokat az éleket termeli ugyanabban a sorrendben, mint korábban, az új EdgeCandidateChecks tulajdonság pedig megszámolja, hány kimeneti téglalapot tesztelt ténylegesen a legutóbbi építés, így az állítás mérhető, nem pedig retorikai. Az EdgeBuildDeepChainsCheckOneCandidatePerDependency regressziós teszt 1024 és 100 000 csomópontos pontreferencia-láncokat épít, fordított sorrendben beszúrva, hogy kikényszerítse a térbeli rendezést, és pontosan N − 1 ellenőrzést állít — a hosszú láncnál 99 999-et —, plusz minden csomópontra a várt precedenst, dependenst és topológiai sorrendet. A kísérő tesztek lefedik a munkalapterjedelmeken át rendezetlenül beszúrt tömbgyökereket, a duplikált kemény és lookup-scan hivatkozásokat (10 ellenőrzés, a fenti elnyomási szabályokkal), valamint az AddNode utáni újraépítést, amely törli a rendezési jelzőt, így a következő BuildEdges vagy NodeIndexOf újraépíti a fát és visszaállítja a számlálót, ahelyett hogy halmozná

Mért eredmények: 18,5 másodpercről nagyjából 0,1 másodpercre

A javítás előtti Win32 trace, amely a 2.383.0-s verzió projekt teljesítménybázisában megőrződött, két kényszerített újraszámolást rögzített, 18 488 és 19 578 ms értékkel. Az indexelés után architektúránként három soros fókuszált futás 102,332–109,429 ms-ot mért Win32-n és 116,990–133,995 ms-ot Win64-en, nagyjából 170–180-szoros gyorsulás Win32-n; javítás előtti Win64 bázis nem rögzült, ezért Win64 gyorsulást nem állítunk. Ugyanezek a futások átmentek a meglévő kapun, amely a csak olvasható újraszámolási auditot a kényszerített újraszámolás 1,35-szörösén belül tartja. Az abszolút számok a géptől és annak terhelésétől függenek, ezért idézés előtt reprodukálja a terhelést a saját hardverén

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 láncszemes lánc az A oszlopban
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 függő a B oszlopban
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // az első hívás megépíti a gráfot
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Hol válik haszontalanná a kimeneti index?

A fa csak a sorokra metsz, és ez néhány becsületes határt hagy, amelyeket érdemes ismerni, mielőtt nagyon nagy modellt építene rá

• Az oszlopmellélövéseket továbbra is a leveleken fizeti meg: az A100:Z200-t kitöltő 2626 képlet mind eléri a 100. sort, így egy az AA100:AA200-ra hivatkozás mindegyiket leteszteli, mielőtt elutasítaná
• A tág hivatkozások, például az egész oszlopos tartományok, valóban sok precedenssel rendelkeznek; az index a pazarló ellenőrzéseket veszi el, nem a valódi éleket, és ezen élek megépítése továbbra is a darabszámukkal arányos
• Több munkalapot átívelő hivatkozásoknál a tárolt maximum figyelmen kívül hagyja a munkalapot, így a köztes munkalapokon ülő, mély kimenetű képletek eljutnak a levéltesztig; az eredmények helyesek maradnak, csak a metszés gyengébb
• A fa képletcsomópontonként négy egész számot visz, 100 000 csomópontnál nagyjából 1,6 MB-ot, és bármely AddNode érvényteleníti, így a topológiaváltozás teljes O(n log n) újarendezést fizet, a következő élépítésen pedig O(n) faépítést

Ugyanaz a kvadratikus alak a jelentéssáv-nevek klónozásában

A 2.383.2-es verzió egy testvérproblémát javított a TXLSXDefinedNames.UniqueCloneName-ben: minden másolt definiált név újraindította az utótagkeresését a _2-nél, így az ismételt jelentéssáv-mások kvadratikusan duzzadtak a névkeresésekben. A hatókörrel rendelkező névindex mostantól bázisnévenként és hatókörönként utótagemlékeztetőt tart, és újraellenőrzi az utoljára visszaadott jelöltet, mert előfordulhat, hogy a hívó valójában nem adja hozzá; a név törlése, átnevezése vagy más hatókörbe helyezése érvényteleníti az indexet, ami visszaállítja az első szabad elnevezést. A regressziós készletben 1024 szekvenciális klón 5088 jelöltkeresést igényel, négy váltakozó bázisnév 5039-et, miközben a jelentésbenchmark minimumai nagyjából 240 ms-ról 18–20 ms-ra estek. Maga a jelentéssáv-időzítési kapu továbbra sem stabil — a javítás utáni első kísérletben hat futásból három lépte túl az 1,05-ös arányát —, és a teljesítménytörténet nyilvántartja ezeket a kudarcokat ahelyett, hogy addig csiszolná a küszöböt, míg át nem megy

Ha az Ön Delphi vagy C++Builder alkalmazása nagy Excel munkafüzeteket generál vagy újraszámol, a HotXLS Excel komponens Delphihez és C++Builderhez az újraszámolási motorjában szállítja ezt az indexelt függőséggráfot, klasszikus és XLSX munkafüzetosztályaihoz egyaránt