[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

161 ↗

(On Diff #168926)

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

161 ↗

(On Diff #168926)

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

lld/trunk/ELF/CallGraphSort.cpp

 ///
 //===----------------------------------------------------------------------===//
 
 #include "CallGraphSort.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 
+#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{sec}, size(s) {}
+  Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {}
 
   double getDensity() const {
     if (size == 0)
       return 0;
     return double(weight) / double(size);
   }
 
-  std::vector<int> sections;
+  int next;
+  int prev;
   size_t size = 0;
   uint64_t weight = 0;
   uint64_t initialWeight = 0;
   Edge bestPred = {-1, 0};
 };
 
 class CallGraphSort {
 public:
   CallGraphSort();
 
   DenseMap<const InputSectionBase *, int> run();
 
 private:
   std::vector<Cluster> clusters;
   std::vector<const InputSectionBase *> sections;
-
-  void groupClusters();
 };
 
 // Maximum ammount the combined cluster density can be worse than the original
 // cluster to consider merging.
 constexpr int MAX_DENSITY_DEGRADATION = 8;
 
 // Maximum cluster size in bytes.
 constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024;
 } // end anonymous namespace
 
 using SectionPair =
     std::pair<const InputSectionBase *, const InputSectionBase *>;
 
 // Take the edge list in Config->CallGraphProfile, resolve symbol names to
 // Symbols, and generate a graph between InputSections with the provided
 // weights.
 CallGraphSort::CallGraphSort() {
   MapVector<SectionPair, uint64_t> &profile = config->callGraphProfile;
   DenseMap<const InputSectionBase *, int> secToCluster;
 
   auto getOrCreateNode = [&](const InputSectionBase *isec) -> int {
-    auto res = secToCluster.insert(std::make_pair(isec, clusters.size()));
+    auto res = secToCluster.try_emplace(isec, clusters.size());
     if (res.second) {
       sections.push_back(isec);
       clusters.emplace_back(clusters.size(), isec->getSize());
     }
     return res.first->second;
   };
 
   // Create the graph.

 }
 
 // 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);
   return newDensity < a.getDensity() / MAX_DENSITY_DEGRADATION;
 }
 
-static void mergeClusters(Cluster &into, Cluster &from) {
-  into.sections.insert(into.sections.end(), from.sections.begin(),
-                       from.sections.end());
+// Find the leader of V's belonged cluster (represented as an equivalence
+// class). We apply union-find path-halving technique (simple to implement) in
+// the meantime as it decreases depths and the time complexity.
+static int getLeader(std::vector<int> &leaders, int v) {
+  while (leaders[v] != v) {
+    leaders[v] = leaders[leaders[v]];
+    v = leaders[v];
+  }
+  return v;
+}
+
+static void mergeClusters(std::vector<Cluster> &cs, Cluster &into, int intoIdx,
+                          Cluster &from, int fromIdx) {
+  int tail1 = into.prev, tail2 = from.prev;
+  into.prev = tail2;
+  cs[tail2].next = intoIdx;
+  from.prev = tail1;
+  cs[tail1].next = fromIdx;
   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 (size_t i = 0; i < clusters.size(); ++i) {
-    sortedSecs[i] = i;
-    secToCluster[i] = &clusters[i];
-  }
+DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
+  std::vector<int> sorted(clusters.size());
+  std::vector<int> leaders(clusters.size());
 
-  llvm::stable_sort(sortedSecs, [&](int a, int b) {
+  std::iota(leaders.begin(), leaders.end(), 0);
+  std::iota(sorted.begin(), sorted.end(), 0);
+  llvm::stable_sort(sorted, [&](int a, int b) {
     return clusters[a].getDensity() > clusters[b].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];
+  for (int l : sorted) {
+    // The cluster index is the same as the index of its leader here because
+    // clusters[L] has not been merged into another cluster yet.
+    Cluster &c = clusters[l];
 
     // Don't consider merging if the edge is unlikely.
     if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)
       continue;
 
-    Cluster *predC = secToCluster[c.bestPred.from];
-    if (predC == &c)
+    int predL = getLeader(leaders, c.bestPred.from);
+    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;
-
-    mergeClusters(*predC, c);
+    leaders[l] = predL;
+    mergeClusters(clusters, *predC, predL, c, l);
   }
 
-  // Remove empty or dead nodes. Invalidates all cluster indices.
-  llvm::erase_if(clusters, [](const Cluster &c) {
-    return c.size == 0 || c.sections.empty();
-  });
-
-  // Sort by density.
-  llvm::stable_sort(clusters, [](const Cluster &a, const Cluster &b) {
-    return a.getDensity() > b.getDensity();
+  // Sort remaining non-empty clusters by density.
+  sorted.clear();
+  for (int i = 0, e = (int)clusters.size(); i != e; ++i)
+    if (clusters[i].size > 0)
+      sorted.push_back(i);
+  llvm::stable_sort(sorted, [&](int a, int b) {
+    return clusters[a].getDensity() > clusters[b].getDensity();
   });
-}
-
-DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
-  groupClusters();
 
-  // Generate order.
   DenseMap<const InputSectionBase *, int> orderMap;
-  ssize_t curOrder = 1;
-
-  for (const Cluster &c : clusters)
-    for (int secIndex : c.sections)
-      orderMap[sections[secIndex]] = curOrder++;
+  int curOrder = 1;
+  for (int leader : sorted)
+    for (int i = leader;;) {
+      orderMap[sections[i]] = curOrder++;
+      i = clusters[i].next;
+      if (i == leader)
+        break;
+    }
 
   if (!config->printSymbolOrder.empty()) {
     std::error_code ec;
     raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::OF_None);
     if (ec) {
       error("cannot open " + config->printSymbolOrder + ": " + ec.message());
       return orderMap;
     }
 
     // Print the symbols ordered by C3, in the order of increasing curOrder
     // Instead of sorting all the orderMap, just repeat the loops above.
-    for (const Cluster &c : clusters)
-      for (int secIndex : c.sections)
+    for (int leader : sorted)
+      for (int i = leader;;) {
         // Search all the symbols in the file of the section
         // and find out a Defined symbol with name that is within the section.
-        for (Symbol *sym: sections[secIndex]->file->getSymbols())
+        for (Symbol *sym : sections[i]->file->getSymbols())
           if (!sym->isSection()) // Filter out section-type symbols here.
             if (auto *d = dyn_cast<Defined>(sym))
-              if (sections[secIndex] == d->section)
+              if (sections[i] == d->section)
                 os << sym->getName() << "\n";
+        i = clusters[i].next;
+        if (i == leader)
+          break;
+      }
   }
 
   return orderMap;
 }
 
 // Sort sections by the profile data provided by -callgraph-profile-file
 //
 // This first builds a call graph based on the profile data then merges sections
 // according to the C³ huristic. All clusters are then sorted by a density
 // metric to further improve locality.
 DenseMap<const InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
   return CallGraphSort().run();
 }