C/C++ Optimisation Patterns

Subcategory: None · Core · Maths

Compiler Optimisations (Release Builds)

Modern C/C++ compilers support many automatic low-level optimisations which can improve the performance of the compiled code. The actual performance gain depends on your specific code, but it is not uncommon to see 5–10x speedups, and in some cases, 50x or more, especially for compute-intensive tasks.

Read More

Modern C/C++ compilers support many automatic low-level optimisations which can improve the performance of the compiled code. The actual performance gain depends on your specific code, but it is not uncommon to see 5–10x speedups, and in some cases, 50x or more, especially for compute-intensive tasks.

Compiler optimisations are not enabled by default because they make debugging more difficult. Optimised builds can:

• Reorder or eliminate code, making it harder to set breakpoints or inspect variables
• Inline functions, obscuring the call stack
• Remove or coalesce variables that appear unused

As a result, developers typically use unoptimised builds (debug) during development and optimised builds (release) for production.

Enabling Optimisations

If you wish to enable compiler optimisations (or check whether they are enabled) the guidance differs slightly between compilers.

GCC / Clang

The main optimisation flags provided by GCC and Clang are:

• -O0: No optimisation (default)
• -O1, -O2, -O3: Increasing levels of optimisation
• -Ofast: Aggressive optimisations, may break strict standards compliance
• -Os: Optimize for size

You should typically ensure that -O2 is passed to the compiler (either on the command-line or within the makefile/project) when compiling for release, to take advantage of compiler optimisations. If you’re not sure whether they’re being used, look out for them in the compile log.

-O3 and -Ofast can provide mixed results, as they use the most aggressive optimisations which can have inadvertent effects such as greatly increasing the binary size for limited to no further impact to performance.

CMake

CMake supports Debug and Release build configurations via the CMAKE_BUILD_TYPE argument at configure time.

cmake -DCMAKE_BUILD_TYPE=Release .
cmake --build .

If the CMake project is correctly structured (it may be worth reviewing the compilation log to make sure you can see an optimisation flag), passing Release will enable compiler optimisations . It’s up to the project maintainer in this scenario, whether the default configuration corresponds to Debug, Release or something else entirely.

Visual Studio (MSVC)

The default project structure within visual studio will contain both a Debug and a Release build configuration, the latter will have compiler optimisations enabled and should be used for production builds.

To enable compiler optimisations manually, navigate to Project Properties > C/C++ > Optimization and set this value to /O2 (Maxmimise speed) or /Ox (Full optimisation).

The Technical Detail

There are many different optimisations which can be performed by a compiler, GCC lists most of their compiler optimisations and allows them to be individually toggled.

Inlining

Calling a function has a small overhead, for small (e.g. mathematical) functions this can be high relative to the cost of actually executing the function. By moving regularly called small functions into headers and marking them as inline, the compiler will inline them where appropriate when compiler optimisations are enabled, removing the call overhead.

Read More

Calling a function has a small overhead, for small (e.g. mathematical) functions this can be high relative to the cost of actually executing the function. By moving regularly called small functions into headers and marking them as inline, the compiler will inline them where appropriate when compiler optimisations are enabled, removing the call overhead.

If when function-level profiling your code you see a function listed, that function has not been inlined. If you have small/cheap functions (e.g. 1-3 lines of maths) which are called frequently during execution and they appear among the functions using the most CPU time during execution. Consider making them inline, this should reduce the cost of calling them.

The implementation of an inlined function must be visible to the compiler when the function is being called in order for it to be inlined. This typically involves moving the implementation of the inlined function into it’s corresponding header file, either within the class definition or after it. Both the function prototype and implementation should be marked inline.

The inline keyword does not guarantee a compiler will inline calls to the function, compilers may use heuristics to decide when inlining is not appropriate.

The cost of a function call is relatively small, so inlining is only effective for small functions, where the cost of calling the function is a large proportion of it’s total cost. The performance impact will only typically be visible over the inlining of many thousands of function calls.

Example

A project implemented a bespoke small vector class that was used heavily during it’s simulations.

Vec3.h

#ifndef VEC3_H__
#define VEC3_H__
/**
 * Three dimensional, double type vector
 */
class Vec3 {
 public:
    // Storage
    double x,y,z;
    // Constructor
    Vec3(const double &a = 0, const double &b = 0, const double &c = 0){
        x=a;
        y=b;
        z=c;
    }
    // Arithmetic operator prototypes
    Vec3 operator+(const Vec3 &vec) const;
    Vec3& operator+=(const Vec3 &vec);
    // etc...
};
#endif // VEC3_H__

