c - 空间与时间局部性

Question

我理解这些术语的定义，但我无法将它们的概念应用到代码中。对于一个练习，我们被要求描述以下代码是空间的还是时间的：

for (int i=0; i<10; i++) {
    printf(some_array[i]);
}

我觉得这是空间局部性，因为当访问数组的一个索引时，一旦循环迭代，就会访问下一个索引内存位置。这是看待它的正确方法吗？什么决定了代码是时间的还是空间的？更多的例子会很棒。

Answer 1

这是一个有点愚蠢的练习，真的。代码不是时间的或空间的。

但是时间局部性意味着您将在时间上相对接近地多次访问同一个地址。您在这里没有这样做（除非您计算 access i，我猜），因此通过消除过程，您可以得出结论，这一定是空间局部性。

更准确地说，您正在访问some_array[0], thensome_array[1]等。这些在地址空间中非常接近，所以是的，这可能是“依赖”空间局部性。

Answer 2

In the context of hardware cache memory, which is where these concepts usually come up, the analysis is not usually done on a memory address basis, so to speak. Locality is analyzed by access to memory blocks, those which are transferred between cache and main memory.

If you think of it that way, your code has both temporal and spatial locality. When your code reads some_array[0], if its address is not found in the cache, it is read from main memory and the whole block which contains it is copied to the cache. It replaces some other block following a certain policy: MRU, for example.

Then, when you access some_array[1] a short time later, its block is already in cache, so read time will be smaller. Notice that you accessed the same block, and in a small amount of time. So you have both spatial and temporal locality.

Cache memory takes advantage of spatial and temporal locality to provide faster memory access. On the other hand, whether your code can take advantage of this is a whole different issue altogether. Nevertheless, the compiler will do most of the optimizations for you, so you should only concern yourself with this after finding a bottleneck in a profile session. In Linux environments, Cachegrind is great for this.

Answer 3

此代码在指令缓存中具有时间局部性，因为您在每个循环中重复代码（假设您的优化器没有展开循环）。它在数据缓存中也具有空间局部性，因为如果您访问数组元素 i，您将很快访问元素 i+1、i+2 等。如果您的数据缓存行大小是 16 字节并且您的数组是 32 位整数，那么当您请求元素 0 时，您的数据缓存还加载了元素 1、2 和 3（假设我们的数组从缓存行边界开始）。

Answer 4

该代码仅具有空间局部性，但没有时间局部性 - 在高速缓存访​​问的上下文中。

在将数据加载到缓存中时，会加载整个行/块 - 因此对完全相同的内存位置以及也是缓存中同一块的一部分的地址的后续访问将具有快速访问时间。

有一些方法可以优化您的代码，使得尽可能多的读取来自缓存而不是直接来自主内存： 1. 如果您可以通过仅利用第一次缓存未命中来访问所有附近的内存地址，并且在此之前块被驱逐出缓存 - 然后你利用空间局部性。2. 如果在缓存中的块被驱逐之前，您按照程序所需的次数访问同一内存位置 - 那么您就利用了时间局部性。

像矩阵乘法这样的例子将同时具有时间和空间局部性。