Γράφος εξαρτήσεων HotXLS: δεικτοδότηση εξόδων τύπων array

Το HotXLS 2.383.1, η native βιβλιοθήκη Excel για Delphi και C++Builder, χτίζει τις ακμές εξάρτησης τύπων μέσα από έναν δείκτη διαστημάτων εξόδων: οι κόμβοι τύπων μένουν ταξινομημένοι κατά κελί άγκυρας, και ένα segment tree που κρατάει τη μεγαλύτερη γραμμή εξόδου (OutRow2) κάθε υποδένδρου αφήνει το TXLSDepGraph.BuildEdges να προσπερνάει ολόκληρα μπλοκ τύπων που δεν μπορούν να φτάσουν ένα αναφερόμενο εύρος. Σε ένα workbook Win32 με περίπου 100.000 τύπους, ο εξαναγκασμένος επανυπολογισμός έπεσε από 18.488 δευτερόλεπτα σε 102–109 milliseconds

Κανείς δεν κάνει profiling τον γράφο εξαρτήσεων μέχρι μια batch εργασία που άργησε ένα δευτερόλεπτο να αρχίσει να αργεί είκοσι. Ο γράφος ξαναχτίζεται όποτε αλλάζει η τοπολογία των τύπων — το πρώτο Recalculate μετά το φόρτωμα ή τη δημιουργία ενός workbook, ή οποιοδήποτε πέρασμα αφού ο γράφος έχει ακυρωθεί — και στο trace πριν τη διόρθωση μόνο εκείνο το πρώτο πέρασμα πήρε 16.074 ms. Η αξιολόγηση δεν ήταν ποτέ το πρόβλημα· το πρόβλημα ήταν να αποφασίσεις ποιος εξαρτάται από ποιον

Γιατί ο επανυπολογισμός 100.000 τύπων κράταγε 18 δευτερόλεπτα;

Ο παλιός builder ακμών ήταν τετραγωνικός ως προς το πλήθος των τύπων σε ένα sheet. Για κάθε εύρος εξάρτησης, το BuildEdges έκανε δυαδική αναζήτηση ενός παραθύρου υποψήφιων κόμβων και μετά τεστούσε τον καθένα με RangeIntersectsOutput, και εκείνο το παράθυρο ξεκινούσε από την κορυφή του αναφερόμενου sheet. Τα κλειδιά των κόμβων βγαίνουν από το XLSDepMakeKey, που πακέταρει τον δείκτη sheet από το bit 34 και πάνω, τη γραμμή στα bits 14–33, και τη στήλη στα bits 0–13, οπότε το κάτω όριο (Sheet1, 0, 0) σήμαινε «κάθε τύπος από τη γραμμή 1 μέχρι τον πάτο του αναφερόμενου εύρους»

