在托管代码中，如何实现良好的引用局部性？

Question

由于RAM似乎是the new disk，而且由于该语句还意味着现在对内存的访问被认为是缓慢的，这与磁盘访问一直以来的情况类似，所以我确实想为高性能应用程序最大化内存中的引用局部性。例如，在排序索引中，我希望相邻值接近（不像在哈希表中），我也希望索引指向的数据也接近。在

在C语言中，我可以用一个专门的内存管理器创建一个数据结构，就像（非常复杂）Judy array的开发人员那样。通过直接控制指针，他们甚至可以在指针值本身中编码额外的信息。当我在Python、Java或C中工作时，我故意远离这种类型的解决方案一个（或多个）抽象级别，我委托JIT编译器和优化运行时，在较低级别上做一些巧妙的技巧。在

不过，我想，即使在这个高度抽象的层次上，有些东西在语义上可以被认为是“更接近”的，因此在较低的层次上很可能更接近。例如，我想知道以下几点（括号中是我的猜测）：

• 我能指望一个数组是一个相邻的内存块吗？在
• 同一实例中的两个整数是否比同一类的不同实例中的两个更接近（可能）？在
• 一个对象是否占据了内存中的连续区域（否）？在
• 一个只有两个int字段的对象数组和带有两个int[]字段的单个对象有什么区别？（这个例子可能是Java特有的）

我开始在Java上下文中考虑这些问题，但是我的想法变得更加普遍，所以我建议不要把它当作Java问题来处理。在

Answer 1

关于阵列，这里是CLI（公共语言基础设施）规范的摘录：

Array elements shall be laid out within the array object in row-major order (i.e., the elements associated with the rightmost array dimension shall be laid out contiguously from lowest to highest index). The actual storage allocated for each array element can include platform-specific padding. (The size of this storage, in bytes, is returned by the sizeof instruction when it is applied to the type of that array’s elements.

Answer 2

首先，你的头衔意味着C#。”如果我没弄错的话，“托管代码”是微软发明的一个术语。在

Java基元数组保证是一个连续的内存块。如果你有

int[] array = new int[4];

您可以从JNI（native C）获得一个int *p来指向实际的数组。我认为这也适用于容器的Array*类（ArrayList、ArrayBlockingQueue等）。在

我认为，JVM的早期实现将对象作为连续结构，但这不能用较新的JVM来假设。（JNI将此抽象化）。在

同一个对象中的两个整数可能会如你所说的“更接近”，但它们可能不是。即使使用同一个JVM，这可能也会有所不同。在

一个有两个int字段的对象就是一个对象，我不认为任何JVM都能保证成员是“接近”的。一个包含两个元素的int数组很可能由一个8字节长的数组作为后盾。在

Answer 3

• 在.NET中，数组的元素肯定是连续的。在Java中，我希望它们能在大多数实现中出现，但似乎不能保证。在
• 我认为假设一个实例用于字段的内存在一个块中是合理的。。。但别忘了，这些字段中的一些可能是对其他对象的引用。在

对于Java数组部分，Sun's JNI documentation包含以下注释，隐藏在有关字符串的讨论中：

For example, the Java virtual machine may not store arrays contiguously.

对于最后一个问题，如果您有两个int[]，那么这些数组中的每一个都将是一个连续的内存块，但是它们在内存中可能非常“相距”。如果您有一个带有两个int字段的对象数组，那么每个对象之间可能会有很长的距离，但是每个对象中的两个整数将非常接近。潜在的更重要的是，由于每个对象的开销，“大量对象”解决方案将占用更多的内存。在.NET中，您可以使用一个带有两个整数的自定义结构，并有一个这样的数组-将所有数据保存在一个大的块中。在

我相信，在Java和.NET中，如果在一个线程中快速连续地分配许多小对象，那么这些对象很可能具有良好的引用局部性。当GC压缩一个堆时，这可能会有所改善，或者可能会变得更糟，如果

A B C D E

压实到

^{pr2}$

（在收集C的地方）突然之间，A和B，它们以前可能是“接近”的，现在却相距很远了。我不知道这是否真的发生在任何垃圾回收器中（周围有负载！）但这是有可能的。在

基本上，在托管环境中，您通常不会像在非托管环境中那样对引用的区域性有太多的控制—您必须相信托管环境非常善于管理它，并且您可以通过编写到更高级别的平台来节省足够的时间，以便您花时间在其他地方进行优化。在