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.
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.
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.
#include <iostream> #include <algorithm> #include <ctime> #include <vector> using namespace std;
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.
// create a type for seconds typedef double seconds; // create vector and populate with consecutive integers vectorv(1000000); int i = 0; for (vector ::iterator it = v.begin(); it < v.end(); it++) { (*it) = i; i++; }
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.
// start timing the sort of vector of consecutive integers clock_t consecutiveStart = clock(); sort(v.begin(), v.end()); clock_t consecutiveEnd = clock();
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:
// 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();
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.
// 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;
And finally, we will use this code to output our results.
// output results cout << "Time to sort a consecutive vector: " << consecutiveTime << " seconds" << endl; cout << "Time to sort a shuffled vector: " << shuffledTime << " seconds" << endl;
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.
// create a type for seconds typedef double seconds;
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.
Here is a copy-and-pastable listing of our entire C++ example application.
// 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 // https://opensource.org/licenses/MIT #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.
This example C++ program was created on Microsoft Visual Studio IDE running on Windows 10. Microsoft Visual Studio Community Edition is a free download, while the Professional and Enterprise versions can be purchased. This example C++ program will run equally well on Unix and Linux with either the g++ compiler or the CLANG compiler.
For those who wish to try out and learn Unix, there is a NetBSD Unix shell account available from SDF at http://sdf.org for $9 every 3 months. Also, a free OpenBSD Unix shell account is available on https://tilde.institute. There is free Linux offerings on the internet as well. A free Ubuntu Linux shell account is available at https://tilde.team. Many Linux versions are available as free downloads on the internet as well.
To see my Curriculum Vitae, go to Michael G Workman CV
To see my projects on Azure DevOps, go to https://dev.azure.com/AbionTechnology/
To see my Posts and Answers on Stack Overflow,
go to Michael G. Workman on Stack Overflow
If you have any questions about C, C++, Microsoft C# .NET, Microsoft Azure Cloud, Unix, Linux, and/or Mobile Apps, please feel free to contact me by email at:
michael.g.workman@outlook.com
