Cache Blocking优化技术咨询：特定三重循环代码的缓存分块作用

先明确：缓存分块的核心逻辑就是让CPU尽可能复用缓存里的数据，少去碰慢得要死的主存——毕竟CPU访问L1缓存的速度比主存快几十上百倍，频繁缓存失效（Cache Miss）会直接把性能拖垮。

先看你给的这段代码（补了语法细节）：

void func(double *array, double *array2) {
    for(int i = 0; i < 1000; i++){
        for(int j = 0; j < 1000; j++){
            for(int k = 0; k < 1000; k++){
                int index = (i*10) + (20*j) + k; 
                array[index] = compute(array2[index]);
            }
        }
    }
}

原代码的内存访问问题 #

计算index时，k从0到999的过程中索引是连续递增的（每次+1），此时array2[index]和array[index]属于连续内存访问，缓存能直接命中，这部分没问题。
但当j加1时，索引会直接跳变20（20*(j+1) - 20*j = 20）；i加1时跳变10。问题在于：如果缓存块大小（比如常见的64字节，仅能放下8个double）覆盖不了20个double的间隔，那每次切换j循环时，下一组k循环要访问的内存根本不在缓存里，必须从主存重新加载——这就是缓存失效，次数多了性能会直接崩盘。

缓存分块怎么解决这个问题？ #

核心是把大循环拆成小的「块（Block）」，让每个块内的所有内存访问都落在缓存的有效覆盖范围内，尽量复用缓存里的数据。

具体到这段代码，可以这么操作：

1. 对j循环分块：把j的1000次循环拆成每次处理B个j（B的大小看缓存规格，比如L1缓存是32KB的话，选16或32都合适）。处理一个j块时，对应的20*j +k范围的内存会被一次性加载到缓存，后续k循环和小范围的i循环访问都能直接用缓存，不用再频繁读写主存。
2. 对i循环分块：同理，把i的大循环也拆成小块，确保i块内的i*10偏移对应的内存区域也能被缓存覆盖，进一步减少跨块时的缓存失效。

给你个简化的分块实现例子：

#define BLOCK_SIZE 16  // 根据实际缓存大小调整，比如L1是32KB就选32

void func_blocked(double *array, double *array2) {
    for(int i_block = 0; i_block < 1000; i_block += BLOCK_SIZE){
        for(int j_block = 0; j_block < 1000; j_block += BLOCK_SIZE){
            // 处理当前i块和j块内的所有元素
            for(int i = i_block; i < i_block + BLOCK_SIZE && i <1000; i++){
                for(int j = j_block; j < j_block + BLOCK_SIZE && j <1000; j++){
                    for(int k = 0; k <1000; k++){
                        int index = (i*10) + (20*j) +k;
                        array[index] = compute(array2[index]);
                    }
                }
            }
        }
    }
}

最终效果 #

• 每个块内的内存访问集中在一个小区域，缓存能一次性加载所有需要的数据，后续循环全程用缓存，缓存命中率暴增。
• 大幅减少主存和缓存之间的数据传输次数，CPU不用再等慢内存——尤其是当compute函数不算特别耗时的时候，内存访问的开销会成为性能瓶颈，缓存分块能把性能提好几倍。

顺便说一句：虽然这段代码不是矩阵乘法，但缓存分块的核心和矩阵乘法里完全一致——都是优化内存访问的局部性，让缓存物尽其用，只是分块的维度和块大小要适配你的索引计算规则而已。

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