| <!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> |