java - 为什么快速排序的 JDK 实现有堆栈溢出的风险？

Question

前几天我看到一个演讲，演讲者使用了 McIlroy 的论文中概述的技术 A Killer Adversary for Quicksort 为将触发 O(n²) 行为的原始类型生成 Arrays.sort 的输入。该序列导致基准选择始终只将数组大小减少一个常数，这导致 Java Arrays.sort 函数导致堆栈溢出。

根据 the source files from the JDK , Arrays.sort1 快速排序实现函数没有防止堆栈溢出的保护措施。通过让排序例程不触发两次递归调用，而是使用 while 循环为较大的子数组重用当前堆栈帧并且只递归一次(在较小的子数组上)，总是可以使快速排序永远不会堆栈溢出。这导致最小的性能下降，并且不可能导致任何合理大小的输入的堆栈溢出，因为堆栈深度永远不会超过大小为 n 的输入的 O(log n) 个堆栈帧。作者也可以使用 introsort算法，它修改快速排序以在快速排序递归深度超过某个限制时切换到最坏情况 O(n log n) 排序算法，以防止这种情况发生。

Arrays.sort 的作者有什么理由不选择这样做吗？内置排序算法可能导致堆栈溢出似乎是一个严重的问题，因为它可以通过触发重复的堆栈溢出来对此类系统发起 DoS 攻击。

Answer 1

为什么？因为解决问题太过分了。

所使用的算法在除异常情况外的所有情况下都是稳定的，如果这些情况比通常更可能发生，那么这种情况将受到外部保护。这就是为什么他们有 API 文档来定义幕后使用的算法。所以您可以抵御它。

出现破坏算法的特定顺序的可能性微乎其微。

我希望如果您足够仔细地观察，就会发现导致几乎所有标准 JVM 结构崩溃的数据集。 抵御它们的成本是多少？这种成本是否值得付出努力以及由于防御措施导致算法不可避免的退化。