4、算法优化策略：减少计算量

说到算子性能优化，我最先想聊的就是算法层面的优化。为什么？因为这是性价比最高的手段。你想想看，硬件加速、指令集优化这些固然重要，但如果算法本身就有冗余计算，那再怎么优化底层也是事倍功半。

我个人习惯是，拿到一个算子先不急着写代码。先问自己三个问题：这个计算能不能省？能不能合并？能不能分块？这三个问题对应了今天要讲的三个核心策略。

4.1 算法降复杂度：从根源上砍掉冗余

说白了，就是让计算机少干活。我见过太多人一上来就写O(n²)的算法，其实稍微动动脑子就能降到O(n log n)甚至O(n)。

举个实际例子：矩阵乘法中的对称性利用。

假设我们要计算一个对称矩阵A与向量x的乘积。常规做法是直接算，复杂度O(n²)。但A是对称的，A[i][j] = A[j][i]。这意味着有一半的元素是重复的。

// 常规做法：O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        y[i] += A[i][j] * x[j];
    }
}

// 优化后：利用对称性，减少一半乘法
for (int i = 0; i < n; i++) {
    y[i] = A[i][i] * x[i];  // 对角线
    for (int j = i + 1; j < n; j++) {
        float tmp = A[i][j] * x[j];
        y[i] += tmp;
        y[j] += tmp;  // 一次计算，两次使用
    }
}

另一个常见场景：卷积运算中的im2col优化。传统卷积需要多层循环，但通过将输入图像展开成矩阵，就可以用高效的矩阵乘法库（如cuBLAS）来加速。这本质上是用空间换时间，但计算量确实降了。

4.2 算子融合：把多个小操作合并成一个

算子融合，英文叫Kernel Fusion。这个概念在深度学习框架里特别常见。为什么要融合？因为每次启动一个kernel都有开销——显存分配、数据传输、kernel launch延迟。把这些开销省掉，性能自然就上去了。

我举个例子：一个典型的卷积+批归一化+ReLU激活函数。

如果不融合，流程是这样的：

1. 启动卷积kernel，计算结果写入显存
2. 启动批归一化kernel，读取卷积结果，写入归一化结果
3. 启动ReLU kernel，读取归一化结果，写入最终结果

三次kernel启动，三次显存读写。如果融合成一个kernel：

// 融合后的伪代码
__global__ void fused_conv_bn_relu(...) {
    // 计算卷积
    float conv_out = convolution_pixel(...);
    // 计算批归一化
    float bn_out = (conv_out - mean) / sqrt(var + eps) * gamma + beta;
    // 计算ReLU
    float relu_out = max(0.0f, bn_out);
    // 直接写回
    output[idx] = relu_out;
}

我在项目中遇到过这样一个场景：一个模型有30多个小算子，逐个执行需要12毫秒。我把其中连续的5个算子融合成一个，时间直接降到了7毫秒。你想想看，这还只是融合了一组。

4.3 循环展开与分块：让数据待在缓存里

循环展开和分块，这两个技术经常一起用。它们的核心思想是一样的：提高数据局部性，减少缓存缺失。

先说说循环展开。说白了，就是减少循环控制的开销，同时给编译器更多优化空间。

// 未展开
for (int i = 0; i < 100; i++) {
    a[i] = b[i] + c[i];
}

// 展开4次
for (int i = 0; i < 100; i += 4) {
    a[i]   = b[i]   + c[i];
    a[i+1] = b[i+1] + c[i+1];
    a[i+2] = b[i+2] + c[i+2];
    a[i+3] = b[i+3] + c[i+3];
}

展开后，循环次数从100次减少到25次。每次循环可以同时处理4个元素，指令级并行度提高了。编译器也更容易做向量化。

再来说说分块。这个在矩阵运算中特别重要。为什么？因为矩阵通常很大，放不进缓存。如果不分块，每次访问下一行数据时，上一行的数据可能已经被踢出缓存了。

// 矩阵乘法分块：让子块驻留在L1缓存中
#define BLOCK_SIZE 32

void matmul_tiled(float *A, float *B, float *C, int N) {
    for (int i = 0; i < N; i += BLOCK_SIZE) {
        for (int j = 0; j < N; j += BLOCK_SIZE) {
            for (int k = 0; k < N; k += BLOCK_SIZE) {
                // 计算子块 C[i:i+BS][j:j+BS] += A[i:i+BS][k:k+BS] * B[k:k+BS][j:j+BS]
                for (int ii = i; ii < i + BLOCK_SIZE; ii++) {
                    for (int jj = j; jj < j + BLOCK_SIZE; jj++) {
                        float sum = 0;
                        for (int kk = k; kk < k + BLOCK_SIZE; kk++) {
                            sum += A[ii * N + kk] * B[kk * N + jj];
                        }
                        C[ii * N + jj] += sum;
                    }
                }
            }
        }
    }
}

你可能会问：分块和循环展开，哪个更重要？我的答案是：都重要，但分块往往能带来更大的收益。因为缓存缺失的代价远大于循环控制的开销。我见过一个矩阵乘法，不分块时缓存缺失率高达80%，分块后降到了5%以下。性能提升了近10倍。

知识体系总览

下面这张图总结了今天讲的三个策略，以及它们之间的关系：

这三个策略不是孤立的。实际项目中，我经常把它们组合使用。比如先做算子融合减少kernel启动次数，再对融合后的kernel做分块优化提高缓存命中率，最后在分块内部做循环展开。每一步都能带来可观的收益。

好了，这一章的内容就到这里。记住一句话：最好的优化，是让计算机少干活。下一章我们会聊具体怎么用工具来定位性能瓶颈，到时候再细聊。

想要更多资料，联系可可