Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit343e96e

Browse files
Optimizestd::includes by usingranges::includes approach (#5543)
Co-authored-by: Stephan T. Lavavej <stl@microsoft.com>
1 parenta4c5e3f commit343e96e

File tree

3 files changed

+146
-7
lines changed

3 files changed

+146
-7
lines changed

‎benchmarks/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -112,6 +112,7 @@ add_benchmark(fill src/fill.cpp)
112112
add_benchmark(find_and_count src/find_and_count.cpp)
113113
add_benchmark(find_first_of src/find_first_of.cpp)
114114
add_benchmark(has_single_bit src/has_single_bit.cpp)
115+
add_benchmark(includes src/includes.cpp)
115116
add_benchmark(iota src/iota.cpp)
116117
add_benchmark(is_sorted_until src/is_sorted_until.cpp)
117118
add_benchmark(locale_classic src/locale_classic.cpp)

‎benchmarks/src/includes.cpp‎

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
// Copyright (c) Microsoft Corporation.
2+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
3+
4+
#include<algorithm>
5+
#include<benchmark/benchmark.h>
6+
#include<cstddef>
7+
#include<cstdint>
8+
#include<cstdlib>
9+
#include<iostream>
10+
#include<random>
11+
#include<ranges>
12+
#include<type_traits>
13+
#include<vector>
14+
15+
#include"skewed_allocator.hpp"
16+
#include"utility.hpp"
17+
18+
usingnamespacestd;
19+
20+
enumclassalg_type { std_fn, rng };
21+
22+
enumclassneedle_spread { dense, dense_random, sparse, sparse_random };
23+
24+
template<classT, alg_type Alg>
25+
voidbm_includes(benchmark::State& state) {
26+
constauto hay_size =static_cast<size_t>(state.range(0));
27+
constauto needle_size =static_cast<size_t>(state.range(1));
28+
constauto spread =static_cast<needle_spread>(state.range(2));
29+
constauto expected_match =static_cast<bool>(state.range(3));
30+
31+
auto hay = random_vector<T, not_highly_aligned_allocator>(hay_size);
32+
ranges::sort(hay);
33+
34+
vector<T, not_highly_aligned_allocator<T>> needle;
35+
switch (spread) {
36+
case needle_spread::dense:
37+
needle.assign(hay.begin() + hay_size /2 - needle_size /2, hay.begin() + hay_size /2 + (needle_size +1) /2);
38+
break;
39+
40+
case needle_spread::dense_random:
41+
{
42+
mt19937 gen{};
43+
geometric_distribution<size_t> dis_dis{};
44+
vector<size_t>idx(needle_size);
45+
constsize_t mid = needle_size /2;
46+
idx[mid] = hay_size /2;
47+
48+
constsize_t max_shift = hay_size / needle_size;
49+
50+
for (size_t i = mid; i !=0; --i) {
51+
idx[i -1] = idx[i] -min(dis_dis(gen) +1, max_shift);
52+
}
53+
54+
for (size_t i = mid; i != needle_size -1; ++i) {
55+
idx[i +1] = idx[i] +min(dis_dis(gen) +1, max_shift);
56+
}
57+
58+
needle.assign_range(idx |views::transform([&hay](constsize_t i) {return hay[i]; }));
59+
}
60+
break;
61+
62+
case needle_spread::sparse:
63+
needle.resize(needle_size);
64+
for (size_t i =0; i != needle_size; ++i) {
65+
needle[i] = hay[hay_size * i / needle_size + hay_size / (needle_size *2)];
66+
}
67+
break;
68+
69+
case needle_spread::sparse_random:
70+
needle.resize(needle_size);
71+
ranges::sample(hay, needle.begin(), needle_size, mt19937{});
72+
break;
73+
}
74+
75+
if (!expected_match) {
76+
const T v = needle[needle_size /2];
77+
const T r =static_cast<T>(static_cast<make_unsigned_t<T>>(v) +1);
78+
ranges::replace(hay, v, r);
79+
ranges::sort(hay);
80+
}
81+
82+
for (auto _ : state) {
83+
benchmark::DoNotOptimize(hay);
84+
benchmark::DoNotOptimize(needle);
85+
bool found;
86+
ifconstexpr (Alg == alg_type::rng) {
87+
found =ranges::includes(hay, needle);
88+
}else {
89+
found =includes(hay.begin(), hay.end(), needle.begin(), needle.end());
90+
}
91+
benchmark::DoNotOptimize(found);
92+
if (found != expected_match) {
93+
cerr <<"Unexpected 'includes' result:" << found <<'\n';
94+
abort();
95+
}
96+
}
97+
}
98+
99+
voidcommon_args(auto bm) {
100+
for (constauto& spread :
101+
{needle_spread::dense, needle_spread::dense_random, needle_spread::sparse, needle_spread::sparse_random}) {
102+
for (constauto& expected_match : {true,false}) {
103+
for (constauto& needle_size : {3,22,105,1504,2750}) {
104+
bm->Args({3000, needle_size,static_cast<underlying_type_t<needle_spread>>(spread), expected_match});
105+
}
106+
107+
for (constauto& needle_size : {3,22,105,290}) {
108+
bm->Args({300, needle_size,static_cast<underlying_type_t<needle_spread>>(spread), expected_match});
109+
}
110+
}
111+
}
112+
}
113+
114+
BENCHMARK(bm_includes<int8_t, alg_type::std_fn>)->Apply(common_args);
115+
BENCHMARK(bm_includes<int16_t, alg_type::std_fn>)->Apply(common_args);
116+
BENCHMARK(bm_includes<int32_t, alg_type::std_fn>)->Apply(common_args);
117+
BENCHMARK(bm_includes<int64_t, alg_type::std_fn>)->Apply(common_args);
118+
119+
BENCHMARK(bm_includes<int8_t, alg_type::rng>)->Apply(common_args);
120+
BENCHMARK(bm_includes<int16_t, alg_type::rng>)->Apply(common_args);
121+
BENCHMARK(bm_includes<int32_t, alg_type::rng>)->Apply(common_args);
122+
BENCHMARK(bm_includes<int64_t, alg_type::rng>)->Apply(common_args);
123+
124+
BENCHMARK_MAIN();

‎stl/inc/algorithm‎

Lines changed: 21 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -10158,17 +10158,31 @@ _NODISCARD _CONSTEXPR20 bool includes(_InIt1 _First1, _InIt1 _Last1, _InIt2 _Fir
1015810158
const auto _ULast2 = _STD _Get_unwrapped(_Last2);
1015910159
_DEBUG_ORDER_SET_UNWRAPPED(_InIt2, _UFirst1, _ULast1, _Pred);
1016010160
_DEBUG_ORDER_SET_UNWRAPPED(_InIt1, _UFirst2, _ULast2, _Pred);
10161-
for (; _UFirst1 != _ULast1 && _UFirst2 != _ULast2; ++_UFirst1) {
10162-
if (_DEBUG_LT_PRED(_Pred, *_UFirst2, *_UFirst1)) {
10163-
return false;
10164-
}
1016510161

10166-
if (!_Pred(*_UFirst1, *_UFirst2)) {
10162+
if (_UFirst2 == _ULast2) {
10163+
return true;
10164+
} else if (_UFirst1 == _ULast1) {
10165+
return false;
10166+
}
10167+
10168+
for (;;) {
10169+
if (_DEBUG_LT_PRED(_Pred, *_UFirst1, *_UFirst2)) {
10170+
++_UFirst1;
10171+
if (_UFirst1 == _ULast1) {
10172+
return false;
10173+
}
10174+
} else if (_Pred(*_UFirst2, *_UFirst1)) {
10175+
return false;
10176+
} else {
10177+
++_UFirst1;
1016710178
++_UFirst2;
10179+
if (_UFirst2 == _ULast2) {
10180+
return true;
10181+
} else if (_UFirst1 == _ULast1) {
10182+
return false;
10183+
}
1016810184
}
1016910185
}
10170-
10171-
return _UFirst2 == _ULast2;
1017210186
}
1017310187

1017410188
_EXPORT_STD template <class _InIt1, class _InIt2>

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp