ceph/src/boost/libs/algorithm/minmax/doc/minmax_benchs.html

   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&lt;>::iterator</tt> or
  28 <tt>map&lt;>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&lt;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&lt;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&lt;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>&copy; Copyright Herv&eacute;
 518 Br&ouml;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>