C++ 硬件缓存预取：`__builtin_prefetch` 优化内存访问模式

好的，各位观众老爷，欢迎来到今天的“C++硬件缓存预取：让CPU跑得更快一点点”特别节目！今天我们不聊八卦，不谈人生，就聊聊怎么让我们的C++代码在硬件层面更高效地运行。

前言：CPU和内存的小秘密

在我们深入__builtin_prefetch这个神奇的指令之前，先来回顾一下CPU和内存之间不得不说的故事。各位都知道，CPU运算速度飞快，而内存访问速度相对较慢。为了弥补这个速度差距，现代CPU引入了缓存（Cache）。

想象一下，你是个图书馆管理员（CPU），书架（内存）离你的办公桌（CPU核心）很远。每次你要借一本书（数据），都得跑很远去书架取，效率太低了！于是，你在办公桌旁边放了一个小书架（Cache），把你经常借的书放在上面。这样，大部分时候你都不用跑远路了。

缓存的原理就是这样：CPU会把一部分内存数据复制到速度更快的缓存中。当CPU需要数据时，首先查找缓存，如果找到了（Cache Hit），就直接读取；如果没找到（Cache Miss），就从内存中读取，并把读取到的数据复制到缓存中。

硬件缓存预取：未雨绸缪的策略

缓存虽然好用，但也有局限性。当CPU需要的数据不在缓存中时，就会发生Cache Miss，导致性能下降。硬件缓存预取就是一种试图减少Cache Miss的技术。

简单来说，硬件缓存预取就是CPU自己预测你接下来可能会用到哪些数据，提前把这些数据加载到缓存中。这就像图书馆管理员根据读者的借阅记录，提前把他们可能需要的书籍放到办公桌旁边。

但是，CPU的预测能力是有限的。有时候，它会猜错，把不需要的数据加载到缓存中，反而占用了宝贵的缓存空间。

__builtin_prefetch：程序员的“预言术”

这时候，__builtin_prefetch就派上用场了。__builtin_prefetch是GCC和Clang编译器提供的一个内置函数，允许程序员显式地告诉CPU，哪些数据即将被访问，从而帮助CPU更准确地进行预取。

void __builtin_prefetch (const void *addr, int rw, int locality);

addr: 要预取的内存地址。
rw: 读写模式。0表示只读，1表示可写。
locality: 局部性提示。表示预取的数据在缓存中应该保留多久。
- 0：最低的局部性，表示数据很快就会被丢弃。
- 1：较低的局部性。
- 2：中等的局部性。
- 3：最高的局部性，表示数据会长时间保留在缓存中。

__builtin_prefetch 的用法示例

让我们来看几个__builtin_prefetch的实际应用例子，看看如何用它来优化我们的代码。

1. 线性访问数组

这是最常见的应用场景。当我们线性访问一个数组时，可以提前预取数组中的下一个元素。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> data(1024);
    // 初始化数据
    for (int i = 0; i < data.size(); ++i) {
        data[i] = i;
    }

    // 预取优化后的循环
    for (int i = 0; i < data.size(); ++i) {
        // 预取下一个元素
        if (i + 1 < data.size()) {
            __builtin_prefetch(&data[i + 1], 0, 3); // 0表示只读，3表示高局部性
        }
        // 处理当前元素
        data[i] = data[i] * 2; // 模拟一些计算
    }

    // 验证结果
    for (int i = 0; i < 10; ++i) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，我们在循环中预取了数组的下一个元素。__builtin_prefetch(&data[i + 1], 0, 3)告诉CPU，我们即将访问data[i + 1]，并且希望CPU将它加载到缓存中，并长时间保留。

2. 链表遍历

链表是一种非连续的数据结构，CPU无法像访问数组那样进行有效的硬件预取。这时，__builtin_prefetch就可以发挥作用了。

#include <iostream>

struct Node {
    int data;
    Node* next;
};

int main() {
    // 创建一个链表
    Node* head = new Node{1};
    Node* current = head;
    for (int i = 2; i <= 10; ++i) {
        current->next = new Node{i};
        current = current->next;
    }

    // 预取优化后的链表遍历
    current = head;
    while (current != nullptr) {
        // 预取下一个节点
        if (current->next != nullptr) {
            __builtin_prefetch(current->next, 0, 3);
        }
        // 处理当前节点
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;

    // 释放链表内存 (不要忘记!)
    current = head;
    while(current != nullptr) {
        Node* next = current->next;
        delete current;
        current = next;
    }

    return 0;
}

在这个例子中，我们在遍历链表时，预取了下一个节点。这样可以减少CPU访问内存的次数，提高性能。

3. 多维数组访问

对于多维数组，访问模式可能比较复杂。我们可以根据实际的访问模式，选择合适的预取策略。

#include <iostream>
#include <vector>

int main() {
    // 创建一个二维数组
    int rows = 64;
    int cols = 64;
    std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols));

    // 初始化数据
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            matrix[i][j] = i * cols + j;
        }
    }

    // 预取优化后的循环 (按行访问)
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            // 预取下一个元素 (同行)
            if (j + 1 < cols) {
                __builtin_prefetch(&matrix[i][j + 1], 0, 3);
            }
            // 处理当前元素
            matrix[i][j] = matrix[i][j] * 2;
        }
    }

    // 验证结果 (打印部分元素)
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

