Graf zależności HotXLS: indeks wyjść formuł tablicowych

HotXLS 2.383.1, natywna biblioteka Excela dla Delphi i C++Buildera, buduje krawędzie zależności formuł przez indeks przedziałów wyjściowych: węzły formuł pozostają posortowane po komórce kotwicy, a drzewo przedziałowe trzymające największy wiersz wyjścia (OutRow2) każdego poddrzewa pozwala TXLSDepGraph.BuildEdges pomijać całe bloki formuł, które nie mogą sięgnąć referencjonowanego zakresu. W skoroszycie Win32 z około 100 000 formuł wymuszone przeliczenie spadło z 18,488 sekundy do 102–109 milisekund

Nikt nie profiluje grafu zależności, dopóki zadanie wsadowe, które kiedyś trwało sekundę, nie zaczyna trwać dwadzieścia. Graf jest przebudowywany przy każdej zmianie topologii formuł — pierwsze Recalculate po wczytaniu albo wygenerowaniu skoroszytu, a także każdy przebieg po unieważnieniu grafu — i w śladzie sprzed poprawki sam ten pierwszy przebieg brał 16 074 ms. Ewaluacja nigdy nie była problemem; problemem było rozstrzyganie, kto od kogo zależy

Dlaczego przeliczenie 100 000 formuł brało 18 sekund?

Stary builder krawędzi był kwadratowy względem liczby formuł w arkuszu. Dla każdego zakresu zależności BuildEdges wyszukiwał binarnie okno kandydatów, a potem testował każdego z nich przez RangeIntersectsOutput, i to okno startowało od samej góry referencjonowanego arkusza. Klucze węzłów pochodzą z XLSDepMakeKey, która pakuje indeks arkusza od bitu 34 w górę, wiersz w bity 14–33, a kolumnę w bity 0–13, więc dolna granica (Sheet1, 0, 0) znaczyła „każdą formułę od wiersza 1 aż po dół referencjonowanego zakresu”

