问题标签 [cache-locality]

我正在寻找一个库/解决方案，以减轻我在程序中遇到的相当重要的缓存未命中次数

所以，我做的第一件事就是创建一个指向这个向量的std::vector<Foo>每一个点。Foo*它有很大帮助。我的主要问题是std::vector<Foo*> myVec;. 这些向量的每个内部数组都位于内存的不同部分。就像我创建一个单一的一样，我的std::vector<Foo>所有Foo在内存中都是连续的，我希望我的所有都在内存std::vector<Foo*> myVec;中对齐（实际上是内部数组）。如何？

注意：重要的一点myVec是Foo. 否则，我可以轻松地构建一个单一的std::vector<Foo*>并编写 getter/setter。另外，我std::shared_ptr<Foo>不是Foo*因为我不是野蛮人，而是因为它使示例的理解更容易。最后，我保证所有权形成一个 DAG，因此我的共享指针中没有循环。

很久以前，受“C 中的数值配方”的启发，我开始使用以下结构来存储矩阵（二维数组）。

但是最近注意到很多人实现矩阵如下

从局部性的角度来看，第二种方法似乎很完美，但可读性很差......所以我开始怀疑，我的第一种存储辅助数组或**double指针的方法真的很糟糕，还是编译器最终会优化它，这样它会更还是在性能上不及第二种方法？我很怀疑，因为我认为在第一种方法中，在访问值时会进行两次跳转，x[m]然后x[m][n]每次 CPU 都有可能先加载x数组，然后再加载x[m]数组。

ps 不用担心额外的存储空间**double，对于大型矩阵来说，这只是一小部分。

PPS 因为很多人不太了解我的问题，所以我会尝试重新塑造它：我是否理解正确，第一种方法是一种局部性地狱，当每次x[m][n]访问时，第一个x数组将被加载到 CPU 缓存中并然后x[m]将加载数组，从而以与 RAM 通信的速度进行每次访问。还是我错了，从数据局部性的角度来看，第一种方法也可以？

我有两台服务器。第一台服务器 (A) 包含 zookeeper、一个 mongodb 数据库和一个钻头。第二个服务器 (B) 包含一个带有多个 hive 表、一个 postgresql 数据库和另一个钻头的 hadoop 发行版。两个钻头可以在钻头主页上看到彼此，因为它们都连接到服务器 A 上的 zookeeper。当运行如下查询时（视图 dfs.lineorder 包含服务器 B 上的 hive 和 postgresql 数据），drillbit B 成为工头并执行所有操作。它不会将处理 mongodb 表的部分委托给服务器 A 上的钻头，因此运行查询所需的 90% 时间（大约 30 分钟）用于将 mongodb 集合从服务器 A 发送到服务器 B。一种强制drillbit B将查询的mongodb部分委托给drillbit B的方法，或者这可能是一个错误配置问题？此外，是否可以将钻头配置为访问不同的数据库（例如，当每个钻头都可以访问不同的子网时，以便并非所有钻头都可以访问相同的数据库）？

示例查询：

配置（drill-override.conf）：

在 Drillbit A (Windows Server 2008) 上：drill.exec: { cluster-id: "drillbits1", zk.connect: "serverA:2181", impersonation: { enabled: true, max_chained_user_hops: 3 } }

在 Drillbit B (Cloudera CDH 5.8.0) 上：drill.exec: { cluster-id: "drillbits1", zk.connect: "serverA:2181", impersonation: { enabled: true, max_chained_user_hops: 3 } }

我有以下嵌套的for循环：

它按预期打印 (0,1) 到 (6,7) 并且printf()语句运行 28 次，如counter.

我的任务是通过提高它的局部性来提高这段代码的效率（这是测试代码，n实际程序中的值要大得多，i并且j用于索引两个一维数组）并采用了我相信是一种相当标准的技术：

但是，这里printf()只运行了 24 次，因为这j_chunk = i_chunk + 1意味着在j循环打印 (0,1) 到 (0,7) 之前，循环的两次迭代j_chunk打印i+i_chunk == 0(0,1) 到 (0,3) 和(0,5) 到 (0,7) 缺少 (0,4)。

