[llvm-exegesis] InstructionBenchmarkClustering::dbScan(): replace std::vector<> with std::deque<> in llvm::SetVector<>

[lebedev.ri]

Summary

Old: (D54388)

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

       8606.323981      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.11% )
...
           8.60773 +- 0.00978 seconds time elapsed  ( +-  0.11% )

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

       7971.403653      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.14% )
...
            7.9728 +- 0.0113 seconds time elapsed  ( +-  0.14% )

Another -~7%.

[RKSimon]

LGTM as part of the patch series

[lebedev.ri]

In D54389#1296023, @RKSimon wrote:

LGTM as part of the patch series

@courbet

Thank you for the reviews!

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

for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
 
     // 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);
 
     // Process P's neighbors.
-    llvm::SetVector<size_t> ToProcess;
+    llvm::SetVector<size_t, std::deque<size_t>> ToProcess;
     ToProcess.insert(Neighbors.begin(), Neighbors.end());
     while (!ToProcess.empty()) {
       // Retrieve a point from the set.
       const size_t Q = *ToProcess.begin();
       ToProcess.erase(ToProcess.begin());
 
       if (ClusterIdForPoint_[Q].isNoise()) {
         // Change noise point to border point.