Lesson 29-C++ Performance Optimization

Memory Management Optimization

Memory Layout

Memory layout refers to how a program organizes data in memory. In C++, memory layout mainly includes the following areas:

  • Stack
  • Heap
  • Global/Static Area
  • Constant Area
  • Uninitialized Data Area (BSS Area)

Example Code

#include <iostream>

class MyClass {
public:
    int x;
    double y;
    char z;
};

int main() {
    // Local variable on the stack
    MyClass obj1;
    std::cout << "Stack size: " << sizeof(obj1) << " bytes" << std::endl;

    // Dynamic allocation on the heap
    MyClass* obj2 = new MyClass();
    std::cout << "Heap size: " << sizeof(*obj2) << " bytes" << std::endl;

    // Global/static variable
    MyClass globalObj;
    std::cout << "Global/Static size: " << sizeof(globalObj) << " bytes" << std::endl;

    // Constant area
    const int c = 10;
    std::cout << "Constant size: " << sizeof(c) << " bytes" << std::endl;

    // Uninitialized data area
    MyClass uninitializedObj;
    std::cout << "Uninitialized size: " << sizeof(uninitializedObj) << " bytes" << std::endl;

    delete obj2;
    return 0;
}

Memory Alignment

Memory alignment means that data in memory must be placed at addresses that meet its natural alignment requirements. This improves data access speed.

Natural Alignment

  • Each data type has a natural alignment value.
  • For example, int typically requires 4-byte alignment.

Example Code

#include <iostream>

class MyStruct {
public:
    char a;
    int b;
    double c;
};

int main() {
    std::cout << "Size of MyStruct: " << sizeof(MyStruct) << " bytes" << std::endl;

    // Output the offset of struct members
    std::cout << "Offset of a: " << offsetof(MyStruct, a) << " bytes" << std::endl;
    std::cout << "Offset of b: " << offsetof(MyStruct, b) << " bytes" << std::endl;
    std::cout << "Offset of c: " << offsetof(MyStruct, c) << " bytes" << std::endl;

    return 0;
}

Memory Access Patterns

Memory access patterns refer to how a program accesses memory. Common memory access patterns include:

  • Sequential access
  • Random access
  • Strided access

Example Code

#include <iostream>
#include <vector>

void sequentialAccess(std::vector<int>& vec) {
    for (int i = 0; i < vec.size(); ++i) {
        vec[i] *= 2;
    }
}

void randomAccess(std::vector<int>& vec) {
    for (int i = 0; i < vec.size(); ++i) {
        int index = rand() % vec.size();
        vec[index] *= 2;
    }
}

void jumpAccess(std::vector<int>& vec) {
    for (int i = 0; i < vec.size(); i += 10) {
        vec[i] *= 2;
    }
}

int main() {
    std::vector<int> vec(1000000, 1);

    // Sequential access
    sequentialAccess(vec);
    // Random access
    randomAccess(vec);
    // Strided access
    jumpAccess(vec);

    return 0;
}

Cache-Friendly Data Structures

Cache-friendly data structures are those that make full use of the cache mechanism. Common cache-friendly data structures include:

  • Arrays
  • Contiguous storage
  • Circular buffers

Example Code

#include <iostream>
#include <vector>

// Contiguous storage of a 2D array
class Matrix {
private:
    std::vector<int> data;
    int rows;
    int cols;

public:
    Matrix(int rows, int cols) : rows(rows), cols(cols), data(rows * cols) {}

    int& operator()(int row, int col) {
        return data[row * cols + col];
    }
};

