C++ 八股文（性能优化）

1. 如何优化 C++ 中的算法复杂度？

1. 选择合适的数据结构： 根据操作频率选择容器，频繁查找用unordered_map时间O(1)而不是map的O(log n)，频繁插入删除用list而不是vector，需要排序用set或priority_queue，空间换时间用哈希表缓存计算结果。

2. 算法优化技巧： 避免嵌套循环降低时间复杂度，使用双指针、滑动窗口减少遍历次数，二分查找将O(n)降到O(log n)，动态规划避免重复计算，分治算法降低复杂度如归并排序。

3. 提前终止和剪枝： 找到结果立即返回不继续遍历，使用短路求值&&和||，循环中使用break减少无效迭代，递归中剪枝避免无效分支，缓存中间结果避免重复计算。

4. 空间时间权衡： 使用额外空间换取时间如哈希表，预计算结果存储查找表，使用位运算优化空间和时间，lazy evaluation延迟计算，批量处理减少函数调用开销。

// 优化前：O(n²)
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        if(arr[i] + arr[j] == target) return true;

// 优化后：O(n)使用哈希表
std::unordered_set<int> seen;
for(int x : arr) {
    if(seen.count(target - x)) return true;
    seen.insert(x);
}

2. C++ 中如何优化循环和内存访问模式？

1. 缓存友好访问： 按行优先顺序访问二维数组利用空间局部性，连续内存访问提高缓存命中率，避免跨步访问stride access，数组优于链表因为内存连续，结构体成员按访问频率排列热数据放一起。

2. 循环优化技巧： 循环不变量外提减少重复计算，循环展开减少分支判断开销，循环融合合并多个循环减少遍历次数，循环交换改变嵌套顺序优化缓存，使用迭代器而不是索引访问。

3. 减少分支预测失败： 避免循环内的条件判断，使用位运算代替if-else，数据排序后处理减少分支，使用查找表代替复杂条件，编译器likely/unlikely提示优化分支。

4. 向量化和并行： 使用SIMD指令并行处理，编译器自动向量化需要满足条件，OpenMP并行化循环，使用std::transform等算法库，避免循环依赖使能并行。

// 缓存不友好：按列访问
for(int j = 0; j < cols; j++)
    for(int i = 0; i < rows; i++)
        sum += matrix[i][j];

// 缓存友好：按行访问
for(int i = 0; i < rows; i++)
    for(int j = 0; j < cols; j++)
        sum += matrix[i][j];

// 循环展开
for(int i = 0; i < n; i += 4) {
    sum += arr[i] + arr[i+1] + arr[i+2] + arr[i+3];
}

3. 如何使用缓存优化提高 C++ 程序性能？

1. 缓存层次理解： L1缓存最快但最小约32KB，L2缓存较大约256KB，L3缓存更大约8MB但较慢，主内存最慢，缓存行通常64字节，理解缓存工作原理才能有效优化。

2. 数据局部性优化： 时间局部性短时间内重复访问同一数据，空间局部性访问相邻地址的数据，数组优于链表因为连续存储，结构体数组SoA优于数组结构体AoS提高向量化，热数据集中存储冷数据分离。

3. 避免false sharing： 多线程访问不同变量但在同一缓存行导致缓存失效，使用alignas(64)对齐到缓存行，在结构体中添加padding分隔热数据，使用thread_local避免共享，每个线程独立的数据结构。

4. 预取和预分配： 使用__builtin_prefetch预取数据到缓存，容器使用reserve预分配避免重新分配，批量处理数据提高缓存利用率，循环分块tiling优化缓存使用，减少工作集大小适应缓存。

// 避免false sharing
struct alignas(64) ThreadData {  // 缓存行对齐
    int counter;
    char padding[60];  // 填充到64字节
};

// 循环分块优化缓存
const int BLOCK = 64;
for(int ii = 0; ii < n; ii += BLOCK)
    for(int jj = 0; jj < n; jj += BLOCK)
        for(int i = ii; i < ii+BLOCK; i++)
            for(int j = jj; j < jj+BLOCK; j++)
                C[i][j] += A[i][j] * B[i][j];

4. C++ 中如何避免不必要的内存拷贝？

1. 使用移动语义： 返回值使用std::move转移所有权，函数参数使用右值引用接收临时对象，容器插入使用emplace_back而不是push_back，std::move转移大对象避免拷贝，移动构造和移动赋值声明noexcept。

2. 引用传递： 函数参数使用const引用传递大对象，返回引用而不是值避免拷贝，使用std::ref包装引用传递给线程或bind，注意引用生命周期避免悬空引用，小对象按值传递大对象按引用。

3. 原地构造： 使用emplace系列函数原地构造对象，避免先构造再拷贝的两步操作，容器使用reserve预分配避免扩容拷贝，使用placement new在指定位置构造，std::optional和std::variant原地构造。

4. 返回值优化： 编译器RVO返回值优化自动消除拷贝，NRVO命名返回值优化，返回局部对象不要使用std::move阻止RVO，C++17保证拷贝消除，返回大对象时信任编译器优化。

// 避免拷贝：使用移动
std::vector<int> create() {
    std::vector<int> v(1000);
    return v;  // RVO或移动，不拷贝
}

// 避免拷贝：引用传递
void process(const std::string& str) {}  // 不拷贝

// 避免拷贝：原地构造
vec.emplace_back(arg1, arg2);  // 直接构造
vec.push_back(Object(arg1, arg2));  // 先构造再拷贝

5. C++ 中如何提高程序的执行效率？

1. 编译器优化： 使用-O2或-O3优化级别，启用LTO链接时优化，使用PGO配置文件引导优化，选择合适的目标架构-march=native，使用-ffast-math优化浮点运算但可能影响精度。

2. 算法和数据结构： 选择时间复杂度更低的算法，使用合适的容器如unordered_map而不是map，预分配内存避免动态扩容，使用内存池减少分配开销，缓存计算结果避免重复计算。

3. 减少函数调用开销： 小函数使用inline内联，虚函数调用有开销考虑模板或CRTP，减少间接调用如函数指针，批量处理减少调用次数，lambda可能被内联优于函数指针。

4. 并行和异步： 使用多线程并行处理独立任务，使用线程池避免频繁创建销毁线程，异步IO避免阻塞等待，使用std::async或future处理异步任务，SIMD并行处理数据。

// 编译优化
// g++ -O3 -march=native -flto program.cpp

// 预分配避免扩容
std::vector<int> vec;
vec.reserve(1000);  // 预分配

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

// 并行处理
#pragma omp parallel for
for(int i = 0; i < n; i++) {
    process(data[i]);
}

6. 如何优化 C++ 程序中的 I/O 性能？

1. 缓冲区优化： 使用缓冲IO而不是无缓冲，增大缓冲区大小减少系统调用，批量读写减少IO次数，使用setvbuf设置缓冲区大小，关闭同步std::ios::sync_with_stdio(false)。

2. 异步IO： 使用异步IO避免阻塞等待，std::async异步读写文件，使用future获取结果，IO操作和计算重叠提高效率，使用io_uring或IOCP高性能异步IO。

3. 内存映射文件： 使用mmap将文件映射到内存，避免read/write系统调用，操作系统自动管理缓存，适合大文件随机访问，注意内存映射的开销和限制。

4. 格式化IO优化： 避免使用iostream的格式化输出，使用printf/scanf更快，使用二进制IO而不是文本，避免频繁flush刷新缓冲区，使用'\n'而不是std::endl避免flush。

// 关闭同步提速
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

// 批量读写
char buffer[8192];
while(file.read(buffer, sizeof(buffer))) {
    process(buffer, file.gcount());
}

// 使用'\n'而不是endl
std::cout << "data\n";  // 快
std::cout << "data" << std::endl;  // 慢，会flush

// 二进制IO
file.write(reinterpret_cast<char*>(&data), sizeof(data));

7. C++ 中的循环展开（Loop Unrolling）是什么？

1. 基本概念： 循环展开是将循环体复制多次减少循环控制开销，减少分支预测失败，增加指令级并行性，编译器可以自动展开或手动展开，适度展开提高性能过度展开增加代码体积。

2. 优势： 减少循环计数和条件判断次数，减少分支预测失败的惩罚，增加指令级并行ILP，更好的寄存器利用，编译器有更多优化机会如指令重排。

3. 实现方式： 手动展开复制循环体，编译器自动展开使用-funroll-loops，部分展开处理剩余元素，使用#pragma unroll提示编译器，模板元编程编译期展开。

