Timing A Function in C++

March 31, 2020 - John Law - 4 mins read

Recently, I encountered the following interview question:

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

To solve this, I have used a traditional C-style approach (in C++):

#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 << being_called(time(NULL)) << endl;
	cout << being_called(time(NULL)) << endl;
	cout << "=====" << endl;
	sleep(4);
	cout << being_called(time(NULL)) << endl;
	cout << being_called(time(NULL)) << endl;
	cout << being_called(time(NULL)) << endl;
	cout << being_called(time(NULL)) << endl;
	return 0;
}

This works perfectly well and it actually solves the problem. However, there might be 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.0001t=1.0001 would be recorded the same as t=1.9888t=1.9888. This is not very good as if we call the function at t1=0.011,t2=3.511,t3=3.611,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 "C++" Approach

Although the previous ways work in C++, they are not 100% C++-ish. I could have used chrono. It has an extremely rich functionality comparing to ctime.

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

using namespace std;
using namespace std::chrono;

int count;
high_resolution_clock::time_point start;

bool being_called(high_resolution_clock::time_point call_time){
	count++;
	if(duration_cast<seconds>(call_time - start).count() <= 3){
		return !(count < 3);
	}else{
		start = call_time;
		count = 1;
		return false;
	}
}

int main(){
	using namespace literals::chrono_literals;
	high_resolution_clock c;
	start = c.now();
	cout << being_called(c.now()) << endl;
	cout << being_called(c.now()) << endl;
	cout << "=====" << endl;
	this_thread::sleep_for(4s);
	cout << being_called(c.now()) << endl;
	cout << being_called(c.now()) << endl;
	cout << being_called(c.now()) << endl;
	cout << 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){
	count++;
	if(duration<double, milli>(call_time - start).count() <= 3000.0){
		return !(count < 3);
	}else{
		start = call_time;
		count = 1;
		return false;
	}
}

Verifying the Guess

Previously, we made the following guess:

This is not very good as if we call the function at t1=0.011,t2=3.511,t3=3.611,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>

using namespace std;
using namespace std::chrono;

int count;
high_resolution_clock::time_point start;

bool being_called(high_resolution_clock::time_point call_time){
	count++;
	if(duration_cast<seconds>(call_time - start).count() <= 3){
		return !(count < 3);
	}else{
		start = call_time;
		count = 1;
		return false;
	}
}

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

This can be extremely sophisticated if we expand our solution, but it looks good to me for now!

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

Copyright © 2020 John Law