C++教程 第36章 高性能技巧

第36章 高性能技巧

性能优化概述

性能优化是指通过各种技术手段，提高程序的运行速度、减少内存使用、降低CPU占用等。在C++中，性能优化可以从多个层面进行：

1. 算法优化：选择更高效的算法和数据结构
2. 代码优化：优化代码结构和实现细节
3. 编译优化：使用编译器优化选项
4. 内存优化：减少内存使用和提高内存访问效率
5. 并发优化：利用多线程和并行计算

算法与数据结构优化

选择合适的算法

算法的时间复杂度是影响程序性能的关键因素。在选择算法时，应该根据问题的规模和特点，选择时间复杂度较低的算法：

算法	时间复杂度	适用场景
线性查找	O(n)	小规模数据，无序数据
二分查找	O(log n)	有序数据
冒泡排序	O(n²)	小规模数据
快速排序	O(n log n)	大规模数据
哈希表查找	O(1)	需要快速查找的场景

选择合适的数据结构

选择合适的数据结构可以显著提高程序的性能：

1. 数组：随机访问速度快，适合需要频繁随机访问的场景
2. 链表：插入和删除操作快，适合需要频繁插入和删除的场景
3. 栈：后进先出，适合需要后进先出操作的场景
4. 队列：先进先出，适合需要先进先出操作的场景
5. 树：如二叉搜索树、平衡二叉树等，适合需要有序数据的场景
6. 哈希表：如std::unordered_map，适合需要快速查找的场景
7. 图：适合表示复杂的关系网络

示例：查找算法的选择

#include <vector>
#include <algorithm>
#include <unordered_set>

// 线性查找
bool linearSearch(const std::vector<int>& data, int target) {
    for (int num : data) {
        if (num == target) {
            return true;
        }
    }
    return false;
}

