HotXLS priklausomybių grafas: formulių išvesčių indeksas

HotXLS 2.383.1, savoji Excel biblioteka Delphi ir C++Builder, formulių priklausomybių briaunas stato per išvesčių intervalų indeksą: formulių mazgai lieka surūšiuoti pagal inkaro ląstelę, o segmentų medis, laikantis didžiausią kiekvieno pomedžio išvesties eilutę (OutRow2), leidžia TXLSDepGraph.BuildEdges praleisti ištisas formulių blokas, kurie negali pasiekti nuorodos diapazono. Win32 darbaknygėje su maždaug 100 000 formulių priverstinis perskaičiavimas nukrito nuo 18,488 sekundžių iki 102–109 milisekundžių

Niekas neprofilioja priklausomybių grafo, kol paketinė užduotis, anksčiau užimdavusi sekundę, nepradeda užimti dvidešimties. Grafas perstatomas kaskart pasikeitus formulių topologijai — pirmasis Recalculate po darbaknygės įkėlimo ar sugeneravimo arba bet koks žingsnis po to, kai grafas panaikintas — ir prieš pataisą atliktame sekime vien tas pirmasis žingsnis užėmė 16 074 ms. Vertinimas niekada nebuvo problema; problema buvo nuspręsti, kas nuo ko priklauso

Kodėl 100 000 formulių perskaičiavimas užimdavo 18 sekundžių?

Senasis briaunų statytojas, skaičiuojant lapo formulių skaičių, buvo kvadratinis. Kiekvienam priklausomybių diapazonui BuildEdges dvejetaine paieška surasdavo kandidatų mazgų langą ir paskui kiekvieną išbandydavo su RangeIntersectsOutput, o tas langas prasidėdavo nuo pat nuorodoje nurodyto lapo viršaus. Mazgų raktai ateina iš XLSDepMakeKey, kuris lapo indeksą supakoja nuo 34 bito aukštyn, eilutę — į 14–33 bitus, o stulpelį — į 0–13 bitus, tad apatinė riba (Sheet1, 0, 0) reiškė „kiekvieną formulę nuo 1 eilutės žemyn iki nuorodos diapazono apačios“

