空间与时间的局部性

Question

我理解术语的定义,但是我在将它们的概念应用于代码时遇到了麻烦.对于练习,我们被要求描述以下代码是空间的还是时间的:

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

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

Answer 1

真的,这是一个愚蠢的运动.代码不是时间或空间的.

但是时间局部性意味着您将多次访问相同的地址,并且时间相对接近.你不是在这里做的(除非你计算访问i,我猜),所以通过一个消除过程,你可以得出结论,这必须是空间局部性.

更确切地说,你正在访问some_array[0],然后some_array[1]等等.这些在地址空间中很接近,所以是的,这可能是"依赖" 空间局部性.

Answer 2

在通常出现这些概念的硬件高速缓存存储器的上下文中,分析通常不是基于存储器地址进行的,可以这么说.通过访问存储块来分析位置,存储块是在高速缓存和主存储器之间传输的.

如果你这样想,你的代码有时间和空间位置.当您的代码读取时some_array[0],如果在缓存中找不到它的地址,则从主存储器读取它,并将包含它的整个块复制到缓存中.它取代了某个策略后的其他块:MRU,例如.

然后,当您some_array[1]稍后访问时,其块已经在缓存中,因此读取时间将更短.请注意,您在很短的时间内访问了同一个块.所以你有空间和时间的地方.

高速缓存存储器利用空间和时间局部性来提供更快的存储器访问.另一方面,您的代码是否可以利用这一点完全是一个完全不同的问题.然而,编译器将为您完成大部分优化,因此您只应在查找配置文件会话中的瓶颈后关注此问题.在Linux环境中,Cachegrind非常适合这种情况.