int main() {
    Matrix m(100, 100);

    // Initialize matrix
    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 100; ++j) {
            m(i, j) = i * j;
        }
    }

    // Access matrix elements
    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 100; ++j) {
            std::cout << m(i, j) << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

Summary

Memory Layout

  • Stack: Used to store local variables and function call stack.
  • Heap: Used for dynamic memory allocation.
  • Global/Static Area: Used to store global and static variables.
  • Constant Area: Used to store constants.
  • Uninitialized Data Area (BSS Area): Used to store uninitialized global and static variables.

Memory Alignment

  • Each data type has a natural alignment value, e.g., int usually requires 4-byte alignment.
  • The offset of struct members can be obtained using the offsetof function.

Memory Access Patterns

  • Sequential access: Accesses memory in order, suitable for arrays and contiguous storage.
  • Random access: Accesses memory randomly, may cause cache misses.
  • Strided access: Accesses memory in jumps, may reduce cache hit rate.

Cache-Friendly Data Structures

  • Arrays: Contiguous storage, suitable for cache access.
  • Contiguous storage: Minimize memory fragmentation to improve cache utilization.
  • Circular buffers: Use fixed-size buffers to improve cache hit rate.

Algorithm Optimization

Time Complexity

Time complexity measures the growth rate of an algorithm’s execution time, usually expressed using Big O notation (O).

Basic Concepts

  • Constant time complexity (O(1)): Execution time is independent of input size.
  • Linear time complexity (O(n)): Execution time is proportional to input size.
  • Logarithmic time complexity (O(log n)): Execution time is proportional to the logarithm of input size.
  • Polynomial time complexity (O(n^k)): Execution time is proportional to a polynomial of input size.
  • Exponential time complexity (O(2^n)): Execution time grows exponentially.

Analysis Methods

  • Basic operation counting: Count the number of basic operations in the algorithm.
  • Asymptotic analysis: Ignore lower-order terms and constants, focus on the growth rate of the highest-order term.
  • Recursion analysis: Use recurrence relations or the Master Theorem to analyze recursive algorithms.

Example Analysis

Constant Time Complexity (O(1))

int max(int a, int b) {
    return a > b ? a : b;
}

Linear Time Complexity (O(n))

int sum(int n) {
    int total = 0;
    for (int i = 1; i <= n; ++i) {
        total += i;
    }
    return total;
}

Logarithmic Time Complexity (O(log n))

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

Polynomial Time Complexity (O(n^2))

void printPairs(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << arr[i] << " " << arr[j] << std::endl;
        }
    }
}

Exponential Time Complexity (O(2^n))

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Space Complexity

Space complexity measures the growth rate of memory usage by an algorithm, usually expressed using Big O notation (O).

Basic Concepts

  • Constant space complexity (O(1)): Memory usage is independent of input size.
  • Linear space complexity (O(n)): Memory usage is proportional to input size.
  • Polynomial space complexity (O(n^k)): Memory usage is proportional to a polynomial of input size.

Analysis Methods

  • Variable counting: Count the number of variables used in the algorithm.
  • Auxiliary space counting: Count the extra space used by the algorithm.
  • Recursive space counting: Count the depth of the recursion call stack.

Example Analysis

Constant Space Complexity (O(1))

int max(int a, int b) {
    return a > b ? a : b;
}

Linear Space Complexity (O(n))

void reverseArray(int arr[], int n) {
    int temp[n];
    for (int i = 0; i < n; ++i) {
        temp[i] = arr[n - 1 - i];
    }
    for (int i = 0; i < n; ++i) {
        arr[i] = temp[i];
    }
}

Polynomial Space Complexity (O(n^2))

void printPairs(int arr[], int n) {
    int pairs[n][n];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            pairs[i][j] = arr[i] + arr[j];
        }
    }
}

Comprehensive Analysis

In practical applications, we need to consider both time and space complexity to achieve optimal performance and resource utilization.

Balancing Time and Space

  • In some cases, space complexity can be traded for better time complexity.
  • For example, using a hash table can reduce lookup time from O(n) to O(1), but increases space complexity.

Practical Applications

Sorting Algorithms

  • Quick sort: Average time complexity O(n log n), worst case O(n^2), space complexity O(log n).
  • Merge sort: Time complexity O(n log n), space complexity O(n).

Search Algorithms

  • Binary search: Time complexity O(log n), space complexity O(1).
  • Depth-First Search (DFS): Time complexity O(V + E), space complexity O(V).
  • Breadth-First Search (BFS): Time complexity O(V + E), space complexity O(V).

Dynamic Programming

  • Fibonacci sequence: Recursive O(2^n), space complexity O(n); Iterative O(n), space complexity O(1).