4. 注意事项： 过度展开增加代码体积降低缓存效率，需要处理循环次数不是展开因子倍数的情况，对于小循环效果明显大循环可能适得其反，现代编译器通常能自动优化。

// 未展开
for(int i = 0; i < n; i++) {
    sum += arr[i];
}

// 手动展开4次
for(int i = 0; i < n; i += 4) {
    sum += arr[i] + arr[i+1] + arr[i+2] + arr[i+3];
}
// 处理剩余元素
for(int i = n - n%4; i < n; i++) {
    sum += arr[i];
}

// 编译器提示
#pragma unroll(4)
for(int i = 0; i < n; i++) {
    sum += arr[i];
}

8. C++ 中的内联函数（inline）如何优化性能？

1. 基本概念： inline建议编译器将函数调用替换为函数体，消除函数调用开销如参数传递和返回，适合小函数频繁调用的场景，编译器可以忽略inline建议，现代编译器会自动内联。

2. 优势： 消除函数调用开销节省栈操作，避免跳转指令提高指令缓存命中率，编译器可以跨函数优化如常量折叠，减少寄存器保存恢复，对于小函数性能提升明显。

3. 使用场景： 简单的getter/setter函数，数学运算函数如加减乘除，频繁调用的小函数，模板函数通常内联，lambda表达式通常被内联，头文件中的函数定义。

4. 注意事项： 过度内联增加代码体积降低缓存效率，递归函数不能完全内联，虚函数通常不能内联除非去虚化，inline只是建议编译器可以忽略，现代编译器优化通常比手动inline更好。

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

// 类内定义自动内联
class Point {
    int x, y;
public:
    int getX() const { return x; }  // 自动内联
};

// 强制内联（编译器特定）
__attribute__((always_inline)) inline void func() {}

// lambda通常被内联
auto add = [](int a, int b) { return a + b; };

9. C++ 中的 SIMD（单指令多数据）优化如何实现？

1. 基本概念： SIMD一条指令同时处理多个数据，现代CPU支持SSE、AVX、AVX512等指令集，一次处理4/8/16个数据元素，适合数据并行计算如向量运算图像处理，性能提升可达4-16倍。

2. 实现方式： 编译器自动向量化使用-O3 -march=native，使用intrinsics函数如_mm_add_ps，使用SIMD库如Eigen、xsimd，OpenMP SIMD指令#pragma omp simd，手写汇编但不推荐。

3. 自动向量化条件： 循环次数已知或可推导，循环体无依赖关系，内存访问连续对齐，无函数调用或可内联，无复杂控制流，使用restrict关键字提示无别名。

4. 使用技巧： 数据对齐到16/32字节边界，使用SoA而不是AoS提高向量化，避免循环依赖，批量处理数据，使用编译器报告查看向量化情况-fopt-info-vec。

// 自动向量化
void add_arrays(float* a, float* b, float* c, int n) {
    #pragma omp simd
    for(int i = 0; i < n; i++) {
        c[i] = a[i] + b[i];  // 编译器自动向量化
    }
}

// 使用intrinsics
#include <immintrin.h>
void add_avx(float* a, float* b, float* c, int n) {
    for(int i = 0; i < n; i += 8) {
        __m256 va = _mm256_load_ps(&a[i]);
        __m256 vb = _mm256_load_ps(&b[i]);
        __m256 vc = _mm256_add_ps(va, vb);
        _mm256_store_ps(&c[i], vc);
    }
}

// 数据对齐
alignas(32) float data[1024];

10. C++ 中的线程开销如何优化？

1. 减少线程创建销毁： 使用线程池复用线程避免频繁创建销毁，预创建固定数量的工作线程，任务队列分发任务给线程池，线程创建销毁开销大约几微秒到毫秒。

2. 减少同步开销： 减少锁的使用粒度和持有时间，使用无锁数据结构如原子操作，读写锁允许多个读者并发，使用thread_local避免共享数据，批量处理减少同步次数。

3. 避免false sharing： 不同线程访问的数据对齐到不同缓存行，使用alignas(64)对齐，添加padding分隔热数据，每个线程独立的数据结构，减少缓存一致性协议开销。

4. 任务粒度优化： 任务太小线程开销大于计算，任务太大负载不均衡，动态调整任务粒度，使用work stealing平衡负载，考虑线程数量与CPU核心数匹配。