From bbf2ed7890615a587f0209c6d7e9b2c08781ee09 Mon Sep 17 00:00:00 2001 From: Evan Brown Date: Mon, 17 Oct 2022 12:56:53 -0700 Subject: 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 --- absl/container/btree_benchmark.cc | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) (limited to 'absl/container/btree_benchmark.cc') 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 #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>& b) { BIG_TYPE_PTR_BENCHMARKS(32); +void BM_BtreeSet_IteratorSubtraction(benchmark::State& state) { + absl::InsecureBitGen bitgen; + std::vector 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 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(end)) - + set.find(static_cast(begin))); + distance = absl::Uniform(bitgen, 0u, set.size()); + } +} + +BENCHMARK(BM_BtreeSet_IteratorSubtraction)->Range(1 << 10, 1 << 20); + } // namespace } // namespace container_internal ABSL_NAMESPACE_END -- cgit v1.2.3