[llvm-exegesis] InstructionBenchmarkClustering::dbScan(): replace SetVector with custom BitVectorVector

[lebedev.ri]

Summary

As it was suggested in D54381, Set is not the optimal data structure, given the data knowledge.
We know that the values are in range [0, Points_.size()).
Thus, we really only need a single bit to track whether we have the value or not.
Naturally, BitVector fits the bill.
We can't just use BitVector as a Set in SetVector, thus i have copied SetVector
into llvm-exegesis directory, pruned everything that isn't needed, and replaced Set with BitVector terminology.

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

       6564.110422      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.19% )
...
            6.5657 +- 0.0129 seconds time elapsed  ( +-  0.20% )

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

       5553.640326      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.27% )
...
            5.5545 +- 0.0148 seconds time elapsed  ( +-  0.27% )

So another -15%.

[RKSimon]

I'm not convinced you need a new type here - why don't you just use BitVector (or SparseBitVector?) and create a helper function for the insert/erase?

[lebedev.ri]

In D54418#1295286, @RKSimon wrote:

I'm not convinced you need a new type here - why don't you just use BitVector (or SparseBitVector?) and create a helper function for the insert/erase?

I'm not sure i follow your suggestion.
In SetVector, set_ is a private member variable, i can't reach it from my custom function.

[MaskRay]

I'm also not following... DBSCAN is a BFS/Dijkstra-like algorithm. a BitVector + reserved std::vector suffice.

[lebedev.ri]

In D54418#1295941, @MaskRay wrote:

I'm also not following...

I'm sorry that i'm not following what you do not follow :)

DBSCAN is a BFS/Dijkstra-like algorithm. a BitVector + reserved std::vector suffice.

Which is exactly what this BitVectorVector implements, as far as i can tell.
I do not understand what the question is. I'm sorry. Can you reformulate the question, please?

[MaskRay]

In D54418#1295942, @lebedev.ri wrote:

In D54418#1295941, @MaskRay wrote:

I'm also not following...

I'm sorry that i'm not following what you do not follow :)

DBSCAN is a BFS/Dijkstra-like algorithm. a BitVector + reserved std::vector suffice.

Which is exactly what this BitVectorVector implements, as far as i can tell.
I do not understand what the question is. I'm sorry. Can you reformulate the question, please?

Maybe I should quote "talk is cheap" here... My idea is https://reviews.llvm.org/D54442 (I hope it won't interfere your other improvement)

[lebedev.ri]

In D54418#1296001, @MaskRay wrote:

In D54418#1295942, @lebedev.ri wrote:

In D54418#1295941, @MaskRay wrote:

I'm also not following...

I'm sorry that i'm not following what you do not follow :)

DBSCAN is a BFS/Dijkstra-like algorithm. a BitVector + reserved std::vector suffice.

Which is exactly what this BitVectorVector implements, as far as i can tell.
I do not understand what the question is. I'm sorry. Can you reformulate the question, please?

Maybe I should quote "talk is cheap" here... My idea is https://reviews.llvm.org/D54442 (I hope it won't interfere your other improvement)

I still do not understand what the question is.
Yes, that pretty much the same as this code.
Differences:

• uses pop back, instead of pop front. my measurements so far always showed pop back to be worse.
• Both data structures are inline, instead of abstracting them under BitVectorVector.
• One very interesting point - initial insertion is a special case, no need to check in the set. I do expect that to be faster, let's see..

[MaskRay]

In D54418#1296028, @lebedev.ri wrote:

In D54418#1296001, @MaskRay wrote:

In D54418#1295942, @lebedev.ri wrote:

In D54418#1295941, @MaskRay wrote:

I'm also not following...

I'm sorry that i'm not following what you do not follow :)

DBSCAN is a BFS/Dijkstra-like algorithm. a BitVector + reserved std::vector suffice.

Which is exactly what this BitVectorVector implements, as far as i can tell.
I do not understand what the question is. I'm sorry. Can you reformulate the question, please?

Maybe I should quote "talk is cheap" here... My idea is https://reviews.llvm.org/D54442 (I hope it won't interfere your other improvement)

I still do not understand what the question is.
Yes, that pretty much the same as this code.
Differences:

• uses pop back, instead of pop front. my measurements so far always showed pop back to be worse.
• Both data structures are inline, instead of abstracting them under BitVectorVector.
• One very interesting point - initial insertion is a special case, no need to check in the set. I do expect that to be faster, let's see..

Can you suggest some way to get the large benchmark file as you have in /tmp/benchmarks.yaml? I need to experiment with it but it is still unclear to me why pop_back is slower.

[lebedev.ri]

In D54418#1296040, @MaskRay wrote:

In D54418#1296028, @lebedev.ri wrote:

In D54418#1296001, @MaskRay wrote:

In D54418#1295942, @lebedev.ri wrote:

In D54418#1295941, @MaskRay wrote:

I'm also not following...

I'm sorry that i'm not following what you do not follow :)

DBSCAN is a BFS/Dijkstra-like algorithm. a BitVector + reserved std::vector suffice.

Which is exactly what this BitVectorVector implements, as far as i can tell.
I do not understand what the question is. I'm sorry. Can you reformulate the question, please?

Maybe I should quote "talk is cheap" here... My idea is https://reviews.llvm.org/D54442 (I hope it won't interfere your other improvement)

I still do not understand what the question is.
Yes, that pretty much the same as this code.
Differences:

• uses pop back, instead of pop front. my measurements so far always showed pop back to be worse.
• Both data structures are inline, instead of abstracting them under BitVectorVector.
• One very interesting point - initial insertion is a special case, no need to check in the set. I do expect that to be faster, let's see..

Can you suggest some way to get the large benchmark file as you have in /tmp/benchmarks.yaml? I need to experiment with it but it is still unclear to me why pop_back is slower.

benchmarks.yaml22 MBDownload

Please note that it is quite literally just first 500'000 lines of the full uop benchmark, which is ~10x as large.
It is that big because i was experimenting with repeating benchmarking 10x times, and then being able visually undestand what is the correct value when the benchmark ends up being noisy.

[MaskRay]

Thanks for your benchmark file!

llvm-exegesis -mode=analysis -analysis-epsilon=100000 -benchmarks-file=/tmp/Downloads/benchmarks.yaml -analysis-inconsistencies-output-file=/tmp/clusters.html > /tmp/new

https://reviews.llvm.org/D54442 alone (without your other optimization) reduces the time from 16s to 4.2s on my machine. I'll leave the const auto Neighbors = rangeQuery(Q); inlining and other stuff to you :)

[lebedev.ri]

In D54418#1296093, @MaskRay wrote:

Thanks for your benchmark file!

llvm-exegesis -mode=analysis -analysis-epsilon=100000 -benchmarks-file=/tmp/Downloads/benchmarks.yaml -analysis-inconsistencies-output-file=/tmp/clusters.html > /tmp/new

https://reviews.llvm.org/D54442 alone (without your other optimization) reduces the time from 16s to 4.2s on my machine. I'll leave the const auto Neighbors = rangeQuery(Q); inlining and other stuff to you :)

After thinking, i see what the question was - why use abstractions when you can avoid using abstractions.
Well, because they are abstractions :) I have seen a bit much code, than i would have liked to, that intentionally avoided abstractions.
So i personally would not write everything inline like it is in D54442, and would not review that.
If it is abstracted, it is more readable, actually testable. And one day might even be moved to a more common (ADT e.g.) place should others need it.
If it is all inline, someone *will* have to refactor it to use abstractions later on.
So i guess the question boils down to - why bother writing good code when one can write "C spaghetti".

I'm not sure if D54442 is just a proof-of-concept or actually for the review,
but i would personally guess that small incremental patches
(with actual perf changes stated! since it is a perf improvements patchset) are better,
since small incremental changes are anyway recommended by the coding standards.

[MaskRay]

In D54418#1296615, @lebedev.ri wrote:

In D54418#1296093, @MaskRay wrote:

Thanks for your benchmark file!

llvm-exegesis -mode=analysis -analysis-epsilon=100000 -benchmarks-file=/tmp/Downloads/benchmarks.yaml -analysis-inconsistencies-output-file=/tmp/clusters.html > /tmp/new

https://reviews.llvm.org/D54442 alone (without your other optimization) reduces the time from 16s to 4.2s on my machine. I'll leave the const auto Neighbors = rangeQuery(Q); inlining and other stuff to you :)

After thinking, i see what the question was - why use abstractions when you can avoid using abstractions.
Well, because they are abstractions :) I have seen a bit much code, than i would have liked to, that intentionally avoided abstractions.
So i personally would not write everything inline like it is in D54442, and would not review that.
If it is abstracted, it is more readable, actually testable. And one day might even be moved to a more common (ADT e.g.) place should others need it.
If it is all inline, someone *will* have to refactor it to use abstractions later on.
So i guess the question boils down to - why bother writing good code when one can write "C spaghetti".

I'm not sure if D54442 is just a proof-of-concept or actually for the review,
but i would personally guess that small incremental patches
(with actual perf changes stated! since it is a perf improvements patchset) are better,
since small incremental changes are anyway recommended by the coding standards.

D54442 is also for review. It uses inlined bit vector Added (vector<char> is faster than BitVector in this case) as I don't think the abstraction is really necessary. It is used similarly as what would be used in BFS or Dijkstra's algorithm.

[lebedev.ri]

Okay, if everyone hates abstractions, so be it, D54514 :)
Did benchmarks, std::vector<char> is indeed slightly better here.

tools/llvm-exegesis/lib/BitVectorVector.h

+//===- BitVectorVector.h - BitVector plus Vector ----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a BitVectorVector, that is much like a SetVector,
+// but uses BitVector instead of a Set.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_EXEGESIS_BITVECTORVECTOR_H
+#define LLVM_TOOLS_LLVM_EXEGESIS_BITVECTORVECTOR_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Compiler.h"
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <vector>
+
+namespace llvm {
+namespace exegesis {
+
+template <typename T, typename Vector = std::vector<T>,
+          typename BitVector = BitVector>
+class BitVectorVector {
+public:
+  using value_type = T;
+  using key_type = T;
+  using reference = T &;
+  using const_reference = const T &;
+  using bitvector_type = BitVector;
+  using vector_type = Vector;
+  using iterator = typename vector_type::const_iterator;
+  using const_iterator = typename vector_type::const_iterator;
+  using reverse_iterator = typename vector_type::const_reverse_iterator;
+  using const_reverse_iterator = typename vector_type::const_reverse_iterator;
+  using size_type = typename vector_type::size_type;
+
+  /// Construct an empty BitVectorVector
+  BitVectorVector() = default;
+
+  /// Construct an empty BitVectorVector with size Size.
+  BitVectorVector(size_t Size) : bitvector_(Size), vector_(Size) {}
+
+  /// Determine if the BitVectorVector is empty or not.
+  bool empty() const { return vector_.empty(); }
+
+  /// Get an iterator to the beginning of the BitVectorVector.
+  iterator begin() { return vector_.begin(); }
+
+  /// Get a const_iterator to the beginning of the BitVectorVector.
+  const_iterator begin() const { return vector_.begin(); }
+
+  /// Insert a range of elements into the BitVectorVector.
+  template <typename It> void insert(It Start, It End) {
+    for (; Start != End; ++Start) {
+      if (bitvector_.test(*Start))
+        continue;
+      bitvector_.set(*Start);
+      vector_.push_back(*Start);
+    }
+  }
+
+  /// Erase a single element from the bitvector vector.
+  /// \returns an iterator pointing to the next element that followed the
+  /// element erased. This is the end of the BitVectorVector if the last element
+  /// is erased.
+  iterator erase(iterator I) {
+    const key_type &V = *I;
+    assert(bitvector_.test(V) && "Corrupted BitVectorVector instances!");
+    bitvector_.reset(V);
+
+    // FIXME: No need to use the non-const iterator when built with
+    // std:vector.erase(const_iterator) as defined in C++11. This is for
+    // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
+    auto NI = vector_.begin();
+    std::advance(NI, std::distance<iterator>(NI, I));
+
+    return vector_.erase(NI);
+  }
+
+  /// Completely clear the BitVectorVector
+  void clear() {
+    bitvector_.reset();
+    vector_.clear();
+  }
+
+private:
+  bitvector_type bitvector_; ///< The bitvector.
+  vector_type vector_;       ///< The vector.
+};
+
+} // end namespace exegesis
+} // end namespace llvm
+
+#endif // LLVM_TOOLS_LLVM_EXEGESIS_BITVECTORVECTOR_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 "BitVectorVector.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.
+  BitVectorVector<size_t, std::deque<size_t>> ToProcess(Points_.size());
   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.clear();
     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.