Timing A Function in C++

March 31, 2020 - John Law - 4 mins read

Recently, I encountered the following question:

Write a function that returns true if it has been called 3 times in 3 seconds.

I have used a traditional C-style approach (in C++) without using a queue:

#include<iostream>
#include<ctime>
#include<unistd.h>

using namespace std;

time_t start;
int count;

bool being_called(time_t call_time){
	count++;
	if(call_time - 3 <= start){
		return !(count < 3);
	}else{
		start = call_time;
		count = 1;
		return false;
	}
}

int main(){
	start = time(NULL);
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << "=====" << endl;
	sleep(4);
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << boolalpha << being_called(time(NULL)) << endl;
	return 0;
}

This works perfectly well and it actually solves the problem. However, there are other alternatives.

Precision

time_t time (time_t* timer) returns a Unix time, which is simply a integer value. Since it is an integer, $t=1.0001$ would be recorded in the same way as $t=1.9888$ . This is not very good as if we call the function at $t_1=0.011, t_2=3.511, t_3=3.611,$ then the function returns true and the flaw is obvious. This is verified in the last section.

This can be solved with a int gettimeofday(struct timeval *tv, struct timezone *tz) in sys/time.h. The struct timeval *tv contains seconds and microseconds of the current time. The precision is slightly improved, despite the fact that there will be still some errors when dealing with doubles.

A Better Approach

To solve this, we can use a queue for this problem by checking the size of the queue and poping an element if the time created is more than 3 seconds ago. While this may be solved without a queue, this data structure is the right choice here. I could have used chrono and a queue<high_resolution_clock::time_point>. chrono has an extremely rich functionality comparing to ctime.

#include<iostream>
#include<chrono>
#include<thread>
#include<queue>

using namespace std;
using namespace std::chrono;

queue<high_resolution_clock::time_point> call_queue;

bool being_called(high_resolution_clock::time_point call_time){
	call_queue.push(call_time);
	while(duration_cast<seconds>(call_time - call_queue.front()).count() > 3){
		call_queue.pop();
	}
	if(call_queue.size() >= 3){
		return true;
	}
	return false;
}

int main(){
	using namespace literals::chrono_literals;
	high_resolution_clock c;
	cout << boolalpha << being_called(c.now()) << endl;
	cout << boolalpha << being_called(c.now()) << endl;
	cout << "=====" << endl;
	this_thread::sleep_for(4s);
	cout << boolalpha << being_called(c.now()) << endl;
	cout << boolalpha << being_called(c.now()) << endl;
	cout << boolalpha << being_called(c.now()) << endl;
	cout << boolalpha << being_called(c.now()) << endl;
	return 0;
}

One should notice that C++14 is required to access std::literals::chrono_literals. There is a difference between a duration cast and plain duration. duration<double, milli>, for example, requires a milli ratio type to process the time. On the other hand, duration cast is useful for getting the whole integral number of seconds of time, like the above case. For a better precision, we can do the following.

bool being_called(high_resolution_clock::time_point call_time){
	call_queue.push(call_time);
	while(duration<double, milli>(call_time - call_queue.front()).count() > 3000.0){
		call_queue.pop();
	}
	if(call_queue.size() >= 3){
		return true;
	}
	return false;
}

Verifying the Guess

Previously, we made the following guess:

This is not very good as if we call the function at $t_1=0.011, t_2=3.511, t_3=3.611,$ then the function returns true and the flaw is obvious.

#include<iostream>
#include<chrono>
#include<thread>
#include<queue>

using namespace std;
using namespace std::chrono;

queue<high_resolution_clock::time_point> call_queue;

bool being_called(high_resolution_clock::time_point call_time){
	call_queue.push(call_time);
	while(duration<double, milli>(call_time - call_queue.front()).count() > 3000.0){
		call_queue.pop();
	}
	if(call_queue.size() >= 3){
		return true;
	}
	return false;
}

int main(){
	using namespace literals::chrono_literals;
	high_resolution_clock c;
	cout << "=====" << endl;
	this_thread::sleep_for(11ms);
	high_resolution_clock::time_point t = c.now();
	cout << boolalpha << being_called(c.now()) << endl;
	cout << "=====" << endl;
	this_thread::sleep_for(3500ms);
	cout << boolalpha << being_called(c.now()) << endl;
	cout << "=====" << endl;
	this_thread::sleep_for(100ms);
	cout << boolalpha << being_called(c.now()) << endl;
	cout << "=====" << endl;
	cout << "Time elapsed: " << 
		duration<double, milli>(c.now() - t).count() << "ms" << endl;
	return 0;
}

=====
false
=====
false
=====
false
=====
Time elapsed: 3624.28ms

This is John Law, signing off. You read 301 words.