Using Timing of Algorithms With The C++ Programming Language

When it came out in 1979, C++ was a revolutionary programming language, it was based upon the C programming language, but had the ability to do object oriented programming (OO) with classes. In later years, the ability to use templates and generic programming was added as well.

At first it was merely a small project by its creator, Bjarne Stroustrup, a Danish computer scientist, but afterwards it rapidly grew in adoption and now has millions of users and is one of the top 10 programming languages of all time. C++ allows for the development of high level object oriented software, but at the same time also allows low level memory management and is backwardly compatible with the C programming language. It is tremendously useful, in particular for systems programming. C++ is used in many advanced projects, in particular it is the software for the F-35 Joint Strike Fighter (JSF), the worlds most technologically advanced aircraft, and is also used for the launch software for the NASA Artemis Rocket, which will carry astronauts to the Moon and beyond to Mars.

C++, due to its small footprint, is also a favorite for Embedded Systems and Programmable Logic Controllers (PLC).

C++ programming language is also a favorite option for Arduino and Raspberry Pi micro-controller development.

Bjarne Stroustrup, a computer scientist from Denmark, is the creator of the C++ programming language. He is a graduate of University of Aarhus in Denmark, and earned his PhD in Computer Science at Cambridge University in England. He is currently a director of technology at Morgan Stanley in New York City, and is also a visiting professor of Computer Science at Columbia University. www.stroustrup.com


Linus Torvalds, originally from the Swedish population of Finland, is the creator and lead developer of the Linux Kernel, and is currently one of the world's most accomplished operating system engineers. He is a graduate of the University of Helsinki in Finland. He is also an avid Scuba Diver. He currently resides in Oregon and works at the Linux Foundation.







However, software engineers being somewhat opinionated, C++ does have some vocal critics, in particular Linus Torvalds, creator of Linux. Linus did all of his early Linux kernel development in the C programming language, and is currently one of the world's best operating systems engineers. He is also a very vocal and opinionated critic of C++. Linus is also a very vocal, opinionated critic of other operating systems. In the early years of Linux, Linus had some boisterous and very loud flame wars with Andrew Tanenbaum, creator of the MINIX operating system. In spite of  Linus' opinion of C++, both Linus and Bjarne have good arguments in defense of their favorite programming languages. However, it is an undeniable fact that object oriented development with C++ provides great benefit for, in particular, large complex systems. Common functionality can be implemented in base classes used by other, derived classes and when it comes time to maintain or update the software project, having the common functionality in a base class is worlds easier to maintain than it would be in a non-OO language like the C programming language.

Unlike Java and C#, and other interpreted languages. C++ source code compiles directly into executable machine code, and there is no intermediate layer like with bytecodes in Java, etc. As a result, C++ executables are often much smaller than corresponding Java and C# software, and also run much faster.

In this blog post I will show how to use timing in C++ to do time analysis of algorithms for performance optimization. This is fairly simple to do in C++, and is very useful for optimizing software to run faster and more efficiently.

A good example to show that C++ is a well designed programming language, is to view the timing differences in sorting a vector with consecutive integer numbers, and sorting a shuffled vector where the integer numbers are not consecutive, but are shuffled. An efficient and fast sorting algorithm should be able to sort the consecutive vector much faster than a shuffled vector. The software example in this blog post will show this fact clearly.

First we will start with the following include files. and also a using statement so we will not have to use the STD:: prefix in each COUT, SORT, and VECTOR statement. We will use the "sort" method of a vector to sort the data in the vectors from the <vector> include, the shuffle method available in the <algorithm> include, and the timing options available in the <ctime> include.


Next, we will implement our main() method and the first part we will define the vector to use with our sorting. In this example the vector will have one million entries, but you are free to set the size of the vector to any size you wish. I made it a large vector so it would not sort instantly. I am also using  a TYPEDEF to make it easier to refactor the code. I will explain the TYPEDEF at the end of this blog post. We at first populate the vector with consecutive integers with the following FOR loop like in this example.


Next we will read the time from the system clock at the beginning of the SORT of the vector, sort the vector, then read the time at the end of the sort. We will do this first for the vector of consecutive integers.


Next, we will then shuffle the entries in the vector, with the RANDOM_SHUFFLE method, so they are mixed up and not consecutive like they were at first, then time the sort of the shuffled vector like in this example:


