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

Question

由于RAM似乎是新磁盘,并且因为该声明也意味着现在认为对内存的访问速度与磁盘访问的方式类似,我确实希望最大化内存中的引用位置以用于高性能应用程序.例如,在排序索引中,我希望相邻值接近(不像说,在哈希表中),我也希望索引指向的数据也接近.

在C中,我可以使用专门的内存管理器来创建数据结构,就像(非常复杂的)Judy数组的开发人员一样.通过直接控制指针,它们甚至可以在指针值本身中编码附加信息.在Python,Java或C#中工作时,我故意将这种类型的解决方案中的一个(或多个)抽象级别委托给JIT编译器并优化运行时,为我做低级别的巧妙技巧.

尽管如此,我猜想,即使在这种高水平的抽象中,也有一些东西可以在语义上被认为是"更接近",因此可能实际上更接近于低水平.例如,我想知道以下(我在括号中的猜测):

• 我可以期待一个数组成为相邻的内存块(是)吗？
• 同一个实例中的两个整数是否比同一个类的不同实例中的两个更接近(可能)？
• 对象是否占据内存中的一个重要区域(否)？
• 只有两个int字段的对象数组和一个有两个int[]字段的对象之间的区别是什么？(这个例子可能是Java特定的)

我开始在Java环境中对这些问题感到疑惑,但我的想法变得更加普遍,所以我建议不要将其视为Java问题.

Answer 1

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

对于Java数组部分,Sun的JNI文档包含此注释,隐藏在关于字符串的讨论中:

例如,Java虚拟机可能不会连续存储数组.

对于你的上一个问题,如果你有两个,int[]那么每个阵列都将是一个连续的内存块,但它们在内存中可能非常"相距甚远".如果你有一个带有两个int字段的对象数组,那么每个对象可能相距很远,但每个对象中的两个整数将靠近在一起.可能更重要的是,你会最终采取了很多更多的内存与"大量的对象"的解决方案,由于每个对象的开销.在.NET中,您可以使用具有两个整数的自定义结构,并且具有这些结构的数组 - 这将使所有数据保持在一个大块中.

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

A B C D E

被压缩到

A D E B

(收集C的地方) - 突然之间可能已经"接近"的A和B相隔很远.我不知道这是否真的发生在任何垃圾收集器中(周围有负载!)但它是可能的.

基本上在托管环境中,您通常不像在非托管环境中那样控制引用的位置 - 您必须相信托管环境足以管理它,并且您将节省足够的时间通过编码到更高级别的平台,让您花时间优化其他地方.