townforge/algorithm
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
cc
algorithm/minmax/doc/minmax_benchs.html
Douglas Gregor d9ebe5da13 Merged from Version_1_33_1 
[SVN r31949]
2005-12-08 03:23:02 +00:00

525 lines
7.2 KiB
HTML
Raw Permalink Blame History

<!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&lt;>::iterator</tt> or
<tt>map&lt;>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&lt;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&lt;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&lt;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>&copy; Copyright Herv&eacute;
Br&ouml;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>
Reference in New Issue View Git Blame Copy Permalink