From 7717a549e91c4fb554b78fce38e75b0147fb6cac Mon Sep 17 00:00:00 2001 From: Peng Liu Date: Wed, 26 Feb 2025 12:18:25 -0500 Subject: [libc++] Optimize ranges::equal for vector::iterator (#121084) This PR optimizes the performance of `std::ranges::equal` for `vector::iterator`, addressing a subtask outlined in issue #64038. The optimizations yield performance improvements of up to 188x for aligned equality comparison and 82x for unaligned equality comparison. Moreover, comprehensive tests covering up to 4 storage words (256 bytes) with odd and even bit sizes are provided, which validate the proposed optimizations in this patch. --- libcxx/test/benchmarks/algorithms/equal.bench.cpp | 51 +++++++++++++++++++++++ 1 file changed, 51 insertions(+) (limited to 'libcxx/test/benchmarks/algorithms/equal.bench.cpp') diff --git a/libcxx/test/benchmarks/algorithms/equal.bench.cpp b/libcxx/test/benchmarks/algorithms/equal.bench.cpp index 2dc1158..328b396 100644 --- a/libcxx/test/benchmarks/algorithms/equal.bench.cpp +++ b/libcxx/test/benchmarks/algorithms/equal.bench.cpp @@ -45,4 +45,55 @@ static void bm_ranges_equal(benchmark::State& state) { } BENCHMARK(bm_ranges_equal)->DenseRange(1, 8)->Range(16, 1 << 20); +static void bm_ranges_equal_vb_aligned(benchmark::State& state) { + auto n = state.range(); + std::vector vec1(n, true); + std::vector vec2(n, true); + for (auto _ : state) { + benchmark::DoNotOptimize(std::ranges::equal(vec1, vec2)); + benchmark::DoNotOptimize(&vec1); + benchmark::DoNotOptimize(&vec2); + } +} + +static void bm_ranges_equal_vb_unaligned(benchmark::State& state) { + auto n = state.range(); + std::vector vec1(n, true); + std::vector vec2(n + 8, true); + auto beg1 = std::ranges::begin(vec1); + auto end1 = std::ranges::end(vec1); + auto beg2 = std::ranges::begin(vec2) + 4; + auto end2 = std::ranges::end(vec2) - 4; + for (auto _ : state) { + benchmark::DoNotOptimize(std::ranges::equal(beg1, end1, beg2, end2)); + benchmark::DoNotOptimize(&vec1); + benchmark::DoNotOptimize(&vec2); + } +} + +// Test std::ranges::equal for vector::iterator +BENCHMARK(bm_ranges_equal_vb_aligned)->RangeMultiplier(4)->Range(8, 1 << 20); +BENCHMARK(bm_ranges_equal_vb_unaligned)->Range(8, 1 << 20); + +static void bm_equal_vb(benchmark::State& state, bool aligned) { + auto n = state.range(); + std::vector vec1(n, true); + std::vector vec2(aligned ? n : n + 8, true); + auto beg1 = vec1.begin(); + auto end1 = vec1.end(); + auto beg2 = aligned ? vec2.begin() : vec2.begin() + 4; + for (auto _ : state) { + benchmark::DoNotOptimize(std::equal(beg1, end1, beg2)); + benchmark::DoNotOptimize(&vec1); + benchmark::DoNotOptimize(&vec2); + } +} + +static void bm_equal_vb_aligned(benchmark::State& state) { bm_equal_vb(state, true); } +static void bm_equal_vb_unaligned(benchmark::State& state) { bm_equal_vb(state, false); } + +// Test std::equal for vector::iterator +BENCHMARK(bm_equal_vb_aligned)->Range(8, 1 << 20); +BENCHMARK(bm_equal_vb_unaligned)->Range(8, 1 << 20); + BENCHMARK_MAIN(); -- cgit v1.1