Skip to main content

Benchmarking

Description

Benchmarking is a process of measuring the performance of any algorithm. In this article, we will see how to benchmark the performance of any algorithm. The basic idea behind this is to start a timer when the algorithm starts executing and stop the timer when the algorithm ends. We should repeat this many times and take the average. The more we repeat, the more accurate will be the time measured.

Basic Algorithm :

   Repeat n time
   {
        Note the start time  Si

        Run the Algorithm whose performance is to be measured.
             
        Note the finish time   Fi

     Time taken Ti = Fi - Si
}
Tavg  = ( T1 + T2 + T3 + T4 ... Tn ) / n
    Output the average time Tavg

In C++, Chrono library is used to deal with dates and times.

Clock :
A clock consists of a starting point also called epoch and a tick rate. There are 3 types of clock in C++ :
  1. system_clock-It is the current time according to the system. Syntax-std::chrono::system_clock
  2. steady_clock-It is a monotonic clock that will never be adjusted. It goes at a uniform rate. Syntax- std::chrono::steady_clock
  3. high_resolution_clock - It gives the smallest possible tick period. Syntax-std::chrono::high_resolution_clock
Timepoint :
A time_point object expresses a point in time relative to a clock's epoch.
Syntax -  std::chrono::time_point<std::chrono::clock type> s ;
Here clock type can be system_clock, steady_clock and high_resolution_clock.
now() function is used to get the current time relative to cloak epoch .                                  
Syntax - std::chrono::clock type::now();

A simple program to measure the time of execution of a simple function 
#include<iostream>
#include<chrono>
using namespace std;

void function(int n) //function whose execution time is to be measured
{
 long long sum=0;
 for(int i=1;i<=n;i++)
  sum+=i;
 cout<<sum<<endl;
}
int main(void)
{
 using namespace std::chrono;  
 
 time_point<high_resolution_clock> start_point, end_point; // creating time points
 
 start_point = high_resolution_clock::now(); // storing the starting time point in start 
 
 function(100000); // function whose performance is to me measured.
  
 end_point = high_resolution_clock::now(); //storing the ending time in end 
 
 auto start = time_point_cast<microseconds>(start_point).time_since_epoch().count(); 
 // casting the time point to microseconds and measuring the time since time epoch
 
 auto end = time_point_cast<microseconds>(end_point).time_since_epoch().count();
 
 cout<<"Time taken = "<<(end-start)<<" microseconds"<<endl;
 
 return 0; 
}

Output :
5000050000
Time taken = 1962 microseconds 

NOTE: The output is machine-dependent.

So, by the above idea, we can measure the performance of various sorting algorithms. For example, lets measure the performance of std::sort over 1000000 random integers.

Benchmarking Code

#include <iostream>
#include <sstream>
#include <chrono>
#include <numeric>
#include <array>
#include <algorithm>
#include <ctime>
#include <cstdlib>
namespace cpp_secrets{
///Runnable: A class which has a valid and public default ctor and a "run()" function.
///BenchmarkingTimer tests the "run()" function of Runnable
///num_run_cycles: It is the number of times run() needs to be run for a single test. 
///One Runnable object is used for a single test.
///Note: if the run() function is statefull then it can only be run once for an object in order 
///to get meaningful results.
///num_tests: It is the number of tests that need to be run.
 template <typename Runnable, int num_run_cycles = 1000000, int num_tests = 10>
  struct BenchmarkingTimer{
   /// runs the run() function of the Runnable object and captures timestamps around each test
   void run(){
    for(int i = 0; i < num_tests; i++){
     Runnable runnable_object_{};
     Timer t{intervals_[i].first, intervals_[i].second};
     for(int i = 0; i < num_run_cycles; i++){
      runnable_object_.run();
     }
    }
   }

   ///utility function to print durations of all tests
   std::string durations() const{
    std::stringstream ss;
    int i{1};
    for(const auto& interval: intervals_){
     ss << "Test-" << i++  << " duration = " << (interval.second - interval.first) * 0.001 << " ms" << std::endl;
    }
    return ss.str();
   }

   ///utility function to print average duration of all tests
   double average_duration(){
    auto duration_sum{0.0};
    for(const auto& interval: intervals_){
     duration_sum += (interval.second - interval.first) * 0.001;
    }
    if (num_tests) return (duration_sum/num_tests);
    return 0;
   }

   private:
   std::array<std::pair<double, double>, num_tests> intervals_{};

