# 10-性能优化技术

性能优化是编写高效程序的关键。优化应基于profiling数据，遵循"测量-优化-验证"循环，避免过早优化。

## 编译器优化

现代编译器自带强大优化能力。选择合适优化级别和选项可显著提升性能，无需修改代码。

### 编译选项优化

编译优化分多个级别：`-O2` 平衡性能和编译时间，`-O3` 激进优化，`-Os` 优化体积。`-march=native` 针对当前CPU优化。


```cpp
// 编译时优化选项
// -O0: 无优化（调试用）
// -O1: 基本优化
// -O2: 推荐优化级别
// -O3: 激进优化
// -Os: 优化代码大小
// -Ofast: 最快执行速度

// 示例编译命令
// g++ -O2 -march=native -mtune=native -flto source.cpp

// 链接时优化
// g++ -O2 -flto source1.cpp source2.cpp
```

### 内联函数

内联函数在调用处展开，消除函数调用开销。适合短小、频繁调用的函数。编译器根据代码复杂度决定是否真正内联。

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

// 类内定义自动内联
class Calculator {
public:
    int multiply(int a, int b) {  // 自动内联
        return a * b;
    }
};

// 模板函数通常内联
template<typename T>
T maximum(T a, T b) {
    return (a > b) ? a : b;
}

// 强制内联（不推荐）
inline __attribute__((always_inline)) int fastAdd(int a, int b) {
    return a + b;
}
```

### 循环优化

循环是性能热点。循环展开减少分支判断，循环不变式外提避免重复计算，缓存循环边界减少函数调用。

```cpp
// 循环展开
void unrolledLoop(int* arr, int size) {
    for (int i = 0; i < size; i += 4) {
        arr[i] *= 2;
        arr[i + 1] *= 2;
        arr[i + 2] *= 2;
        arr[i + 3] *= 2;
    }
}

// 循环不变式外提
void optimizedLoop(int* arr, int size, int factor) {
    // factor在循环中不变，编译器会自动外提
    for (int i = 0; i < size; ++i) {
        arr[i] *= factor;
    }
}

// 减少循环中的函数调用
void inefficientLoop(std::vector<int>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {  // 每次调用size()
        vec[i] *= 2;
    }
}

void efficientLoop(std::vector<int>& vec) {
    size_t size = vec.size();  // 只调用一次
    for (size_t i = 0; i < size; ++i) {
        vec[i] *= 2;
    }
}
```

## 内存优化

### 内存对齐
```cpp
#include <cstddef>

// 结构体对齐优化
struct UnoptimizedStruct {
    char c;      // 1字节
    int i;       // 4字节，需要3字节填充
    char c2;     // 1字节，需要3字节填充
    double d;    // 8字节
};
// 总大小：24字节

struct OptimizedStruct {
    double d;    // 8字节
    int i;       // 4字节
    char c;      // 1字节
    char c2;     // 1字节
    // 2字节填充
};
// 总大小：16字节

// 强制对齐
struct alignas(16) AlignedStruct {
    double data[2];
};

// 查询对齐要求
void checkAlignment() {
    std::cout << "int alignment: " << alignof(int) << std::endl;
    std::cout << "double alignment: " << alignof(double) << std::endl;
}
```

### 缓存友好设计
```cpp
// 缓存友好的数据结构
class CacheFriendlyMatrix {
private:
    std::vector<double> data;
    size_t rows, cols;
    
public:
    CacheFriendlyMatrix(size_t r, size_t c) 
        : rows(r), cols(c), data(r * c) {}
    
    // 行优先存储，访问连续内存
    double& operator()(size_t row, size_t col) {
        return data[row * cols + col];
    }
    
    const double& operator()(size_t row, size_t col) const {
        return data[row * cols + col];
    }
    
    // 缓存友好的矩阵乘法
    CacheFriendlyMatrix multiply(const CacheFriendlyMatrix& other) const {
        CacheFriendlyMatrix result(rows, other.cols);
        
        // 分块乘法，提高缓存命中率
        const size_t blockSize = 64;
        
        for (size_t i = 0; i < rows; i += blockSize) {
            for (size_t j = 0; j < other.cols; j += blockSize) {
                for (size_t k = 0; k < cols; k += blockSize) {
                    // 处理块
                    for (size_t ii = i; ii < std::min(i + blockSize, rows); ++ii) {
                        for (size_t jj = j; jj < std::min(j + blockSize, other.cols); ++jj) {
                            double sum = 0.0;
                            for (size_t kk = k; kk < std::min(k + blockSize, cols); ++kk) {
                                sum += (*this)(ii, kk) * other(kk, jj);
                            }
                            result(ii, jj) += sum;
                        }
                    }
                }
            }
        }
        
        return result;
    }
};
```

### 内存池
```cpp
#include <memory>
#include <vector>

template<typename T>
class MemoryPool {
private:
    struct Block {
        alignas(T) char data[sizeof(T)];
        bool inUse;
    };
    
    std::vector<Block> blocks;
    size_t nextFree;
    
public:
    MemoryPool(size_t initialSize = 1024) : nextFree(0) {
        blocks.resize(initialSize);
    }
    
    T* allocate() {
        // 查找空闲块
        for (size_t i = nextFree; i < blocks.size(); ++i) {
            if (!blocks[i].inUse) {
                blocks[i].inUse = true;
                nextFree = i + 1;
                return reinterpret_cast<T*>(blocks[i].data);
            }
        }
        
        // 扩展池
        size_t oldSize = blocks.size();
        blocks.resize(oldSize * 2);
        
        blocks[oldSize].inUse = true;
        nextFree = oldSize + 1;
        return reinterpret_cast<T*>(blocks[oldSize].data);
    }
    
    void deallocate(T* ptr) {
        for (auto& block : blocks) {
            if (reinterpret_cast<T*>(block.data) == ptr) {
                block.inUse = false;
                if (&block - &blocks[0] < nextFree) {
                    nextFree = &block - &blocks[0];
                }
                break;
            }
        }
    }
};
```

## 算法优化

### 时间复杂度优化
```cpp
// 原始O(n²)算法
int findMaxSumSlow(const std::vector<int>& arr) {
    int maxSum = INT_MIN;
    for (size_t i = 0; i < arr.size(); ++i) {
        for (size_t j = i; j < arr.size(); ++j) {
            int sum = 0;
            for (size_t k = i; k <= j; ++k) {
                sum += arr[k];
            }
            maxSum = std::max(maxSum, sum);
        }
    }
    return maxSum;
}