// 二分查找
bool binarySearch(const std::vector<int>& data, int target) {
    int left = 0, right = data.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (data[mid] == target) {
            return true;
        } else if (data[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

// 哈希表查找
bool hashSearch(const std::unordered_set<int>& data, int target) {
    return data.find(target) != data.end();
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::unordered_set<int> numSet(nums.begin(), nums.end());
    
    // 对于小规模数据，三种方法性能差异不大
    // 对于大规模数据，二分查找和哈希表查找明显快于线性查找
    
    return 0;
}

代码优化技巧

1. 减少函数调用开销

函数调用会产生开销，包括参数传递、栈帧设置和销毁等。对于频繁调用的小函数，可以考虑：

• 内联函数：使用inline关键字或模板，让编译器在调用处展开函数
• 宏：对于极其简单的操作，可以使用宏（但要注意宏的副作用）

// 内联函数
inline int add(int a, int b) {
    return a + b;
}

// 模板函数（自动内联）
template<typename T>
T max(T a, T b) {
    return a > b ? a : b;
}

2. 减少内存访问

内存访问速度远慢于CPU计算速度，减少内存访问可以显著提高性能：

• 缓存局部性：按顺序访问内存，避免随机访问
• 减少间接访问：避免多级指针和复杂的数据结构
• 使用寄存器变量：对于频繁使用的变量，使用register关键字（但现代编译器会自动优化）

// 优化前：每次循环都访问内存
void sum1(const std::vector<int>& data, int& result) {
    result = 0;
    for (size_t i = 0; i < data.size(); ++i) {
        result += data[i];
    }
}

// 优化后：使用局部变量，减少内存访问
void sum2(const std::vector<int>& data, int& result) {
    int sum = 0;
    for (size_t i = 0; i < data.size(); ++i) {
        sum += data[i];
    }
    result = sum;
}

3. 循环优化

循环是程序中最常见的性能瓶颈，优化循环可以显著提高程序性能：

• 循环展开：减少循环次数，增加每次循环的工作量
• 循环合并：将多个独立的循环合并为一个
• 循环不变式外提：将循环中不变的计算移到循环外
• 消除循环携带依赖：避免循环中后一次迭代依赖前一次迭代的结果

// 优化前：简单循环
void multiply1(const std::vector<int>& a, const std::vector<int>& b, std::vector<int>& result) {
    for (size_t i = 0; i < a.size(); ++i) {
        result[i] = a[i] * b[i];
    }
}

// 优化后：循环展开
void multiply2(const std::vector<int>& a, const std::vector<int>& b, std::vector<int>& result) {
    size_t i = 0;
    for (; i + 3 < a.size(); i += 4) {
        result[i] = a[i] * b[i];
        result[i+1] = a[i+1] * b[i+1];
        result[i+2] = a[i+2] * b[i+2];
        result[i+3] = a[i+3] * b[i+3];
    }
    for (; i < a.size(); ++i) {
        result[i] = a[i] * b[i];
    }
}

// 循环不变式外提
void process1(const std::vector<int>& data, std::vector<int>& result, int factor) {
    for (size_t i = 0; i < data.size(); ++i) {
        result[i] = data[i] * (factor * 2); // 每次循环都计算 factor * 2
    }
}

void process2(const std::vector<int>& data, std::vector<int>& result, int factor) {
    int scaledFactor = factor * 2; // 循环外计算
    for (size_t i = 0; i < data.size(); ++i) {
        result[i] = data[i] * scaledFactor;
    }
}

4. 减少分支预测失败

现代CPU使用分支预测来提高性能，分支预测失败会导致性能下降。可以通过以下方法减少分支预测失败：

• 避免复杂的条件判断：使用查表法代替复杂的条件判断
• 减少条件分支：使用条件表达式或位运算代替if-else语句
• 排序数据：对于有序数据，分支预测更容易成功

// 优化前：复杂的条件判断
int getGrade1(int score) {
    if (score >= 90) {
        return 5;
    } else if (score >= 80) {
        return 4;
    } else if (score >= 70) {
        return 3;
    } else if (score >= 60) {
        return 2;
    } else {
        return 1;
    }
}

// 优化后：使用查表法
int getGrade2(int score) {
    static const int grades[] = {1, 1, 1, 1, 1, 1, 2, 3, 4, 5};
    int index = score / 10;
    if (index < 0) index = 0;
    if (index > 9) index = 9;
    return grades[index];
}

// 优化前：条件分支
int max1(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

// 优化后：条件表达式
int max2(int a, int b) {
    return a > b ? a : b;
}

5. 减少虚函数调用

虚函数调用会产生额外的开销，因为需要通过虚函数表查找函数地址。对于性能敏感的代码，可以考虑：

• 避免使用虚函数：对于不需要多态的场景，使用普通函数
• 使用模板：使用模板实现静态多态，避免运行时多态
• 虚函数内联：对于简单的虚函数，编译器可能会内联（但通常不会）

// 优化前：使用虚函数
class Shape {
public:
    virtual ~Shape() = default;
    virtual double area() const = 0;
};

class Circle : public Shape {
public:
    Circle(double radius) : radius(radius) {}
    double area() const override {
        return M_PI * radius * radius;
    }
private:
    double radius;
};

// 优化后：使用模板

template<typename T>
double calculateArea(const T& shape) {
    return shape.area();
}

class Circle {
public:
    Circle(double radius) : radius(radius) {}
    double area() const {
        return M_PI * radius * radius;
    }
private:
    double radius;
};

内存优化技巧

1. 减少内存分配和释放

内存分配和释放是昂贵的操作，减少内存分配和释放可以显著提高性能：

• 预分配内存：对于已知大小的容器，使用reserve或resize预分配内存
• 对象池：对于频繁创建和销毁的对象，使用对象池
• 避免内存碎片：使用内存池或自定义分配器

// 优化前：频繁分配内存
void process1(const std::vector<int>& data) {
    for (size_t i = 0; i < data.size(); ++i) {
        std::vector<int> temp; // 每次循环都分配内存
        temp.push_back(data[i]);
        // 处理temp
    }
}

// 优化后：预分配内存
void process2(const std::vector<int>& data) {
    std::vector<int> temp;
    temp.reserve(1); // 预分配内存
    for (size_t i = 0; i < data.size(); ++i) {
        temp.clear(); // 清空内容，不释放内存
        temp.push_back(data[i]);
        // 处理temp
    }
}

2. 提高内存访问效率

内存访问效率直接影响程序性能，以下是一些提高内存访问效率的技巧：

• 内存对齐：使用alignas关键字确保数据对齐
• 连续内存：使用连续内存的数据结构，如std::vector
• 避免缓存行冲突：合理安排数据布局，避免多个线程同时访问同一缓存行

// 内存对齐
alignas(64) struct Data {
    int x;
    int y;
    // 其他成员
};

// 连续内存 vs 非连续内存
// 连续内存：std::vector
std::vector<int> vec(1000);
for (size_t i = 0; i < vec.size(); ++i) {
    vec[i] = i; // 连续访问，缓存命中率高
}

// 非连续内存：std::list
std::list<int> lst;
for (int i = 0; i < 1000; ++i) {
    lst.push_back(i);
}
for (auto it = lst.begin(); it != lst.end(); ++it) {
    *it = 0; // 非连续访问，缓存命中率低
}

3. 智能指针的性能考虑

智能指针虽然方便，但也会带来性能开销：

• std::unique_ptr：开销最小，几乎与原始指针相当
• std::shared_ptr：开销较大，因为需要维护引用计数
• std::weak_ptr：开销与std::shared_ptr相当

在性能敏感的代码中，应该根据实际情况选择合适的智能指针：

// 性能敏感场景：使用std::unique_ptr
std::unique_ptr<int> up(new int(42));

// 需要共享所有权：使用std::shared_ptr
std::shared_ptr<int> sp1(new int(42));
std::shared_ptr<int> sp2 = sp1;

// 避免循环引用：使用std::weak_ptr
class B;
class A {
public:
    std::shared_ptr<B> b;
};
class B {
public:
    std::weak_ptr<A> a;
};

编译优化

编译器优化选项

现代编译器提供了多种优化选项，可以显著提高程序性能：

• O0：无优化，编译速度快，适合调试
• O1：基本优化，平衡编译速度和运行速度
• O2：高级优化，适合生产环境
• O3：最高级优化，可能会增加代码大小
• Os：优化代码大小
• Ofast：启用所有O3优化，加上一些可能违反标准的优化

使用示例：

# 使用O2优化
g++ -O2 main.cpp -o app

# 使用O3优化
g++ -O3 main.cpp -o app

# 优化代码大小
g++ -Os main.cpp -o app

编译器特性

• 链接时优化（LTO）：在链接时进行全局优化
• 内联函数扩展：自动内联合适的函数
• 循环展开：自动展开循环
• 死代码消除：删除不会执行的代码
• 常量折叠：在编译时计算常量表达式

使用示例：

# 启用链接时优化
g++ -O2 -flto main.cpp -o app

并发优化

多线程编程

利用多线程可以充分利用多核CPU，提高程序性能：

• std::thread：C++11引入的线程类
• std::async：异步执行任务
• std::future：获取异步任务的结果

#include <thread>
#include <vector>
#include <numeric>

void parallelSum(const std::vector<int>& data, size_t start, size_t end, int& result) {
    result = std::accumulate(data.begin() + start, data.begin() + end, 0);
}

int main() {
    std::vector<int> data(1000000, 1);
    const size_t numThreads = std::thread::hardware_concurrency();
    const size_t chunkSize = data.size() / numThreads;
    
    std::vector<std::thread> threads;
    std::vector<int> results(numThreads, 0);
    
    // 创建线程
    for (size_t i = 0; i < numThreads; ++i) {
        size_t start = i * chunkSize;
        size_t end = (i == numThreads - 1) ? data.size() : (i + 1) * chunkSize;
        threads.emplace_back(parallelSum, std::ref(data), start, end, std::ref(results[i]));
    }
    
    // 等待线程完成
    for (auto& thread : threads) {
        thread.join();
    }
    
    // 汇总结果
    int total = std::accumulate(results.begin(), results.end(), 0);
    std::cout << "Total: " << total << std::endl;
    
    return 0;
}

并行算法

C++17引入了并行算法，使用起来更加方便：

#include <algorithm>
#include <execution>
#include <vector>

int main() {
    std::vector<int> data(1000000);
    
    // 并行填充
    std::fill(std::execution::par, data.begin(), data.end(), 1);
    
    // 并行排序
    std::sort(std::execution::par, data.begin(), data.end());
    
    return 0;
}

避免线程竞争

线程竞争会导致程序行为不确定，同时也会影响性能：

• 互斥锁：使用std::mutex保护共享资源
• 原子操作：使用std::atomic进行无锁操作
• 线程局部存储：使用thread_local避免共享

#include <atomic>
#include <thread>
#include <vector>

std::atomic<int> counter(0);

void increment() {
    for (int i = 0; i < 1000000; ++i) {
        counter++;
    }
}

int main() {
    std::vector<std::thread> threads;
    for (int i = 0; i < 4; ++i) {
        threads.emplace_back(increment);
    }
    
    for (auto& thread : threads) {
        thread.join();
    }
    
    std::cout << "Counter: " << counter << std::endl;
    
    return 0;
}

SIMD优化

SIMD（Single Instruction Multiple Data）是一种并行计算技术，可以在一条指令中处理多个数据元素。C++中可以通过以下方式使用SIMD：

• 编译器内置函数：如GCC的__builtin_vec_*函数
• Intel Intrinsics：Intel提供的SIMD指令集接口
• C++20 SIMD库：C++20引入的标准SIMD库

使用Intel Intrinsics

#include <immintrin.h>

void vectorAdd(const float* a, const float* b, float* result, size_t size) {
    size_t i = 0;
    // 处理16个元素的块（使用AVX指令集）
    for (; i + 15 < size; i += 16) {
        __m256 va = _mm256_loadu_ps(&a[i]);
        __m256 vb = _mm256_loadu_ps(&b[i]);
        __m256 vresult = _mm256_add_ps(va, vb);
        _mm256_storeu_ps(&result[i], vresult);
        
        __m256 va2 = _mm256_loadu_ps(&a[i + 8]);
        __m256 vb2 = _mm256_loadu_ps(&b[i + 8]);
        __m256 vresult2 = _mm256_add_ps(va2, vb2);
        _mm256_storeu_ps(&result[i + 8], vresult2);
    }
    // 处理剩余元素
    for (; i < size; ++i) {
        result[i] = a[i] + b[i];
    }
}

使用C++20 SIMD库

#include <experimental/simd>

namespace stdx = std::experimental;

void vectorAdd(const float* a, const float* b, float* result, size_t size) {
    using V = stdx::native_simd<float>;
    const size_t N = V::size();
    
    size_t i = 0;
    for (; i + N <= size; i += N) {
        V va = V::load(&a[i]);
        V vb = V::load(&b[i]);
        V vresult = va + vb;
        vresult.store(&result[i]);
    }
    
    for (; i < size; ++i) {
        result[i] = a[i] + b[i];
    }
}

性能分析工具

1. 性能分析器

性能分析器可以帮助我们找出程序的性能瓶颈：

• gprof：GCC自带的性能分析工具
• perf：Linux系统的性能分析工具
• Valgrind：内存分析和性能分析工具
• Intel VTune Profiler：Intel提供的性能分析工具
• Visual Studio Performance Profiler：Windows系统的性能分析工具

2. 使用示例

使用gprof

# 编译时添加-pg选项
g++ -pg main.cpp -o app

# 运行程序（生成gmon.out文件）
./app

# 分析性能
gprof app gmon.out > analysis.txt

使用perf

# 运行程序并分析性能
perf record ./app

# 查看分析结果
perf report

性能优化最佳实践

1. 先分析，后优化

• 使用性能分析工具找出性能瓶颈
• 针对瓶颈进行优化，而不是盲目优化
• 优化后再次分析，验证优化效果

2. 权衡代码可读性和性能

• 不要过度优化，牺牲代码可读性
• 对于性能关键路径，才进行深度优化
• 为优化的代码添加注释，说明优化的原因

3. 考虑平台特性

• 不同平台的CPU架构和内存模型不同
• 针对目标平台进行优化
• 使用条件编译处理不同平台的差异

4. 保持代码的可维护性

• 优化代码的同时，保持代码的可维护性
• 使用清晰的变量名和函数名
• 添加适当的注释

5. 测试优化效果

• 使用基准测试（benchmark）验证优化效果
• 测试不同输入规模下的性能
• 比较优化前后的性能差异

示例：性能优化综合应用

矩阵乘法优化

矩阵乘法是一个计算密集型操作，通过多种优化技术可以显著提高其性能：

#include <vector>
#include <chrono>
#include <iostream>

// 普通矩阵乘法
void matrixMultiplyNaive(const std::vector<std::vector<float>>& A, 
                         const std::vector<std::vector<float>>& B, 
                         std::vector<std::vector<float>>& C) {
    size_t n = A.size();
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            C[i][j] = 0;
            for (size_t k = 0; k < n; ++k) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

// 优化1：缓存优化（交换循环顺序）
void matrixMultiplyCacheOptimized(const std::vector<std::vector<float>>& A, 
                                  const std::vector<std::vector<float>>& B, 
                                  std::vector<std::vector<float>>& C) {
    size_t n = A.size();
    for (size_t i = 0; i < n; ++i) {
        for (size_t k = 0; k < n; ++k) {
            float aik = A[i][k];
            for (size_t j = 0; j < n; ++j) {
                C[i][j] += aik * B[k][j];
            }
        }
    }
}

// 优化2：分块优化
void matrixMultiplyBlocked(const std::vector<std::vector<float>>& A, 
                          const std::vector<std::vector<float>>& B, 
                          std::vector<std::vector<float>>& C) {
    size_t n = A.size();
    const size_t BLOCK_SIZE = 64; // 分块大小
    
    for (size_t i0 = 0; i0 < n; i0 += BLOCK_SIZE) {
        for (size_t k0 = 0; k0 < n; k0 += BLOCK_SIZE) {
            for (size_t j0 = 0; j0 < n; j0 += BLOCK_SIZE) {
                // 计算块内的元素
                size_t i_end = std::min(i0 + BLOCK_SIZE, n);
                size_t k_end = std::min(k0 + BLOCK_SIZE, n);
                size_t j_end = std::min(j0 + BLOCK_SIZE, n);
                
                for (size_t i = i0; i < i_end; ++i) {
                    for (size_t k = k0; k < k_end; ++k) {
                        float aik = A[i][k];
                        for (size_t j = j0; j < j_end; ++j) {
                            C[i][j] += aik * B[k][j];
                        }
                    }
                }
            }
        }
    }
}

// 生成随机矩阵
std::vector<std::vector<float>> generateRandomMatrix(size_t n) {
    std::vector<std::vector<float>> matrix(n, std::vector<float>(n));
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            matrix[i][j] = static_cast<float>(rand()) / RAND_MAX;
        }
    }
    return matrix;
}

// 测试函数
template<typename Func>
void testMatrixMultiply(Func func, const std::string& name, size_t n) {
    auto A = generateRandomMatrix(n);
    auto B = generateRandomMatrix(n);
    auto C = std::vector<std::vector<float>>(n, std::vector<float>(n, 0));
    
    auto start = std::chrono::high_resolution_clock::now();
    func(A, B, C);
    auto end = std::chrono::high_resolution_clock::now();
    
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << name << " took " << duration << " ms" << std::endl;
}

int main() {
    size_t n = 1000; // 矩阵大小
    
    std::cout << "Matrix size: " << n << "x" << n << std::endl;
    testMatrixMultiply(matrixMultiplyNaive, "Naive", n);
    testMatrixMultiply(matrixMultiplyCacheOptimized, "Cache Optimized", n);
    testMatrixMultiply(matrixMultiplyBlocked, "Blocked", n);
    
    return 0;
}

总结

性能优化是C++编程中的重要环节，通过合理的算法选择、代码优化、内存优化、编译优化和并发优化，可以显著提高程序的性能。

在进行性能优化时，应该遵循以下原则：

1. 先分析，后优化：使用性能分析工具找出瓶颈
2. 权衡代码可读性和性能：不要过度优化
3. 考虑平台特性：针对目标平台进行优化
4. 保持代码的可维护性：优化的同时保持代码清晰
5. 测试优化效果：使用基准测试验证优化效果

通过本章的学习，读者应该掌握C++中常见的性能优化技巧，能够根据实际情况选择合适的优化策略，提高程序的性能。