Java 7中的String.substring复杂度问题

Question

在Java 6之前，我们有一个在String上具有恒定时间子字符串的方法。 在Java 7中，为什么他们决定使用复制char数组 - 并降级为线性时间复杂度，而像StringBuilder这样的东西正好是用于此目的？

- anoopelias

---

为避免长度较小的字符串触发垃圾回收，可以防止任意大的char[]被回收。 - Mike Samuel

使用 StringBuilder 应该可以解决这个问题，不是吗？ - anoopelias

使用StringBuilder可以让你在意识到问题存在时解决它。但它不能修复现有代码中的内存泄漏。这种改变可以修复现有代码中的内存泄漏，并且由于缓冲区复制通常是硬件支持的，所以对于任何适合于一个虚拟内存页面的子字符串，最终不会产生线性时间成本。 - Mike Samuel

Answer 1

为什么他们决定这样做在Oracle bug #4513622 : (str) keeping a substring of a field prevents GC for object中有讨论：

当你调用String.substring，就像例子中一样，不会为存储分配一个新的字符数组。它使用原始字符串的字符数组。因此，只有当子字符串的引用也可以被垃圾回收时，原始字符串的字符数组才能被垃圾回收。这是一种有意的优化，以防止在常见情况下使用子字符串时进行过多的分配。不幸的是，有问题的代码遇到了原始数组开销明显的情况。要同时优化两种极端情况是困难的。任何关于空间/大小权衡的优化通常都很复杂，而且往往是特定于平台的。

还有这个note，指出曾经的优化根据测试结果变成了性能下降：

长时间以来，我们一直在进行准备和计划，以移除java.lang.String中的偏移量和计数字段。这两个字段使得多个String实例可以共享相同的字符缓冲区。共享字符缓冲区对于旧的基准测试来说是一个重要的优化，但是对于当前的真实世界代码和基准测试来说，不共享后备缓冲区实际上更好。只有在非常频繁使用String.substring的情况下，共享字符数组后备缓冲区才能获得优势。受到负面影响的情况可能包括解析器和编译器，但是当前的测试结果显示，总体上这个改变是有益的。

- Andy Thomas

Answer 2

如果您有一个短命的、大型父字符串的长期小子字符串，那么支持父字符串的大char[]将无法在小子字符串移出作用域之前被垃圾回收。这意味着子字符串可能会占用比人们预期更多的内存。

唯一性能显著优于Java 6的情况是当某人从大型父字符串中取出一个大的子字符串时，这是非常罕见的情况。

显然，他们决定这种变化所带来的微小性能成本被旧方式导致的隐藏内存问题所抵消。决定因素是问题被隐藏了，而不是有解决方法。

- ILMTitan

---

trim()会从一个大的父字符串中取出一个较小的子字符串，并且经常被使用。 - Don

由于这个（糟糕的..）设计决策，算法性能受损是常见而不是罕见的情况。 - WestCoastProjects

Answer 3

这只是解决JVM垃圾收集限制的低效方式。

在Java 7之前，如果我们想避免垃圾回收无法工作的问题，我们可以始终复制子字符串而不是保留子字符串引用。这只是对复制构造函数的额外调用:

String smallStr = new String(largeStr.substring(0,2));

但是现在，我们无法再拥有一个常数时间的子字符串操作。太糟糕了。

- Alex

---

这是完全正确的。许多类型的程序都从共享子字符串的使用中受益。编译器和解析器是最受伤的类型操作的很好的示例，但损坏远不止于那些特定类型的程序。 - WestCoastProjects

有没有人知道有什么第三方库/代码，具有自定义实现 CharSequence（或类似内容），可以复制“旧”的子字符串行为？我经常需要处理类似于 CSV 的大型文件（500+MB），每当我对它们进行分析时，我发现至少有 10% 的处理时间似乎浪费在对 Arrays.copyOfRange() 的调用上。 - Simon Berthiaume

@SimonBerthiaume 性能错误在于首先创建String实例，这已经带有不必要的复制操作，甚至在调用substring之前。由于每个CharsetDecoder（包括封装在Reader中的那些）都在CharBuffer上运行，因此这是您的起点。而且它已经是解决方案了，因为它实现了CharSequence，所以您可以将其传递给诸如正则表达式模式匹配引擎之类的工具，并具有无需复制的subSequence和slice操作。您只需要创建最终的匹配结果字符串。即使是简单的java.util.Scanner也是这样工作的。 - Holger

现在我们可以使用 subSequence(startIndex: Int, endIndex: Int): CharSequence。 - SL5net

Answer 4

这将会对后缀数组等数据结构的复杂度造成很大影响。Java应该提供一些替代方法来获取原始字符串的一部分。

- Heisenberg

Answer 5

我认为主要的动机是最终将String和它的char[]“共存”。现在它们位于不同的位置，这对缓存行造成了重大惩罚。如果每个String都拥有自己的char[]，JVM可以将它们合并在一起，读取速度会更快。

- ZhongYu