我可以在Java代码中做些什么来优化CPU缓存？

Question

编写Java程序时,是否会影响CPU如何利用其缓存来存储数据？例如,如果我有一个被大量访问的数组,如果它足够小以适应一个缓存行(通常是64位机器上的128个字节),它会有帮助吗？如果我将一个使用频繁的对象保持在该限制内,我可以期待它的成员使用的内存靠近并保持缓存吗？

背景:我正在构建一个压缩的数字树,它受到了C中的Judy数组的启发.虽然我主要使用节点压缩技术,但Judy将CPU缓存优化作为中心设计目标,节点类型为以及在它们之间切换的启发式方法受到很大影响.我想知道我是否有机会获得这些好处？

编辑:到目前为止答案的一般建议是,当你离开机器时,不要试图微观优化机器级细节,就像你在Java中一样.我完全同意,所以觉得我必须添加一些(希望)澄清的评论,以更好地解释为什么我认为这个问题仍然有意义.这些如下:

有些东西通常更容易被计算机处理,因为它们的构建方式.我已经看到Java代码在压缩数据(来自内存)上的运行速度明显更快,即使解压缩必须使用额外的CPU周期.如果数据存储在磁盘上,很明显为什么会这样,但当然在RAM中它的原理是相同的.

现在,计算机科学有很多东西可以说这些东西是什么,例如,C语言中的引用位置很好,我想它在Java中仍然很好,甚至可能更好,如果它有助于优化运行时做更聪明的事情.但是你如何实现它可能会有很大的不同.在C中,我可能编写代码来管理更大的内存块本身,并使用相邻的指针来获取相关数据.

在Java中,我不能(并且不想)了解特定运行时将如何管理内存.因此,我必须对更高级别的抽象进行优化.我的问题基本上是,我该怎么做？对于引用的局部性,"在一起"是什么意思在我在Java中工作的抽象层次？相同的对象？相同的类型？相同的阵列？

总的来说,我不认为抽象层会改变"物理定律",比喻说.即使你不再调用malloc(),每次空间不足时,你的数组大小加倍也是一个很好的策略.

Answer 1

使用Java获得良好性能的关键是编写惯用代码,而不是尝试智胜JIT编译器.如果您编写代码以试图影响它以在本地指令级别以某种方式执行某些操作,那么您更有可能在自己的脚下开枪.

这并不是说像参考地点这样的共同原则无关紧要.他们这样做,但我会考虑使用数组等,这是性能感知的,惯用的代码,但不是"棘手的".

HotSpot和其他优化运行时非常聪明,它们如何优化特定处理器的代码.(例如,请查看此讨论.)如果我是专家机器语言程序员,我会编写机器语言,而不是Java.如果我不是,那么认为我可以比专家更好地优化我的代码是不明智的.

此外,即使您确实知道为特定CPU实现某些功能的最佳方法,Java的优点在于可以随处运行."优化"Java代码的聪明技巧往往会使JIT难以识别优化机会.遵循常用习语的直接代码更易于识别.因此,即使您为测试平台获得了最佳的Java代码,该代码也可能在不同的架构上表现糟糕,或者至多在未来的JIT中无法利用增强功能.

如果您想获得良好的性能,请保持简单.真正聪明人的团队正努力使其快速发展.

Answer 2

如果您正在处理的数据主要或完全由基元组成(例如,在数字问题中),我会建议如下.

在初始化时分配固定大小的基元数组的平面结构,并确保其中的数据被周期性地压缩/碎片整理(0-> n,其中n是给定元素计数时可能的最小最大索引),以进行迭代过度使用for循环.这是保证Java中连续分配的唯一方法,压缩进一步有助于改善引用的局部性.压缩是有益的,因为它减少了迭代未使用元素的需要,减少了条件数:当for循环迭代时,终止发生得更早,迭代次数越少=通过堆的移动越少=缓存未命中的机会越少.虽然压缩会在其中产生开销,但如果您愿意,这可能只是定期(相对于您的主要处理区域).

更好的是,您可以在这些预先分配的数组中交错值.例如,如果要表示2D空间中数千个实体的空间变换,并且正在处理每个实体的运动方程,那么您可能会像

int axIdx, ayIdx, vxIdx, vyIdx, xIdx, yIdx;

//Acceleration, velocity, and displacement for each
//of x and y totals 6 elements per entity.
for (axIdx = 0; axIdx < array.length; axIdx += 6) 
{
    ayIdx = axIdx+1;
    vxIdx = axIdx+2;
    vyIdx = axIdx+3;
    xIdx = axIdx+4;
    yIdx = axIdx+5;

    //velocity1 = velocity0 + acceleration 
    array[vxIdx] += array[axIdx];
    array[vyIdx] += array[ayIdx];

    //displacement1 = displacement0 + velocity
    array[xIdx] += array[vxIdx];
    array[yIdx] += array[vxIdx];
}

此示例忽略了诸如使用关联的(x,y)渲染这些实体的问题......渲染始终需要非基元(因此,引用/指针).如果你确实需要这样的对象实例,那么你就不能再保证引用的局部性,并且可能会在整个堆中跳转.因此,如果您可以将代码拆分为如上所示的原始密集型处理的部分,那么这种方法将对您有所帮助.至少对于游戏来说,AI,动态地形和物理可能是处理器密集程度最高的一些方面,并且都是数字的,因此这种方法非常有用.

Answer 3

如果你到了几个百分点的改进有所作为的地方,使用C,你将获得50-100%的改善!

如果您认为Java的易用性使其成为一种更好的语言,那么请不要将其与可疑的优化相混淆.

好消息是,Java将在运行时完成很多内容以改进您的代码,但几乎肯定不会进行您正在讨论的那种优化.

如果您决定使用Java,只需尽可能清楚地编写代码,不要将少量优化考虑在内.(对于正确的工作使用正确的集合,而不是在循环内分配/释放对象等主要的工作仍然值得)

Answer 4

到目前为止，建议非常有力，一般来说最好不要试图超越 JIT。但正如你所说，一些关于细节的知识有时是有用的。

关于对象的内存布局，Sun 的 JVM（现在是 Oracle 的）按类型将对象放入内存中（即首先是双精度型和长型，然后是整数和浮点型，然后是短型和字符型，然后是字节和布尔型，最后是对象引用）。您可以在此处获得更多详细信息..

局部变量通常保存在堆栈中（即引用和原始类型）。

正如 Nick 所说，在 Java 中确保内存布局的最佳方法是使用原始数组。这样您就可以确保数据在内存中是连续的。不过要注意数组大小，GC 在处理大数组时会遇到麻烦。它也有缺点，你必须自己做一些内存管理。

从好的方面来说，您可以使用享元模式在保持快速性能的同时获得类对象的可用性。

如果您需要额外的性能，动态生成您自己的字节码有助于解决一些问题，只要生成的代码执行足够多的次数并且您的 VM 的本机代码缓存未满（这会禁用所有实用的 JIT目的）。