[llvm-exegesis] InstructionBenchmarkClustering::dbScan(): use manual std::deque<size_t> + std::vector<char> instead of SetVector.

[lebedev.ri]

Summary

Initially this was D54418 "[llvm-exegesis] InstructionBenchmarkClustering::dbScan(): replace SetVector with custom BitVectorVector"
but the review was strongly negative about having an abstraction for this. Also, @MaskRay has suggested in D54418/D54442
that plain std::vector<char> may be better than llvm::BitVector here, at the cost of more memory usage.

This replaces D54418+D54445.

Old: (D54415)

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

       6169.091472      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.26% )
...
            6.1713 +- 0.0160 seconds time elapsed  ( +-  0.26% )

Old: (D54445)

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

       5612.071736      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.16% )
...
           5.61284 +- 0.00896 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' (16 runs):

       5455.563761      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.28% )
...
            5.4569 +- 0.0155 seconds time elapsed  ( +-  0.28% )

So this is -11.5% as compared to D54415, or -3% as compared to BitVector/D54445

[MaskRay]

This has evolved to resemble some Bellman-Ford's FIFO variant, but I think Set should not be reset to 0 as elements can be pushed while they are neither Noise nor Undef, and that is wasteful. I still hope my https://reviews.llvm.org/D54442 can be reviewed (but I'll not do anything else to interfere with your other optimization :)

[lebedev.ri]

In D54514#1298649, @MaskRay wrote:

... but I think Set should not be reset to 0 as elements can be pushed while they are neither Noise nor Undef, and that is wasteful.

I'm absolutely sure there is more headroom here.
I won't touch that in this patchseries though, as i'm already worried that there are too many patches
and it won't be reviewed (which kind-of stalls my further potential bdver2 improvements.)

I still hope my https://reviews.llvm.org/D54442 can be reviewed (but I'll not do anything else to interfere with your other optimization :)

That "don't remove from set" part looks interesting, so if this patchseries goes in first, you could rebase D54442 to contain only that opt :)

[lebedev.ri]

@courbet this is the last one..

tools/llvm-exegesis/lib/Clustering.cpp

114–117

There is basically just one interesting point here, as of now.
Each time we do pop_front (until there is something to pop), we remove from set too.
So when the vector is empty, the set is empty too.
So we don't need to zero-init the set.

[courbet]

I think you can submit the other ones independently. I'd like to take more time to review this.

[lebedev.ri]

In D54514#1302749, @courbet wrote:

I think you can submit the other ones independently. I'd like to take more time to review this.

Okay, sure :)
Thank you for taking a look!

[MaskRay]

I commented in some other revision that the change to llvm::SetVector<size_t, std::deque<size_t>> ToProcess; is unnecessary... Anyway, I think this is superseded by https://reviews.llvm.org/D54442

[lebedev.ri]

In D54514#1303114, @MaskRay wrote:

Anyway, I think this is superseded by https://reviews.llvm.org/D54442

I looked at that, and i think it does at least four things at once:

1. Exactly what this diff does, llvm::SetVector<> -> std::{CONTAINER}<size_t> Workqueue + std::{CONTAINER}<size_t> Set.
2. std::deque<size_t> Workqueue -> std::vector<size_t> with manual begin/end tracking. FIXME: how does this affect the capacity?
3. Not removing from the Set after processing.
4. assert instead of continue

[MaskRay]

In D54514#1303127, @lebedev.ri wrote:

In D54514#1303114, @MaskRay wrote:

Anyway, I think this is superseded by https://reviews.llvm.org/D54442

I looked at that, and i think it does at least four things at once:

1. Exactly what this diff does, llvm::SetVector<> -> std::{CONTAINER}<size_t> Workqueue + std::{CONTAINER}<size_t> Set.
2. std::deque<size_t> Workqueue -> std::vector<size_t> with manual begin/end tracking. FIXME: how does this affect the capacity?
3. Not removing from the Set after processing.
4. assert instead of continue

The queue does not need to use std::queue. It can be pre-allocated and use manual begin/end tracking. This does not affect the capacity (<= N).

Workqueue.assign(Neighbors.begin(), Neighbors.end()); // only elements that have not been added should be assigned

