Index: tools/llvm-exegesis/lib/Clustering.cpp
===================================================================
--- tools/llvm-exegesis/lib/Clustering.cpp
+++ tools/llvm-exegesis/lib/Clustering.cpp
@@ -102,7 +102,10 @@
 }
 
 void InstructionBenchmarkClustering::dbScan(const size_t MinPts) {
-  for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
+  const size_t NumPoints = Points_.size();
+  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.
     const auto Neighbors = rangeQuery(P);
@@ -118,13 +121,16 @@
     Cluster &CurrentCluster = Clusters_.back();
     ClusterIdForPoint_[P] = CurrentCluster.Id; /* Label initial point */
     CurrentCluster.PointIndices.push_back(P);
+    Added[P] = 1;
 
     // Process P's neighbors.
-    std::unordered_set<size_t> ToProcess(Neighbors.begin(), Neighbors.end());
-    while (!ToProcess.empty()) {
+    std::copy(Neighbors.begin(), Neighbors.end(), ToProcess.begin());
+    for (size_t Q : Neighbors)
+      Added[Q] = 1;
+    size_t Head = Neighbors.size();
+    for (size_t Tail = 0; Tail < Head; ++Tail) {
       // Retrieve a point from the set.
-      const size_t Q = *ToProcess.begin();
-      ToProcess.erase(Q);
+      size_t Q = ToProcess[Tail];
 
       if (ClusterIdForPoint_[Q].isNoise()) {
         // Change noise point to border point.
@@ -132,17 +138,17 @@
         CurrentCluster.PointIndices.push_back(Q);
         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.
-      const auto Neighbors = rangeQuery(Q);
-      if (Neighbors.size() + 1 >= MinPts) {
-        ToProcess.insert(Neighbors.begin(), Neighbors.end());
-      }
+      const std::vector<size_t> Neighbors = rangeQuery(Q);
+      if (Neighbors.size() + 1 >= MinPts)
+        for (size_t P : Neighbors)
+          if (!Added[P]) {
+            ToProcess[Head++] = P;
+            Added[P] = 1;
+          }
     }
   }