[llvm-exegesis] Optimize ToProcess in dbScan

[MaskRay]

Summary

Use vector<char> Added + vector<size_t> ToProcess to replace SetVector ToProcess

We also check Added[P] to enqueueing a point more than once, which
also saves us a ClusterIdForPoint_[Q].isUndef() check.

[MaskRay]

.

[MaskRay]

.

[lebedev.ri]

That is more or less how it ends up looking in D54418, just without abstraction.

tools/llvm-exegesis/lib/Clustering.cpp

128–129

I did try this, at different stages of the patchset.
It always measured to be slower than deque + pop front.

[MaskRay]

Optimize

[MaskRay]

.

[MaskRay]

tools/llvm-exegesis/lib/Clustering.cpp

128–129

I moved the vector definition outside to avoid construction/destruction.

Added is not really necessary but it is faster than doing two checks: if an element is either Undef or Noise.

[lebedev.ri]

Looking forward further improvements!

[MaskRay]

rebase

[MaskRay]

.

[MaskRay]

I've rebased the revision.

Old:

% perf stat -r 10 ~/llvm/Release/bin/llvm-exegesis -mode=analysis -analysis-epsilon=100000 -benchmarks-file=/tmp/Downloads/benchmarks.yaml -analysis-inconsistencies-output-file=/tmp/clusters.html > /dev/null
4356.618418 task-clock (msec)
...

New:

% perf stat -r 10 ~/llvm/Release/bin/llvm-exegesis -mode=analysis -analysis-epsilon=100000 -benchmarks-file=/tmp/Downloads/benchmarks.yaml -analysis-inconsistencies-output-file=/tmp/clusters.html > /dev/null
4225.986843 task-clock (msec)

[MaskRay]

Use std::vector<size_t> ToProcess(NumPoints);

sorry messed it up while rebasing

[courbet]

tools/llvm-exegesis/lib/Clustering.cpp

120–126

All of this makes the dbscan implementation harder to follow. Please move all this to a separate struct:

// This is long-lived.
struct WorkSetStorage {
  public:
   WorkSetStorage(size_t NumPoints) : ToProcess(NumPoints), Added(NumPoints) {}

   void setProcessed(size_t P) { Added[P] = 1; }

  private:
   friend class WorkSet;
   std::vector<size_t> ToProcess;
   std::vector<char> Added;
};

// This is short-lived and replaces  llvm::SetVector<size_t, std::deque<size_t>> ToProcess;
class WorkSet {
  public:
   WorkSet(WorkSetStorage& Storage) : Storage(Storage), Head(0), Tail(0) {}

   // Inserts a point if not already processed.
   void insert(size_t P);

   // returns the first element from the work set and pops it.
   size_t pop();

  private:
   WorkSetStorage& Storage;
   size_t Head;
   size_t Tail;
};

136–145

did you just remove the rangeQuery() call on Q ? You have the neighbours from P here.

[MaskRay]

Reinstated rangeQuery(Q, Neighbors)

rebase made me sad

[MaskRay]

tools/llvm-exegesis/lib/Clustering.cpp

120–126

Sorry I don't think making the abstraction is very necessary. The use of Head/Tail is very local and takes very few lines of code. The dbscan algorithm is in essence a variant of Dijkstra or FIFO Bellman-Ford. There is not much fantasy here. Keeping these lines inline is IMHO more readable.

[lebedev.ri]

tools/llvm-exegesis/lib/Clustering.cpp

120–126

(FWIW i have initially implemented this in D54418 with (but different) abstractions, before this review was submitted)

[MaskRay]

Friendly ping

[RKSimon]

Reverted at rL349139

[courbet]

I don't think we've reached a consensus here. Sorry for missing the ping.

tools/llvm-exegesis/lib/Clustering.cpp

120–126

The abstraction makes it clear that we're working with a set. I'm no saying we should have exactly this abstraction (actually D54418 had another approach), but clearly no abstraction makes it harder to read at least for me...

[lebedev.ri]

tools/llvm-exegesis/lib/Clustering.cpp

120–126

I can reopen that one, or change it to such manual deque.

[MaskRay]

