# Measure execution time of sorting algorithms

I have to measure execution time of certain sorting algorithms being passed as functions in following program. I also do not have to measure it on random container but also on ascending as well as descending sorted containers.

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <tuple>
#include <iomanip>

class sortT {
private:
std::vector<std::vector<long long>> asc;
std::vector<std::vector<long long>> desc;
std::vector<std::vector<long long>> random;
unsigned int upLim; // Upperlimit 1=10, 2=100...
void seed();
unsigned int findSentinel(); // returns largest upperlimit possible

public:
// default + param constructor -> calls seed()
sortT(unsigned int lim = 3) : upLim(lim) {
if (upLim < 1)
upLim = 3;
else {
unsigned int s = findSentinel();
if (upLim > s) { upLim = 3; }
}
seed();
};

// exposing list in public
std::vector<std::tuple<std::chrono::microseconds, std::chrono::microseconds,
std::chrono::microseconds>> list;

void testWith(void sortF(std::vector<long long>::iterator,
std::vector<long long>::iterator));
void printList();
unsigned int getUpLim() { return upLim; }
};


.cpp file:

#include "cs-iv-algorithm.h"

unsigned int sortT::findSentinel() {

/*
* Get numeric limit of long long
* normalize it by subtracting remainder
* find out max upperlimit by clean divide of 10
*/

long long sentinel = std::numeric_limits<long long>::max();
sentinel = sentinel - (sentinel % 10);
unsigned int k = 0;
while (sentinel != 0) {
sentinel /= 10;
++k;
}
return k;
}

void sortT::seed() {
// reserve upLim amount of sub-vectors
random.reserve(upLim);
asc.reserve(upLim);
desc.reserve(upLim);

for (unsigned int i = 1; i <= upLim; ++i) {
unsigned int j = i;
long long limit = 1;
while (j != 0) {
limit *= 10;
--j;
}

// r,a,d represent sub-vectors for random,...
std::vector<long long> r, a, d;
r.reserve(limit);
a.reserve(limit);
d.reserve(limit);

// random number generation
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<> distr(1, 10000);

for (long long k = 1; k <= limit; ++k) {
r.push_back(distr(eng));
a.push_back(k);
d.push_back(limit - k);
}

random.push_back(r);
asc.push_back(a);
desc.push_back(d);
}
}

void sortT::testWith(void sortF(std::vector<long long>::iterator,
std::vector<long long>::iterator)) {
unsigned int i = 0;

while (i < upLim) {
auto tp1 = std::chrono::high_resolution_clock::now();
sortF(random[i].begin(), random[i].end());
auto tp2 = std::chrono::high_resolution_clock::now();
auto duration1 =
std::chrono::duration_cast<std::chrono::microseconds>(tp2 - tp1);

tp1 = std::chrono::high_resolution_clock::now();
sortF(asc[i].begin(), asc[i].end());
tp2 = std::chrono::high_resolution_clock::now();
auto duration2 =
std::chrono::duration_cast<std::chrono::microseconds>(tp2 - tp1);

tp1 = std::chrono::high_resolution_clock::now();
sortF(desc[i].begin(), desc[i].end());
tp2 = std::chrono::high_resolution_clock::now();
auto duration3 =
std::chrono::duration_cast<std::chrono::microseconds>(tp2 - tp1);

list.push_back(std::make_tuple(duration1, duration2, duration3));
++i;
}
}