// Iki 2.383.1 — TXLSDepGraph.BuildEdges, mazgo d priklausomybių diapazonui r
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // lapo viršus
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...dvi dvejetainės paieškos per FNodeOrder duoda langą [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // kieta briauna arba LookupScan briauna, dubliavimams per EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Šį defektą atskleidė paprastas kaskadinis našumo pavyzdys: A2:A50000 kiekvienas prideda vienetą prie ląstelės aukščiau, o B1:B50000 kiekvienas padvigubina kaimyną A stulpelyje. Nuoroda į eilutę r tad per stačiakampio testą vilkdavo apie 2r kandidatų, tad vienas grafo statymas atlikdavo penkių milijardų eilės sankirtos patikrų — apskaičiavimas ant popieriaus lapelio, bet jis sutampa su 18,5 sekundėmis laikrodyje. Kiekviena patikra sakdavo „ne“, išskyrus vieną kitą

Kodėl briaunų statytojas negali pradėti paieškos nuo nuorodos eilutės?

Nes masyvinė formulė, įvinkaruota aukščiau diapazono, gali valdyti ląsteles jo viduje. Kiekvienas TXLSDepNode apibūdina išvesties stačiakampį nuo savo inkaro (Row, Col) iki (OutRow2, OutCol2), o CSE masyvinė formulė gauna vieną mazgą visam savo stačiakampiui, kaip aiškina straipsnis apie inkrementinį perskaičiavimą ir priklausomybių grafą. Šaknis, įvinkaruota ties A1 ir užpildanti A1:A10, vis tiek turi gauti briauną iš formulės, skaitančios vien A5; pradėję dvejetainę paiešką nuo 5 eilutės tą briauną tyliai prarasite, o tai reiškia pasenusią podėlio reikšmę išsiųstoje ataskaitoje vietoj lėtos. Užklausa iš tikrųjų dvipusė — inkaras ties Row2 ar aukščiau, išvestis, siekianti bent Row1 — ir viena rūšiavimo tvarka abiejų pusių neatsako. Kelialąsteliai rezultatai šiuolaikinėse darbaknygėse irgi pasirodo, o straipsnis apie dinamines masyvines spill formules dengia, kaip išsiliejantys diapazonai elgiasi HotXLS

Segmentų medis didžiausioms išvesties eilutėms

HotXLS palieka inkaro rūšiavimą viršutinei ribai ir prideda papildytą segmentų medį apatinei ribai. BuildNodeIndex surūšiuoja FNodeOrder pagal mazgo raktą kaip ir anksčiau, tada BuildMaxOutRowTree užpildo FNodeMaxOutRow2 (priskirtą po keturis įrašus mazgui) didžiausiu kiekvieno pomedžio rastu OutRow2. QueryNodeTree leidžiasi tik rakto lango viduje ir apleidžia bet kokį pomedį, kurio didžiausia išvesties eilutė yra aukščiau FRanges[r].Row1, nes jokia jo formulė negali pasiekti nuorodos eilučių. Išgyvenę lapai vis tiek praeina pilną RangeIntersectsOutput testą, tad lapų apimtys ir stulpeliai tikrinami lygiai kaip anksčiau

// TXLSDepGraph.BuildNodeIndex / BuildEdges nuo 2.383.1 (truputį sutrumpinta)
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
  // už rakto lango, arba jokia šio pomedžio išvestis nesiekia 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
      // nepakinta: EdgeStamp / ScanStamp slopinimas, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // pirmiausia kairysis pomedis
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // išlaiko seną tvarką
end;

Kairysis-prieš-dešinįjį rekursija nėra stiliaus pasirinkimas. Išgyvenę lapai aplankomi lygiai ta tvarka, kuria juos aplankydavo senasis while ciklas, tad Dependents ir Precedents masyvai užpildomi ta pačia seka, o topologinė tvarka lieka deterministinė. Tas pats galioja abiem briaunų rūšims: pirmiausia užregistruota kieta briauna ir toliau slopina vėlesnę LookupScan briauną tai pačiai porai, o prieš kieta užregistruota skenavimo briauna išlaiko savo vietą — tas skirtumas, neleidžiantis paieškos diapazonams gaminti netikrų ciklinių nuorodų. Vienai nuorodai kaina nukrinta nuo lango dydžio iki O((k + 1) log n), kur k yra formulių, kurių išvestis iš tikrųjų pasiekia nuorodos eilutes, skaičius

Ką garantuoja išvesčių indeksas ir kaip tai patikrinama?

TXLSDepGraph duoda tas pačias briaunas ta pačia tvarka kaip anksčiau, o naujoji EdgeCandidateChecks savybė suskaičiuoja, kiek išvesties stačiakampių paskutinis statymas iš tiesų išbandė, tad teiginys išmatuojamas, o ne retorinis. Regresinis testas EdgeBuildDeepChainsCheckOneCandidatePerDependency stato taškinių nuorodų grandines iš 1 024 ir 100 000 mazgų, įterptų atvirkštine tvarka, kad priverstų erdvinį rūšiavimą, ir tiksliai reikalauja N − 1 patikros — 99 999 ilgoji grandinė — plius tikėtos precedento, priklausinio ir topologinės tvarkos kiekvienam mazgui. Pagalbiniai testai dengia netvarkingai įterptas per lapų apimtis masyvines šaknis, pasikartojančias kietas ir paieškos-skenavimo nuorodas (10 patikrų, su aukščiau aprašytomis slopinimo taisyklėmis) ir perstatymą po AddNode, kuris išvalo rūšiavimo žymę, tad kitas BuildEdges ar NodeIndexOf medį perstato ir skaitiklį nuresetina, užuot jį kaupęs

Išmatuoti rezultatai: nuo 18,5 sekundžių iki maždaug 0,1 sekundės

Prieš pataisą atliktas Win32 seimas, paliktas projekto našumo bazinėje linijoje versijai 2.383.0, užfiksavo du priverstinius perskaičiavimus po 18 488 ms ir 19 578 ms. Po indeksavimo trys iš eilės einantys fokusuoti paleidimai kiekvienai architektūrai išmatavo 102,332–109,429 ms Win32 ir 116,990–133,995 ms Win64, maždaug 170–180 kartų greičiau Win32; prieš pataisą Win64 bazinė linija neužfiksuota, tad jokio Win64 pagreitėjimo neteigiama. Tie patys paleidimai praeino esamus vartus, laikančius tik skaitomo perskaičiavimo auditą per 1,35 karto nuo priverstinio perskaičiavimo. Absoliutūs skaičiai priklauso nuo mašinos ir jos apkrovos, tad prieš cituodami atkartokite darbo krūvį savo geležyje

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 nuorodų grandinė A stulpelyje
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 priklausinių B stulpelyje
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

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

Kur išvesčių indeksas nustoja padėti?

Medis genėja tik pagal eilutes, ir tai palieka kelias sąžiningas ribas, vertas žinoti, prieš aplink jį sudėliojant labai didelį modelį

• Už stulpelių nepataikymus vis tiek mokama lapuose: 2 626 formulės, užpildančios A100:Z200, visos pasiekia 100 eilutę, tad nuoroda į AA100:AA200 kiekvieną jų išbando prieš atmesdama
• Plačios nuorodos, tokios kaip ištisi stulpeliai, iš tikrųjų turi daug precedentų; indeksas pašalina iššvaistytas patikras, o ne tikras briaunas, ir tų briaunų statymas vis tiek proporcingas jų skaičiui
• Keliems lapams besitęsiančioms nuorodoms saugomas maksimumas ignoriuoja lapą, tad tarpinių lapų formulės su giliomis išvestimis nueina iki lapų testo; rezultatai lieka teisingi, silpnesnis tik genėjimas
• Medis kainuoja keturis sveikuosius vienam formulių mazgui, apie 1,6 MB už 100 000 mazgų, ir bet koks AddNode jį panaikina, tad topologijos pokyčiai moka pilną O(n log n) per-rūšiavimą plius O(n) medžio statymą kito briaunų statymo metu

Ta pati kvadratinė forma ataskaitos juostų vardų klonavime

Versija 2.383.2 sutvarkė brolio problemą TXLSXDefinedNames.UniqueCloneName: kiekvienas nukopijuotas apibrėžtas vardas savo priesagos paiešką paleisdavo iš naujo nuo _2, tad pasikartojančios ataskaitos juostų kopijos vardų paieškose augdavo kvadratiškai. Apibrėžtų vardų indeksas dabar laiko priesagos užuominą pagal bazinį vardą ir pagal aprėptį ir dar kartą patikrina paskutinį grąžintą kandidatą, nes kvietėjas jo gali ir nepridėti; ištrynus, pervadinus ar pakeitus vardo aprėptį indeksas panaikinamas, o tai atstato pirmojo laisvo vardavimo tvarką. Regresiniame rinkinyje 1 024 iš eilės klonams reikia 5 088 kandidatų paieškų, keturiems kaitaliojamiems baziniams vardams — 5 039, o ataskaitos benchmark minimumai nukrito nuo maždaug 240 ms iki 18–20 ms. Pats ataskaitos juostų laiko vartai vis dar nestabilūs — pirmame po pataisos paleidime trys iš šešių pranoko jų 1,05 santykį — ir našumo istorija tuos nesėkmes palieka įrašytas, užuot šlifavusi slenkstį, kol praeis

Jei jūsų Delphi ar C++Builder programa generuoja ar perskaičiuoja didelias Excel darbaknyges, HotXLS Excel komponentas Delphi ir C++Builder šį indeksuotą priklausomybių grafą neša perskaičiavimo variklyje abiem savo darbaknygių klasėms — ir klasikinei, ir XLSX