缓存读/缺失数计算：不同循环与参数下的求解方法

前提参数明确 #

首先统一基础计算参数：

• 32位整数占4字节，grid[i][j]是包含x和y的结构体，因此每个结构体占8字节
• 内存块大小16字节，每个块可容纳 16 ÷ 8 = 2 个连续的grid结构体
• C语言二维数组采用行优先存储：同一行的grid[i][0]、grid[i][1]...grid[i][23]连续存放，行与行之间依次衔接

问题1：顶层循环的强制缺失数推导 #

顶层循环逻辑：遍历i=0~32（共33行），倒序遍历j=23~0（共24列），访问grid[i][j].x。

强制缺失的定义：第一次访问某个内存块时触发的缺失，与缓存容量无关，仅由内存块的首次访问决定。推导步骤：

1. 计算每行的内存块数量：一行有24个结构体，每个块存2个，因此每行对应 24 ÷ 2 = 12 个内存块
2. 分析访问顺序：同一行内倒序访问j，但grid[i][j]与grid[i][j-1]属于连续结构体，共享同一个内存块（地址差8字节，小于块大小16字节）。因此每行的12个内存块会被依次首次访问，每个块触发1次强制缺失
3. 总行数为33，因此总强制缺失数 = 行数 × 每行内存块数

问题2：容量256字节直接映射缓存的顶层循环总缺失数推导 #

直接映射缓存参数：容量256字节，块大小16字节 → 缓存总块数 = 256 ÷ 16 = 16；内存块映射到缓存的索引规则为 (内存块地址 ÷ 16) mod 16。

总缺失数包含强制缺失、冲突缺失、容量缺失，推导步骤：

1. 拆分数据访问：循环中的读操作分为两类——访问grid[i][j].x、访问total_x
2. grid部分缺失计算：
   • 每个内存块被连续访问2次（同一行的两个相邻j对应的x），第一次访问触发强制缺失，第二次访问时块仍在缓存中（两次访问间隔极短，未被替换），因此无额外缺失
   • grid部分缺失数 = 强制缺失数 = 33行 × 12块/行
3. total_x部分缺失计算：
   • 第一次访问total_x时触发1次强制缺失
   • 后续访问total_x时，需判断其所在缓存块是否被grid的块替换：
     • 计算total_x所在内存块的缓存索引，以及所有grid块的缓存索引
     • 统计与total_x索引相同的grid块数量：每遇到一个这样的块，访问时会替换total_x的块，下一次读total_x时触发1次缺失
   • total_x总缺失数 = 1 + 与total_x索引相同的grid块数量
4. 顶层循环总缺失数 = grid部分缺失数 + total_x部分缺失数

问题3：切换为底层循环的计算逻辑变化 #

底层循环逻辑：遍历j=0~23（共24列），倒序遍历i=127~0（共128行），访问grid[i][j].y，核心差异是访问模式从行优先变为列优先，导致计算逻辑完全变化：

强制缺失数计算逻辑变化 #

• 行优先（顶层循环）：同一行的相邻j共享内存块，每行的强制缺失数等于该行的内存块数
• 列优先（底层循环）：同一列的不同i对应的grid[i][j]地址差为 128×8=1024 字节（远大于块大小16字节），因此每个grid[i][j].y所在的内存块都是首次访问，强制缺失数等于访问的结构体总数（或对应的内存块总数，因每个块仅被访问1次）

总缓存缺失数计算逻辑变化 #

• 虽然每个grid内存块仍仅被访问1次，无重复访问导致的容量/冲突缺失，但列优先模式下total_y的缓存块被替换的频率显著提高（大量grid块会映射到有限的缓存索引），因此total_y的缺失数计算逻辑更复杂，需统计更多替换场景
• 若存在循环重复遍历的场景，列优先模式会因内存块映射冲突产生大量额外缺失，而行优先模式则因块复用率高，缺失数远低于列优先

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