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
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
Number of elements per second for standard vector 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 list 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
Runtimes for standard set/multiset container iterators


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)