基于Strassen算法的2的幂次矩阵乘法代码性能优化咨询

针对你当前的Strassen实现，以下是几个关键的性能优化方向，结合代码调整建议：

1. 消除频繁动态内存分配，复用临时缓冲区 #

当前代码中add/sub函数每次调用都会malloc新数组，递归过程中还会大量分配矩阵块内存，内存分配与释放的开销极大。改为传入预先分配的结果缓冲区，避免重复分配：

// 修改add为无返回值，直接写入传入的res缓冲区
void add(int n, int* m1, int* m2, int* res) {
    for (int i = 0; i < n * n; i++) {
        res[i] = m1[i] + m2[i];
    }
}

// sub函数同理修改
void sub(int n, int* m1, int* m2, int* res) {
    for (int i = 0; i < n * n; i++) {
        res[i] = m1[i] - m2[i];
    }
}

递归时预先分配足够的临时缓冲区（比如在顶层调用时一次性分配所有需要的临时块），或者在递归函数中复用内存，避免每层递归都malloc。同时注意及时释放内存，原代码存在大量内存泄漏，会导致内存碎片和性能下降，比如递归中分配的A/B/p1-p7等，在拷贝完结果后必须free。

2. 优化矩阵分块的拷贝效率 #

原代码用嵌套循环逐个拷贝矩阵块元素，效率极低。利用memcpy批量拷贝连续行数据（行优先存储下，单行为连续内存）：

// 替换原矩阵分块的嵌套循环
int* src_A = m1;
int* dst_A = A;
for (int i = 0; i < n; i++) {
    memcpy(dst_A, src_A, n * sizeof(int));
    src_A += 2 * n; // 跳到大矩阵下一行的开头
    dst_A += n;
}
// B/C/D/E/F/G/H块同理批量拷贝

3. 进一步提升basefmm的缓存友好性 #

当前basefmm已经做了列转存，但还可以通过阻塞分块（Tiling）和循环展开提升缓存命中率：

void basefmm(int n, int* m1, int* m2, int* result, int* col1) {
    const int BLOCK_SIZE = 8; // 根据CPU L1缓存大小调整，比如8/16
    // 预先清零结果矩阵
    memset(result, 0, n * n * sizeof(int));

    for (int j = 0; j < n; j++) {
        // 转存m2的第j列到col1
        for (int k = 0; k < n; k++) {
            col1[k] = m2[k * n + j];
        }

        // 按块处理行和列，利用缓存
        for (int i = 0; i < n; i += BLOCK_SIZE) {
            for (int k = 0; k < n; k += BLOCK_SIZE) {
                for (int ii = i; ii < i + BLOCK_SIZE && ii < n; ii++) {
                    register int sum = 0;
                    int* row_ptr = m1 + ii * n;
                    for (int kk = k; kk < k + BLOCK_SIZE && kk < n; kk++) {
                        sum += row_ptr[kk] * col1[kk];
                    }
                    result[ii * n + j] += sum;
                }
            }
        }
    }
}

使用register关键字提示编译器将sum放入寄存器，减少内存读写；同时调整循环顺序，让内存访问更符合缓存的局部性原则。

4. 调整递归终止阈值 #

当前阈值n < 64并非最优值，需要根据你的CPU缓存大小实际测试调整。比如测试n=32、64、128时的性能，选择让basefmm刚好能填满L1/L2缓存的阈值，能最大化缓存命中率。

5. 启用编译器优化选项 #

编译时开启最高级优化，并针对本地CPU架构优化：

# GCC编译示例
gcc -O3 -march=native your_code.c -o fmm

-O3会触发循环展开、指令调度等优化，-march=native会生成适配你CPU的专属指令，这能带来显著的性能提升。

6. 用SIMD指令加速加减与基础乘法 #

利用CPU的SIMD向量单元（如AVX2、SSE）并行处理多个元素，比如优化add函数：

#include <immintrin.h> // 引入SIMD头文件

void add(int n, int* m1, int* m2, int* res) {
    int i = 0;
    // 用AVX2一次处理8个int
    for (; i <= n * n - 8; i += 8) {
        __m256i vec_m1 = _mm256_loadu_si256((__m256i*)&m1[i]);
        __m256i vec_m2 = _mm256_loadu_si256((__m256i*)&m2[i]);
        __m256i vec_res = _mm256_add_epi32(vec_m1, vec_m2);
        _mm256_storeu_si256((__m256i*)&res[i], vec_res);
    }
    // 处理剩余不足8个的元素
    for (; i < n * n; i++) {
        res[i] = m1[i] + m2[i];
    }
}

Strassen算法包含大量加减操作，SIMD优化能大幅提升这部分的运算速度。

内容的提问来源于stack exchange，提问作者Itay Derazon