二进制搜索运行时中的某些异常

Question

我有一个二叉搜索的修改版本，它以排序顺序和一个值接收数组，并返回等于或大于给定值的元素的最小可能索引（如果值大于最大值，则返回 -1）

运行上述算法后，一切正常，方法按预期工作。但是，我在不同的输入大小上运行它以测量运行时。

   for(int i=1;i<=20;i++){  
  int size=10*(i*i*i*i);
 int[] array=createRandomSortedArray(size);
 long startTime=System.nanoTime();
 int index=findSmallestIndex(array, needle);
 long et=System.nanoTime()-startTime;
 System.out.println("To find "+needle+" in "+size+" inputs "+" execution time is "+et+" nanoseconds");
}

以下是纪念活动：

To find 50 in 10 inputs  execution time is 5775 nanoseconds
To find 50 in 160 inputs  execution time is 1925 nanoseconds  
To find 50 in 810 inputs  execution time is 4330 nanoseconds
To find 50 in 2560 inputs  execution time is 5293 nanoseconds
To find 50 in 6250 inputs  execution time is 3849 nanoseconds
To find 50 in 12960 inputs  execution time is 3368 nanoseconds
To find 50 in 24010 inputs  execution time is 3849 nanoseconds
To find 50 in 40960 inputs  execution time is 11548 nanoseconds
To find 50 in 65610 inputs  execution time is 9143 nanoseconds
To find 50 in 100000 inputs  execution time is 4812 nanoseconds
To find 50 in 146410 inputs  execution time is 4812 nanoseconds
To find 50 in 207360 inputs  execution time is 11549 nanoseconds  
To find 50 in 285610 inputs  execution time is 8661 nanoseconds
To find 50 in 384160 inputs  execution time is 8661 nanoseconds
To find 50 in 506250 inputs  execution time is 11549 nanoseconds 
To find 50 in 655360 inputs  execution time is 11067 nanoseconds 
To find 50 in 835210 inputs  execution time is 11549 nanoseconds
To find 50 in 1049760 inputs  execution time is 11549 nanoseconds 
To find 50 in 1303210 inputs  execution time is 11067 nanoseconds
To find 50 in 1600000 inputs  execution time is 12030 nanoseconds

我看到 10 个输入的

执行时间明显高于其连续的 160 个输入大小。为了验证事情，我在循环外自行运行了 10 个输入的执行，结果如下

To find 50 in 10 inputs  execution time is 962 nanoseconds

为什么会这样？为什么会出现这种异常？还有其他几个步骤，其中运行时比其前面的较低输入大小慢。

Answer 1

在运行微基准测试之前，您是否让虚拟机"预热"？ 在实际记录任何结果之前，请尝试运行此代码几千次，看看这是否有所作为。 可以添加以下命令行参数以查看 JIT 编译的内容：

-XX:+PrintCompilation

您还可以使用

-Xint

以关闭所有热点优化，并尝试获取苹果与苹果的比较。

如果这不是问题所在 - 我怀疑简单地调用您的方法会产生一些恒定的成本。 尝试线性增加输入大小，看看是否可以以这种方式绘制任何相关性。 很难说你什么时候从 10 跳到 160。

最后，您可能希望包含一个标志，该标志在启用时将记录代码正在执行的行为（例如 # 的比较等），以查看您是否做了任何不必要的工作。

Answer 2

可能是Hotspot在施展它的魔力。反转运行顺序（大优先）以验证这一点。

Answer 3

为了分析这一点，我将输出算法正在搜索的实际数组。由于每次运行的数组看起来并不相同，因此很难进行比较，因为访问的指示项数量完全取决于数组和搜索项的内容。