if (!ClusterIdForPoint_[Q].isUndef()) { is unnecessary

[lebedev.ri]

In D54514#1303148, @MaskRay wrote:

In D54514#1303127, @lebedev.ri wrote:

In D54514#1303114, @MaskRay wrote:

Anyway, I think this is superseded by https://reviews.llvm.org/D54442

I looked at that, and i think it does at least four things at once:

1. Exactly what this diff does, llvm::SetVector<> -> std::{CONTAINER}<size_t> Workqueue + std::{CONTAINER}<size_t> Set.

2. std::deque<size_t> Workqueue -> std::vector<size_t> with manual begin/end tracking. FIXME: how does this affect the capacity?

The queue does not need to use std::queue. It can be pre-allocated and use manual begin/end tracking. This does not affect the capacity (<= N).

Aha, ok, then that your change looks like a good follow-up.

3. Not removing from the Set after processing.
4. assert instead of continue

I'll leave it up to @courbet.
I'm just not super happy these 'assortment' commits, with multiple separable changes.

[courbet]

In D54514#1303407, @lebedev.ri wrote:

In D54514#1303148, @MaskRay wrote:

In D54514#1303127, @lebedev.ri wrote:

In D54514#1303114, @MaskRay wrote:

Anyway, I think this is superseded by https://reviews.llvm.org/D54442

I looked at that, and i think it does at least four things at once:

1. Exactly what this diff does, llvm::SetVector<> -> std::{CONTAINER}<size_t> Workqueue + std::{CONTAINER}<size_t> Set.

2. std::deque<size_t> Workqueue -> std::vector<size_t> with manual begin/end tracking. FIXME: how does this affect the capacity?

The queue does not need to use std::queue. It can be pre-allocated and use manual begin/end tracking. This does not affect the capacity (<= N).

Aha, ok, then that your change looks like a good follow-up.

3. Not removing from the Set after processing.
4. assert instead of continue

I'll leave it up to @courbet.
I'm just not super happy these 'assortment' commits, with multiple separable changes.

I think I have a slight preference for the other commit because of the vector vs deque (not in the current form though, but when everything is moved to a separate struct).

[lebedev.ri]

In D54514#1305100, @courbet wrote:

In D54514#1303407, @lebedev.ri wrote:

In D54514#1303148, @MaskRay wrote:

In D54514#1303127, @lebedev.ri wrote:

In D54514#1303114, @MaskRay wrote:

Anyway, I think this is superseded by https://reviews.llvm.org/D54442

I looked at that, and i think it does at least four things at once:

1. Exactly what this diff does, llvm::SetVector<> -> std::{CONTAINER}<size_t> Workqueue + std::{CONTAINER}<size_t> Set.

2. std::deque<size_t> Workqueue -> std::vector<size_t> with manual begin/end tracking. FIXME: how does this affect the capacity?

The queue does not need to use std::queue. It can be pre-allocated and use manual begin/end tracking. This does not affect the capacity (<= N).

Aha, ok, then that your change looks like a good follow-up.

3. Not removing from the Set after processing.
4. assert instead of continue

I'll leave it up to @courbet.
I'm just not super happy these 'assortment' commits, with multiple separable changes.

I think I have a slight preference for the other commit because of the vector vs deque

Cool.

(not in the current form though, but when everything is moved to a separate struct).

Abstractions are good :)

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,
llvm::Error InstructionBenchmarkClustering::validateAndSetup() {
   if (LastMeasurement) {
     NumDimensions_ = LastMeasurement->size();
   }
   return llvm::Error::success();
 }
 
 void InstructionBenchmarkClustering::dbScan(const size_t MinPts) {
   std::vector<size_t> Neighbors; // Persistent buffer to avoid allocs.
+  std::deque<size_t> Workqueue(Points_.size());
+  std::vector<char> Set(Points_.size(), char(0));
   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();
       continue;
     }
 
     // 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, std::deque<size_t>> ToProcess;
-    ToProcess.insert(Neighbors.begin(), Neighbors.end());
-    while (!ToProcess.empty()) {
+    Workqueue.assign(Neighbors.begin(), Neighbors.end());
+    for (size_t Neighbor : Neighbors)
+      Set[Neighbor] = 1;
+    while (!Workqueue.empty()) {
       // Retrieve a point from the set.
-      const size_t Q = *ToProcess.begin();
-      ToProcess.erase(ToProcess.begin());
+      const size_t Q = Workqueue.front();
+      Workqueue.pop_front();
+      Set[Q] = 0;
 
       if (ClusterIdForPoint_[Q].isNoise()) {
         // Change noise point to border point.
         ClusterIdForPoint_[Q] = CurrentCluster.Id;
         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.
       rangeQuery(Q, Neighbors);
       if (Neighbors.size() + 1 >= MinPts) {
-        ToProcess.insert(Neighbors.begin(), Neighbors.end());
+        for (size_t Neighbor : Neighbors) {
+          if (Set[Neighbor])
+            continue;
+          Set[Neighbor] = 1;
+          Workqueue.push_back(Neighbor);
+        }
       }
     }
   }
   // 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) {