我理解它为什么会这样做，但我无法为我的生活想出一个解决方案；任何帮助，将不胜感激。

我对 L1 缓存的理解是内存获取会加载缓存行。假设缓存行大小为 64 字节，如果我在 address 访问内存p，它会将整个块从pto加载p + 64到缓存中。因此，最好从左到右（而不是从右到左）遍历数组以最大化缓存局部性。

但是，我编写了示例 C 代码，该代码分配了一个包含 1 亿个字符的数组，将随机值写入其中并求和（复制如下以供参考）。一个版本的代码从左到右求和，另一个从右到左求和。当我对其进行基准测试时，我得到了非常相似的结果（其中“时钟周期”是用 . 来衡量的clock。代码是在没有优化的情况下编译的。

所以我的问题是：现代处理器除了“缓存读取+ 64字节”之外还做其他事情吗？他们是否向前和向后缓存？编译器可以“告诉”处理器代码正在向后迭代吗？

作为参考，我正在Mac OS X 10.13.3使用gcc-7 (Homebrew GCC 7.2.0_1) 7.2.0具有 64 字节缓存行的 x86-64 Intel 处理器运行。

基准测试：

我本来预计前向迭代会快大约 64 倍，因为每 64 个元素应该是缓存命中，而对于后向迭代，每个元素都应该是缓存未命中。

所以，我在上面调用了cachegrind。两者的缓存命中未命中率几乎相同：

代码：

我已经阅读了这个博客，但我仍然不确定位置的重要性。为什么局部性对缓存性能很重要？是因为它导致更少的缓存未命中吗？此外，如何编写程序以实现良好的局部性并因此获得良好的缓存性能？

我正在为我的架构期末考试而学习，并遇到了以下代码行：

问题是：“此代码片段如何演示时间和空间局部性的示例？一定要考虑数据和指令的内存引用。”

就空间局部性而言，我相信代码通过访问连续的内存位置（a[0] 然后 a[i] 等）来演示它。然而，我的困惑来自时间局部性。我不确定这段代码如何在短时间内引用相同的位置？任何形式的帮助将不胜感激。

我是操作系统的初学者，我正在尝试理解一些代码片段。您能向我解释一下这些代码片段之间的区别吗？

和

不同的部分是双重For 属性其中一个应该比另一个更快吗？如果是这样，你能解释一下为什么，因为我不明白。

鉴于我们有一个应用程序被并发构造严重污染，使用了多种技术（不同的人在没有清晰架构的情况下工作），多个有问题的锁“以防万一”，线程安全队列。CPU 使用率约为 20%。

现在我的目标是对其进行优化，以便更好地利用缓存并总体提高其性能和服务时间。

我正在考虑将父进程固定到单个核心，删除所有导致内存条的东西，替换所有线程安全数据结构并用一些UnsafeReentrantLock 简单地使用普通引用字段但照顾排他执行需求的锁替换所有锁......

我希望我们最终会得到对缓存更友好的应用程序，因为我们不会一直快速刷新缓存（没有 membars）。我们的开销会更少，因为我们不需要线程安全的数据结构、volaties、原子和替换各种锁，我认为服务时间也会改善，因为我们不再在多个线程安全队列上同步......

有什么我在这里忽略的吗？

也许必须注意阻塞操作，因为它们不会出现在 20% 的使用中？

在教科书Computer Systems: a Programmer's Perspective中，有一些令人印象深刻的基准来优化行主要顺序访问。

我创建了一个小程序来测试自己是否从行主要访问到列主要访问的简单更改会对我自己的机器产生巨大影响。

平均而言，行主要顺序访问在我的系统上进行8.42s（n=5试验），而列主要顺序访问在我的系统上进行30.12s（n=5试验），这非常重要。

从表面上看，优化应该是一件非常简单的事情。

为什么现代编译器不优化这些场景？