1 files changed, 524 insertions, 0 deletions
diff --git a/libs/algorithm/minmax/doc/minmax_benchs.html b/libs/algorithm/minmax/doc/minmax_benchs.html
new file mode 100644
index 000000000..1db516d7d
--- /dev/null
+++ b/libs/algorithm/minmax/doc/minmax_benchs.html
@@ -0,0 +1,524 @@
+<!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>