[libc++] Optimize ranges::find for vector<bool>

Benchmark results:
```
----------------------------------------------------------------
Benchmark                                    old             new
----------------------------------------------------------------
bm_vector_bool_ranges_find/1             5.64 ns         6.08 ns
bm_vector_bool_ranges_find/2             16.5 ns         6.03 ns
bm_vector_bool_ranges_find/3             20.3 ns         6.07 ns
bm_vector_bool_ranges_find/4             22.2 ns         6.08 ns
bm_vector_bool_ranges_find/5             23.5 ns         6.05 ns
bm_vector_bool_ranges_find/6             24.4 ns         6.10 ns
bm_vector_bool_ranges_find/7             26.7 ns         6.10 ns
bm_vector_bool_ranges_find/8             25.0 ns         6.08 ns
bm_vector_bool_ranges_find/16            27.9 ns         6.07 ns
bm_vector_bool_ranges_find/64            44.5 ns         5.35 ns
bm_vector_bool_ranges_find/512            243 ns         25.7 ns
bm_vector_bool_ranges_find/4096          1858 ns         35.6 ns
bm_vector_bool_ranges_find/32768        15461 ns         93.5 ns
bm_vector_bool_ranges_find/262144      126462 ns          571 ns
bm_vector_bool_ranges_find/1048576     497736 ns         2272 ns
```

Reviewed By: #libc, Mordante

Spies: var-const, Mordante, libcxx-commits

Differential Revision: https://reviews.llvm.org/D156039

1 files changed, 28 insertions, 0 deletions

diff --git a/libcxx/benchmarks/algorithms/find.bench.cpp b/libcxx/benchmarks/algorithms/find.bench.cpp
index 65b2cda..b87c575 100644
--- a/libcxx/benchmarks/algorithms/find.bench.cpp
+++ b/libcxx/benchmarks/algorithms/find.bench.cpp
@@ -46,4 +46,32 @@ BENCHMARK(bm_ranges_find<char>)->DenseRange(1, 8)->Range(16, 1 << 20);
 BENCHMARK(bm_ranges_find<short>)->DenseRange(1, 8)->Range(16, 1 << 20);
 BENCHMARK(bm_ranges_find<int>)->DenseRange(1, 8)->Range(16, 1 << 20);
 
+static void bm_vector_bool_find(benchmark::State& state) {
+  std::vector<bool> vec1(state.range(), false);
+  std::mt19937_64 rng(std::random_device{}());
+
+  for (auto _ : state) {
+    auto idx  = rng() % vec1.size();
+    vec1[idx] = true;
+    benchmark::DoNotOptimize(vec1);
+    benchmark::DoNotOptimize(std::find(vec1.begin(), vec1.end(), true));
+    vec1[idx] = false;
+  }
+}
+BENCHMARK(bm_vector_bool_find)->DenseRange(1, 8)->Range(16, 1 << 20);
+
+static void bm_vector_bool_ranges_find(benchmark::State& state) {
+  std::vector<bool> vec1(state.range(), false);
+  std::mt19937_64 rng(std::random_device{}());
+
+  for (auto _ : state) {
+    auto idx  = rng() % vec1.size();
+    vec1[idx] = true;
+    benchmark::DoNotOptimize(vec1);
+    benchmark::DoNotOptimize(std::ranges::find(vec1, true));
+    vec1[idx] = false;
+  }
+}
+BENCHMARK(bm_vector_bool_ranges_find)->DenseRange(1, 8)->Range(16, 1 << 20);
+
 BENCHMARK_MAIN();