Implement btree_iterator::operator-, which is faster than std::distance for btree iterators.

Note: btree_iterator::operator- is still O(N) because in the worst case (end()-begin()), we will have at least one operation per node in the tree, and there are at least N/M nodes, where M (a constant) is the maximum number of values per node.
PiperOrigin-RevId: 481716874
Change-Id: Ic0225b7509208ed96b75a2dc626d2aa4a24f4946

1 files changed, 25 insertions, 0 deletions

diff --git a/absl/container/btree_benchmark.cc b/absl/container/btree_benchmark.cc
index cc9a106d..0d26fd42 100644
--- a/absl/container/btree_benchmark.cc
+++ b/absl/container/btree_benchmark.cc
@@ -27,6 +27,7 @@
 #include <vector>
 
 #include "benchmark/benchmark.h"
+#include "absl/algorithm/container.h"
 #include "absl/base/internal/raw_logging.h"
 #include "absl/container/btree_map.h"
 #include "absl/container/btree_set.h"
@@ -37,6 +38,7 @@
 #include "absl/hash/hash.h"
 #include "absl/log/log.h"
 #include "absl/memory/memory.h"
+#include "absl/random/random.h"
 #include "absl/strings/cord.h"
 #include "absl/strings/str_format.h"
 #include "absl/time/time.h"
@@ -733,6 +735,29 @@ double ContainerInfo(const btree_map<int, BigTypePtr<Size>>& b) {
 
 BIG_TYPE_PTR_BENCHMARKS(32);
 
+void BM_BtreeSet_IteratorSubtraction(benchmark::State& state) {
+  absl::InsecureBitGen bitgen;
+  std::vector<int> vec;
+  // Randomize the set's insertion order so the nodes aren't all full.
+  vec.reserve(state.range(0));
+  for (int i = 0; i < state.range(0); ++i) vec.push_back(i);
+  absl::c_shuffle(vec, bitgen);
+
+  absl::btree_set<int> set;
+  for (int i : vec) set.insert(i);
+
+  size_t distance = absl::Uniform(bitgen, 0u, set.size());
+  while (state.KeepRunningBatch(distance)) {
+    size_t end = absl::Uniform(bitgen, distance, set.size());
+    size_t begin = end - distance;
+    benchmark::DoNotOptimize(set.find(static_cast<int>(end)) -
+                             set.find(static_cast<int>(begin)));
+    distance = absl::Uniform(bitgen, 0u, set.size());
+  }
+}
+
+BENCHMARK(BM_BtreeSet_IteratorSubtraction)->Range(1 << 10, 1 << 20);
+
 }  // namespace
 }  // namespace container_internal
 ABSL_NAMESPACE_END