在这个例子中，我们按行访问二维数组，并预取了同一行的下一个元素。

__builtin_prefetch 的注意事项

虽然__builtin_prefetch很强大，但也需要谨慎使用。以下是一些注意事项：

不要过度预取： 预取太多的数据可能会占用过多的缓存空间，反而降低性能。
选择合适的局部性提示： 局部性提示会影响数据在缓存中的保留时间。选择不合适的局部性提示可能会导致数据过早或过晚地被丢弃。
__builtin_prefetch只是一个提示： CPU不一定会按照你的提示进行预取。预取是否生效取决于CPU的硬件和当前的系统状态。
性能测试： 使用__builtin_prefetch后，一定要进行性能测试，验证是否 действительно提高了性能。

__builtin_prefetch 的适用场景

__builtin_prefetch最适合以下场景：

数据访问模式可预测： 例如线性访问数组、链表遍历等。
Cache Miss 成为性能瓶颈： 如果你的代码中Cache Miss很多，可以尝试使用__builtin_prefetch来减少Cache Miss。
对性能有极致要求： 例如高性能计算、游戏开发等。

__builtin_prefetch 的局限性

__builtin_prefetch 并非万能的。它也有一些局限性：

增加了代码的复杂度： 使用__builtin_prefetch需要在代码中显式地添加预取指令，增加了代码的复杂度。
可移植性问题： __builtin_prefetch是GCC和Clang的内置函数，可能在其他编译器上不可用。虽然大部分现代编译器都支持，但还是需要注意。
可能降低性能： 如果使用不当，__builtin_prefetch反而会降低性能。

一个更复杂的例子：矩阵乘法

让我们用一个更复杂的例子来演示__builtin_prefetch的用法：矩阵乘法。矩阵乘法是科学计算中常见的操作，对性能要求很高。

#include <iostream>
#include <vector>

void matrix_multiply(const std::vector<std::vector<double>>& A,
                     const std::vector<std::vector<double>>& B,
                     std::vector<std::vector<double>>& C) {
    int rowsA = A.size();
    int colsA = A[0].size();
    int rowsB = B.size();
    int colsB = B[0].size();

    if (colsA != rowsB) {
        std::cerr << "Error: Incompatible matrix dimensions." << std::endl;
        return;
    }

    int rowsC = rowsA;
    int colsC = colsB;

    for (int i = 0; i < rowsC; ++i) {
        for (int j = 0; j < colsC; ++j) {
            double sum = 0.0;
            for (int k = 0; k < colsA; ++k) {
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
}

// 使用预取的矩阵乘法
void matrix_multiply_prefetch(const std::vector<std::vector<double>>& A,
                              const std::vector<std::vector<double>>& B,
                              std::vector<std::vector<double>>& C) {
    int rowsA = A.size();
    int colsA = A[0].size();
    int rowsB = B.size();
    int colsB = B[0].size();

    if (colsA != rowsB) {
        std::cerr << "Error: Incompatible matrix dimensions." << std::endl;
        return;
    }

    int rowsC = rowsA;
    int colsC = colsB;

    for (int i = 0; i < rowsC; ++i) {
        for (int j = 0; j < colsC; ++j) {
            double sum = 0.0;
            for (int k = 0; k < colsA; ++k) {
                // 预取下一个A[i][k+1]和B[k+1][j]
                if(k + 1 < colsA) {
                    __builtin_prefetch(&A[i][k+1], 0, 1); // 预取A
                    __builtin_prefetch(&B[k+1][j], 0, 1); // 预取B
                }
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
}

int main() {
    int size = 64;
    std::vector<std::vector<double>> A(size, std::vector<double>(size, 1.0));
    std::vector<std::vector<double>> B(size, std::vector<double>(size, 2.0));
    std::vector<std::vector<double>> C(size, std::vector<double>(size, 0.0));

    // 测量普通矩阵乘法的时间
    auto start = std::chrono::high_resolution_clock::now();
    matrix_multiply(A, B, C);
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "Normal matrix multiplication time: " << duration.count() << " microseconds" << std::endl;

    // 重新初始化C
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            C[i][j] = 0.0;
        }
    }

    // 测量预取矩阵乘法的时间
    start = std::chrono::high_resolution_clock::now();
    matrix_multiply_prefetch(A, B, C);
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "Prefetch matrix multiplication time: " << duration.count() << " microseconds" << std::endl;

    return 0;
}

在这个例子中，我们在矩阵乘法的内循环中，预取了下一个A[i][k+1]和B[k+1][j]。这可以减少CPU访问内存的次数，提高矩阵乘法的性能。

总结：__builtin_prefetch，用好了是神器，用不好是负担

__builtin_prefetch是一个强大的工具，可以帮助我们优化C++代码，提高性能。但是，它也需要谨慎使用。只有在数据访问模式可预测、Cache Miss成为性能瓶颈的情况下，才能发挥其优势。在使用__builtin_prefetch后，一定要进行性能测试，验证是否确实提高了性能。

最后，记住一句箴言：不要过度优化！过早的优化是万恶之源。只有在确定性能瓶颈后，再考虑使用__builtin_prefetch等高级优化技术。

希望今天的讲座对大家有所帮助！下次再见！

发表回复 取消回复

发表回复取消回复