Java Arrays.sort() 影响程序中其他方法的性能；为什么？

Question

我正在开发一个java程序，其中使用了一个类实例的大数组。我必须对数组的每个对象进行一些计算(使用其类方法)。当我使用 Arrays.Sort 或其他方法对数组进行排序时，我注意到执行计算的计算时间有所增加，这不包括进行排序的时间!

如果我注释 Arrays.sort 函数，在其他计算之前，计算时间约为 1 或 2 毫秒，而取消注释则会增加到 5 或 6 毫秒。

我必须执行大量步骤(甚至 300,000)才能完成这项工作，因此增量对我的性能有很大影响。

对于这种奇怪的行为有什么解释吗？

Answer 1

考虑到我对代码知之甚少，这是我的最佳猜测:

对象通常(但并非总是)按照它们分配的顺序大致放置在堆上。 GC 会移动它们，但顺序有可能会被大致保留。

然后，当您轮流访问每个对象以对其数据进行计算时，您最终可能会得到大致线性的内存访问。或者更重要的是，内存访问在某种程度上是可预测的。这使得您的 CPU 缓存和内存子系统更加高效。

如果对象没有按排序顺序分配，然后对它们进行排序，则会将这种可预测的内存访问转变为不可预测的随机访问，速度会更慢。