问题标签 [localityofreference]

我正在阅读关于Locality of Reference的 Wikipedia 文章，我不禁发现对Equidistant Locality给出的解释相当神秘。

我真的无法理解它，我想知道是否有人可以尝试用简单的英语解释它？

等距局部性：在空间局部性和分支局部性之间。考虑以等距模式访问位置的循环，即时空坐标空间中的路径是虚线。在这种情况下，一个简单的线性函数可以预测在不久的将来会访问哪个位置。

“以等距模式访问位置的循环”是什么意思？这些位置之间的距离是否相等？

“时空坐标空间是一条虚线。 ”这些垃圾是什么？这对我来说毫无意义。

如果有人可以对Equidistant locality应该是什么意思做出一些澄清，那就太好了！

我正在学习有关空间局部性的缓存操作。（到目前为止，我的参考资料是Lin 和 Snyder的《并行编程原理》 、本教程，当然还有 Wikipedia。）

以下面的例子为例，使用 gcc 编译，在 Windows 7 Professional 上运行，使用 Intel Core2 Duo CPU (L7500)。

现在在例程的后半部分，将读取整个整数数组，因此 CPU 应根据空间位置提前将它们加载到缓存中。但是在循环期间的任何时候，有多少数组可以/应该/应该加载到缓存中？一次一个缓存行（64 字节/每个 int 4 字节 = 16 个整数），它的大块，还是一举一动整个数组？

此外，据我了解，将数据从 RAM 加载到缓存（或根据教科书，从非本地内存到本地内存）所涉及的延迟可能比实际运行例程所需的时间要重要得多。真的？

现在假设我们将此代码移动到多处理器/多核机器上，并将代码的计数部分更改为在 4、8、16 等并行线程中运行（使用 pthreads），对数组的单独部分进行计数，然后添加私人最后一起计算。这是否会导致 RAM 到缓存延迟的多次单独出现，从而使并行版本的运行速度比串行版本慢？

我的教授说，与第二种方式相比，以第一种方式初始化二维数组的成本要高得多。有人可以解释导致这种情况的引擎盖下发生了什么吗？或者，这两种初始化方式是否具有相同的性能？

我一直在运行很多测试，将结构数组与类数组和类列表进行比较。这是我一直在运行的测试：

我在发布模式下使用以下命令运行它：

结果：

使用 padding=0 我得到：

使用 padding=64 我得到：

使用 padding=128 我得到：

我对这些结果有点困惑，因为我预计差异会更大。毕竟所有的结构都很小并且一个接一个地放在内存中，而类被最多 128 字节的垃圾分开。

这是否意味着我什至不应该担心缓存友好性？还是我的测试有缺陷？

假设我有一个 C++ 类，其实现如下所示：

在 C++ 级别，我是否可以控制这些方法的空间局部性，还是只希望编译器会注意到相关方法并相应地优化其程序集？理想情况下，我希望它们彼此相邻，以便将它们一起加载到指令缓存中，但我不知道如何让编译器知道我真的希望发生这种情况。

我目前正在尝试编写一个 map-reduce 作业，其中输入数据不在 HDFS 中，并且基本上无法加载到 HDFS 中，因为使用数据的程序不能使用来自 HDFS 的数据，并且有太多可以将其复制到 HDFS 中，至少每个节点 1TB。

所以我在集群中的 4 个节点上都有 4 个目录。理想情况下，我希望我的映射器只接收这 4 个本地目录的路径并读取它们，使用类似 file:///var/mydata/... 的东西，然后 1 个映射器可以处理每个目录。即总共16个映射器。

但是，为了能够做到这一点，我需要确保每个节点正好有 4 个映射器，并且正好有 4 个映射器被分配到该机器的本地路径。这些路径是静态的，因此可以硬编码到我的文件输入格式和记录读取器中，但是我如何保证给定的拆分最终出现在具有已知主机名的给定节点上。如果它在 HDFS 中，我可以使用 FileInputFormat 的变体设置 isSplittable 为 false，hadoop 会处理它，但由于所有数据都是本地的，这会导致问题。

基本上，我想要的是能够在集群中的每个节点上抓取一次本地目录结构，处理这些目录中的 SSTables 集合并发出行（在映射器上），并将结果（在 reduce 步骤中）减少到HDFS 用于进一步的批量处理。

我注意到 inputSplits 提供了一个 getLocations 函数，但我相信这并不能保证执行的位置，只会优化它，并且如果我尝试在每个映射器中使用 file:///some_path 我需要确保确切的位置，否则我可能会结束重复阅读一些目录，而其他根本不阅读。

任何帮助将不胜感激。

考虑到带有用于移动和新内存控制器的新指令的新 CPU，如果在 C++ 中我有一个由虚拟成员函数组成的Derived对象向量Derived，这对本地来说是好事还是坏事？

如果我有一个指向基类的指针向量，在该基类Base*中存储对从 1-2-3 级的派生对象的引用，该Base怎么办？

基本上动态类型适用于这两种情况，但哪一种更适合缓存和内存访问？

我在这两个之间有偏好，但我希望看到关于这个主题的完整答案。

在过去的 2-3 年里，硬件行业有什么新的东西需要考虑作为突破？

假设我们有一个未排序的数组和链表。为两种数据结构搜索元素时最坏的情况是 O(n)，但我的问题是：

由于在缓存中使用空间局部性，数组是否仍然会更快，或者缓存是否会利用分支局部性允许链表与任何数组一样快？

我对数组的理解是，如果访问了一个元素，那么该内存块和许多周围的块将被带入缓存，从而实现更快的内存访问。

我对链表的理解是，由于遍历链表的路径是可预测的，因此缓存将利用它并仍然存储适当的内存块，即使链表的节点在堆内可能相距很远.

考虑到一个指向一个函数的指针返回另一个指向另一个函数的指针是 C 中用来引入一些运行时多态性/回调的机制，在 C++ 中实现这一点的等效方法是什么，同时提高了局部性并降低了指针和间接的成本?

例如，这种语法糖可以提供帮助，但我对此并不真正感兴趣，尽管它是一种以 C++ 方式而不是更 C-ish 做事的好方法typedef，但我更感兴趣的是改善局部性，同时尝试减少在运行时使用显式指针。

如果我运行以下程序，然后在 sum+=arr[i][j] 中交换 i 和 j 后再次运行它，则执行时间非常不同，即 9.8 秒与交换前的 2.7 秒相比。我只是不明白为什么会这样。有人可以告诉我为什么会这样吗？