Vec3.cpp

// Arithmetic operator implementation
Vec3 Vec3::operator+(const Vec3 &vec) const {
    return Vec3(
        x + vec.x,
        y + vec.y,
        z + vec.z);
}

tVect& tVect::operator+=(const Vec3 &vec) {
    x += vec.x;
    y += vec.y;
    z += vec.z;
    return *this;
}
// etc...

When this project was profiled with gProf, the two most expensive functions were Vec3::operator+() and Vec3::operator*(), combined they were over 25% of the cumulative runtime, being called around 100 billion times each during the profile.

In response to this they were inlined by adding inline to all function prototypes in the header.

Due to the size of Vec3.cpp, it was decided not to move the implementations into the header but to rename the file Vec3.inl and to include it at the bottom of the header.

Vec3.h

#ifndef VEC3_H__
#define VEC3_H__
/**
 * Three dimensional, double type vector
 */
struct Vec3 {
    // Storage
    double x,y,z;
    // Constructor
    Vec3(const double &a = 0, const double &b = 0, const double &c = 0){
        x=a;
        y=b;
        z=c;
    }
    // Arithmetic operator prototypes
    inline Vec3 operator+(const Vec3 &vec) const;
    inline Vec3& operator+=(const Vec3 &vec);
    // etc...
};
#include "Vec3.inl"
#endif // VEC3_H__

Vec3.inl

// Arithmetic operator implementation
inline Vec3 Vec3::operator+(const Vec3 &vec) const {
    return Vec3(
        x + vec.x,
        y + vec.y,
        z + vec.z);
}

inline tVect& tVect::operator+=(const Vec3 &vec) {
    x += vec.x;
    y += vec.y;
    z += vec.z;
    return *this;
}
// etc...

After applying this optimisation to the project’s vector and quaternion classes, they no longer appeared within the profile instead the self cost of calling functions increased slightly.

When benchmarking the project before and after this optimisation, a 1.87x speedup had been achieved.

The Technical Detail

When a compiler inlines a function call, it removes the instruction to call the function (typically call) and replaces it with the full implementation of the function. This removes the cost of calling the function, with the trade-off of increasing the compiled binary’s size (the function’s implementation is duplicated everywhere it has been inlined).

Use BLAS/LAPACK Instead of Reimplementing Maths Functions

BLAS (Basic Linear Algebra Subprograms) and LAPACK (Linear Algebra PACKage) are widely used open-source libraries for doing maths, especially matrix operations. They are highly optimised, often for specific CPU architectures by the vendors (Intel, AMD, etc.) themselves, and can be found on all modern HPC systems. Therefore, they are significantly faster than anything we can write ourselves, especially for larger matrices, and should be used in most circumstances.

Read More

---

BLAS (Basic Linear Algebra Subprograms) and LAPACK (Linear Algebra PACKage) are widely used open-source libraries for doing maths, especially matrix operations. They are highly optimised, often for specific CPU architectures by the vendors (Intel, AMD, etc.) themselves, and can be found on all modern HPC systems. Therefore, they are significantly faster than anything we can write ourselves, especially for larger matrices, and should be used in most circumstances.

The BLAS and LAPACK standards are originally defined using Fortran, so using them is a little bit cumbersome:

1. The function signature for any BLAS/LAPACK function to be used has to be first declared.
2. If using C/C++, the function name must have an underscore, e.g. dgemm is used as dgemm_.
3. All arguments must be passed by reference.
4. Matrices must be contiguous arrays in column-major order (more on this below).

Other than that, using them is very straightforward — all we need to do is call a function in our code, and then link against BLAS when compiling our code, e.g.:

gcc example.c -o example -lopenblas

or in CMake:

find_package(BLAS REQUIRED)

add_executable(example example.c)
target_link_libraries(example ${BLAS_LIBRARIES})

IMPORTANT: When using BLAS/LAPACK, make sure you don’t link against the reference BLAS (this is the reference implementation and has not been optimised). A good shorthand is to use OpenBLAS, but depending on your CPU etc., other implementations may be faster. Check which implementations are available on your HPC system and ask your local friendly HPC administrators if unsure.

Example

This is a small benchmark comparing a hand coded matrix multiplication versus BLAS’s implementation:

#include <cstdlib>
#include <cstdio>
#include <chrono>

/**
 * Crude random matrix generator
 */
