8. Need for Speed – Performance and Optimization

Learning Objectives

By the end of this chapter, you will be able to:

• Time your code performance manually
• Use source code instrumentation to measure code execution time
• Use the perf tool to analyze program performance
• Use the godbolt compiler explorer tool to analyze machine code generated by a compiler
• Use compiler flags to generate better code
• Apply code idioms that result in performance
• Write cache-friendly code
• Apply algorithm-level optimizations to real-world problems

In this chapter, we will explore concepts that will allow us to write fast code in general and several practical techniques that apply to C++ in particular.

Introduction

In today's world of extremely large and complicated software systems, stability and maintainability are usually considered the major goals for most software projects, whereas optimization has not been widely seen as a worthwhile goal since the 2000s. This is because of the rapid acceleration of hardware technology that overtook software demands on a regular schedule.

For many years, it seemed like the hardware improvements would continue to keep up with the performance demands of software, but applications continued to grow larger and more complex. Low-level native-compiled languages such as C and C++ dropped in popularity compared to less performant but easier to use interpreted languages such as Python or Ruby.

By the late 2000s, though, the trend of CPU transistor count (and performance) doubling every 18 months (a consequence of Moore's Law) had stopped, and performance improvements had flattened out. The expectation of 5 to 10 GHz processors being widely available...

Performance Measurement

The most important aspect of optimization is the measurement of code execution time. Unless we measure our application's performance with a wide range of input datasets, we will have no clue as to which part takes the most time and, our optimization efforts will be shot in the dark, with no guarantee of a result. There are several approaches for measurement, and some of them are listed here:

• Runtime instrumentation or profiling
• Source code instrumentation
• Manual execution timing
• Studying generated assembly code
• Manual estimation by studying the code and algorithms used

The preceding list is ordered in terms of how accurate the measurement is (with the most accurate one first). However, each of these methods has different advantages. The choice of which approach to adopt depends on the goals and scope of the optimization effort. In an all-out effort to get the fastest possible implementation, all of these may be required. We will examine...

Runtime Profiling

Profiling is a non-intrusive method of measuring the performance of the functions in a program. Profilers work by sampling a program's current execution address at frequent intervals (hundreds of times in a second) and making a log of which functions happened to be executing at the time. This is a statistical sampling approach that has reasonable accuracy. Sometimes, though, the results can be confusing as a program may spend a lot of time on functions that are a part of the operating system kernel. The most popular runtime profiling tool on Linux is perf. In the next section, we'll make use of perf to profile our program.

Exercise 3: Using perf to Profile Programs

perf can be installed on Ubuntu as follows:

apt-get install linux-tools-common linux-tools-generic

To get familiar with the basics of using perf, we'll profile and analyze the program from the previous exercise with the help of the perf tool. Perform the following steps to complete this exercise:

...

Optimization Strategies

Optimization of code can be done in several ways, such as the following:

• Compiler-based optimization
• Source code micro-optimization
• Cache-friendly code
• Algorithmic optimization

Here, each technique has its pros and cons. We will examine each of these methods in detail in the upcoming sections. Roughly speaking, these are ordered in terms of effort required and also potential gains in performance. We'll look at compiler-based optimization in the next section.

Compiler-Based Optimization

Passing the correct options to the compiler can net many performance benefits. A real-world example of this is the Clear Linux distro (Linux distribution) that was created by Intel. This distro has been compiled to extract the maximum performance from all the code and outperforms most other Linux distributions by 30% on most benchmarks, which is a very significant speedup. On the gcc and clang family of compilers, the most basic option for optimization is -O<...

Further Optimizations

Several other techniques exist that can be implemented as you code; some of them are not guaranteed to produce better code, but it takes very little effort to change your coding habits to do these reflexively. They cost nothing but may result in gains. A few of these techniques are as follows:

• Pass parameters that are not primitive types by const reference when possible. Even though move constructors can make copying inexpensive, they still involve more overhead than using a const reference.
• Use pre-increment (++i) or pre-decrement (--i) operators rather than the postfix versions. This usually has no utility for simple types such as integers but may do so for complex types with a custom increment operator. Getting into a habit of writing ++i rather than i++ is good practice unless post-increment is actually the desired behavior. Apart from performance benefits, such code declares the intent more clearly by using the right operator.
• Declare variables as...

Cache Friendly Code

Computer science was developed in the mid-20th century, when computers hardly existed, but nevertheless, by the 1980s, most of the useful data structures and algorithms had been discovered and refined. Algorithmic complexity analysis is a topic that anyone who learns computer science encounters – and there are well-accepted textbook definitions of the complexity of data structure operations. However, after 50 years since these things were analyzed, computers have evolved in a way that is quite different from what could have been envisaged. For example, a common "fact" is that the list data structures are faster for insertion operations than arrays. This seems like common sense because inserting an element into an array involves moving all the items after that point to new locations, whereas inserting into a list is merely a few pointer manipulations. We will test this hypothesis in the following exercise.

Exercise 10: Exploring the Effect of Caches on...

Summary

We have covered a lot of complex material in this chapter. Optimizing code is a difficult but necessary skill for any modern C++ developer. The demands of machine learning, hyper-realistic games, big data analysis, and energy-efficient computing make this a very vital area to learn about for any C++ professional. We have learned that the process of performance optimization is divided into two stages.

Firstly, optimization starts with a proper performance measurement strategy, with test conditions mirroring real-world data and usage patterns. We have learned how to measure performance by various methods – studying assembler code, manual timing, source code instrumentation, and using runtime profilers. Once we have accurate measurements, we can actually understand which portions of our programs are actually slow and focus our efforts there to get the maximum improvements.The second stage involves actually modifying the program – we learned about several strategies, starting...