]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <!doctype html public "-//w3c//dtd html 4.0 transitional//en"> |
2 | <html> | |
3 | <head> | |
4 | <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> | |
5 | <meta name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]"> | |
6 | <meta name="Author" content="Herve Bronnimann"> | |
7 | <meta name="Description" content="Small library to propose minmax_element algorithm."> | |
8 | <title>Boost minmax library</title> | |
9 | </head> | |
10 | <body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000"> | |
11 | ||
12 | <center> | |
13 | <h1> | |
14 | Minmax_element Performance</h1></center> | |
15 | ||
16 | <h3> | |
17 | <a NAME="Performance"></a><b>About performance</b></h3> | |
18 | Of course, there are many factors that affect the performance of an algorithm. | |
19 | The number of comparison is only one, but also branch prediction, pipelining, | |
20 | locality of reference (affects cache efficiency), etc. In practice, | |
21 | we observe that when the iterator type is a pointer, | |
22 | <tt>boost::minmax_element</tt> | |
23 | is only a tad slower than | |
24 | <tt>std::min_element</tt>, and is even faster | |
25 | than | |
26 | <tt>boost::first_min_last_max_element</tt>! This is even more true | |
27 | for slower iterators (<tt>list<>::iterator</tt> or | |
28 | <tt>map<>iterator</tt> | |
29 | for instance). The following experiments were conducted on a Pentium III | |
30 | 500 Mhz running Linux and compiled with g++, version 2.95.2, flags -O3. | |
31 | In the tables, we use different distributions: <i>Identical</i> means that | |
32 | all the elements are identical, <i>2-valued</i> means that we replace the | |
33 | second half of the identical elements by a distinct element, <i>increasing</i> | |
34 | means that all the elements are distinct and in increasing order, <i>decrea</i>sing | |
35 | is the reverse, and <i>random</i> is produced by random_shuffle. | |
36 | <br> | |
37 | The program that created these tables is included in the distribution, | |
38 | under <a href="../example/minmax_timer.cpp">minmax_timer.cpp</a> | |
39 | <br> | |
40 | <center><table BORDER NOSAVE > | |
41 | <tr NOSAVE> | |
42 | <td NOSAVE><b>vector<int>::iterator</b></td> | |
43 | ||
44 | <td>Identical</td> | |
45 | ||
46 | <td>2-valued</td> | |
47 | ||
48 | <td>Increasing</td> | |
49 | ||
50 | <td>Decreasing</td> | |
51 | ||
52 | <td>Random</td> | |
53 | </tr> | |
54 | ||
55 | <tr> | |
56 | <td>std::min_element</td> | |
57 | ||
58 | <td>23.26M/s</td> | |
59 | ||
60 | <td>23.26M/s</td> | |
61 | ||
62 | <td>23.15M/s</td> | |
63 | ||
64 | <td>22.94M/s</td> | |
65 | ||
66 | <td>22.94M/s</td> | |
67 | </tr> | |
68 | ||
69 | <tr> | |
70 | <td>std::max_element</td> | |
71 | ||
72 | <td>23.26M/s</td> | |
73 | ||
74 | <td>23.26M/s</td> | |
75 | ||
76 | <td>23.15M/s</td> | |
77 | ||
78 | <td>22.94M/s</td> | |
79 | ||
80 | <td>22.62M/s</td> | |
81 | </tr> | |
82 | ||
83 | <tr> | |
84 | <td>boost::first_min_element</td> | |
85 | ||
86 | <td>23.15M/s</td> | |
87 | ||
88 | <td>23.04M/s</td> | |
89 | ||
90 | <td>23.04M/s</td> | |
91 | ||
92 | <td>22.94M/s</td> | |
93 | ||
94 | <td>22.83M/s</td> | |
95 | </tr> | |
96 | ||
97 | <tr> | |
98 | <td>boost::last_min_element</td> | |
99 | ||
100 | <td>23.26M/s</td> | |
101 | ||
102 | <td>23.26M/s</td> | |
103 | ||
104 | <td>23.26M/s</td> | |
105 | ||
106 | <td>22.83M/s</td> | |
107 | ||
108 | <td>16.23M/s</td> | |
109 | </tr> | |
110 | ||
111 | <tr> | |
112 | <td>boost::first_max_element</td> | |
113 | ||
114 | <td>23.15M/s</td> | |
115 | ||
116 | <td>23.26M/s</td> | |
117 | ||
118 | <td>23.15M/s</td> | |
119 | ||
120 | <td>23.04M/s</td> | |
121 | ||
122 | <td>22.93M/s</td> | |
123 | </tr> | |
124 | ||
125 | <tr> | |
126 | <td>boost::last_max_element</td> | |
127 | ||
128 | <td>23.26M/s</td> | |
129 | ||
130 | <td>23.15M/s</td> | |
131 | ||
132 | <td>23.15M/s</td> | |
133 | ||
134 | <td>22.94M/s</td> | |
135 | ||
136 | <td>16.18M/s</td> | |
137 | </tr> | |
138 | ||
139 | <tr> | |
140 | <td>boost::minmax_element</td> | |
141 | ||
142 | <td>21.83M/s</td> | |
143 | ||
144 | <td>21.83M/s</td> | |
145 | ||
146 | <td>21.83M/s</td> | |
147 | ||
148 | <td>21.55M/s</td> | |
149 | ||
150 | <td>17.79M/s</td> | |
151 | </tr> | |
152 | ||
153 | <tr> | |
154 | <td>boost::first_min_last_max_element</td> | |
155 | ||
156 | <td>18.52M/s</td> | |
157 | ||
158 | <td>18.38M/s</td> | |
159 | ||
160 | <td>18.38M/s</td> | |
161 | ||
162 | <td>18.94M/s</td> | |
163 | ||
164 | <td>16.29M/s</td> | |
165 | </tr> | |
166 | ||
167 | <tr> | |
168 | <td>boost::last_min_first_max_element</td> | |
169 | ||
170 | <td>20.08M/s</td> | |
171 | ||
172 | <td>20.83M/s</td> | |
173 | ||
174 | <td>20.75M/s</td> | |
175 | ||
176 | <td>19.76M/s</td> | |
177 | ||
178 | <td>15.87M/s</td> | |
179 | </tr> | |
180 | ||
181 | <tr> | |
182 | <td>boost::last_min_last_max_element</td> | |
183 | ||
184 | <td>18.66M/s</td> | |
185 | ||
186 | <td>19.69M/s</td> | |
187 | ||
188 | <td>19.69M/s</td> | |
189 | ||
190 | <td>19.23M/s</td> | |
191 | ||
192 | <td>15.77M/s</td> | |
193 | </tr> | |
194 | ||
195 | <caption ALIGN=BOTTOM>Number of elements per second for standard vector | |
196 | container iterators</caption> | |
197 | </table></center> | |
198 | ||
199 | <center><table BORDER NOSAVE > | |
200 | <tr NOSAVE> | |
201 | <td NOSAVE><b>list<int>::iterator</b></td> | |
202 | ||
203 | <td>Identical</td> | |
204 | ||
205 | <td>2-valued</td> | |
206 | ||
207 | <td>Increasing</td> | |
208 | ||
209 | <td>Decreasing</td> | |
210 | ||
211 | <td>Random</td> | |
212 | </tr> | |
213 | ||
214 | <tr> | |
215 | <td>std::min_element</td> | |
216 | ||
217 | <td>5.8M/s</td> | |
218 | ||
219 | <td>5.8M/s</td> | |
220 | ||
221 | <td>5.80M/s</td> | |
222 | ||
223 | <td>5.73M/s</td> | |
224 | ||
225 | <td>5.73M/s</td> | |
226 | </tr> | |
227 | ||
228 | <tr> | |
229 | <td>std::max_element</td> | |
230 | ||
231 | <td>5.81M/s</td> | |
232 | ||
233 | <td>5.81M/s</td> | |
234 | ||
235 | <td>5.78M/s</td> | |
236 | ||
237 | <td>5.73M/s</td> | |
238 | ||
239 | <td>5.75M/s</td> | |
240 | </tr> | |
241 | ||
242 | <tr> | |
243 | <td>boost::first_min_element</td> | |
244 | ||
245 | <td>5.81M/s</td> | |
246 | ||
247 | <td>5.81M/s</td> | |
248 | ||
249 | <td>5.79M/s</td> | |
250 | ||
251 | <td>5.75M/s</td> | |
252 | ||
253 | <td>5.73M/s</td> | |
254 | </tr> | |
255 | ||
256 | <tr> | |
257 | <td>boost::last_min_element</td> | |
258 | ||
259 | <td>5.81M/s</td> | |
260 | ||
261 | <td>5.80M/s</td> | |
262 | ||
263 | <td>5.79M/s</td> | |
264 | ||
265 | <td>5.73M/s</td> | |
266 | ||
267 | <td>5.03M/s</td> | |
268 | </tr> | |
269 | ||
270 | <tr> | |
271 | <td>boost::first_max_element</td> | |
272 | ||
273 | <td>5.81M/s</td> | |
274 | ||
275 | <td>5.80M/s</td> | |
276 | ||
277 | <td>5.78M/s</td> | |
278 | ||
279 | <td>5.74M/s</td> | |
280 | ||
281 | <td>5.73M/s</td> | |
282 | </tr> | |
283 | ||
284 | <tr> | |
285 | <td>boost::last_max_element</td> | |
286 | ||
287 | <td>5.81M/s</td> | |
288 | ||
289 | <td>5.80M/s</td> | |
290 | ||
291 | <td>5.79M/s</td> | |
292 | ||
293 | <td>5.73M/s</td> | |
294 | ||
295 | <td>5.07M/s</td> | |
296 | </tr> | |
297 | ||
298 | <tr> | |
299 | <td>boost::minmax_element</td> | |
300 | ||
301 | <td>5.68M/s</td> | |
302 | ||
303 | <td>5.80M/s</td> | |
304 | ||
305 | <td>5.66M/s</td> | |
306 | ||
307 | <td>5.74M/s</td> | |
308 | ||
309 | <td>5.30M/s</td> | |
310 | </tr> | |
311 | ||
312 | <tr> | |
313 | <td>boost::first_min_last_max_element</td> | |
314 | ||
315 | <td>5.79M/s</td> | |
316 | ||
317 | <td>5.81M/s</td> | |
318 | ||
319 | <td>5.78M/s</td> | |
320 | ||
321 | <td>5.73M/s</td> | |
322 | ||
323 | <td>5.04M/s</td> | |
324 | </tr> | |
325 | ||
326 | <tr> | |
327 | <td>boost::last_min_first_max_element</td> | |
328 | ||
329 | <td>5.69M/s</td> | |
330 | ||
331 | <td>5.79M/s</td> | |
332 | ||
333 | <td>5.69M/s</td> | |
334 | ||
335 | <td>5.73M/s</td> | |
336 | ||
337 | <td>4.84M/s</td> | |
338 | </tr> | |
339 | ||
340 | <tr> | |
341 | <td>boost::last_min_last_max_element</td> | |
342 | ||
343 | <td>5.61M/s</td> | |
344 | ||
345 | <td>5.79M/s</td> | |
346 | ||
347 | <td>5.64M/s</td> | |
348 | ||
349 | <td>5.74M/s</td> | |
350 | ||
351 | <td>4.75M/s</td> | |
352 | </tr> | |
353 | ||
354 | <caption ALIGN=BOTTOM>Runtimes for standard list container iterators</caption> | |
355 | </table></center> | |
356 | ||
357 | <center><table BORDER NOSAVE > | |
358 | <tr NOSAVE> | |
359 | <td NOSAVE><b>multiset<int>::iterator</b></td> | |
360 | ||
361 | <td>Identical</td> | |
362 | ||
363 | <td>2-valued</td> | |
364 | ||
365 | <td>Increasing</td> | |
366 | ||
367 | <td>Decreasing</td> | |
368 | ||
369 | <td>Random</td> | |
370 | </tr> | |
371 | ||
372 | <tr> | |
373 | <td>std::min_element</td> | |
374 | ||
375 | <td>4.03M/s</td> | |
376 | ||
377 | <td>4.04M/s</td> | |
378 | ||
379 | <td>4.02M/s</td> | |
380 | ||
381 | <td>4.04M/s</td> | |
382 | ||
383 | <td>2.97M/s</td> | |
384 | </tr> | |
385 | ||
386 | <tr> | |
387 | <td>std::max_element3.007M</td> | |
388 | ||
389 | <td>4.02M/s</td> | |
390 | ||
391 | <td>4.02M/s</td> | |
392 | ||
393 | <td>4.01M/s</td> | |
394 | ||
395 | <td>4.02M/s</td> | |
396 | ||
397 | <td>2.96M/s</td> | |
398 | </tr> | |
399 | ||
400 | <tr> | |
401 | <td>boost::first_min_element</td> | |
402 | ||
403 | <td>4.01M/s</td> | |
404 | ||
405 | <td>4.04M/s</td> | |
406 | ||
407 | <td>4.03M/s</td> | |
408 | ||
409 | <td>4.04M/s</td> | |
410 | ||
411 | <td>3.01M/s</td> | |
412 | </tr> | |
413 | ||
414 | <tr> | |
415 | <td>boost::last_min_element</td> | |
416 | ||
417 | <td>4.03M/s</td> | |
418 | ||
419 | <td>4.04M/s</td> | |
420 | ||
421 | <td>4.04M/s</td> | |
422 | ||
423 | <td>4.04M/s</td> | |
424 | ||
425 | <td>3.00M/s</td> | |
426 | </tr> | |
427 | ||
428 | <tr> | |
429 | <td>boost::first_max_element</td> | |
430 | ||
431 | <td>4.04M/s</td> | |
432 | ||
433 | <td>4.04M/s</td> | |
434 | ||
435 | <td>4.04M/s</td> | |
436 | ||
437 | <td>4.06M/s</td> | |
438 | ||
439 | <td>3.01M/s</td> | |
440 | </tr> | |
441 | ||
442 | <tr> | |
443 | <td>boost::last_max_element</td> | |
444 | ||
445 | <td>4.04M/s</td> | |
446 | ||
447 | <td>4.04M/s</td> | |
448 | ||
449 | <td>4.03M/s</td> | |
450 | ||
451 | <td>4.04M/s</td> | |
452 | ||
453 | <td>3.00M/s</td> | |
454 | </tr> | |
455 | ||
456 | <tr> | |
457 | <td>boost::minmax_element</td> | |
458 | ||
459 | <td>3.98M/s</td> | |
460 | ||
461 | <td>3.99M/s</td> | |
462 | ||
463 | <td>3.98M/s</td> | |
464 | ||
465 | <td>3.99M/s</td> | |
466 | ||
467 | <td>3.00M/s</td> | |
468 | </tr> | |
469 | ||
470 | <tr> | |
471 | <td>boost::first_min_last_max_element</td> | |
472 | ||
473 | <td>3.99M/s</td> | |
474 | ||
475 | <td>3.98M/s</td> | |
476 | ||
477 | <td>3.97M/s</td> | |
478 | ||
479 | <td>3.99M/s</td> | |
480 | ||
481 | <td>2.99M/s</td> | |
482 | </tr> | |
483 | ||
484 | <tr> | |
485 | <td>boost::last_min_first_max_element</td> | |
486 | ||
487 | <td>3.97M/s</td> | |
488 | ||
489 | <td>3.98M/s</td> | |
490 | ||
491 | <td>3.96M/s</td> | |
492 | ||
493 | <td>3.98M/s</td> | |
494 | ||
495 | <td>3.00M/s</td> | |
496 | </tr> | |
497 | ||
498 | <tr> | |
499 | <td>boost::last_min_last_max_element</td> | |
500 | ||
501 | <td>4.00M/s</td> | |
502 | ||
503 | <td>4.00M/s</td> | |
504 | ||
505 | <td>4.00M/s</td> | |
506 | ||
507 | <td>4.02M/s</td> | |
508 | ||
509 | <td>2.97M/s</td> | |
510 | </tr> | |
511 | ||
512 | <caption ALIGN=BOTTOM>Runtimes for standard set/multiset container iterators</caption> | |
513 | </table></center> | |
514 | ||
515 | <hr SIZE="6"> | |
516 | <br>Last modified 2004-06-28 | |
517 | <p><font face="Arial,Helvetica"><font size=-1>© Copyright Hervé | |
518 | Brönnimann, Polytechnic University, 2002--2004. | |
519 | Use, modification, and distribution is subject to the Boost Software | |
520 | License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at | |
521 | <a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>) | |
522 | </font></font> | |
523 | </body> | |
524 | </html> |