[ELF] Use union-find set and doubly linked list in Call-Chain Clustering (C³) heuristic

[MaskRay]

Summary

Before, SecToClusters[*] was used to track the belonged cluster.
During a merge (From -> Into), every element of From has to be updated.
Use a union-find set to speed up this use case.

Also, replace std::vector<int> Sections; with a doubly-linked
pointers: int Next, Prev;

[MaskRay]

Hi Raphael, sorry for hearing that... But may I beg your last review at this revision, considering it was created before your announcement?

[Bigcheese]

Sorry for the delay. What change in performance does this give?

[MaskRay]

Glad to know you are still around :) (your IRC nick seems to be immune to PRIVMSG.. usermode +g or +j? nevermind)

This revision mostly optimizes the cluster number reassignment loop (expected O(n log n), but can be O(n^2) at worst):

// line 210
    for (int SI : C.Sections)
      SecToCluster[SI] = PredC;

to union-find set (fast in practice, O(n log n) at worst (not union-by-rank) but expected O(n α(n)) (I believe)) + list splice (linear)

[Bigcheese]

I mean performance of actual cases. I'm interested in if the cache effects of list vs vector matter.

[MaskRay]

std::vector<int> Sections; This also calls malloc when the first element is pushed.

[MaskRay]

I want to use a data structure supporting O(1) splice and can be pre-allocated (1 malloc call instead of N calls) but I cannot find one (and I don't think hand-rolled next/prev doubly linked list justifies the amount of code) :( vector<int> isn't good either (ok you can argue you could replace it with a SmallVector but note the all intermediate vectors are counted in memory usage)

[MaskRay]

Update description and also serves as a ping

[MaskRay]

clear() -> not destructed

[ruiu]

ELF/CallGraphSort.cpp

157

I perhaps didn't spent enough effort to understand this function, but it feels something is wrong with this function. The function name implies this function "finds" something, but looks like it actually mutates a given vector.

[MaskRay]

Add a comment about findLeader which uses path-halving technique

[ruiu]

ELF/CallGraphSort.cpp

157

I don't think any function that has a side effect (other than caching a result) have a function name that starts with "find". "Find" implies a pure function. Please give it a different name.

[MaskRay]

Rename findLeader to getLeader (not sure it conveys the meaning better that it is mutable. I'm not good at naming things)

[ruiu]

Honestly I do not understand the code. What is this code doing? Can you explain it for me?

[MaskRay]

In D46228#1264054, @ruiu wrote:

Honestly I do not understand the code. What is this code doing? Can you explain it for me?

Sure. A cluster is a list of sections (C.Sections). This loop iterates over sections by descending density and tries grouping sections together (grouped sections are linearly ordered for locality).

The loop body needs a way to find the cluster a section belongs. What it used to do is the lookup table SecToCluster which is maintained after each merge operation. The merge operation is slow (thus the old comment "NOTE: Consider using a disjoint-set to track section -> cluster mapping"). Since a section can only belong to a cluster and clusters are disjoined, union-find algorithm naturally fits here.

I use the path-halving technique (one-liner Leaders[V] = Leaders[Leaders[V]];) to decrease complexity and it is extremely simple to implement. Other techniques can achieve the same goal but they would have more code (https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf).

[MaskRay]

Rename old SortedSec as the name was confusing (it referrs to cluster but a name about section was chosen)
Change B < A to A > B to be consistent with the next stable_sort condition

[MaskRay]

Greeting from a dev meeting attendee:)

[smeenai]

Do you have real world performance numbers (both time and memory) for this? Computational complexity isn't always the best predictor of actual performance because of e.g. cache characteristics (as @Bigcheese mentioned).

[MaskRay]

In D46228#1269419, @smeenai wrote:

Do you have real world performance numbers (both time and memory) for this? Computational complexity isn't always the best predictor of actual performance because of e.g. cache characteristics (as @Bigcheese mentioned).

I think I've made it clear in the description that std::vector does not do a better job here. (the vectors are not even destroyed to free intermediate memory usage)

[Bigcheese]

Pretty sure I understand the algorithm now, but I still want to see what performance impact it has to see if it's worth the (minor) complexity. I'll benchmark it on some large links and see what happens.

[MaskRay]

std::list<int> Sections; -> int Next, Prev;

[MaskRay]

Rebase after one year since there is not interest in maintaining Call-Chain Clustering.

This file has not been touched much.

• Adapt variable renaming
• Use DenseMap::try_emplace

[MaskRay]

@Bigcheese Ping :)