Code Examples

Time Complexity Examples

#include <iostream>

// Constant time complexity O(1)
int max(int a, int b) {
    return a > b ? a : b;
}

// Linear time complexity O(n)
int sum(int n) {
    int total = 0;
    for (int i = 1; i <= n; ++i) {
        total += i;
    }
    return total;
}

// Logarithmic time complexity O(log n)
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// Polynomial time complexity O(n^2)
void printPairs(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << arr[i] << " " << arr[j] << std::endl;
        }
    }
}

// Exponential time complexity O(2^n)
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Max: " << max(3, 5) << std::endl;
    std::cout << "Sum: " << sum(n) << std::endl;
    std::cout << "Binary Search: " << binarySearch(arr, 0, n - 1, 3) << std::endl;
    std::cout << "Fibonacci: " << fibonacci(5) << std::endl;

    return 0;
}

Space Complexity Examples

Linear Space Complexity (O(n))

#include <iostream>

// Linear space complexity O(n)
void reverseArray(int arr[], int n) {
    int temp[n];
    for (int i = 0; i < n; ++i) {
        temp[i] = arr[n - 1 - i];
    }
    for (int i = 0; i < n; ++i) {
        arr[i] = temp[i];
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    reverseArray(arr, n);

    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Polynomial Space Complexity (O(n^2))

#include <iostream>

// Polynomial space complexity O(n^2)
void printPairs(int arr[], int n) {
    int pairs[n][n];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            pairs[i][j] = arr[i] + arr[j];
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << pairs[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printPairs(arr, n);

    return 0;
}

Comprehensive Analysis and Optimization

In actual development, we need to consider both time and space complexity to achieve optimal performance. Here are some common optimization techniques:

Time Complexity Optimization

Loop Optimization

  • Use more efficient loop conditions.
  • Minimize computation within loops.

Algorithm Selection

  • Choose algorithms more suitable for the current problem.
  • Use advanced algorithms like divide-and-conquer, dynamic programming, etc.

Data Structure Optimization

  • Use more efficient data structures, such as hash tables, trees, etc.

Space Complexity Optimization

In-Place Operations

  • Avoid using extra space, operate directly on the original array.
  • For example, reverse an array without using an additional array.

Space Reuse

  • Reuse existing space to reduce additional space usage.
  • For example, use rolling arrays in dynamic programming.

Constant Space Complexity

  • Minimize the use of auxiliary variables.
  • For example, use pointers or indices instead of arrays.

Example Analysis

Time Complexity Optimization Example

Optimized Loop

#include <iostream>

// Optimized linear time complexity O(n)
int sum(int n) {
    int total = 0;
    for (int i = 1; i <= n; ++i) {
        total += i;
    }
    return total;
}

int main() {
    int n = 1000000;
    std::cout << "Sum: " << sum(n) << std::endl;

    return 0;
}

Optimized Algorithm

#include <iostream>
#include <unordered_map>

// Optimized linear time complexity O(n)
int findDuplicate(int arr[], int n) {
    std::unordered_map<int, int> countMap;
    for (int i = 0; i < n; ++i) {
        if (countMap[arr[i]] > 0) {
            return arr[i];
        }
        countMap[arr[i]]++;
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Duplicate: " << findDuplicate(arr, n) << std::endl;

    return 0;
}

Space Complexity Optimization Example

In-Place Operation

#include <iostream>

// In-place operation with linear space complexity O(1)
void reverseArrayInPlace(int arr[], int n) {
    int start = 0;
    int end = n - 1;
    while (start < end) {
        std::swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    reverseArrayInPlace(arr, n);

    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Space Reuse

#include <iostream>

// Space reuse with polynomial space complexity O(n)
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

int main() {
    int n = 10;
    std::cout << "Fibonacci: " << fibonacci(n) << std::endl;

    return 0;
}

Compiler Optimization

Compiler Optimization Flags

Compiler optimization flags control the level of optimization during compilation. Different compilers have different flags, but most modern compilers support the following common optimization flags:

GCC/G++

  • -O0: No optimization.
  • -O1: Basic optimization.
  • -O2: More optimization, this is the default optimization level.
  • -O3: Maximum optimization, may sacrifice code readability and debugging convenience.
  • -Ofast: Maximum optimization, allows the compiler to ignore some standard behaviors for higher performance.

Clang

  • -O0: No optimization.
  • -O1: Basic optimization.
  • -O2: More optimization, this is the default optimization level.
  • -O3: Maximum optimization, may sacrifice code readability and debugging convenience.
  • -Ofast: Maximum optimization, allows the compiler to ignore some standard behaviors for higher performance.

Inline Functions

An inline function is a special function definition that reduces function call overhead. When a function is declared inline, the compiler inserts the function body directly at the call site, avoiding function call overhead.

Inline Function Declaration

inline int add(int a, int b) {
    return a + b;
}

Advantages of Inline Functions

  • Reduce function call overhead.
  • Improve code execution speed.

Disadvantages of Inline Functions

  • Increase compilation time and generated code size.
  • Not suitable for complex functions, as it may cause code bloat.

Inline Assembly

Inline assembly refers to embedding assembly code directly in C/C++ code. This method enables lower-level optimization but requires knowledge of assembly language.

Basic Syntax of Inline Assembly

#include <immintrin.h> // Include SSE instruction set header

__m128i addVectors(__m128i a, __m128i b) {
    return _mm_add_epi32(a, b);
}

int main() {
    __m128i vec1 = _mm_set1_epi32(1);
    __m128i vec2 = _mm_set1_epi32(2);
    __m128i result = addVectors(vec1, vec2);

    int resultArray[4];
    _mm_storeu_si128((__m128i *)resultArray, result);

    for (int i = 0; i < 4; ++i) {
        std::cout << resultArray[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Advantages of Inline Assembly

  • Enables lower-level optimization.
  • Leverages specific hardware features (such as SIMD instruction sets).

Disadvantages of Inline Assembly

  • Poor code portability.
  • Requires in-depth knowledge of assembly language.

Example Code

Compiler Optimization Flag Example

#include <iostream>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main() {
    int n = 10;
    std::cout << "Factorial: " << factorial(n) << std::endl;

    return 0;
}

Compilation Command:

g++ -O3 -std=c++17 example.cpp -o example

Inline Function Example

#include <iostream>

inline int add(int a, int b) {
    return a + b;
}

int main() {
    int x = 5;
    int y = 10;
    std::cout << "Sum: " << add(x, y) << std::endl;

    return 0;
}

Inline Assembly Example

#include <iostream>
#include <immintrin.h> // Include SSE instruction set header

__m128i addVectors(__m128i a, __m128i b) {
    return _mm_add_epi32(a, b);
}

int main() {
    __m128i vec1 = _mm_set1_epi32(1);
    __m128i vec2 = _mm_set1_epi32(2);
    __m128i result = addVectors(vec1, vec2);

    int resultArray[4];
    _mm_storeu_si128((__m128i *)resultArray, result);

    for (int i = 0; i < 4; ++i) {
        std::cout << resultArray[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Parallel Computing

OpenMP

OpenMP (Open Multi-Processing) is a parallel programming model for shared-memory multicore processors. It uses simple compiler directives (pragmas) to guide the compiler on how to parallelize code.

OpenMP Basic Syntax

#include <iostream>
#include <omp.h>

int main() {
    #pragma omp parallel
    {
        int thread_id = omp_get_thread_num();
        int num_threads = omp_get_num_threads();

        std::cout << "Thread ID: " << thread_id << ", Total Threads: " << num_threads << std::endl;
    }

    return 0;
}

OpenMP Directives

  • #pragma omp parallel: Instructs the compiler to parallelize a code block.
  • #pragma omp for: Parallelizes a for loop.
  • #pragma omp critical: Protects a critical section to prevent multiple threads from accessing the same resource simultaneously.
  • #pragma omp single: Specifies that a code block is executed by a single thread.
  • #pragma omp barrier: Waits for all threads to reach a certain point.

Example: Parallelizing a for Loop

#include <iostream>
#include <omp.h>

int main() {
    const int N = 1000000;
    double sum = 0.0;
    double data[N];

    // Initialize data
    for (int i = 0; i < N; ++i) {
        data[i] = i;
    }

    #pragma omp parallel for reduction(+:sum)
    for (int i = 0; i < N; ++i) {
        sum += data[i];
    }

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

Compilation Command:

g++ -fopenmp example.cpp -o example

Run Command:

./example

MPI (Message Passing Interface)

MPI is a parallel programming model for distributed memory systems. It achieves parallel computing through message passing between processes.

MPI Basic Syntax

#include <mpi.h>
#include <iostream>

int main(int argc, char *argv[]) {
    MPI_Init(&argc, &argv);

    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    std::cout << "Process Rank: " << rank << ", Total Processes: " << size << std::endl;

    MPI_Finalize();

    return 0;
}

Common MPI Functions

  • MPI_Init: Initializes the MPI library.
  • MPI_Finalize: Finalizes the MPI library.
  • MPI_Comm_rank: Gets the rank of the current process.
  • MPI_Comm_size: Gets the total number of processes.
  • MPI_Send: Sends a message.
  • MPI_Recv: Receives a message.
  • MPI_Bcast: Broadcasts a message.
  • MPI_Gather: Gathers messages.
  • MPI_Scatter: Scatters messages.

Example: Parallelizing Matrix Multiplication

#include <mpi.h>
#include <iostream>

#define N 1000

void multiplyMatrix(double *A, double *B, double *C, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            C[i * n + j] = 0.0;
            for (int k = 0; k < n; ++k) {
                C[i * n + j] += A[i * n + k] * B[k * n + j];
            }
        }
    }
}

int main(int argc, char *argv[]) {
    MPI_Init(&argc, &argv);

    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    double *A, *B, *C;
    if (rank == 0) {
        A = new double[N * N];
        B = new double[N * N];
        C = new double[N * N];

        // Initialize matrices A and B
        for (int i = 0; i < N * N; ++i) {
            A[i] = 1.0;
            B[i] = 2.0;
        }
    } else {
        A = nullptr;
        B = nullptr;
        C = nullptr;
    }

    // Broadcast matrices A and B
    MPI_Bcast(A, N * N, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    MPI_Bcast(B, N * N, MPI_DOUBLE, 0, MPI_COMM_WORLD);

    // Compute local matrix multiplication
    int local_n = N / size;
    double *local_A = new double[local_n * N];
    double *local_B = new double[N * N];
    double *local_C = new double[local_n * N];

    MPI_Scatter(A, local_n * N, MPI_DOUBLE, local_A, local_n * N, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    MPI_Bcast(B, N * N, MPI_DOUBLE, 0, MPI_COMM_WORLD);

    multiplyMatrix(local_A, B, local_C, local_n);

    // Gather results
    MPI_Gather(local_C, local_n * N, MPI_DOUBLE, C, local_n * N, MPI_DOUBLE, 0, MPI_COMM_WORLD);

    if (rank == 0) {
        // Output result
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                std::cout << C[i * N + j] << " ";
            }
            std::cout << std::endl;
        }
    }

    delete[] A;
    delete[] B;
    delete[] C;
    delete[] local_A;
    delete[] local_B;
    delete[] local_C;

    MPI_Finalize();

    return 0;
}

Compilation Command:

mpicxx -o matrix_multiply matrix_multiply.cpp

Run Command:

mpirun -np 4 ./matrix_multiply

Summary

Parallel computing can be achieved using OpenMP and MPI, which are suitable for shared-memory multicore processors and distributed memory systems, respectively.

OpenMP:

  • Suitable for shared-memory multicore processors.
  • Achieves parallelization through simple compiler directives.
  • Common directives include #pragma omp parallel, #pragma omp for, #pragma omp critical, etc.

MPI:

  • Suitable for distributed memory systems.
  • Achieves parallel computing through message passing between processes.
  • Common functions include MPI_Init, MPI_Finalize, MPI_Comm_rank, MPI_Comm_size, MPI_Send, MPI_Recv, etc.
  • By properly using these parallel computing techniques, program computational efficiency and the ability to handle large-scale data can be significantly improved.

Share your love