[llvm-exegesis] InstructionBenchmarkClustering::rangeQuery(): write into llvm::SmallVectorImpl& output parameter

[lebedev.ri]

Summary

I do believe this is the correct fix.
We call rangeQuery() *very* often. And many times it's output vector is large (tens of thousands entries), so small-size-opt won't help.

Old: (D54389)

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

       7934.528363      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.19% )
...
            7.9354 +- 0.0148 seconds time elapsed  ( +-  0.19% )

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' (10 runs):

       7383.793440      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.47% )
...
            7.3868 +- 0.0340 seconds time elapsed  ( +-  0.46% )

And another -7%. And that isn't even the good bit yet.

Old:

• calls to allocation functions: 2081419
• temporary allocations: 219658 (10.55%)
• bytes allocated in total (ignoring deallocations): 4.31 GB

New:

• calls to allocation functions: 1880295 (-10%)
• temporary allocations: 18758 (1%) (-91% *sic*)
• bytes allocated in total (ignoring deallocations): 545.15 MB (-88% *sic*)

[MaskRay]

LG. The issue is that there shouldn't be frequent SmallVector construction/destruction in the loop body.

Here comes my own question: when the specific vector type does not matter too much (as in this case), when shall we choose SmallVector and when std::vector?

[MaskRay]

tools/llvm-exegesis/lib/Clustering.cpp

105

It can be set to of size`NumPoints`

[lebedev.ri]

In D54390#1294939, @MaskRay wrote:

LG. The issue is that there shouldn't be frequent SmallVector construction/destruction in the loop body.

Here comes my own question: when the specific vector type does not matter too much (as in this case), when shall we choose SmallVector and when std::vector?

If there are preexisting contract/interface requirements - the one required by the contract/interface.
Else, if there are no concerns about memory usage, but the element count is hard to guess, SmallVector is much better because it doubles it's capacity.

[lebedev.ri]

tools/llvm-exegesis/lib/Clustering.cpp

105

Indeed, D54415.

[lebedev.ri]

This comment was removed by lebedev.ri.

[lebedev.ri]

In D54390#1294939, @MaskRay wrote:

LG.

@courbet

Thank you for the reviews!

tools/llvm-exegesis/lib/Clustering.h

public:
   bool isNeighbour(const std::vector<BenchmarkMeasure> &P,
                    const std::vector<BenchmarkMeasure> &Q) const;
 
 private:
   InstructionBenchmarkClustering(
       const std::vector<InstructionBenchmark> &Points, double EpsilonSquared);
   llvm::Error validateAndSetup();
   void dbScan(size_t MinPts);
-  llvm::SmallVector<size_t, 0> rangeQuery(size_t Q) const;
+  void rangeQuery(size_t Q, llvm::SmallVectorImpl<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

tools/llvm-exegesis/lib/Clustering.cpp

 // We've used DBSCAN here because it's simple to implement. This is a pretty
 // 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).
-llvm::SmallVector<size_t, 0>
-InstructionBenchmarkClustering::rangeQuery(const size_t Q) const {
-  llvm::SmallVector<size_t, 0> Neighbors;
+void InstructionBenchmarkClustering::rangeQuery(
+    const size_t Q, llvm::SmallVectorImpl<size_t> &Neighbors) const {
+  Neighbors.clear();
   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)) {
       Neighbors.push_back(P);
     }
   }
-  return Neighbors;
 }
 
 bool InstructionBenchmarkClustering::isNeighbour(
     const std::vector<BenchmarkMeasure> &P,
     const std::vector<BenchmarkMeasure> &Q) const {
   double DistanceSquared = 0.0;
   for (size_t I = 0, E = P.size(); I < E; ++I) {
     const auto Diff = P[I].PerInstructionValue - Q[I].PerInstructionValue;
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.
   for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
     if (!ClusterIdForPoint_[P].isUndef())
       continue; // Previously processed in inner loop.
-    const auto Neighbors = rangeQuery(P);
+    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.
while (!ToProcess.empty()) {
       }
       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.
-      const auto Neighbors = rangeQuery(Q);
+      rangeQuery(Q, Neighbors);
       if (Neighbors.size() + 1 >= MinPts) {
         ToProcess.insert(Neighbors.begin(), Neighbors.end());
       }
     }
   }
 
   // Add noisy points to noise cluster.
   for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {