[llvm-exegesis] BitVectorVector: provide assign() method, use it.

[lebedev.ri]

Summary

Original idea by @MaskRay in D54442.
When doing the initial filing of the BitVectorVector, we know beforehand that
we will not have duplicates in the input values, and the storage is empty,
so we don't have to check before assigning.

Old: (D54418)

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

       5597.034043      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.35% )
...
            5.5975 +- 0.0198 seconds time elapsed  ( +-  0.35% )

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

       5578.307677      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.18% )
...
            5.5800 +- 0.0101 seconds time elapsed  ( +-  0.18% )

-0.3%, not that much, but not nothing, too.

[lebedev.ri]

I will cut this patchseries here for now.
Old walltime was around ~25sec, new is ~5.6sec, so -77.58%.

5 patches remain in need of review:

• D54383 [llvm-exegesis] Analysis: writeMeasurementValue(): don't alloc string for double each time. <- self-contained, pretty trivial
• D54388 [llvm-exegesis] InstructionBenchmarkClustering::rangeQuery(): use llvm::SmallVector<size_t, 0> for storage. <- was essentially replaced by D54415, but that was only possible after D54390, so it kind-of makes sense as an intermediate step.
• Small incremental improvements to the dbScan():
  • D54381 [llvm-exegesis] InstructionBenchmarkClustering::dbScan(): use llvm::SetVector<> instead of ILLEGAL std::unordered_set<> <- very straight-forward replacement, nothing complicated
  • D54418 [llvm-exegesis] InstructionBenchmarkClustering::dbScan(): replace SetVector with custom BitVectorVector
  • D54445 [llvm-exegesis] BitVectorVector: provide assign() method, use it. <- trivial

The biggest remaining problem is within isNeighbour. It contains 99% of cache misses, due to that vector-within-vector storage.
I believe i will be able to get some improvement by

1. Precalculating (into BitVector) the is neighbor matrix. I actually already tried that, not much of an improvement, anoter 100ms i think, not worth it on it's own.

and

2. Parallelizing this computation. I have not *yet* tried this, but i'm optimistic about it.

Thanks!

[lebedev.ri]

Replaced by D54514

tools/llvm-exegesis/lib/BitVectorVector.h

public:
   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(); }
 
+  /// Assign a range of elements, replacing the existing content.
+  template <typename It> void assign(It Start, It End) {
+    clear();
+    vector_.assign(Start, End);
+    for (const value_type Value : llvm::make_range(Start, End))
+      bitvector_.set(Value);
+  }
+
   /// 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);
     }

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.
-    ToProcess.clear();
-    ToProcess.insert(Neighbors.begin(), Neighbors.end());
+    ToProcess.assign(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.
         ClusterIdForPoint_[Q] = CurrentCluster.Id;