C++17: Benchmark of Singular Min/Max and Iterator Versions

• Download source - 6.3 KB
• Benchmark code hosted at GitHub

Introduction

In this tip, we'll benchmark native </> operator with singular min()/max() and iterator versions like min_element()/max_element(). Lastly, we benchmark the combined operations with minmax_element().

This is the benchmark code:

const size_t MAX_LOOP = (argc == 2) ? atoi(argv[1]) : 1000;

using int_type = uint64_t;
std::vector<int_type> vec(1000000);
std::iota(vec.begin(), vec.end(), 1);
std::random_device rd;
std::mt19937 g(rd());

std::shuffle(vec.begin(), vec.end(), g);
timer stopwatch;

stopwatch.start("manual min");
int_type min = vec[0];
for (size_t k = 0; k < MAX_LOOP; ++k)
{
    min = vec[0];
    for (auto n : vec)
    {
        if (n < min)
            min = n;
    }
}
stopwatch.stop(min);

stopwatch.start("std min");
min = vec[0];
for (size_t k = 0; k < MAX_LOOP; ++k)
{
    min = vec[0];
    for (auto n : vec)
        min = std::min(n, min);
}
stopwatch.stop(min);

stopwatch.start("std min_element");
min = vec[0];
for (size_t k = 0; k < MAX_LOOP; ++k)
{
    min = vec[0];
    min = * std::min_element(vec.cbegin(), vec.cend());
}
stopwatch.stop(min);

std::cout << std::endl;

stopwatch.start("manual max");
int_type max = vec[0];
for (size_t k = 0; k < MAX_LOOP; ++k)
{
    max = vec[0];
    for (auto n : vec)
    {
        if (n > max)
            max = n;
    }
}
stopwatch.stop(max);

stopwatch.start("std max");
max = vec[0];
for (size_t k = 0; k < MAX_LOOP; ++k)
{
    max = vec[0];
    for (auto n : vec)
        max = std::max(n, max);
}
stopwatch.stop(max);

stopwatch.start("std max_element");
max = vec[0];
for (size_t k = 0; k < MAX_LOOP; ++k)
{
    max = vec[0];
    max = *std::max_element(vec.cbegin(), vec.cend());
}
stopwatch.stop(max);

std::cout << std::endl;

stopwatch.start("manual min max");
for (size_t k = 0; k < MAX_LOOP; ++k)
{
    min = vec[0];
    max = vec[0];
    for (auto n : vec)
    {
        if (n < min)
            min = n;
        if (n > max)
            max = n;
    }
}
stopwatch.stop(min, max);

stopwatch.start("std min & max");
for (size_t k = 0; k < MAX_LOOP; ++k)
{
    min = vec[0];
    max = vec[0];
    for (auto n : vec)
    {
        min = std::min(n, min);
        max = std::max(n, max);
    }
}
stopwatch.stop(min, max);

stopwatch.start("std minmax_element");
std::pair<std::vector<int_type>::const_iterator, std::vector<int_type>::const_iterator> minmax;
for (size_t k = 0; k < MAX_LOOP; ++k)
{
    minmax = std::minmax_element(vec.cbegin(), vec.cend());
}
stopwatch.stop(*minmax.first, *minmax.second);

The benchmark is done on Intel i7-8700 CPU at 3.2GHz. Clang++ and G++ benchmark is built and run on Windows Subsystem for Linux(WSL)(Ubuntu 18.04 version) on Windows 10 update 19.10. The timing is based on 1 billion iterations.

VC++ update 16.4, /Ox

From the Visual C++ results, we can see the iterator versions are consistently slower than the native </> operators and min()/max(). In other words, iterator versions are not worth the trouble to use them.

        manual min:  592ms, result:1
           std min:  630ms, result:1
   std min_element: 1889ms, result:1

        manual max:  832ms, result:1000000
           std max:  585ms, result:1000000
   std max_element: 1891ms, result:1000000

    manual min max:  816ms, result:1,1000000
     std min & max:  762ms, result:1,1000000
std minmax_element: 2143ms, result:1,1000000

Clang++ 6.0.0, -O3

From the Clang++ results, the iterator version of min_element() and minmax_element() performs better than singular version.

        manual min:  521ms, result:1
           std min:  419ms, result:1
   std min_element:  386ms, result:1

        manual max:  416ms, result:1000000
           std max:  445ms, result:1000000
   std max_element:  428ms, result:1000000

    manual min max:  701ms, result:1,1000000
     std min & max:  969ms, result:1,1000000
std minmax_element:  514ms, result:1,1000000

G++ 7.4.0, -O3

For G++, we can just stick to </> operators for min/max since their results comes neck to neck. From the results, minmax_element() is to be avoided since it performs worse than the combined </> and min()/max().

        manual min:  801ms, result:1
           std min:  810ms, result:1
   std min_element:  808ms, result:1

        manual max:  566ms, result:1000000
           std max:  552ms, result:1000000
   std max_element:  555ms, result:1000000

    manual min max:  799ms, result:1,1000000
     std min & max:  796ms, result:1,1000000
std minmax_element: 2052ms, result:1,1000000

History

• 16^th January, 2020: Initial version