编程测量CPU缓存相联性：现有C方案无结果，求正确实现方法

算力阿峰

2026-5-20

分析你的缓存相联性测试方案&正确实现方法

Hey there! Let's walk through your problem step by step—first, I'll point out where your current approach might be falling short, then break down the correct way to test L1 cache associativity, and even share a working code example.

先纠正一个小计算错误

你提到L1缓存32KB、行大小64字节，算出共有500行，这里其实算错啦：
32KB = 32 * 1024 = 32768字节，32768 / 64 = 512行，这个数字很重要，后续测试逻辑都基于它。

你的现有方案为什么没效果？

核心问题在于：你用的是刚好等于L1缓存大小的数组（8192个int，每个4字节，8192*4=32768字节）。当整个数组都能完全放进L1缓存时，不管你怎么迭代访问，缓存命中率都会接近100%，根本不会出现因为缓存冲突导致的耗时突变——自然看不到你预期的“每x次迭代耗时变长”的现象。

要测试相联性，我们需要主动制造缓存冲突不命中：当多个内存地址映射到同一个缓存组，且数量超过该组的可用缓存行数（也就是相联性）时，就会频繁挤出旧缓存行，被迫从内存加载数据，耗时会显著上升。

正确的测试思路

组相联缓存的核心逻辑是：内存地址被分成三部分：

偏移位：对应缓存行内的位置（64字节=2^6，所以6位）
组索引位：决定该地址映射到哪个缓存组（组数=总行数/相联性，比如8路相联的话，组数=512/8=64，对应6位）
标记位：用于区分同一组内不同的缓存行

我们的测试方法是：

创建多个数组（或一个足够大的数组），让这些数组的对应元素都映射到同一个缓存组
依次访问这些数组的元素，当访问的元素数量超过相联性时，就会触发冲突不命中，耗时骤增
通过观察耗时突变的临界点，就能确定相联性数值

实现代码示例

下面是一个简化的C语言实现，用rdtsc指令做高精度计时，注意要禁用编译器优化（编译时加-O0）：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <errno.h>

#define L1_SIZE 32768          // 32KB L1缓存
#define CACHE_LINE_SIZE 64     // 64字节缓存行
#define NUM_TESTS 16           // 测试1到16路相联
#define ARRAY_SIZE (L1_SIZE / sizeof(int))
#define REPEAT_COUNT 100       // 重复测试次数取平均

// 高精度计时函数，用rdtsc读取CPU周期
static inline uint64_t rdtsc() {
    uint32_t lo, hi;
    __asm__ volatile ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | lo;
}

int main() {
    // 分配NUM_TEST个数组，每个数组对齐到缓存行
    int **arrays = malloc(NUM_TESTS * sizeof(int*));
    if (!arrays) {
        perror("malloc failed");
        return 1;
    }
    for (int i = 0; i < NUM_TESTS; i++) {
        if (posix_memalign((void**)&arrays[i], CACHE_LINE_SIZE, ARRAY_SIZE * sizeof(int)) != 0) {
            perror("posix_memalign failed");
            return 1;
        }
        // 初始化数组，避免页错误
        for (int j = 0; j < ARRAY_SIZE; j++) {
            arrays[i][j] = j;
        }
    }

    // 预热缓存
    for (int i = 0; i < NUM_TESTS; i++) {
        for (int j = 0; j < ARRAY_SIZE; j++) {
            volatile int tmp = arrays[i][j];
        }
    }

    printf("Testing associativity from 1 to %d (average over %d repeats):\n", NUM_TESTS, REPEAT_COUNT);
    for (int k = 1; k <= NUM_TESTS; k++) {
        uint64_t total_cycles = 0;
        for (int r = 0; r < REPEAT_COUNT; r++) {
            uint64_t start = rdtsc();
            // 循环访问k个数组的对应元素，制造缓存冲突
            for (int j = 0; j < ARRAY_SIZE; j++) {
                for (int i = 0; i < k; i++) {
                    volatile int tmp = arrays[i][j];
                }
            }
            uint64_t end = rdtsc();
            total_cycles += (end - start);
        }
        uint64_t avg_cycles = total_cycles / (ARRAY_SIZE * k * REPEAT_COUNT);
        printf(" %d-way: %lu cycles per access\n", k, avg_cycles);
    }

    // 释放内存
    for (int i = 0; i < NUM_TESTS; i++) {
        free(arrays[i]);
    }
    free(arrays);
    return 0;
}

关键注意事项

禁用编译器优化：如果用-O2或更高优化，编译器会把无意义的访问循环优化掉，导致计时完全不准
缓存预热：第一次访问数组会触发页错误，预热后才能得到真实的缓存访问时间
内存屏障：用volatile关键字防止编译器优化掉对数组的访问，确保每次访问都真实执行
多次测试取平均：增加重复测试次数，减少CPU波动带来的计时误差

关于你提到的相关论文

这类缓存微基准测试的核心思路大多都是通过制造冲突不命中来探测缓存参数，和上面的方法一致。比如经典的缓存测试论文都会用到类似的“冲突数组”策略，你可以对照论文里的细节调整测试逻辑（比如优化计时方式、增加不同访问模式的测试等）。

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

编程测量CPU缓存相联性：现有C方案无结果，求正确实现方法

先纠正一个小计算错误 #

你的现有方案为什么没效果？ #

正确的测试思路 #

实现代码示例 #

关键注意事项 #