[llvm-exegesis] InstructionBenchmarkClustering::rangeQuery(): use llvm::SmallVector<size_t, 0> for storage.

[lebedev.ri]

Summary

Old: (D54383)

 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):

       9098.781978      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.16% )
...
            9.1015 +- 0.0148 seconds time elapsed  ( +-  0.16% )

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):

       8553.352480      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.12% )
...
            8.5539 +- 0.0105 seconds time elapsed  ( +-  0.12% )

So another -6%.
That is because the SmallVector doubles it size when reallocating, which is great here,
since we can't reserve() since we can't know how many Neighbors we will have.

[MaskRay]

tools/llvm-exegesis/lib/Clustering.cpp

38

The size of Neighbors is bound by the number of points. The vector can be reserved before the loop calling rangeQuery and passed as a parameter into rangeQuery.

[lebedev.ri]

tools/llvm-exegesis/lib/Clustering.cpp

38

Good point.

That is the upper bound, not in all cases that will be actual size of the vector.
Given that you have accepted D54390, such optimization can be safely made
but only *after* D54390 (and it can be replaced by a std::vector),
but i really really don't want to change/reorder patches,
because that would require to re-do all of the benchmarks/measurements.

So i will add a new patch with that fix.

[lebedev.ri]

tools/llvm-exegesis/lib/Clustering.cpp

38

D54415

[courbet]

You don't need this one anymore right ? Though I don't oppose to you keeping it for benchmarking reference.

[lebedev.ri]

In D54388#1302661, @courbet wrote:

You don't need this one anymore right ? Though I don't oppose to you keeping it for benchmarking reference.

Correct. It has been effectively superseeded by further patches, but it would make sense to keep it for consistency, as a fine-grained refactoring step.
Thank you for the review!

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);
-  std::vector<size_t> rangeQuery(size_t Q) const;
+  llvm::SmallVector<size_t, 0> rangeQuery(size_t Q) 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

 //===-- 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,
 //    typically < 10).
 //  (B) - Number of points : ~thousands (points are measurements of an MCInst)
 //  (C) - Number of clusters: ~tens.
 //  (D) - The number of clusters is not known /a priory/.
 //  (E) - The amount of noise is relatively small.
 // The problem is rather small. In terms of algorithms, (D) disqualifies
 // k-means and makes algorithms such as DBSCAN[1] or OPTICS[2] more applicable.
 //
 // 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).
-std::vector<size_t>
+llvm::SmallVector<size_t, 0>
 InstructionBenchmarkClustering::rangeQuery(const size_t Q) const {
-  std::vector<size_t> Neighbors;
+  llvm::SmallVector<size_t, 0> Neighbors;
   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)) {