Initially we get the data as CLOCKS, by subtracting the beginning clock reading from the end clock reading, the result will be the amount of time in CLOCKS that it took to complete the sort operation. Then we cast that operation as  a DOUBLE so our results will be a decimal number, and then we use the constant CLOCKS_PER_SEC to get the time in seconds. In order for us to get a decimal value result of the time in seconds, we must also cast the CLOCKS_PER_SEC, an integer value, as a DOUBLE floating point number in order to get a proper decimal number for our result.


And finally, we will use this code to output our results.


I used Microsoft Visual Studio on Windows 10 to do this example as a C++ console application, as well as Fedora Linux for the example using the command line and g++. This is the results when running the application in Debug mode in Visual Studio, for this first run we are using the SECONDS as a double type so we can get a decimal number for our timing results.


Note that it takes almost twice as long in seconds to sort a shuffled vector, compared to how long it takes to sort a consecutive vector. This is the exact result we are looking for, it shows that the sort method is well designed and does not waste CPU cycles trying to sort a vector that is already sorted.

Next, since we are using a TYPEDEF for our SECONDS variable type, we only have to change that one line of typedef code and then all the places SECONDS is used in the application will also be changed. In a hypothetical application where say we are using 100 different variables of type SECONDS, we could change all 100 of them by changing one line of the TYPEDEF code. This is a very powerful feature of C++ that is very useful when refactoring code in large applications. As an example in this application, we will change our typedef type SECONDS from DOUBLE to an INT, to show the results as whole numbers, not a decimal number.


After making this change in our example application, this is what our results look like, note they are whole integer numbers instead of double decimal numbers.


If you are implementing this example on BSD Unix, Linux, or Apple MacOS, and do not use a graphical text editor. You can use the PICO or NANO text editors from the command line and compile the example application from the command line also. This is how you would do it using the g++ compiler:


Note once again it is taking about twice as long to sort the shuffled vector in comparison to sorting the consecutive vector.

If you get the following error when trying to run the compiled executable on BSD Unix, Linux, or Apple MacOS, it means that your executable does not have execute permissions. To add execute permissions to your executable, use the CHMOD command at the command line like the following.



Once again, after changing our typedef to INT instead of DOUBLE, this will cause the results of our timing the sorts to be cast to non-decimal integer numbers. We will re-compile our example program and run it again to see the change in the results.


Finally, this is what our entire example program looks like with all of the C++ code listed, in copy and pastable text.

 // CPPTimingAlgorithms.cpp - by Michael G. Workman  
 //  
 // This C++ console application shows how to time algorithms using the clock
 //
 // This example freely distributable under terms of MIT open source license
   
 #include <iostream>  
 #include <algorithm>  
 #include <ctime>  
 #include <vector>  
   
 using namespace std;  
   
 int main()  
 {  
      // create a type for seconds  
      typedef double seconds;  
   
      // create vector and populate with consecutive integers  
      vector<int> v(1000000);  
      int i = 0;  
      for (vector<int>::iterator it = v.begin(); it < v.end(); it++)  
      {  
           (*it) = i;  
           i++;  
      }  
   
      // start timing the sort of vector of consecutive integers  
      clock_t consecutiveStart = clock();  
      sort(v.begin(), v.end());  
      clock_t consecutiveEnd = clock();  
   
      // shuffle the vector, then start timing the sort of the vector of shuffled integers  
      random_shuffle(v.begin(), v.end());  
      clock_t shuffledStart = clock();  
      sort(v.begin(), v.end());  
      clock_t shuffledEnd = clock();  
   
      // determine the time in seconds of the sort of vector of consecutive integers  
      seconds consecutiveTime = ((double) consecutiveEnd - consecutiveStart) / (double) CLOCKS_PER_SEC;  
   
      // determine the time in seconds of the sort of vector of shuffled integers  
      seconds shuffledTime = ((double) shuffledEnd - shuffledStart) / (double) CLOCKS_PER_SEC;  
   
      // output results  
      cout << "Time to sort a consecutive vector: "  
           << consecutiveTime << " seconds" << endl;  
   
      cout << "Time to sort a shuffled vector: "  
           << shuffledTime << " seconds" << endl;  
   
      return 0;  
 }  

This is a good example of using timing to determine the efficiency of your algorithms, the same method can be used with most any C++ algorithm.

The source code for this example C++ program is also available at my GitHub version control at the following URL:

CPPTimingAlgorithms.cpp

 If you have any questions about C, C++, Microsoft C# .NET, and/or Microsoft Azure Cloud, please feel free to contact me by email at michael DOT g DOT workman AT gmail DOT COM

Also feel free to review my Curriculum Vitae at http://www.michaelgworkman.com

Comments

Popular Posts