cod*_*inn 2 java sorting algorithm runtime
排序算法变得更快（在 Java 中）？！
我已经实现了一些排序算法和 getNanoTime 方法，它给出了该排序算法的 NanoTime。
我想计算平均值。我认识到平均时间与测试算法一次的时间不同。
我以为我做错了什么。
但后来我找到了。
做时：
int length = 5000;
int bereich = 1000;
long time;
time = Bubblesort.getNanoTime(length, bereich);
System.out.println("BUBBLESORT: " + (1.0 * time / 1_000_000) + " ms");
time = Insertionsort.getNanoTime(length, bereich);
System.out.println("INSERTIONSORT: " + (1.0 * time / 1_000_000) + " ms");
time = Mergesort.getNanoTime(length, bereich);
System.out.println("MERGESORT: " + (1.0 * time / 1_000_000) + " ms");
time = Quicksort.getNanoTime(length, bereich);
System.out.println("QUICKSORT: " + (1.0 * time / 1_000_000) + " ms");
time = Selectionsort.getNanoTime(length, bereich);
System.out.println("SELECTIONSORT: " + (1.0 * time / 1_000_000) + " ms");
我有：
冒泡排序：75.7835 毫秒
插入排序：27.250875 毫秒
合并排序：17.450083 毫秒
快速排序：7.092709 毫秒
选择排序：967.638792 毫秒
但是当做例如：
for (int i = 0; i < 20; i++) {
System.out.println(1.0 * Bubblesort.getNanoTime(5000, 1000) / 1_000_000);
}
我有：
85.473625 毫秒
62.681959 毫秒
68.866542 毫秒
48.737333 毫秒
47.402708 毫秒
47.368708 毫秒
47.567792 毫秒
47.018042 毫秒
45.1795 毫秒
47.871416 毫秒
49.570208 毫秒
50.285875 毫秒
56.37975 毫秒
50.342917 毫秒
50.262833 毫秒
50.036959 毫秒
50.286542 毫秒
51.752708 毫秒
50.342458 毫秒
51.511541 毫秒
第一次总是很高（这里是第一次 85 ms），第一次之后的时间较低。所以，我认为，机器学习，并且变得更快
可能是这样吗？你知道更多吗？
我认为，机器学习，并且变得更快
是的。
查找“即时编译”，在了解它的同时，花几周时间成为一名火箭科学家，这样您就可以完全理解CPU 缓存的工作原理。
或者，如果您不想在接下来的 10 周里学习，但确实想更好地了解其中的工作原理，请阅读本答案的其余部分，然后看看Douglas Hawkins 的关于 JVM 性能难题的演讲。我敢打赌，看完这 40 分钟后，您会对这个难题感到完全明白。
这里发生了两件事（JIT 预热效应和缓存页效应），可能还有更多：
JIT 正在“热身”：java 的工作方式是，它以最愚蠢、最慢、最愚蠢的方式运行类文件代码，此外还浪费更多的时间来维护代码上的大量簿记，例如“这个if块进入的频率与跳过的频率是多少？” 没有充分的理由。一切都像糖蜜一样缓慢。确实是故意的。
但是……由于 JVM 在某个时刻的所有记录，会出现：嗯。从字面上看（我在这里并没有夸大这种情况，这种情况很常见！）99% 的 CPU 时间都花在了整个代码库的这 0.1% 上。
然后需要一些时间来分析这 0.1% 中的日光，创建一个非常微调的机器代码版本，该版本完全适合您正在运行的实际 CPU。这需要花费大量时间，将使用所有簿记（毕竟，这并不是毫无意义！）来执行诸如重新排序代码之类的事情，以便 if/else 块中最常采用的“分支”是它可以在没有代码跳转的情况下运行（由于管道重置而速度很慢），甚至可以将当前观察到的事实（稍后可能不成立）转变为假设。就像这样，代码被“编译”成机器代码，如果这些假设（到目前为止，由于所有的簿记，观察到总是正确的）最终是错误的，那么机器代码将直接不起作用，然后将添加钩子在整个虚拟机中，如果任何代码碰巧打破了假设，精心设计的机器代码将被标记为现在无效，并且将不再使用。例如，如果您有一个类不是， final则可以对其进行扩展。并且 java 始终是动态分派：如果您调用foo.hello()，您将获得变量所指向的对象的实际类型hello()的实现，而不是表达式本身的类型。java中的类加载本质上是动态的（类可以随时加载，JVM永远不知道它已经“完成加载类”。这意味着必须涉及查找表。这是一个昂贵的烦恼！但是，热点优化器绕过了它并消除了它表：如果优化器发现非最终类当前尚未扩展，或者所有扩展都没有覆盖有问题的实现，那么它可以省略查找表并直接将方法调用链接到实现。还向类加载器添加了钩子，如果加载了任何扩展目标类的类（并更改了相关方法的 impl），则直接跳转到 impl 的机器代码将失效。该方法的实际性能再次急剧下降, 因为 JVM 又回到了慢如糖蜜的方式。如果它仍然运行很多，不用担心。hotspot 会再执行一次，这次考虑到有多个实现。foofoo
一旦此机器代码可用，对此方法的所有调用都将重定向以使用此微调的机器代码运行。这速度快得令人难以置信；事实上，通常比-O3编译的 C 代码更快，因为 JVM 可以考虑运行时行为，而这是 C 编译器永远无法做到的。
然而，通常虚拟机中只有大约 1% 的代码实际上在这种模式下运行。简单的事实是，几乎任何应用程序的所有代码都与性能无关。它不会做任何复杂的事情，不会在“热”时刻运行，就这样。没有。事情。smartypants 的分析只针对 1% 左右的人，这实际上会大量进行。
这可能解释了很大一部分差异：一堆排序算法的循环在 dogslow（非热点）模式下运行，而一旦在第一次排序运行期间完成热点，下一次排序运行就会受益从一开始就热点代码。
其次，数据需要位于缓存页面中，CPU 才能真正快速地完成处理。通常重复计算意味着第一次运行会受到 CPU 必须交换一堆缓存页面的惩罚，而所有未来的运行都不需要付出这个代价，因为内存的相关部分已经在缓存中。
结论很简单：像这样的微基准测试非常复杂，你不能只用 System.nanoTime 来计时，JVM 非常复杂，CPU 非常复杂，即使是那些花时间编写 JVM 本身的冬天工程师也很忙。记录表明他们太愚蠢了，无法猜测这样的表现。所以你绝对没有任何机会。
幸运的是，解决方案也非常非常简单。这些 JVM 工程师想知道东西的运行速度，因此他们编写了一个完整的框架，让您可以进行微基准测试，主动检查热点预热，进行大量空运行，确保优化器不会优化整个算法（这可能会发生这种情况，如果您对列表进行排序，然后将列表扔进垃圾箱，优化器可能会发现整个排序操作最好通过完全跳过它来优化，因为，嘿，如果没有人真正关心排序的结果，为什么要排序，对吧？你需要一个“接收器”来确保优化器不会得出结论，它可能会因为数据被丢弃而导致整个事情变成垃圾！） - 它被称为JMH。在 JMH 中重写您的基准测试并让它发挥作用。您会发现它的时间一致，并且这些时间通常是有意义的（与您所写的内容相比，这几乎没有任何意义）。