void sortT::printList() {
unsigned int i = 1;

std::cout << std::left;
std::cout << std::setw(10) << "Iteration" << std::setw(0) << "|\t";
std::cout << std::setw(10) << "limit" << std::setw(0) << "|\t";
std::cout << std::setw(10) << "RandomBox" << std::setw(0) << "|\t";
std::cout << std::setw(10) << "AscBox" << std::setw(0) << "|\t";
std::cout << std::setw(10) << "DescBox" << std::setw(0) << "|\t";

for (auto &listTuple : list) {

unsigned int j = i;
long long limit = 1;
while (j > 0) {
limit *= 10;
--j;
}

std::cout << "\n";
std::cout << std::setw(10) << i << std::setw(0) << "|\t";
std::cout << std::setw(10) << limit << std::setw(0) << "|\t";
std::cout << std::setw(10) << std::get<0>(listTuple).count()
<< std::setw(0) << "|\t";
std::cout << std::setw(10) << std::get<1>(listTuple).count()
<< std::setw(0) << "|\t";
std::cout << std::setw(10) << std::get<2>(listTuple).count()
<< std::setw(0) << "|\t";

++i;
}
std::cout << std::endl;
}


For now I've implemented it only for integers and I'm looking forward to implement it for floating point type too. Under current implementation, I'm exposing the list vector so that a dev can view and clear according to his/her needs. I've also included a temporarily print function to show the results. I would like to know what design improvements can be made on following code or any other suggestion you might like to give.

Here is an alternative repo that contains test file too.

Generally speaking, there isn't much to say and I can't find any obvious flow at first sight. I'll have to comment on small things instead:

• This signature struck me as begin rather restrictive:

void testWith(void sortF(std::vector<long long>::iterator,
std::vector<long long>::iterator));


I understand that you only test vector sorting algorithms, but you could have the function type as a template parameter instead:

template<typename BinaryFunction>
void testWith(BinaryFunction sortF);


And still call it like that:

sortF(random[i].begin(), random[i].end());


This would allow you to use function objects too and to use generic functions not especially designed to sort vectors, but that can still sort a vector.

• You could avoid duplication with a dedicated function to time one function at a time:

template<typename Function>
auto timeIt(Function function)
-> std::chrono::microseconds
{
auto tp1 = std::chrono::high_resolution_clock::now();
function();
auto tp2 = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::microseconds>(tp2 - tp1);
}


Then you could reimplement testWith with a few lambdas to simplify things:

template<typename BinaryFunction>
void sortT::testWith(BinaryFunction sortF) {
for (unsigned int i = 0 ; i < upLim ; ++i) {
auto duration1 = timeIt([]{
sortF(random[i].begin(), random[i].end());
});

auto duration2 = timeIt([]{
sortF(asc[i].begin(), asc[i].end());
});

auto duration3 = timeIt([]{
sortF(desc[i].begin(), desc[i].end());
});

list.push_back(std::make_tuple(duration1, duration2, duration3));
}
}


Note that I also rewrote your algorithm with a for loop instead of a while loop. When you have severa tools at hand, try to pick the most suitable one for the job. Actually, it would make sense for most of your while loops to be replaced by for loops.

• By the way, instead of constructing an std::tuple and pushing it into list, you could directly create it into list with emplace_back:

list.emplace_back(duration1, duration2, duration3);

• Also, since you know that your list will only ever contain instances of std::chrono::microseconds, you might want to use an std::array<std::chrono::microseconds, 3u> instead of the more verbose std::tuple<std::chrono::microseconds, std::chrono::microseconds, std::chrono::microseconds>. It will make your code easier to expand and to read.

• I speak of expanding the code since you probably want to add a pipe organ test case to your tests since some sorting algorithms are known to perform poorly with pipe organ patterns.

• const-correctness is important in C++ semantics. If one of your functions does not alter the class members, then mark it const:

unsigned int getUpLim() const { return upLim; }

• Instead of having a printList method, it would be more idiomatic to overload operator<< between std::ostream& and sortT so that you can print your list to any output stream instead of simply std::cout.

• When possible, try to use compound assignment operators to make your code shorter and hypothetically more performant. For example, turn this line:

sentinel = sentinel - (sentinel % 10);


into this one:

sentinel -= sentinel % 10;

• Instead of reinitializing your random number engine everytime you call seed, you could let it live its life once initialized since it should still produce different results everytime seed is invoked:

// random number generation


Making the instances thread_local make sure there is one instance per thread. It makes generating random numbers inherently thread-safe while not having to initialize the engine again everytime you call seed.

• Can't be bothered to write an answer so I'll just append to Morvenn's. :) You should discard the first run of the benchmark to remove any effects of cache warmup. – Emily L. Jul 27 '15 at 8:31

I'm going to try not to duplicate anything from Morwenn's answer in mine.

Your function sortT::findSentinel takes 16 lines to implement the equivalent of

int sortT::findSentinel() {
return 1 + std::numeric_limits<long long>::digits10;
}


Once we write it in the shorter way, it's easy to see that your version has a bug: when upLim == findSentinel(), you try to compute 1019 as a long long, which invokes undefined behavior. To fix the bug, we need to remove the 1 + from the code above.

But of course even before that, it probably fails the preceding iteration's attempt to allocate 1018 bytes of memory, so you'll never see the undefined behavior in practice.

Solution: Replace findSentinel with a reasonable constant such as 8, and constant-propagate it into the sortT constructor.

sortT(int lim = 3) :
upLim(std::min(std::max(1, lim), 8))  // 10^8 should be enough for anybody
{
seed();
}


This:

    random.push_back(r);
asc.push_back(a);
desc.push_back(d);


makes copies of the large vectors r, a, and d. Prefer to move them into place:

    random.emplace_back(std::move(r));
asc.emplace_back(std::move(a));
desc.emplace_back(std::move(d));


Or of course you could just make r a reference to the appropriate member of random from the beginning:

void sortT::seed() {
random.resize(upLim);
asc.resize(upLim);
desc.resize(upLim);

std::mt19937 eng(std::random_device()());

long long limit = 1;
for (int i = 0; i < upLim; ++i) {
limit *= 10;

auto& r = random[i];
auto& a = asc[i];
auto& d = desc[i];

a.resize(limit);
std::iota(a.begin(), a.end(), 1);

d.resize(limit);
std::generate(d.begin(), d.end(), [k=limit]() mutable { return k--; });

r.resize(limit);
std::generate(r.begin(), r.end(),
[&]() {
return std::uniform_int_distribution<>(1,1000)(eng);
}
);
}
}


The above code is too clever for its own good, so let's refactor one more time:

        a.resize(limit);
for (int j=0; j < limit; ++j) a[j] = j + 1;

d.resize(limit);
for (int j=0; j < limit; ++j) d[j] = limit - j;

r.resize(limit);
for (int j=0; j < limit; ++j) r[j] = std::uniform_int_distribution<>(1, 1000)(eng);


Yeah, that's nicer.

One more important point about code organization: Your .h file starts off with the lines

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <tuple>
#include <iomanip>


This is terrible! You're making every user of your .h file import all those headers, even though they probably won't be used. You should #include only the small set of headers that your own code actually requires.

Then, in your .cpp file, you should #include whatever headers that code requires. For example, since your .cpp file uses std::random_device, you should #include <random> in your .cpp file — and since your .h file does not use anything from <random>, your .h file should not #include <random>. Makes sense, right?

• Is there any advantage in this case to change push_back into emplace_back? Since push_back already has an rvalue-reference constructor, I fail to see what emplace_back adds here. – Morwenn Jul 27 '15 at 9:59
• I didn't make a conscious choice; after thinking about it, I think you're right that push_back would be equivalent in this case. In general I prefer to use the emplace spellings whenever possible, just for consistency's sake. (I also prefer ++i over i++ whenever possible, just for consistency's sake, because it's more efficient on some types, and I don't want to be bothered thinking about which case I'm currently in.) – Quuxplusone Jul 27 '15 at 20:05
• I want to award bounty on both answers but I'm not able to do so. This answer is written very well and thankyou for that :) – Abhinav Gauniyal Jul 28 '15 at 8:08