123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524 |
- <!doctype html public "-//w3c//dtd html 4.0 transitional//en">
- <html>
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
- <meta name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]">
- <meta name="Author" content="Herve Bronnimann">
- <meta name="Description" content="Small library to propose minmax_element algorithm.">
- <title>Boost minmax library</title>
- </head>
- <body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000">
- <center>
- <h1>
- Minmax_element Performance</h1></center>
- <h3>
- <a NAME="Performance"></a><b>About performance</b></h3>
- Of course, there are many factors that affect the performance of an algorithm.
- The number of comparison is only one, but also branch prediction, pipelining,
- locality of reference (affects cache efficiency), etc. In practice,
- we observe that when the iterator type is a pointer,
- <tt>boost::minmax_element</tt>
- is only a tad slower than
- <tt>std::min_element</tt>, and is even faster
- than
- <tt>boost::first_min_last_max_element</tt>! This is even more true
- for slower iterators (<tt>list<>::iterator</tt> or
- <tt>map<>iterator</tt>
- for instance). The following experiments were conducted on a Pentium III
- 500 Mhz running Linux and compiled with g++, version 2.95.2, flags -O3.
- In the tables, we use different distributions: <i>Identical</i> means that
- all the elements are identical, <i>2-valued</i> means that we replace the
- second half of the identical elements by a distinct element, <i>increasing</i>
- means that all the elements are distinct and in increasing order, <i>decrea</i>sing
- is the reverse, and <i>random</i> is produced by random_shuffle.
- <br>
- The program that created these tables is included in the distribution,
- under <a href="../example/minmax_timer.cpp">minmax_timer.cpp</a>
- <br>
- <center><table BORDER NOSAVE >
- <tr NOSAVE>
- <td NOSAVE><b>vector<int>::iterator</b></td>
- <td>Identical</td>
- <td>2-valued</td>
- <td>Increasing</td>
- <td>Decreasing</td>
- <td>Random</td>
- </tr>
- <tr>
- <td>std::min_element</td>
- <td>23.26M/s</td>
- <td>23.26M/s</td>
- <td>23.15M/s</td>
- <td>22.94M/s</td>
- <td>22.94M/s</td>
- </tr>
- <tr>
- <td>std::max_element</td>
- <td>23.26M/s</td>
- <td>23.26M/s</td>
- <td>23.15M/s</td>
- <td>22.94M/s</td>
- <td>22.62M/s</td>
- </tr>
- <tr>
- <td>boost::first_min_element</td>
- <td>23.15M/s</td>
- <td>23.04M/s</td>
- <td>23.04M/s</td>
- <td>22.94M/s</td>
- <td>22.83M/s</td>
- </tr>
- <tr>
- <td>boost::last_min_element</td>
- <td>23.26M/s</td>
- <td>23.26M/s</td>
- <td>23.26M/s</td>
- <td>22.83M/s</td>
- <td>16.23M/s</td>
- </tr>
- <tr>
- <td>boost::first_max_element</td>
- <td>23.15M/s</td>
- <td>23.26M/s</td>
- <td>23.15M/s</td>
- <td>23.04M/s</td>
- <td>22.93M/s</td>
- </tr>
- <tr>
- <td>boost::last_max_element</td>
- <td>23.26M/s</td>
- <td>23.15M/s</td>
- <td>23.15M/s</td>
- <td>22.94M/s</td>
- <td>16.18M/s</td>
- </tr>
- <tr>
- <td>boost::minmax_element</td>
- <td>21.83M/s</td>
- <td>21.83M/s</td>
- <td>21.83M/s</td>
- <td>21.55M/s</td>
- <td>17.79M/s</td>
- </tr>
- <tr>
- <td>boost::first_min_last_max_element</td>
- <td>18.52M/s</td>
- <td>18.38M/s</td>
- <td>18.38M/s</td>
- <td>18.94M/s</td>
- <td>16.29M/s</td>
- </tr>
- <tr>
- <td>boost::last_min_first_max_element</td>
- <td>20.08M/s</td>
- <td>20.83M/s</td>
- <td>20.75M/s</td>
- <td>19.76M/s</td>
- <td>15.87M/s</td>
- </tr>
- <tr>
- <td>boost::last_min_last_max_element</td>
- <td>18.66M/s</td>
- <td>19.69M/s</td>
- <td>19.69M/s</td>
- <td>19.23M/s</td>
- <td>15.77M/s</td>
- </tr>
- <caption ALIGN=BOTTOM>Number of elements per second for standard vector
- container iterators</caption>
- </table></center>
- <center><table BORDER NOSAVE >
- <tr NOSAVE>
- <td NOSAVE><b>list<int>::iterator</b></td>
- <td>Identical</td>
- <td>2-valued</td>
- <td>Increasing</td>
- <td>Decreasing</td>
- <td>Random</td>
- </tr>
- <tr>
- <td>std::min_element</td>
- <td>5.8M/s</td>
- <td>5.8M/s</td>
- <td>5.80M/s</td>
- <td>5.73M/s</td>
- <td>5.73M/s</td>
- </tr>
- <tr>
- <td>std::max_element</td>
- <td>5.81M/s</td>
- <td>5.81M/s</td>
- <td>5.78M/s</td>
- <td>5.73M/s</td>
- <td>5.75M/s</td>
- </tr>
- <tr>
- <td>boost::first_min_element</td>
- <td>5.81M/s</td>
- <td>5.81M/s</td>
- <td>5.79M/s</td>
- <td>5.75M/s</td>
- <td>5.73M/s</td>
- </tr>
- <tr>
- <td>boost::last_min_element</td>
- <td>5.81M/s</td>
- <td>5.80M/s</td>
- <td>5.79M/s</td>
- <td>5.73M/s</td>
- <td>5.03M/s</td>
- </tr>
- <tr>
- <td>boost::first_max_element</td>
- <td>5.81M/s</td>
- <td>5.80M/s</td>
- <td>5.78M/s</td>
- <td>5.74M/s</td>
- <td>5.73M/s</td>
- </tr>
- <tr>
- <td>boost::last_max_element</td>
- <td>5.81M/s</td>
- <td>5.80M/s</td>
- <td>5.79M/s</td>
- <td>5.73M/s</td>
- <td>5.07M/s</td>
- </tr>
- <tr>
- <td>boost::minmax_element</td>
- <td>5.68M/s</td>
- <td>5.80M/s</td>
- <td>5.66M/s</td>
- <td>5.74M/s</td>
- <td>5.30M/s</td>
- </tr>
- <tr>
- <td>boost::first_min_last_max_element</td>
- <td>5.79M/s</td>
- <td>5.81M/s</td>
- <td>5.78M/s</td>
- <td>5.73M/s</td>
- <td>5.04M/s</td>
- </tr>
- <tr>
- <td>boost::last_min_first_max_element</td>
- <td>5.69M/s</td>
- <td>5.79M/s</td>
- <td>5.69M/s</td>
- <td>5.73M/s</td>
- <td>4.84M/s</td>
- </tr>
- <tr>
- <td>boost::last_min_last_max_element</td>
- <td>5.61M/s</td>
- <td>5.79M/s</td>
- <td>5.64M/s</td>
- <td>5.74M/s</td>
- <td>4.75M/s</td>
- </tr>
- <caption ALIGN=BOTTOM>Runtimes for standard list container iterators</caption>
- </table></center>
- <center><table BORDER NOSAVE >
- <tr NOSAVE>
- <td NOSAVE><b>multiset<int>::iterator</b></td>
- <td>Identical</td>
- <td>2-valued</td>
- <td>Increasing</td>
- <td>Decreasing</td>
- <td>Random</td>
- </tr>
- <tr>
- <td>std::min_element</td>
- <td>4.03M/s</td>
- <td>4.04M/s</td>
- <td>4.02M/s</td>
- <td>4.04M/s</td>
- <td>2.97M/s</td>
- </tr>
- <tr>
- <td>std::max_element3.007M</td>
- <td>4.02M/s</td>
- <td>4.02M/s</td>
- <td>4.01M/s</td>
- <td>4.02M/s</td>
- <td>2.96M/s</td>
- </tr>
- <tr>
- <td>boost::first_min_element</td>
- <td>4.01M/s</td>
- <td>4.04M/s</td>
- <td>4.03M/s</td>
- <td>4.04M/s</td>
- <td>3.01M/s</td>
- </tr>
- <tr>
- <td>boost::last_min_element</td>
- <td>4.03M/s</td>
- <td>4.04M/s</td>
- <td>4.04M/s</td>
- <td>4.04M/s</td>
- <td>3.00M/s</td>
- </tr>
- <tr>
- <td>boost::first_max_element</td>
- <td>4.04M/s</td>
- <td>4.04M/s</td>
- <td>4.04M/s</td>
- <td>4.06M/s</td>
- <td>3.01M/s</td>
- </tr>
- <tr>
- <td>boost::last_max_element</td>
- <td>4.04M/s</td>
- <td>4.04M/s</td>
- <td>4.03M/s</td>
- <td>4.04M/s</td>
- <td>3.00M/s</td>
- </tr>
- <tr>
- <td>boost::minmax_element</td>
- <td>3.98M/s</td>
- <td>3.99M/s</td>
- <td>3.98M/s</td>
- <td>3.99M/s</td>
- <td>3.00M/s</td>
- </tr>
- <tr>
- <td>boost::first_min_last_max_element</td>
- <td>3.99M/s</td>
- <td>3.98M/s</td>
- <td>3.97M/s</td>
- <td>3.99M/s</td>
- <td>2.99M/s</td>
- </tr>
- <tr>
- <td>boost::last_min_first_max_element</td>
- <td>3.97M/s</td>
- <td>3.98M/s</td>
- <td>3.96M/s</td>
- <td>3.98M/s</td>
- <td>3.00M/s</td>
- </tr>
- <tr>
- <td>boost::last_min_last_max_element</td>
- <td>4.00M/s</td>
- <td>4.00M/s</td>
- <td>4.00M/s</td>
- <td>4.02M/s</td>
- <td>2.97M/s</td>
- </tr>
- <caption ALIGN=BOTTOM>Runtimes for standard set/multiset container iterators</caption>
- </table></center>
- <hr SIZE="6">
- <br>Last modified 2004-06-28
- <p><font face="Arial,Helvetica"><font size=-1>© Copyright Hervé
- Brönnimann, Polytechnic University, 2002--2004.
- Use, modification, and distribution is subject to the Boost Software
- License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at
- <a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)
- </font></font>
- </body>
- </html>
|