[llvm-exegesis] InstructionBenchmarkClustering::rangeQuery(): reserve for the upper bound of Neighbors

[lebedev.ri]

Summary

As it was pointed out in D54388+D54390, the maximal size of Neighbors is known,
it will contain at most Points_.size() minus one (the center of the cluster)

While that is the upper bound, meaning in the most cases, the actual count
will be much smaller, since D54390 made the allocation persistent,
we no longer have to worry about overly-optimistically reserve()ing.

Old: (D54393)

 Performance counter stats for './bin/llvm-exegesis -mode=analysis -analysis-epsilon=100000 -benchmarks-file=/tmp/benchmarks.yaml -analysis-inconsistencies-output-file=/tmp/clusters.html' (16 runs):

       6553.167456      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.21% )
...
            6.5547 +- 0.0134 seconds time elapsed  ( +-  0.20% )

New:

 Performance counter stats for './bin/llvm-exegesis -mode=analysis -analysis-epsilon=100000 -benchmarks-file=/tmp/benchmarks.yaml -analysis-inconsistencies-output-file=/tmp/clusters.html' (16 runs):

       6315.057872      task-clock (msec)         #    0.999 CPUs utilized            ( +-  0.24% )
...
            6.3187 +- 0.0160 seconds time elapsed  ( +-  0.25% )

And that is another -~4%.

[MaskRay]

tools/llvm-exegesis/lib/Clustering.cpp

140 ↗

(On Diff #173619)

I've lost in the patch series :( I think I understand the DBSCAN implementation well enough now. You may consider merging some revisions related to the vector optimization and commit them at once? They should be quite obvious.

I understand that reordering/rebasing several commits is painful... (I am also try avoiding git rebase --onto readPubNamesAndTypes HEAD\^)

[lebedev.ri]

tools/llvm-exegesis/lib/Clustering.cpp

140 ↗

(On Diff #173619)

I've lost in the patch series :(

It is quite easy to orient.
Ctrl+F for "Revision Contents", then click on the "Stack (n open)" tab.
They are all listed there, in their correct order, from bottom to top.

[lebedev.ri]

tools/llvm-exegesis/lib/Clustering.cpp

140 ↗

(On Diff #173619)

(replied too quickly)

I understand that reordering/rebasing several commits is painful.

The rebasing itself is absolutely not painful for me. It's trivial.
The only problem is that it will force me to re-benchmark every single differential,
and will result in less of an atomic incremental changes
(while those changes do make sense on their own.)

[lebedev.ri]

@MaskRay @courbet thank you for the reviews!

llvm/trunk/tools/llvm-exegesis/lib/Clustering.h

bool isNeighbour(const std::vector<BenchmarkMeasure> &P,
     return DistanceSquared <= EpsilonSquared_;
   }
 
 private:
   InstructionBenchmarkClustering(
       const std::vector<InstructionBenchmark> &Points, double EpsilonSquared);
   llvm::Error validateAndSetup();
   void dbScan(size_t MinPts);
-  void rangeQuery(size_t Q, llvm::SmallVectorImpl<size_t> &Scratchpad) const;
+  void rangeQuery(size_t Q, std::vector<size_t> &Scratchpad) const;
 
   const std::vector<InstructionBenchmark> &Points_;
   const double EpsilonSquared_;
   int NumDimensions_ = 0;
   // ClusterForPoint_[P] is the cluster id for Points[P].
   std::vector<ClusterId> ClusterIdForPoint_;
   std::vector<Cluster> Clusters_;
   Cluster NoiseCluster_;
   Cluster ErrorCluster_;
 };
 
 } // namespace exegesis
 } // namespace llvm
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_CLUSTERING_H

llvm/trunk/tools/llvm-exegesis/lib/Clustering.cpp

 // straightforward and inefficient implementation of the pseudocode in [2].
 //
 // [1] https://en.wikipedia.org/wiki/DBSCAN
 // [2] https://en.wikipedia.org/wiki/OPTICS_algorithm
 
 // Finds the points at distance less than sqrt(EpsilonSquared) of Q (not
 // including Q).
 void InstructionBenchmarkClustering::rangeQuery(
-    const size_t Q, llvm::SmallVectorImpl<size_t> &Neighbors) const {
+    const size_t Q, std::vector<size_t> &Neighbors) const {
   Neighbors.clear();
+  Neighbors.reserve(Points_.size() - 1); // The Q itself isn't a neighbor.
   const auto &QMeasurements = Points_[Q].Measurements;
   for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
     if (P == Q)
       continue;
     const auto &PMeasurements = Points_[P].Measurements;
     if (PMeasurements.empty()) // Error point.
       continue;
     if (isNeighbour(PMeasurements, QMeasurements)) {
llvm::Error InstructionBenchmarkClustering::validateAndSetup() {
   }
   if (LastMeasurement) {
     NumDimensions_ = LastMeasurement->size();
   }
   return llvm::Error::success();
 }
 
 void InstructionBenchmarkClustering::dbScan(const size_t MinPts) {
-  llvm::SmallVector<size_t, 0> Neighbors; // Persistent buffer to avoid allocs.
+  std::vector<size_t> Neighbors; // Persistent buffer to avoid allocs.
   for (size_t P = 0, NumPoints = Points_.size(); 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();
while (!ToProcess.empty()) {
       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(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()) {
       NoiseCluster_.PointIndices.push_back(P);
     }
   }
 }