// 优化为O(n)算法（Kadane算法）
int findMaxSumFast(const std::vector<int>& arr) {
    int maxSoFar = arr[0];
    int maxEndingHere = arr[0];
    
    for (size_t i = 1; i < arr.size(); ++i) {
        maxEndingHere = std::max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = std::max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}
```

### 空间复杂度优化
```cpp
// 原始算法：O(n)空间
int fibonacciSlow(int n) {
    if (n <= 1) return n;
    
    std::vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

// 优化算法：O(1)空间
int fibonacciFast(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
```

## 数据结构优化

### 高效容器选择
```cpp
#include <unordered_map>
#include <unordered_set>
#include <deque>

// 根据使用场景选择合适的数据结构
class OptimizedDataStructures {
public:
    // 频繁查找：使用unordered_map
    void frequentLookup() {
        std::unordered_map<int, std::string> map;
        // O(1)平均查找时间
    }
    
    // 有序数据：使用map
    void orderedData() {
        std::map<int, std::string> map;
        // O(log n)查找时间，但保持有序
    }
    
    // 频繁插入删除：使用list
    void frequentInsertDelete() {
        std::list<int> list;
        // O(1)插入删除时间
    }
    
    // 双端操作：使用deque
    void doubleEndedOperations() {
        std::deque<int> deque;
        // O(1)双端插入删除
    }
};
```

### 自定义分配器
```cpp
#include <memory>

template<typename T>
class FastAllocator {
private:
    static constexpr size_t BLOCK_SIZE = 1024;
    struct Block {
        alignas(T) char data[BLOCK_SIZE * sizeof(T)];
        size_t used;
    };
    
    std::vector<std::unique_ptr<Block>> blocks;
    
public:
    using value_type = T;
    
    T* allocate(size_t n) {
        if (n > BLOCK_SIZE) {
            return static_cast<T*>(::operator new(n * sizeof(T)));
        }
        
        // 查找可用块
        for (auto& block : blocks) {
            if (block->used + n <= BLOCK_SIZE) {
                T* ptr = reinterpret_cast<T*>(block->data + block->used * sizeof(T));
                block->used += n;
                return ptr;
            }
        }
        
        // 创建新块
        auto newBlock = std::make_unique<Block>();
        newBlock->used = n;
        T* ptr = reinterpret_cast<T*>(newBlock->data);
        blocks.push_back(std::move(newBlock));
        return ptr;
    }
    
    void deallocate(T* ptr, size_t n) {
        // 简单实现：不实际释放
        // 实际应用中需要更复杂的逻辑
    }
};
```

## 并行优化

### OpenMP并行
```cpp
#include <omp.h>

class ParallelOptimization {
public:
    // 并行循环
    void parallelLoop(std::vector<int>& data) {
        #pragma omp parallel for
        for (size_t i = 0; i < data.size(); ++i) {
            data[i] *= 2;
        }
    }
    
    // 并行归约
    int parallelSum(const std::vector<int>& data) {
        int sum = 0;
        #pragma omp parallel for reduction(+:sum)
        for (size_t i = 0; i < data.size(); ++i) {
            sum += data[i];
        }
        return sum;
    }
    
    // 并行矩阵乘法
    void parallelMatrixMultiply(const std::vector<std::vector<double>>& A,
                               const std::vector<std::vector<double>>& B,
                               std::vector<std::vector<double>>& C) {
        size_t n = A.size();
        
        #pragma omp parallel for
        for (size_t i = 0; i < n; ++i) {
            for (size_t j = 0; j < n; ++j) {
                C[i][j] = 0.0;
                for (size_t k = 0; k < n; ++k) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
    }
};
```

### SIMD优化
```cpp
#include <immintrin.h>

class SIMDOptimization {
public:
    // 使用AVX2进行向量化
    void vectorizedAdd(const float* a, const float* b, float* result, size_t n) {
        size_t i = 0;
        
        // 处理8个float的向量
        for (; i + 8 <= n; i += 8) {
            __m256 va = _mm256_load_ps(&a[i]);
            __m256 vb = _mm256_load_ps(&b[i]);
            __m256 vresult = _mm256_add_ps(va, vb);
            _mm256_store_ps(&result[i], vresult);
        }
        
        // 处理剩余元素
        for (; i < n; ++i) {
            result[i] = a[i] + b[i];
        }
    }
    
    // 使用SSE进行向量化
    void sseVectorizedMultiply(const float* a, const float* b, float* result, size_t n) {
        size_t i = 0;
        
        // 处理4个float的向量
        for (; i + 4 <= n; i += 4) {
            __m128 va = _mm_load_ps(&a[i]);
            __m128 vb = _mm_load_ps(&b[i]);
            __m128 vresult = _mm_mul_ps(va, vb);
            _mm_store_ps(&result[i], vresult);
        }
        
        // 处理剩余元素
        for (; i < n; ++i) {
            result[i] = a[i] * b[i];
        }
    }
};
```

## 性能分析工具

### 基准测试
```cpp
#include <chrono>
#include <iostream>

class Benchmark {
public:
    template<typename Func>
    static double measureTime(Func&& func) {
        auto start = std::chrono::high_resolution_clock::now();
        func();
        auto end = std::chrono::high_resolution_clock::now();
        
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        return duration.count() / 1000.0;  // 返回毫秒
    }
    
    template<typename Func>
    static void comparePerformance(const std::string& name1, Func&& func1,
                                  const std::string& name2, Func&& func2,
                                  int iterations = 1000) {
        double time1 = 0, time2 = 0;
        
        for (int i = 0; i < iterations; ++i) {
            time1 += measureTime(func1);
            time2 += measureTime(func2);
        }
        
        time1 /= iterations;
        time2 /= iterations;
        
        std::cout << name1 << ": " << time1 << " ms" << std::endl;
        std::cout << name2 << ": " << time2 << " ms" << std::endl;
        std::cout << "Speedup: " << time1 / time2 << "x" << std::endl;
    }
};
```

### 性能计数器
```cpp
#include <chrono>
#include <map>
#include <string>

class PerformanceCounter {
private:
    std::map<std::string, double> counters;
    std::map<std::string, std::chrono::high_resolution_clock::time_point> timers;
    
public:
    void startTimer(const std::string& name) {
        timers[name] = std::chrono::high_resolution_clock::now();
    }
    
    void endTimer(const std::string& name) {
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(
            end - timers[name]).count();
        counters[name] = duration / 1000.0;  // 毫秒
    }
    
    void addCounter(const std::string& name, double value) {
        counters[name] += value;
    }
    
    void printReport() {
        std::cout << "Performance Report:" << std::endl;
        for (const auto& pair : counters) {
            std::cout << pair.first << ": " << pair.second << " ms" << std::endl;
        }
    }
};
```

## CPU缓存优化

### 缓存局部性原理

现代CPU有多级缓存（L1/L2/L3），访问延迟差异巨大：
- L1缓存：~1ns
- L2缓存：~3ns
- L3缓存：~10ns
- 主内存：~100ns

**优化目标：提高缓存命中率**

### 空间局部性优化

```cpp
// ❌ 缓存不友好：结构体数组（AoS）
struct Particle {
    float x, y, z;     // 位置
    float vx, vy, vz;  // 速度
    float r, g, b;     // 颜色
};

Particle particles[10000];

void updatePosition() {
    for (int i = 0; i < 10000; ++i) {
        particles[i].x += particles[i].vx;  // 加载整个struct，浪费缓存
        particles[i].y += particles[i].vy;
        particles[i].z += particles[i].vz;
    }
}

// ✅ 缓存友好：数组结构体（SoA）
struct Particles {
    float x[10000], y[10000], z[10000];      // 位置
    float vx[10000], vy[10000], vz[10000];   // 速度
    float r[10000], g[10000], b[10000];      // 颜色
};

Particles particles;

void updatePosition() {
    for (int i = 0; i < 10000; ++i) {
        particles.x[i] += particles.vx[i];  // 连续访问，缓存友好
        particles.y[i] += particles.vy[i];
        particles.z[i] += particles.vz[i];
    }
}
```

### 时间局部性优化

```cpp
// ❌ 缓存不友好：列优先访问
int matrix[1000][1000];

void sumColumns() {
    for (int col = 0; col < 1000; ++col) {
        for (int row = 0; row < 1000; ++row) {
            sum += matrix[row][col];  // 跳跃访问，缓存miss
        }
    }
}

// ✅ 缓存友好：行优先访问
void sumRows() {
    for (int row = 0; row < 1000; ++row) {
        for (int col = 0; col < 1000; ++col) {
            sum += matrix[row][col];  // 连续访问，缓存命中
        }
    }
}

// 性能差异：可达10倍以上！
```

### 数据对齐优化

```cpp
// ❌ 未对齐：跨缓存行
struct Unaligned {
    char c;      // 1字节
    int i;       // 4字节，可能跨缓存行
    double d;    // 8字节
};  // 可能24字节（填充）

// ✅ 对齐优化
struct Aligned {
    double d;    // 8字节（对齐到8）
    int i;       // 4字节
    char c;      // 1字节
};  // 16字节

// ✅ 缓存行对齐（避免伪共享）
struct alignas(64) CacheLine {  // 64字节对齐（典型缓存行大小）
    std::atomic<int> counter;
    char padding[60];  // 填充到64字节
};

// 多线程场景：不同线程的数据分布在不同缓存行
CacheLine counters[8];  // 8个线程，避免伪共享
```

## 分支预测优化

### 分支预测原理

现代CPU使用分支预测器猜测分支走向，预测错误导致流水线清空（~10-20周期损失）。

```cpp
// ❌ 难预测的分支
void process(std::vector<int>& data) {
    for (int x : data) {
        if (x % 2 == 0) {  // 50/50概率，难预测
            // ...
        } else {
            // ...
        }
    }
}

// ✅ 优化1：排序后分支可预测
void process(std::vector<int>& data) {
    std::sort(data.begin(), data.end());  // 先排序
    
    for (int x : data) {
        if (x < threshold) {  // 连续true或false，易预测
            // ...
        } else {
            // ...
        }
    }
}

// ✅ 优化2：branchless编程
int max(int a, int b) {
    // 传统：if (a > b) return a; else return b;
    return a > b ? a : b;  // 可能编译为branchless代码
}

int abs(int x) {
    // 传统：if (x < 0) return -x; else return x;
    int mask = x >> 31;  // branchless
    return (x + mask) ^ mask;
}

// ✅ 优化3：likely/unlikely提示（GCC）
void process(int x) {
    if (__builtin_expect(x > 0, 1)) {  // 提示通常为真
        // 热路径
    } else {
        // 冷路径
    }
}
```

### 性能对比

```cpp
// 测试：100万随机数求和（偶数乘2）
// 未排序：~15ms（分支预测失败50%）
// 已排序：~5ms （分支预测成功100%）
// Branchless：~3ms（无分支）
```

**优化建议：**
1. **避免随机分支**：预处理数据，使分支可预测
2. **热路径优先**：常执行的分支放在if而非else
3. **消除短循环分支**：循环展开或branchless
4. **Profile指导**：用perf查看分支预测失败率