[MaskRay]

mergeclusters -> mergeClusters

[Bigcheese]

lgtm

ELF/CallGraphSort.cpp

 ///
 //===----------------------------------------------------------------------===//
 
 #include "CallGraphSort.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 
+#include <list>
+#include <numeric>
+
 using namespace llvm;
 using namespace lld;
 using namespace lld::elf;
 
 namespace {
 struct Edge {
   int From;
   uint64_t Weight;
 };
 
 struct Cluster {
   Cluster(int Sec, size_t S) {
     Sections.push_back(Sec);
     Size = S;
   }
 
   double getDensity() const {
     if (Size == 0)
       return 0;
     return double(Weight) / double(Size);
   }
 
-  std::vector<int> Sections;
+  std::list<int> Sections;
   size_t Size = 0;
   uint64_t Weight = 0;
   uint64_t InitialWeight = 0;
   std::vector<Edge> Preds;
 };
 
 class CallGraphSort {
 public:

 // It's bad to merge clusters which would degrade the density too much.
 static bool isNewDensityBad(Cluster &A, Cluster &B) {
   double NewDensity = double(A.Weight + B.Weight) / double(A.Size + B.Size);
   if (NewDensity < A.getDensity() / MAX_DENSITY_DEGRADATION)
     return true;
   return false;
 }
 
+static int findLeader(std::vector<int> &Leaders, int V) {
+  while (Leaders[V] != V) {
+    Leaders[V] = Leaders[Leaders[V]];
+    V = Leaders[V];
+  }
+  return V;
+}
+
 static void mergeClusters(Cluster &Into, Cluster &From) {
-  Into.Sections.insert(Into.Sections.end(), From.Sections.begin(),
-                       From.Sections.end());
+  Into.Sections.splice(Into.Sections.end(), From.Sections);
   Into.Size += From.Size;
   Into.Weight += From.Weight;
-  From.Sections.clear();
   From.Size = 0;
   From.Weight = 0;
 }
 
 // Group InputSections into clusters using the Call-Chain Clustering heuristic
 // then sort the clusters by density.
 void CallGraphSort::groupClusters() {
   std::vector<int> SortedSecs(Clusters.size());
-  std::vector<Cluster *> SecToCluster(Clusters.size());
-
-  for (int SI = 0, SE = Clusters.size(); SI != SE; ++SI) {
-    SortedSecs[SI] = SI;
-    SecToCluster[SI] = &Clusters[SI];
-  }
+  std::vector<int> Leaders(Clusters.size());
 
+  std::iota(Leaders.begin(), Leaders.end(), 0);
+  std::iota(SortedSecs.begin(), SortedSecs.end(), 0);
   std::stable_sort(SortedSecs.begin(), SortedSecs.end(), [&](int A, int B) {
     return Clusters[B].getDensity() < Clusters[A].getDensity();
   });
 
   for (int SI : SortedSecs) {
     // Clusters[SI] is the same as SecToClusters[SI] here because it has not
     // been merged into another cluster yet.
-    Cluster &C = Clusters[SI];
+    int L = findLeader(Leaders, SI);
+    Cluster &C = Clusters[L];
 
     int BestPred = -1;
     uint64_t BestWeight = 0;
 
     for (Edge &E : C.Preds) {
       if (BestPred == -1 || E.Weight > BestWeight) {
         BestPred = E.From;
         BestWeight = E.Weight;
       }
     }
 
     // don't consider merging if the edge is unlikely.
     if (BestWeight * 10 <= C.InitialWeight)
       continue;
 
-    Cluster *PredC = SecToCluster[BestPred];
-    if (PredC == &C)
+    int PredL = findLeader(Leaders, BestPred);
+    if (L == PredL)
       continue;
 
+    Cluster *PredC = &Clusters[PredL];
     if (C.Size + PredC->Size > MAX_CLUSTER_SIZE)
       continue;
 
     if (isNewDensityBad(*PredC, C))
       continue;
 
-    // NOTE: Consider using a disjoint-set to track section -> cluster mapping
-    // if this is ever slow.
-    for (int SI : C.Sections)
-      SecToCluster[SI] = PredC;
-
+    Leaders[L] = PredL;
     mergeClusters(*PredC, C);
   }
 
   // Remove empty or dead nodes. Invalidates all cluster indices.
   llvm::erase_if(Clusters, [](const Cluster &C) {
     return C.Size == 0 || C.Sections.empty();
   });