]>
Commit | Line | Data |
---|---|---|
7adcbafe | 1 | // Copyright (C) 2020-2022 Free Software Foundation, Inc. |
ba23e045 FD |
2 | // |
3 | // This file is part of the GNU ISO C++ Library. This library is free | |
4 | // software; you can redistribute it and/or modify it under the | |
5 | // terms of the GNU General Public License as published by the | |
6 | // Free Software Foundation; either version 3, or (at your option) | |
7 | // any later version. | |
8 | ||
9 | // This library is distributed in the hope that it will be useful, | |
10 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
12 | // GNU General Public License for more details. | |
13 | ||
14 | // You should have received a copy of the GNU General Public License along | |
15 | // with this library; see the file COPYING3. If not see | |
16 | // <http://www.gnu.org/licenses/>. | |
17 | ||
18 | #include <vector> | |
19 | #include <algorithm> | |
20 | #include <cmath> | |
21 | ||
22 | #include <testsuite_new_operators.h> | |
23 | #include <testsuite_performance.h> | |
24 | ||
25 | const int max_size = 10000000; | |
26 | const int small_size = 200000; | |
27 | const int front_pivot_idx = 10000; | |
28 | int middle_pivot_idx = max_size / 2; | |
29 | int back_pivot_idx = max_size - front_pivot_idx; | |
30 | ||
31 | void bench(int mem_threshold, int pivot_index, | |
32 | std::vector<int> revv, | |
33 | std::vector<int> fwdv, | |
34 | std::vector<int> wstv, | |
35 | std::vector<int> rndv) | |
36 | { | |
37 | using namespace __gnu_test; | |
38 | ||
39 | time_counter time; | |
40 | resource_counter resource; | |
41 | ||
42 | set_new_limit(mem_threshold); | |
43 | ||
44 | start_counters(time, resource); | |
45 | std::inplace_merge(revv.begin(), revv.begin() + pivot_index, revv.end()); | |
46 | stop_counters(time, resource); | |
47 | ||
48 | set_new_limit(~size_t(0)); | |
49 | ||
50 | report_performance(__FILE__, "reverse", time, resource); | |
51 | clear_counters(time, resource); | |
52 | ||
53 | set_new_limit(mem_threshold); | |
54 | ||
55 | start_counters(time, resource); | |
56 | std::inplace_merge(fwdv.begin(), fwdv.begin() + pivot_index, fwdv.end()); | |
57 | stop_counters(time, resource); | |
58 | ||
59 | set_new_limit(~size_t(0)); | |
60 | ||
61 | report_performance(__FILE__, "forward", time, resource); | |
62 | clear_counters(time, resource); | |
63 | ||
64 | set_new_limit(mem_threshold); | |
65 | ||
66 | start_counters(time, resource); | |
67 | std::inplace_merge(wstv.begin(), wstv.begin() + pivot_index, wstv.end()); | |
68 | stop_counters(time, resource); | |
69 | ||
70 | set_new_limit(~size_t(0)); | |
71 | ||
72 | report_performance(__FILE__, "worst", time, resource); | |
73 | clear_counters(time, resource); | |
74 | ||
75 | set_new_limit(mem_threshold); | |
76 | ||
77 | start_counters(time, resource); | |
78 | std::inplace_merge(rndv.begin(), rndv.begin() + pivot_index, rndv.end()); | |
79 | stop_counters(time, resource); | |
80 | ||
81 | set_new_limit(~size_t(0)); | |
82 | report_performance(__FILE__, "random", time, resource); | |
83 | } | |
84 | ||
85 | void mem_bench(double mem_ratio, | |
86 | const std::vector<int>& front_revv, | |
87 | const std::vector<int>& middle_revv, | |
88 | const std::vector<int>& back_revv, | |
89 | const std::vector<int>& fwdv, | |
90 | const std::vector<int>& front_wstv, | |
91 | const std::vector<int>& middle_wstv, | |
92 | const std::vector<int>& back_wstv, | |
93 | const std::vector<int>& front_rndv, | |
94 | const std::vector<int>& middle_rndv, | |
95 | const std::vector<int>& back_rndv) | |
96 | { | |
97 | using namespace __gnu_test; | |
98 | ||
99 | time_counter time; | |
100 | resource_counter resource; | |
101 | ||
102 | int max_mem = (int)std::ceil(front_pivot_idx * mem_ratio) * sizeof(int); | |
103 | start_counters(time, resource); | |
104 | bench(max_mem, front_pivot_idx, front_revv, fwdv, front_wstv, front_rndv); | |
105 | stop_counters(time, resource); | |
106 | report_performance(__FILE__, "front pivot", time, resource); | |
107 | clear_counters(time, resource); | |
108 | ||
109 | max_mem = (int)std::ceil(middle_pivot_idx * mem_ratio) * sizeof(int); | |
110 | start_counters(time, resource); | |
111 | bench(max_mem, middle_pivot_idx, middle_revv, fwdv, middle_wstv, middle_rndv); | |
112 | stop_counters(time, resource); | |
113 | report_performance(__FILE__, "middle pivot", time, resource); | |
114 | clear_counters(time, resource); | |
115 | ||
116 | max_mem = (int)std::ceil(front_pivot_idx * mem_ratio) * sizeof(int); | |
117 | start_counters(time, resource); | |
118 | bench(max_mem, back_pivot_idx, back_revv, fwdv, back_wstv, back_rndv); | |
119 | stop_counters(time, resource); | |
120 | report_performance(__FILE__, "back pivot", time, resource); | |
121 | } | |
122 | ||
123 | void init_reverse(std::vector<int>& v, size_t pivot_index) | |
124 | { | |
125 | int val = 0; | |
126 | for (size_t i = pivot_index; i != v.size(); ++i) | |
127 | v[i] = val++; | |
128 | for (size_t i = 0; i != pivot_index; ++i) | |
129 | v[i] = val++; | |
130 | } | |
131 | ||
132 | void init_forward(std::vector<int>& v) | |
133 | { | |
134 | int val = 0; | |
135 | for (size_t i = 0; i != v.size(); ++i) | |
136 | v[i] = val++; | |
137 | } | |
138 | ||
139 | void init_worst(std::vector<int>& v, size_t pivot_index) | |
140 | { | |
141 | int val = 0; | |
142 | if (pivot_index + 1 > v.size() / 2) | |
143 | { | |
144 | for (size_t i = 0; i != pivot_index; val += 2, ++i) | |
145 | v[i] = val; | |
146 | val = 1; | |
147 | } | |
148 | else | |
149 | { | |
150 | for (size_t i = pivot_index; i != v.size(); val += 2, ++i) | |
151 | v[i] = val; | |
152 | val -= pivot_index * 2 + 1; | |
153 | } | |
154 | ||
155 | if (pivot_index + 1 > v.size() / 2) | |
156 | for (size_t i = pivot_index; i != v.size(); val += 2, ++i) | |
157 | v[i] = val; | |
158 | else | |
159 | for (size_t i = 0; i != pivot_index; val += 2, ++i) | |
160 | v[i] = val; | |
161 | } | |
162 | ||
163 | void init_random(std::vector<int>& v) | |
164 | { | |
165 | // a simple pseudo-random series which does not rely on rand() and friends | |
166 | v[0] = 0; | |
167 | for (size_t i = 1; i != v.size(); ++i) | |
168 | v[i] = (v[i-1] + 110211473) * 745988807; | |
169 | } | |
170 | ||
171 | void reduce_size(std::vector<int>& front_v, | |
172 | std::vector<int>& middle_v, | |
173 | std::vector<int>& back_v) | |
174 | { | |
175 | front_v.erase(front_v.begin() + front_pivot_idx, | |
176 | front_v.end() - back_pivot_idx); | |
177 | middle_v.erase(middle_v.begin() + small_size / 2, | |
178 | middle_v.end() - small_size / 2); | |
179 | back_v.erase(back_v.begin() + back_pivot_idx, | |
180 | back_v.end() - front_pivot_idx); | |
181 | } | |
182 | ||
183 | int main() | |
184 | { | |
185 | using namespace __gnu_test; | |
186 | ||
187 | // No constraint to build vectors. | |
188 | set_new_limit(~size_t(0)); | |
189 | ||
190 | std::vector<int> front_revv(max_size); | |
191 | init_reverse(front_revv, front_pivot_idx); | |
192 | ||
193 | std::vector<int> middle_revv(max_size); | |
194 | init_reverse(middle_revv, middle_pivot_idx); | |
195 | ||
196 | std::vector<int> back_revv(max_size); | |
197 | init_reverse(back_revv, back_pivot_idx); | |
198 | ||
199 | std::vector<int> fwdv(max_size); | |
200 | init_forward(fwdv); | |
201 | ||
202 | std::vector<int> front_wstv(max_size); | |
203 | init_worst(front_wstv, front_pivot_idx); | |
204 | ||
205 | std::vector<int> middle_wstv(max_size); | |
206 | init_worst(middle_wstv, middle_pivot_idx); | |
207 | ||
208 | std::vector<int> back_wstv(max_size); | |
209 | init_worst(back_wstv, back_pivot_idx); | |
210 | ||
211 | std::vector<int> front_rndv(max_size); | |
212 | init_random(front_rndv); | |
213 | std::vector<int> middle_rndv(front_rndv); | |
214 | std::vector<int> back_rndv(front_rndv); | |
215 | ||
216 | sort(front_rndv.begin(), front_rndv.begin() + front_pivot_idx); | |
217 | sort(front_rndv.begin() + front_pivot_idx, front_rndv.end()); | |
218 | ||
219 | sort(middle_rndv.begin(), middle_rndv.begin() + middle_pivot_idx); | |
220 | sort(middle_rndv.begin() + middle_pivot_idx, middle_rndv.end()); | |
221 | ||
222 | sort(back_rndv.begin(), back_rndv.begin() + back_pivot_idx); | |
223 | sort(back_rndv.begin() + back_pivot_idx, back_rndv.end()); | |
224 | ||
225 | time_counter time; | |
226 | resource_counter resource; | |
227 | ||
228 | start_counters(time, resource); | |
229 | ||
230 | // No limit. | |
231 | mem_bench(1.0, | |
232 | front_revv, middle_revv, back_revv, | |
233 | fwdv, | |
234 | front_wstv, middle_wstv, back_wstv, | |
235 | front_rndv, middle_rndv, back_rndv); | |
236 | ||
237 | stop_counters(time, resource); | |
238 | ||
239 | report_performance(__FILE__, "bench 1 / 1 memory", time, resource); | |
240 | clear_counters(time, resource); | |
241 | ||
242 | start_counters(time, resource); | |
243 | ||
244 | // Limit to the fourth. | |
245 | mem_bench(1.0 / 4, | |
246 | front_revv, middle_revv, back_revv, | |
247 | fwdv, | |
248 | front_wstv, middle_wstv, back_wstv, | |
249 | front_rndv, middle_rndv, back_rndv); | |
250 | ||
251 | stop_counters(time, resource); | |
252 | ||
253 | report_performance(__FILE__, "bench 1 / 4 memory", time, resource); | |
254 | clear_counters(time, resource); | |
255 | ||
256 | start_counters(time, resource); | |
257 | ||
258 | // Really limit allocation. | |
259 | mem_bench(1.0 / 64, | |
260 | front_revv, middle_revv, back_revv, | |
261 | fwdv, | |
262 | front_wstv, middle_wstv, back_wstv, | |
263 | front_rndv, middle_rndv, back_rndv); | |
264 | ||
265 | stop_counters(time, resource); | |
266 | ||
267 | report_performance(__FILE__, "bench 1 /64 memory", time, resource); | |
268 | clear_counters(time, resource); | |
269 | ||
270 | middle_pivot_idx = small_size / 2; | |
271 | back_pivot_idx = small_size - front_pivot_idx; | |
272 | reduce_size(front_revv, middle_revv, back_revv); | |
273 | fwdv.resize(small_size); | |
274 | reduce_size(front_wstv, middle_wstv, back_wstv); | |
275 | reduce_size(front_rndv, middle_rndv, back_rndv); | |
276 | ||
277 | start_counters(time, resource); | |
278 | ||
279 | // No memory. | |
280 | mem_bench(0.0, | |
281 | front_revv, middle_revv, back_revv, | |
282 | fwdv, | |
283 | front_wstv, middle_wstv, back_wstv, | |
284 | front_rndv, middle_rndv, back_rndv); | |
285 | ||
286 | stop_counters(time, resource); | |
287 | ||
288 | report_performance(__FILE__, "bench 0 / 1 memory", time, resource); | |
289 | return 0; | |
290 | } |