Minmax_element Performance

About performance

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, boost::minmax_element is only a tad slower than std::min_element, and is even faster than boost::first_min_last_max_element! This is even more true for slower iterators (list<>::iterator or map<>iterator 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: Identical means that all the elements are identical, 2-valued means that we replace the second half of the identical elements by a distinct element, increasing means that all the elements are distinct and in increasing order, decreasing is the reverse, and random is produced by random_shuffle.
The program that created these tables is included in the distribution, under minmax_timer.cpp

Number of elements per second for standard vector container iterators
vector<int>::iterator	Identical	2-valued	Increasing	Decreasing	Random
std::min_element	23.26M/s	23.26M/s	23.15M/s	22.94M/s	22.94M/s
std::max_element	23.26M/s	23.26M/s	23.15M/s	22.94M/s	22.62M/s
boost::first_min_element	23.15M/s	23.04M/s	23.04M/s	22.94M/s	22.83M/s
boost::last_min_element	23.26M/s	23.26M/s	23.26M/s	22.83M/s	16.23M/s
boost::first_max_element	23.15M/s	23.26M/s	23.15M/s	23.04M/s	22.93M/s
boost::last_max_element	23.26M/s	23.15M/s	23.15M/s	22.94M/s	16.18M/s
boost::minmax_element	21.83M/s	21.83M/s	21.83M/s	21.55M/s	17.79M/s
boost::first_min_last_max_element	18.52M/s	18.38M/s	18.38M/s	18.94M/s	16.29M/s
boost::last_min_first_max_element	20.08M/s	20.83M/s	20.75M/s	19.76M/s	15.87M/s
boost::last_min_last_max_element	18.66M/s	19.69M/s	19.69M/s	19.23M/s	15.77M/s

Runtimes for standard list container iterators
list<int>::iterator	Identical	2-valued	Increasing	Decreasing	Random
std::min_element	5.8M/s	5.8M/s	5.80M/s	5.73M/s	5.73M/s
std::max_element	5.81M/s	5.81M/s	5.78M/s	5.73M/s	5.75M/s
boost::first_min_element	5.81M/s	5.81M/s	5.79M/s	5.75M/s	5.73M/s
boost::last_min_element	5.81M/s	5.80M/s	5.79M/s	5.73M/s	5.03M/s
boost::first_max_element	5.81M/s	5.80M/s	5.78M/s	5.74M/s	5.73M/s
boost::last_max_element	5.81M/s	5.80M/s	5.79M/s	5.73M/s	5.07M/s
boost::minmax_element	5.68M/s	5.80M/s	5.66M/s	5.74M/s	5.30M/s
boost::first_min_last_max_element	5.79M/s	5.81M/s	5.78M/s	5.73M/s	5.04M/s
boost::last_min_first_max_element	5.69M/s	5.79M/s	5.69M/s	5.73M/s	4.84M/s
boost::last_min_last_max_element	5.61M/s	5.79M/s	5.64M/s	5.74M/s	4.75M/s

Runtimes for standard set/multiset container iterators
multiset<int>::iterator	Identical	2-valued	Increasing	Decreasing	Random
std::min_element	4.03M/s	4.04M/s	4.02M/s	4.04M/s	2.97M/s
std::max_element3.007M	4.02M/s	4.02M/s	4.01M/s	4.02M/s	2.96M/s
boost::first_min_element	4.01M/s	4.04M/s	4.03M/s	4.04M/s	3.01M/s
boost::last_min_element	4.03M/s	4.04M/s	4.04M/s	4.04M/s	3.00M/s
boost::first_max_element	4.04M/s	4.04M/s	4.04M/s	4.06M/s	3.01M/s
boost::last_max_element	4.04M/s	4.04M/s	4.03M/s	4.04M/s	3.00M/s
boost::minmax_element	3.98M/s	3.99M/s	3.98M/s	3.99M/s	3.00M/s
boost::first_min_last_max_element	3.99M/s	3.98M/s	3.97M/s	3.99M/s	2.99M/s
boost::last_min_first_max_element	3.97M/s	3.98M/s	3.96M/s	3.98M/s	3.00M/s
boost::last_min_last_max_element	4.00M/s	4.00M/s	4.00M/s	4.02M/s	2.97M/s

Last modified 2004-06-28

© 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 License_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)