// Πριν το 2.383.1 - TXLSDepGraph.BuildEdges, για το εύρος εξάρτησης r του κόμβου d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // κορυφή του sheet
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...δύο δυαδικές αναζητήσεις πάνω στο FNodeOrder παράγουν το παράθυρο [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // σκληρή ακμή ή ακμή LookupScan, χωρίς διπλότυπα μέσω EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Το performance fixture που το ξεσκέπασε είναι ένα συνηθισμένο καταρρακτωό μοντέλο: τα A2:A50000 προσθέτουν από ένα στο κελί από πάνω, και τα B1:B50000 διπλασιάζουν από έναν τον γείτονα στη στήλη A. Μια αναφορά στη γραμμή r παρέσυρε επομένως περίπου 2r υποψηφίους μέσα από το τεστ του ορθογωνίου, ώστε ένα μοναδικό χτίσιμο γράφου εκτελούσε της τάξης των πέντε δισεκατομμυρίων ελέγχων τομής — μια εκτίμηση στον πάτο του φακέλου, αλλά συμφωνεί με τα 18,5 δευτερόλεπτα στο ρολόι. Κάθε έλεγχος έλεγε «όχι» εκτός από έναν ή δύο

Γιατί ο builder ακμών δεν μπορεί να ξεκινήσει την αναζήτηση από την αναφερόμενη γραμμή;

Επειδή ένας τύπος array αγκυρωμένος πάνω από ένα εύρος μπορεί να κατέχει κελιά μέσα του. Κάθε TXLSDepNode περιγράφει ένα ορθογώνιο εξόδου από την άγκυρά του (Row, Col) ως το (OutRow2, OutCol2), και ένας τύπος CSE array παίρνει έναν κόμβο για ολόκληρο το ορθογώνιό του, όπως εξηγεί το άρθρο για τον σταδιακό επανυπολογισμό και τον γράφο εξαρτήσεων. Μια ρίζα αγκυρωμένη στο A1 που γεμίζει το A1:A10 πρέπει να εξακολουθεί να παίρνει ακμή από έναν τύπο που διαβάζει μόνο το A5· ξεκινήστε τη δυαδική αναζήτηση από τη γραμμή 5 και εκείνη η ακμή εξαφανίζεται σιωπηλά, που σημαίνει μια πεπαλαιωμένη cached τιμή σε ένα παραδοτέο report αντί για ένα αργό. Το query είναι στην πραγματικότητα δίπλευρο — άγκυρα στο ή πριν το Row2, έξοδος που φτάνει τουλάχιστον το Row1 — και μία σειρά ταξινόμησης δεν μπορεί να απαντήσει και τα δύο μισά. Αποτελέσματα πολλών κελιών εμφανίζονται και στα σύγχρονα workbooks, και το άρθρο για τους τύπους spill δυναμικών array καλύπτει πώς συμπεριφέρονται τα spilled ranges στο HotXLS

Ένα segment tree μέγιστων γραμμών εξόδου

Το HotXLS κρατάει την ταξινόμηση κατά άγκυρα για το πάνω όριο και προσθέτει ένα εμπλουτισμένο segment tree για το κάτω όριο. Το BuildNodeIndex ταξινομεί το FNodeOrder κατά κλειδί κόμβου όπως πριν, και μετά το BuildMaxOutRowTree γεμίζει το FNodeMaxOutRow2 (δεσμευμένο με τέσσερις εγγραφές ανά κόμβο) με το μεγαλύτερο OutRow2 που βρίσκεται κάτω από κάθε υποδένδρο. Το QueryNodeTree κατεβαίνει μόνο μέσα στο παράθυρο κλειδιών και εγκαταλείπει κάθε υποδένδρο του οποίου η μέγιστη γραμμή εξόδου βρίσκεται πάνω από το FRanges[r].Row1, επειδή κανένας τύπος μέσα του δεν μπορεί να φτάσει τις αναφερόμενες γραμμές. Τα φύλλα που επιβιώνουν εξακολουθούν να περνούν το πλήρες τεστ RangeIntersectsOutput, οπότε sheet spans και στήλες ελέγχονται ακριβώς όπως πριν

// TXLSDepGraph.BuildNodeIndex / BuildEdges από το 2.383.1 (ελαφρώς συμπυκνωμένο)
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
  // έξω από το παράθυρο κλειδιών, ή καμία έξοδος σε αυτό το υποδένδρο δεν φτάνει το 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
      // αμετάβλητο: καταστολή EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // πρώτα το αριστερό υποδένδρο
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // κρατάει την παλιά σειρά
end;

Η αναδρομή αριστερό-πριν-από-δεξιά δεν είναι επιλογή στυλ. Τα επιζώντα φύλλα επισκέπτονται με την ακριβή σειρά που τα επισκεπτόταν ο παλιός βρόχος while, ώστε τα array Dependents και Precedents γεμίζουν με την ίδια ακολουθία και η τοπολογική σειρά μένει ντετερμινιστική. Το ίδιο ισχύει για τα δύο είδη ακμών: μια σκληρή ακμή καταγραμμένη πρώτη εξακολουθεί να καταστέλλει μια μεταγενέστερη ακμή LookupScan για το ίδιο ζεύγος, ενώ μια ακμή σάρωσης καταγραμμένη πριν από μια σκληρή κρατάει τη θέση της — η διάκριση που εμποδίζει τα lookup ranges από το να παράγουν ψευδείς κυκλικές αναφορές. Ανά αναφορά, το κόστος πέφτει από το μέγεθος του παραθύρου σε O((k + 1) log n), όπου k το πλήθος των τύπων των οποίων η έξοδος φτάνει πραγματικά τις αναφερόμενες γραμμές

Τι εγγυάται ο δείκτης εξόδων, και πώς επαληθεύεται;

Το TXLSDepGraph παράγει τις ίδιες ακμές με την ίδια σειρά όπως πριν, και η νέα ιδιότητα EdgeCandidateChecks μετρά πόσα ορθογώνια εξόδου τεστούσε πραγματικά το πιο πρόσφατο χτίσιμο, ώστε ο ισχυρισμός είναι μετρήσιμος και όχι ρητορικός. Το regression τεστ EdgeBuildDeepChainsCheckOneCandidatePerDependency χτίζει αλυσίδες αναφορών σημείου με 1.024 και 100.000 κόμβους, εισαγμένους με ανάστροφη σειρά για να επιβάλει τη χωρική ταξινόμηση, και απαιτεί ακριβώς N − 1 ελέγχους — 99.999 για τη μακριά αλυσίδα — συν την αναμενόμενη σειρά precedent, dependent και τοπολογική για κάθε κόμβο. Συνοδευτικά τεστ καλύπτουν ρίζες array εισαγμένες εκτός σειράς πάνω από sheet spans, διπλές αναφορές hard και lookup-scan (10 έλεγχοι, με τους κανόνες καταστολής παραπάνω), και ένα ξαναχτίσιμο μετά από AddNode, που καθαρίζει τη σημαία ταξινόμησης ώστε το επόμενο BuildEdges ή NodeIndexOf να ξαναχτίζει το δένδρο και να μηδενίζει τον μετρητή αντί να τον αθροίζει

Μετρημένα αποτελέσματα: από 18,5 δευτερόλεπτα σε περίπου 0,1

Το trace Win32 πριν τη διόρθωση, που διατηρείται στη γραμμή βάσης επιδόσεων του έργου για την έκδοση 2.383.0, κατέγραψε δύο εξαναγκασμένους επανυπολογισμούς 18.488 ms και 19.578 ms. Μετά τη δεικτοδότηση, τρεις διαδοχικές στοχευμένες εκτελέσεις ανά αρχιτεκτονική μέτρησαν 102.332–109.429 ms σε Win32 και 116.990–133.995 ms σε Win64, περίπου 170 έως 180 φορές ταχύτερα σε Win32· δεν καταγράφηκε γραμμή βάσης Win64 πριν τη διόρθωση, οπότε δεν επικαλούμαστε επιτάχυνση Win64. Οι ίδιες εκτελέσεις πέρασαν την υπάρχουσα πύλη που κρατάει έναν έλεγχο επανυπολογισμού μόνο για ανάγνωση μέσα σε 1,35 φορές έναν εξαναγκασμένο επανυπολογισμό. Οι απόλυτοι αριθμοί εξαρτώνται από τη μηχανή και το φορτίο της, οπότε αναπαραγάγετε το workload στο δικό σας υλικό πριν τους παραθέσετε

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 κρίκων στη στήλη A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 dependents στη στήλη B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // η πρώτη κλήση χτίζει τον γράφο
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Πού παύει να βοηθά ο δείκτης εξόδων;

Το δένδρο κλαδεύει μόνο σε γραμμές, και αυτό αφήνει μερικά ειλικρινή όρια που αξίζει να ξέρετε πριν σχεδιάσετε γύρω του ένα πολύ μεγάλο μοντέλο

• Τα λάθη στηλών πληρώνονται ακόμη στα φύλλα: οι 2.626 τύποι που γεμίζουν το A100:Z200 φτάνουν όλοι τη γραμμή 100, οπότε μια αναφορά στο AA100:AA200 τεστούζει τον καθένα πριν τον απορρίψει
• Πλατιές αναφορές όπως εύρη ολόκληρων στηλών έχουν πράγματι πολλούς precedents· ο δείκτης αφαιρεί σπαταλημένους ελέγχους, όχι πραγματικές ακμές, και το χτίσιμο εκείνων των ακμών εξακολουθεί να είναι ανάλογο του πλήθους τους
• Για αναφορές που απλώνονται σε πολλά sheets, το αποθηκευμένο μέγιστο αγνοεί το sheet, οπότε τύποι σε ενδιάμεσα sheets με βαθιές εξόδους φτάνουν ως το τεστ των φύλλων· τα αποτελέσματα μένουν σωστά, μόνο το κλάδεμα αποδυναμώνεται
• Το δένδρο κοστίζει τέσσερις ακέραιους ανά κόμβο τύπου, περίπου 1,6 MB για 100.000 κόμβους, και οποιοδήποτε AddNode το ακυρώνει, οπότε οι αλλαγές τοπολογίας πληρώνουν ένα πλήρες ξαναταξινόμημα O(n log n) συν ένα χτίσιμο δένδρου O(n) στο επόμενο χτίσιμο ακμών

Το ίδιο τετραγωνικό σχήμα στην κλωνοποίηση ονομάτων report-band

Η έκδοση 2.383.2 διόρθωσε ένα αδερφό πρόβλημα στο TXLSXDefinedNames.UniqueCloneName: κάθε αντιγραμμένο defined name ξανάρχιζε την αναζήτηση κατάληξής του στο _2, ώστε επαναλαμβανόμενα αντίγραφα report-band μεγάλωναν τετραγωνικά στις αναζητήσεις ονομάτων. Ο δείκτης scoped ονομάτων κρατάει πλέον μια υπόδειξη κατάληξης ανά όνομα βάσης και ανά scope και ξαναελέγχει τον τελευταίο επιστραφέντα υποψήφιο, επειδή ο καλών μπορεί να μην τον προσθέσει τελικά· η διαγραφή, μετονομασία ή αλλαγή scope ενός ονόματος ακυρώνει τον δείκτη, που επαναφέρει την ονοματοδοσία πρώτου διαθέσιμου. Στη σουίτα regression, 1.024 διαδοχικοί κλώνοι χρειάζονται 5.088 αναζητήσεις υποψηφίων και τέσσερα εναλλάσσόμενα ονόματα βάσης χρειάζονται 5.039, ενώ τα ελάχιστα του benchmark report έπεσαν από περίπου 240 ms σε 18–20 ms. Η ίδια η πύλη χρονισμού report-band δεν είναι ακόμη σταθερή — τρεις στις έξι εκτελέσεις ξεπέρασαν το ratio 1,05 της στην πρώτη δοκιμή μετά τη διόρθωση — και το ιστορικό επιδόσεων κρατάει εκείνες τις αποτυχίες καταγεγραμμένες αντί να στρώνει το όριο μέχρι να περάσει

Αν η εφαρμογή σας σε Delphi ή C++Builder παράγει ή επανυπολογίζει μεγάλα workbooks Excel, το HotXLS Excel component για Delphi και C++Builder παραδίδει αυτόν τον δεικτοδοτημένο γράφο εξαρτήσεων μέσα στη μηχανή επανυπολογισμού και για τις δύο κλάσεις workbook του, classic και XLSX