将数据保存在缓存中的技术,地点？

Question

对于超快速代码,我们必须保持引用的位置 - 在CPU缓存中保留尽可能多的密切使用的数据:

http://en.wikipedia.org/wiki/Locality_of_reference

有哪些技术可以实现这一目标？人们能举例吗？

我对Java和C/C++示例感兴趣.有趣的是知道人们用来阻止大量缓存交换的方式.

问候

Answer 1

这可能过于通用而无法得到明确答案.与Java相比,C或C++中的方法将有很大不同(语言布置对象的方式不同).

基本的是,保持将在闭环中一起访问的数据.如果您的循环在类型T上运行,并且它具有成员m1 ... mN,但在关键路径中仅使用m1 ... m4,请考虑将T分解为包含m1 ... m4和包含m4的T2的T1. ..mN.您可能希望向T1添加一个引用T2的指针.尽量避免与缓存边界不对齐的对象(非常依赖于平台).

使用连续的容器(C中的普通旧数组,C++中的vector)并尝试管理迭代上升或下降,但不是随机跳过容器.链接列表是局部性的杀手,列表中的两个连续节点可能处于完全不同的随机位置.

Java中的对象容器(和泛型)也是杀手,而在Vector中,引用是连续的,实际的对象不是(有一个额外的间接级别).在Java中有很多额外的变量(如果你的new两个对象一个接着一个,对象可能最终会在几乎连续的内存位置,即使会有一些额外的信息(通常是两个或三个指针)的Object两者之间的管理数据.GC会移动物体,但希望它不会比它运行前更糟糕.

如果您专注于Java,创建紧凑的数据结构,如果您有一个具有位置的对象,并且要在紧密循环中访问,请考虑在对象中保存x和y原始类型,而不是创建Point并保持引用它.需要更新引用类型,这意味着不同的分配,额外的间接和更少的位置.

Answer 2

两种常见的技术包括：

• 极简主义（数据大小和/或代码大小/路径）
• 使用缓存遗忘技术

极简主义示例：在光线追踪（一种 3D 图形渲染范例）中，使用 8 字节 Kd 树来存储静态场景数据是一种常见的方法。遍历算法只需几行代码。然后，Kd 树通常以通过在树顶部具有大的空节点来最小化遍历步骤数的方式进行编译（Havran 的“Surface Area Heuristics”）。

错误预测的概率通常为 50%，但代价很小，因为实际上很多节点都适合缓存行（考虑每 KiB 有 128 个节点！），并且两个子节点之一始终是记忆。

缓存遗忘技术示例： Morton 数组索引，也称为 Z-order-curve-indexing。如果您通常以不可预测的方向访问附近的数组元素，则这种索引可能是首选。这对于大型图像或体素数据可能很有价值，其中您可能有 32 甚至 64 字节的大像素，然后是数百万个（典型的紧凑型相机测量值是百万像素，对吗？）甚至数千亿用于科学模拟。

然而，这两种技术有一个共同点：将最常访问的东西放在附近，不那么频繁的东西可以放在更远的地方，跨越主内存到硬盘的整个 L1 缓存范围，然后是同一房间、隔壁房间的其他计算机，同一个国家，世界各地，其他星球。