   struct Timer{
    Timer(double& start, double& finish):finish_(finish) { start = now(); }
    ~Timer() { finish_ = now(); }

    private:
    double& finish_;
    double now(){ 
                         ///utility function to return current time in microseconds since epoch
     return std::chrono::time_point_cast<std::chrono::microseconds>(std::chrono::high_resolution_clock::now()).time_since_epoch().count();
    }
   };

  };
}

///sample class which has a statefull run(). 
//run() function is stateful because it is not meaningful to sort a sorted array. 
//that's why num_run_cycles = 1 in this case.
struct randomly_sorted{
 randomly_sorted(){
  srand(time(0));
  for(int i=0;i<1000000;i++){
   arr_.emplace_back(rand());     
                  // making a vector filled with random elements
  }
 }

 void run(){
  sort(arr_.begin(), arr_.end(), std::less<int>());
 }
 private:
 std::vector<int>arr_;
};
int main(){
 cpp_secrets::BenchmarkingTimer<randomly_sorted, 1, 10> test; // randomly_sorted structure run function is run 10 time and average output is given.
 test.run();
 std::cout << test.durations() << std::endl; // outputs the duration of every test.
 std::cout << "average duration = " << test.average_duration() << " ms" << std::endl;
 return 0;
}

/*
Quick Explanation :
   In the above code the code block coloured in red denotes the algorithm whose performance is to be
   measured.The run() funtion in the structure randomly sorted is run 10 time and the average time is taken.
   So, this code gives the average time required to measure the time taken to sort random integers 
   by the std::sort.
   NOTE : The constructor of the the structure randomly_sorted is used to create a vector
          filled with integers which is to be sorted by sort() in the run() function. 
*/

Output :
Test-1 duration = 698.709 ms
Test-2 duration = 699.72 ms
Test-3 duration = 718.309 ms
Test-4 duration = 878.291 ms
Test-5 duration = 875.379 ms
Test-6 duration = 808.616 ms
Test-7 duration = 838.029 ms
Test-8 duration = 844.929 ms
Test-9 duration = 796.873 ms
Test-10 duration = 783.102 ms

average duration = 794.196 ms
NOTE: The output is machine-dependent.

Popular posts from this blog

Introduction to Java Security

Introduction to Java Security The Java security architecture includes a large set of application programming interfaces (APIs), tools, and implementations of commonly-used security algorithms, mechanisms, and protocols. The Java security APIs span a wide range of areas. Cryptographic and public key infrastructure (PKI) interfaces provide the underlying basis for developing secure applications. Interfaces for performing authentication and access control enable applications to guard against unauthorized access to protected resources. The JDK includes a number of providers that implement a core set of security services. It also allows for additional custom providers to be installed. This enables developers to extend the platform with new security mechanisms. The JDK is divided into modules. Modules that contain security APIs include the following:

Module Description java.base Defines the foundational APIs of Java SE;  contained packages include java.securityjavax.cryptojavax.net.ssl,  and…

SQL Injection

Overview A SQL injection attack consists of insertion or "injection" of a SQL query via the input data from the client to the application. A successful SQL injection exploit can read sensitive data from the database, modify database data (Insert/Update/Delete), execute administration operations on the database (such as shutdown the DBMS), recover the content of a given file present on the DBMS file system and in some cases issue commands to the operating system. SQL injection attacks are a type of injection attack, in which SQL commands are injected into data-plane input in order to effect the execution of predefined SQL commands. Threat ModelingSQL injection attacks allow attackers to spoof identity, tamper with existing data, cause repudiation issues such as voiding transactions or changing balances, allow the complete disclosure of all data on the system, destroy the data or make it otherwise unavailable, and become administrators of the database server.SQL Injection is ve…

Insertion Node in the Linkelist.

In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list
public class Linkedlist { Node head; class Node{ int data; Node next; Node(int d){ data =d; next=null; } } // INSERT THE NODE AT THE BEGIN OF LINKEDLIST. public void insertAtfront(int new_data){ // Node temp = head; Node new_node = new Node(new_data); new_node.next = head; head = new_node; }  // INSERT THE NODE AT THE GIVEN POSITION IN LINKEDLIST.
public void insertAtGiven(Node prev_node,int new_data) { if(prev_node == null){ System.out.print("previous node can't be null"); return; } Node new_node = new Node(new_data); new_node.next = prev_node.next; prev_node.next = new_node; } // INSERT THE NODE  AT THE END OF THE LINKEDLIST.   public void insertAtEnd(int new_data){ Node new_node = new Node(new_data); new_node.nex…