Data structure size and cache-line accesses

https://lemire.me/blog/2022/06/06/data-structure-size-and-cache-line-accesses/

这个问题我开始还想错模型了，作者的模型是：假设有一个array里面每个对象字节是X(X<64字节), 那么访问这些对象平均会造成多少次cache line access. 作者给的答案是 1 + (X-g) / 64. 其中 g = GCD(X, 64). 我觉得这个答案好像不是那么显然，花了点时间想了下记录一下过程。

我们需要多少个字节才完全和cache line对齐(一轮对象和cache line对齐的基本单元)，答案是 LCM(X, 64) = X * 64 / g. (LCM = least common multiple)

然后在这么大的存储空间下面，我们有多少个对象以及cache lines?

• 有 LCM/X = 64/g 个对象
• 有 LCM/64 = X/g 个cache lines

当访问 64/g 个对象的时候，所有的对象至少会产生1次cache line access, 而有 (X/g-1)次cross cache line，因此总共会有 64/g + X/g - 1 次cache lines access. 那么平均值就是

(64/g + X/g - 1) / (64/g) = (64 + X - g) / 64 = 1 + (X-g) / 64