Never mind. Someone asked me for reviews of the llvm-exegesis patch series. I said it wasn't necessarily to be done that way and thus created this one. Later that patch series got accepted and merged and they even mentioned . Yes, I don't understand why that patch series changed the same place back and forth.

[MaskRay]

It looks I missed the unittest, sorry for that. And I somehow messed ToProcess[Tail++] = Q;. The test can be simply repaired. What should I do if I don't agree that an additional abstraction layer should be added?

[MaskRay]

.

[MaskRay]

simplify

[MaskRay]

tools/llvm-exegesis/lib/Clustering.cpp

120–126

I have said I don't think the abstraction is necessary. It just makes a simple algorithm complicated and harder to understand as developers have to read 2 separate places for the single usage.

[MaskRay]

tools/llvm-exegesis/lib/Clustering.cpp

120–126

Gentle ping.

Please take another look. I've even simplified the logic. The additional abstraction (which will be one-shot and takes tens of lines) will assuredly make the coder harder to read.

[courbet]

In D54442#1331367, @MaskRay wrote:

It looks I missed the unittest, sorry for that. And I somehow messed ToProcess[Tail++] = Q;.

An abstraction would also be testable independently of the algorithm that uses it, so it might not have had this issue.

tools/llvm-exegesis/lib/Clustering.cpp

120–126

Let me explain my rationale: As a developer, I read the code, the abstraction says it has set semantics, I don't read the implementation and carry on with reading the code keeping in mind that this is a set. I'll only look at the actual implementation if I want to understand more. With the implementation in this patch the set semantics are not obvious.

The pattern:

while (!set.empty()) {
  auto elem = set.top();
  set.pop();
  ...
}

will be *extremely* familiar to anyone.

On the other hand, in:

for (size_t Head = 0; Head < Tail; ++Head) {
  P = ToProcess[Head];
}

it's not trivial what's happening.

[courbet]

In D54442#1331367, @MaskRay wrote:

It looks I missed the unittest, sorry for that.

I don;t see the unit test in the patch.

[MaskRay]

In D54442#1334641, @courbet wrote:

In D54442#1331367, @MaskRay wrote:

It looks I missed the unittest, sorry for that.

I don;t see the unit test in the patch.

LLVMExegesisTests catches this. I didn't notice it.

[MaskRay]

tools/llvm-exegesis/lib/Clustering.cpp

120–126

As a developer, I read the code, the abstraction says it has set semantics, I don't read the implementation and carry on with reading the code keeping in mind that this is a set.

Thanks for expressing your argument. I would say the existing style may not be familiar to users as a point may be added to the queue multiple times, while the patch changes it to a strictly BFS manner.

for (size_t Head = 0; Head < Tail; ++Head) {
P = ToProcess[Head];
}

The for loop is not a foreign BFS style coined by me. It is well established and also used otherwhere.

https://github.com/llvm-mirror/llvm/tree/master/lib/Target/X86/X86ISelLowering.cpp#L18472
https://github.com/llvm-mirror/llvm/tree/master/lib/Transforms/Utils/LoopUtils.cpp#L470
https://github.com/llvm-mirror/llvm/tree/master/lib/CodeGen/LiveRangeCalc.cpp#L360

[lebedev.ri]

Looks like this again got committed in rL350035.

[courbet]

@MaskRay, can you help me understand why you decided to submit this when there are still disagreements in the review thread ?

[lebedev.ri]

In D54442#1343382, @courbet wrote:

@MaskRay, can you help me understand why you decided to submit this when there are still disagreements in the review thread ?

Ping? Is this going to proceed? Shall i resurrect D54514 in some form instead?

[courbet]

In D54442#1377373, @lebedev.ri wrote:

In D54442#1343382, @courbet wrote:

@MaskRay, can you help me understand why you decided to submit this when there are still disagreements in the review thread ?

Ping? Is this going to proceed? Shall i resurrect D54514 in some form instead?

@MaskRay, are you still planning to work on this ?

[lebedev.ri]

Yep, looks stuck. I'm still deeply unhappy with the deeply non-linear performance characteristics
with large number of samples, so i will try to come up with some another take on this..

[MaskRay]

What you've reverted is not the version shown in this diff. It included the ideas from Roman. I feel that I should no longer work on this.