// Przed 2.383.1 — TXLSDepGraph.BuildEdges, dla zakresu zależności r węzła d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // góra arkusza
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...dwa wyszukiwania binarne po FNodeOrder dają okno [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // twarda krawędź albo krawędź LookupScan, deduplikowane przez EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Fixture wydajnościowy, który to wychwycił, to zwykły kaskadowy model: A2:A50000 dodają po jednym do komórki wyżej, a B1:B50000 podwajają sąsiada w kolumnie A. Referencja do wiersza r ciągnęła więc około 2r kandydatów przez test prostokąta, więc pojedyncza budowa grafu wykonywała rzędu pięciu miliardów sprawdzeń przecięcia — szacunek na kolanie, ale zgadza się z 18,5 sekundy na zegarze. Każde sprawdzenie odpowiadało „nie”, poza jednym czy dwoma

Dlaczego builder krawędzi nie może zacząć szukania od referencjonowanego wiersza?

Bo formuła tablicowa zakotwiczona nad zakresem może posiadać komórki wewnątrz niego. Każdy TXLSDepNode opisuje prostokąt wyjścia od swojej kotwicy (Row, Col) do (OutRow2, OutCol2), a formuła tablicowa CSE dostaje jeden węzeł dla całego swojego prostokąta, jak wyjaśnia artykuł o przeliczaniu przyrostowym i grafie zależności. Korzeń zakotwiczony w A1, który wypełnia A1:A10, musi wciąż dostać krawędź od formuły czytającej tylko A5; zacznij wyszukiwanie binarne od wiersza 5, a ta krawędź cicho znika, co oznacza nieaktualną wartość z cache w wysłanym raporcie zamiast wolnej. Zapytanie jest naprawdę dwustronne — kotwica na Row2 albo przed nim, wyjście sięgające co najmniej Row1 — i jeden porządek sortowania nie odpowie na obie połowy. Wyniki wielokomórkowe pojawiają się też w nowoczesnych skoroszytach, a artykuł o formułach rozlewanych dynamicznych tablic opisuje, jak rozlane zakresy zachowują się w HotXLS

Drzewo przedziałowe maksymalnych wierszy wyjścia

HotXLS zostawia sortowanie po kotwicy dla górnej granicy i dodaje augmentowane drzewo przedziałowe dla dolnej. BuildNodeIndex sortuje FNodeOrder po kluczu węzła jak dawniej, a potem BuildMaxOutRowTree wypełnia FNodeMaxOutRow2 (alokowane po cztery wpisy na węzeł) największym OutRow2 znalezionym pod każdym poddrzewem. QueryNodeTree schodzi tylko wewnątrz okna kluczy i porzuca każde poddrzewo, którego maksymalny wiersz wyjścia leży nad FRanges[r].Row1, bo żadna formuła w nim nie sięgnie referencjonowanych wierszy. Liście, które przeżyją, i tak przechodzą pełny test RangeIntersectsOutput, więc zakresy arkuszy i kolumny są sprawdzane dokładnie jak dawniej

// TXLSDepGraph.BuildNodeIndex / BuildEdges od 2.383.1 (lekko skrócone)
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
  // poza oknem kluczy albo żadne wyjście w tym poddrzewie nie sięga 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
      // bez zmian: tłumienie EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // najpierw lewe poddrzewo
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // zachowuje stary porządek
end;

Rekurencja najpierw-lewe-potem-prawe to nie wybór stylistyczny. Ocalałe liście są odwiedzane dokładnie w tej kolejności, w jakiej odwiedzała je stara pętla while, więc tablice Dependents i Precedents wypełniają się w tej samej sekwencji, a porządek topologiczny pozostaje deterministyczny. To samo dotyczy dwóch rodzajów krawędzi: twarda krawędź zapisana pierwsza wciąż tłumi późniejszą krawędź LookupScan dla tej samej pary, a krawędź skanująca zapisana przed twardą zachowuje swoje miejsce — to rozróżnienie, które nie pozwala zakresom wyszukiwania produkować fałszywych odwołań cyklicznych. Na jedną referencję koszt spada z rozmiaru okna do O((k + 1) log n), gdzie k to liczba formuł, których wyjście faktycznie sięga referencjonowanych wierszy

Co gwarantuje indeks wyjść i jak to zweryfikowano?

TXLSDepGraph produkuje te same krawędzie w tej samej kolejności co dawniej, a nowa właściwość EdgeCandidateChecks liczy, ile prostokątów wyjścia ostatnia budowa faktycznie przetestowała, więc teza jest mierzalna, a nie retoryczna. Test regresyjny EdgeBuildDeepChainsCheckOneCandidatePerDependency buduje łańcuchy referencji punktowych z 1 024 i 100 000 węzłów, wstawianych w odwrotnej kolejności, żeby wymusić sortowanie przestrzenne, i asertuje dokładnie N − 1 sprawdzeń — 99 999 dla długiego łańcucha — plus oczekiwany porządek precedentów, zależnych i topologiczny dla każdego węzła. Testy towarzyszące obejmują korzenie tablicowe wstawiane nie po kolei przez zakresy arkuszy, zduplikowane referencje twarde i lookup-scan (10 sprawdzeń, z regułami tłumienia jak wyżej) oraz przebudowę po AddNode, która czyści flagę sortowania, więc następne BuildEdges albo NodeIndexOf przebudowuje drzewo i resetuje licznik zamiast go akumulować

Zmierzone wyniki: z 18,5 sekundy do około 0,1 sekundy

Ślad Win32 sprzed poprawki, zachowany w wydajnościowej bazie projektowej dla wersji 2.383.0, zapisał dwa wymuszone przeliczenia: 18 488 ms i 19 578 ms. Po indeksowaniu trzy seryjne ukierunkowane uruchomienia na architekturę zmierzyły 102,332–109,429 ms na Win32 i 116,990–133,995 ms na Win64, czyli około 170 do 180 razy szybciej na Win32; bazy Win64 sprzed poprawki nie zapisano, więc przyspieszenia dla Win64 się nie deklaruje. Te same uruchomienia przeszły istniejącą bramkę, która trzyma audyt przeliczania tylko do odczytu w granicach 1,35 wymuszonego przeliczenia. Liczby absolutne zależą od maszyny i jej obciążenia, więc zanim je zacytujesz, odtwórz workload na własnym sprzęcie

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                     // łańcuch 49 999 ogniw w kolumnie A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 zależnych w kolumnie B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

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

Gdzie indeks wyjść przestaje pomagać?

Drzewo przycina tylko po wierszach, co zostawia kilka uczciwych ograniczeń, które warto znać, zanim zbudujesz wokół niego bardzo duży model

• Pudła po kolumnach wciąż są płatne na liściach: 2 626 formuł wypełniających A100:Z200 wszystkich sięga wiersza 100, więc referencja do AA100:AA200 przetestuje każdą, zanim ją odrzuci
• Szerokie referencje, jak zakresy całych kolumn, naprawdę mają wiele precedensów; indeks usuwa zmarnowane sprawdzenia, a nie prawdziwe krawędzie, i zbudowanie tych krawędzi wciąż jest proporcjonalne do ich liczby
• Dla referencji obejmujących kilka arkuszy zapisane maksimum ignoruje arkusz, więc formuły na pośrednich arkuszach z głębokimi wyjściami docierają do testu liścia; wyniki pozostają poprawne, słabsze jest tylko przycinanie
• Drzewo kosztuje cztery liczby całkowite na węzeł formuły, około 1,6 MB dla 100 000 węzłów, a każde AddNode je unieważnia, więc zmiany topologii płacą pełne przesortowanie O(n log n) plus budowę drzewa O(n) przy następnej budowie krawędzi

Ta sama kwadratowa sylwetka w klonowaniu nazw pasów raportu

Wersja 2.383.2 naprawiła siostrzany problem w TXLSXDefinedNames.UniqueCloneName: każda skopiowana nazwa zdefiniowana zaczynała szukanie sufiksu od _2, więc powtarzane kopie pasów raportu rosły kwadratowo w wyszukiwaniach nazw. Indeks nazw zakresowych trzyma teraz podpowiedź sufiksu per nazwa bazowa i per zakres i ponownie sprawdza ostatnio zwróconego kandydata, bo wywołujący może go faktycznie nie dodać; usunięcie, przemianowanie albo przeniesienie nazwy do innego zakresu unieważnia indeks, co przywraca nazewnictwo pierwszego wolnego. W zestawie regresyjnym 1 024 sekwencyjne klony potrzebują 5 088 wyszukań kandydatów, a cztery naprzemienne nazwy bazowe 5 039, podczas gdy minima benchmarku raportów spadły z około 240 ms do 18–20 ms. Bramka czasowa pasów raportu sama w sobie wciąż nie jest stabilna — trzy z sześciu uruchomień przekroczyły jej współczynnik 1,05 przy pierwszej próbie po poprawce — i historia wydajności odnotowuje te porażki, zamiast dostrajać próg do skutku

Jeśli twoja aplikacja w Delphi albo C++Builderze generuje albo przelicza duże skoroszyty Excela, komponent Excel HotXLS dla Delphi i C++Buildera dostarcza ten indeksowany graf zależności w silniku przeliczania dla obu swoich klas skoroszytów — klasycznej i XLSX