double* generate_matrix(int m, int n) {
  double* a = (double*)malloc(m * n * sizeof(double));
  for (int i = 0; i < m * n; ++i)
    a[i] = (double)rand() / RAND_MAX;
  return a;
}

/**
 * Manually implemented matrix multiplication
 */
void multiply(const double *matrix1, int m1, int n1, const double *matrix2, int m2, int n2, double *result) {
  for (int i = 0; i < m1; i++) {
    for (int j = 0; j < n2; j++) {
      result[i + j * m1] - 0.0;

      for (int k = 0; k < n1; k++) {
        result[i + j * m1] += matrix1[i + k * m1] * matrix2[k + j * m2];
      }
    }
  }
}

/**
* BLAS's matrix multiplication prototype
*/
extern "C" {
void dgemm_(const char*, const char*, const int*, const int*, const int*, const double*, const double*, const int*, const double*, const int*, const double*, double*, const int*);
}

int main() {
  const int m = 1000, n = 1000;
  const int REPEATS = 10;

  double *matrix1 = generate_matrix(m, n);
  double *matrix2 = generate_matrix(m, n);
  double *result_m = (double*)malloc(m * n * sizeof(double));
  double *result_b = (double*)malloc(m * n * sizeof(double));

  // Benchmark manual version
  auto start_m = std::chrono::high_resolution_clock::now();
  for (int i = 0; i < REPEATS; ++i)
    multiply(matrix1, m, n, matrix2, m, n, result_m);
  auto end_m = std::chrono::high_resolution_clock::now();
  
  std::chrono::duration<double> elapsed_m = end_m - start_m;
  printf("Manual took an average of %f seconds.\n", elapsed_m.count()/REPEATS);
  
  // Benchmark BLAS version
  const double one = 1.0, zero = 0.0;
  auto start_b = std::chrono::high_resolution_clock::now();
  for (int i = 0; i < REPEATS; ++i)
    dgemm_("N", "N", &m, &n, &n, &one, matrix1, &m, matrix2, &m, &zero, result_b, &m);
  auto end_b = std::chrono::high_resolution_clock::now();
  
  std::chrono::duration<double> elapsed_b = end_b - start_b;
  printf("BLAS took an average of %f seconds.\n", elapsed_b.count()/REPEATS);

  free(matrix1); free(matrix2); free(result_m); free(result_b);
}

Tested on local HPC, with 16-cores, using OpenBLAS:

module load OpenBLAS
g++ bench.cpp -O3 -o bench -lopenblas
./bench

Output:

Manual took an average of 1.183420 seconds.
BLAS took an average of 0.002624 seconds.

That’s a 450x speed-up!

CBLAS

The original BLAS interface expects column-major matrices, CBLAS can be used under C/C++ to process row-major matrices which may even perform faster due to improved memory access patterns.

Include <cblas.h> and prepend cblas_ to the method name. Note that char arguments have been replaced with enums and matrix functions have the additional layout argument, so the exact parameters passed to the function are likely to require updating.

/**
 * CBLAS include
 */
#include <cblas.h>

int main() {
...
  // Benchmark CBLAS version
  auto start_cb = std::chrono::high_resolution_clock::now();
  for (int i = 0; i < REPEATS; ++i)
    cblas_dgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans, m, n, n, 1.0, matrix1, n, matrix2, n, 0.0, result_cb, n);
  auto end_cb = std::chrono::high_resolution_clock::now();
  
  std::chrono::duration<double> elapsed_cb = end_cb - start_cb;
  printf("CBLAS took an average of %f seconds.\n", elapsed_cb.count()/REPEATS)
}

Which reports a further 20% speedup!

CBLAS took an average of 0.002022 seconds.

GPU

Even better, modern BLAS and LAPACK implementations are now available for GPUs, allowing us to take advantage of these accelerators with minimal effort (though unfortunately the interface is often different):

• NVIDIA has cuBLAS (though not LAPACK implementation, unfortunately)
• AMD has rocblas/hipblas
• There are also cross-platform (work on both NVIDIA and AMD hardware) implementations like magmaBLAS

Technical Explanation

There is a surprising amount of low-level optimisation possible when writing linear algebra functions - writing a simple double or triple loop to perform the operation is only the beginning, and the compiler can only do so much. One of the basic optimisations is computing the operation in blocks, but the block size needs to be optimised to the cache sizes available on a specific CPU. However, the HPC implementations of these libraries go way further than that, even going as far as writing the innermost computations directly in assembly. Furthermore, many HPC implementations are also parallelised with OpenMP, so using them gives us some parallelism “for free”.