tools/llvm-exegesis/lib/Clustering.cpp

 //===-- Clustering.cpp ------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Clustering.h"
-#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include <string>
 
 namespace llvm {
 namespace exegesis {
 
 // The clustering problem has the following characteristics:
 //  (A) - Low dimension (dimensions are typically proc resource units,
llvm::Error InstructionBenchmarkClustering::validateAndSetup() {
   }
   if (LastMeasurement) {
     NumDimensions_ = LastMeasurement->size();
   }
   return llvm::Error::success();
 }
 
 void InstructionBenchmarkClustering::dbScan(const size_t MinPts) {
-  std::vector<size_t> Neighbors; // Persistent buffer to avoid allocs.
-  for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
+  const size_t NumPoints = Points_.size();
+
+  // Persistent buffers to avoid allocs.
+  std::vector<size_t> Neighbors;
+  std::vector<size_t> ToProcess(NumPoints);
+  std::vector<char> Added(NumPoints);
+
+  for (size_t P = 0; P < NumPoints; ++P) {
     if (!ClusterIdForPoint_[P].isUndef())
       continue; // Previously processed in inner loop.
     rangeQuery(P, Neighbors);
     if (Neighbors.size() + 1 < MinPts) { // Density check.
       // The region around P is not dense enough to create a new cluster, mark
       // as noise for now.
       ClusterIdForPoint_[P] = ClusterId::noise();
       continue;
     }
 
     // Create a new cluster, add P.
     Clusters_.emplace_back(ClusterId::makeValid(Clusters_.size()));
     Cluster &CurrentCluster = Clusters_.back();
     ClusterIdForPoint_[P] = CurrentCluster.Id; /* Label initial point */
     CurrentCluster.PointIndices.push_back(P);
+    Added[P] = 1;
 
     // Process P's neighbors.
-    llvm::SetVector<size_t, std::deque<size_t>> ToProcess;
-    ToProcess.insert(Neighbors.begin(), Neighbors.end());
-    while (!ToProcess.empty()) {
+    size_t Tail = 0;
+    for (size_t Q : Neighbors)
+      if (!Added[Q]) {
+        ToProcess[Tail++] = Q;
+        Added[Q] = 1;
+      }
+    for (size_t Head = 0; Head < Tail; ++Head) {
       // Retrieve a point from the set.
-      const size_t Q = *ToProcess.begin();
-      ToProcess.erase(ToProcess.begin());
+      P = ToProcess[Head];
 
-      if (ClusterIdForPoint_[Q].isNoise()) {
-        // Change noise point to border point.
-        ClusterIdForPoint_[Q] = CurrentCluster.Id;
-        CurrentCluster.PointIndices.push_back(Q);
+      // Add P to the current custer.
+      ClusterId CID = ClusterIdForPoint_[P];
+      ClusterIdForPoint_[P] = CurrentCluster.Id;
+      CurrentCluster.PointIndices.push_back(P);
+      if (CID.isNoise())
         continue;
-      }
-      if (!ClusterIdForPoint_[Q].isUndef()) {
-        continue; // Previously processed.
-      }
-      // Add Q to the current custer.
-      ClusterIdForPoint_[Q] = CurrentCluster.Id;
-      CurrentCluster.PointIndices.push_back(Q);
-      // And extend to the neighbors of Q if the region is dense enough.
-      rangeQuery(Q, Neighbors);
-      if (Neighbors.size() + 1 >= MinPts) {
-        ToProcess.insert(Neighbors.begin(), Neighbors.end());
+      assert(CID.isUndef());
+
+      // And extend to the neighbors of P if the region is dense enough.
+      rangeQuery(P, Neighbors);
+      if (Neighbors.size() + 1 >= MinPts)
+        for (size_t Q : Neighbors)
+          if (!Added[Q]) {
+            ToProcess[Tail++] = Q;
+            Added[Q] = 1;
           }
     }
   }
   // assert(Neighbors.capacity() == (Points_.size() - 1));
   // ^ True, but it is not quaranteed to be true in all the cases.
 
   // Add noisy points to noise cluster.
   for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
     if (ClusterIdForPoint_[P].isNoise()) {