如何生成具备缓存局部性的多数组嵌套循环索引序列？

常规嵌套循环（比如二维两层循环）会导致严重的缓存失效问题，以下是典型的低效代码：

#include <stdio.h>

int main(void) {
  int sizes[5] = {4, 4};
  for (int i = 0 ; i < sizes[0]; i++) {
    for (int j = 0 ; j < sizes[1]; j++) {
      printf("%d%d\n", i, j);
    }
  }
  return 0;
}

这段代码中，外层循环每迭代一次，内层循环会遍历完第二个数组的所有元素，导致对应缓存行被反复加载和清空，缓存命中率极低。

格雷码（反射二进制码）能生成相邻索引仅单维度变化的序列，完美解决这个问题。先看二维场景的Python实现示例：

a = [1, 2, 3, 4]
b = [2, 4, 8, 16]
indexes = set()
correct = set()

print("graycode loop indexes")
for index in range(0, len(a) * len(b)):
  code = index ^ (index >> 1)
  left = code & 0x0003
  right = code >> 0x0002 & 0x0003

  print("{}{}".format(left, right))
  indexes.add((left, right))

assert len(indexes) == 16

print("regular nested loop indexes")

for x in range(0, len(a)):
  for y in range(0, len(b)):
    correct.add((x,y))
    print("{}{}".format(x, y))

assert correct == indexes

通过将线性索引转换为格雷码，再拆分二进制位段得到各维度索引，保证相邻序列只有一个维度数值变化，大幅减少缓存失效。

推广到任意数量、任意长度的数组 #

针对多维度场景（比如大小为5、8、16的三个数组），可以按以下步骤实现：

1. 计算总遍历次数：所有数组长度的乘积（如5×8×16=640）。
2. 为每个维度分配足够的二进制位数：取大于等于数组长度的最小2的幂对应的位数（比如长度5需要3位，因为2²=4<5，2³=8≥5）。
3. 将线性索引转换为格雷码，拆分出每个维度的位段，通过取模适配数组实际长度（即使长度不是2的幂）。
4. 生成的索引序列会确保相邻索引仅单维度变化，最大化缓存利用率。

多维度实现代码示例 #

def generate_graycode_indexes(*array_sizes):
    total = 1
    bit_lengths = []
    for size in array_sizes:
        # 计算每个维度所需的最小二进制位数
        bits = size.bit_length()
        bit_lengths.append(bits)
        total *= size
    
    indexes = set()
    for idx in range(total):
        # 线性索引转格雷码
        gray = idx ^ (idx >> 1)
        current_index = []
        remaining = gray
        # 从低位到高位拆分各维度的位段
        for bits in reversed(bit_lengths):
            mask = (1 << bits) - 1
            dim_idx = remaining & mask
            # 取模适配数组实际长度，避免索引越界
            dim_idx = dim_idx % array_sizes[len(current_index)]
            current_index.append(dim_idx)
            remaining = remaining >> bits
        # 反转后匹配输入数组的顺序
        current_index = current_index[::-1]
        indexes.add(tuple(current_index))
        yield tuple(current_index)
    
    # 验证所有组合都被遍历
    assert len(indexes) == total

# 测试：三个数组，大小5、8、16
sizes = (5, 8, 16)
print("格雷码生成的多维度索引序列（前10个）：")
for i, idx in enumerate(generate_graycode_indexes(*sizes)):
    if i < 10:
        print(idx)

# 验证总数正确性
all_indexes = list(generate_graycode_indexes(*sizes))
assert len(all_indexes) == 5 * 8 * 16
print(f"总索引数：{len(all_indexes)}，符合预期的{5*8*16}")

关键注意事项 #

• 如果数组长度是2的幂，可省略取模操作，直接使用位段结果，效率更高。
• 维度的位段分配顺序可根据缓存访问模式调整：若某维度的缓存局部性更重要，可将其分配到格雷码的高位（高位变化频率更低，对应维度索引更稳定）。
• 该方法适用于绝大多数场景，仅当总遍历次数超过2^64时会受限于整数范围。

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