为什么string.intern()方法很慢？

Question

在有人对使用 string.intern() 提出质疑之前，先说一下：出于内存和性能方面的原因，我需要在特定应用中使用它。[1]

到目前为止，我一直使用 String.intern() 并认为这是最有效的方法。然而，我注意到自从很久以前就成为了软件中的瓶颈。[2]

然后，最近我试图使用一个巨大的映射来代替 String.intern()，在其中放置/获取字符串，以便每次获得唯一实例。我预计这会更慢... 但事实上却完全相反！它非常快！将 intern() 替换为推送/轮询映射（实现完全相同）导致速度提高了一个数量级以上。

问题是：为什么 intern() 如此缓慢？！为什么它不被简单地支持映射（或实际上只是定制集合）并且速度非常快呢？我感到困惑。

[1]：对于那些不信服的人：它用于自然语言处理，并且必须处理吉字节的文本，因此需要避免许多相同字符串的实例以避免内存剧增，而引用字符串比较必须足够快。

[2]：没有它（普通字符串）是不可能的，使用它后，这一特定步骤仍然是计算密集型的。

编辑：

由于此帖子的意外关注，在此提供一些代码进行测试：

http://pastebin.com/4CD8ac69

并且将超过 1 百万个字符串的情况放入 intern() 的结果如下：

• HashMap：4 秒
• String.intern()：54 秒

为了避免一些热身/操作系统IO缓存等问题，实验通过交换两个基准测试的顺序来重复进行：

• String.intern(): 69秒
• HashMap: 3秒

如您所见，两者差异非常明显，超过10倍。（使用OpenJDK 1.6.0_22 64位……但我认为使用sun版本的结果类似）

- dagnelies

---

很好的问题，你能给一些“intern（）”慢了多少的指标吗？ - Steve Kuo

你最终会将多少个字符串实例分配给映射/内部化？ - John Vint

你是把intern和同步的Hashtable还是非同步的HashMap进行比较？intern是同步的，这可能是你观察到的很大一部分原因。 - Chris Dodd

对于实习，我建议使用http://guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Interners.html。 - maaartinus

我并没有确切的答案来解释为什么它运行得如此缓慢，但是我已经对我的一个问题进行了更详细的性能测试实现。https://dev59.com/j2kv5IYBdhLWcg3wZwC- - LordOfThePigs

Answer 1

这篇文章讨论了String.intern()的实现。在Java 6和7中，实现使用固定大小（1009）的哈希表，因此随着条目数量增加，性能变为O（n）。可以使用-XX:StringTableSize=N更改固定大小。显然，在Java8中默认大小更大，但问题仍然存在。

- Martin Serrano

Answer 2

最可能导致性能差异的原因是: String.intern()是一种本地方法，调用本地方法会产生大量开销。

为什么它是本地方法呢？很可能是因为它使用了常量池，这是一个低级别的VM构造。

- Michael Borgwardt

---

@Arnaud: 当然不是的。由于在Java早期年代，JVM速度非常慢，因此出于性能考虑使用本地方法可能是有道理的。但这种情况已经改变了10多年。如今，几乎唯一需要使用JNI的原因是访问不属于Java标准API的功能。 - Michael Borgwardt

我可以告诉你确切的原因，它很慢不是因为它是本地方法。如果那是问题，你将期望支付相同的性能惩罚（跨越JVM本地屏障），无论字符串池的大小如何。我的基准测试（https://dev59.com/j2kv5IYBdhLWcg3wZwC-）显示String.intern()的复杂度为O(n^2)，其中n是池中字符串的数量。这个问题的真实答案是：String.intern使用的算法很差，不具有可扩展性。 - LordOfThePigs

调用本地方法不会“产生巨大的开销”。 - Hot Licks

也许你错过了这一点：“标准库中的本地方法不一定经过JNI”。 JNI很耗费资源。调用JDK中的本地方法非常便宜。 - Hot Licks

这个答案只是猜测，而且还是错误的。 - Martin Serrano

Answer 3

@Michael Borgwardt在评论中提到:

intern()在Java语言级别上至少不是同步的。

我认为你的意思是String.intern()方法在String类的源代码中没有声明为synchronized，这确实是一个正确的陈述。

然而：

• 将intern()声明为synchronized只会锁定当前的String实例，因为它是一个实例方法，而不是静态方法。所以他们无法通过这种方式实现字符串池同步。

• 如果你退后一步并考虑一下，字符串池必须执行某种内部同步。如果它不这样做，在多线程应用程序中它将无法使用，因为使用intern()方法的所有代码都没有可行的方式进行外部同步。

因此，字符串池执行的内部同步可能成为使用intern()大量的多线程应用程序中的瓶颈。

- Stephen C

---

仅供参考，我使用普通和同步映射测试了代码。性能差异可以忽略不计。 - dagnelies

@arnaud - 是的。如果在Map上没有争用，那么同步的成本可以忽略不计。当有大量不同的线程同时尝试使用Map时，性能问题就会出现。 - Stephen C

intern() 肯定是同步的，这很可能是性能差异的主要因素。 intern() 必须确保只有一个版本的字符串进入池中，并且该池从各个角度被访问 -- 多个线程、加载类、处理字符串的本地方法。同步问题非常复杂。 - Hot Licks

Answer 4

我没有太多的经验，但从String文档中可以看出：

"当调用intern方法时，如果池中已经包含一个与该String对象相等的字符串（由{@link #equals(Object)}方法确定），则返回池中的字符串。否则，将此String对象添加到池中，并返回对此String对象的引用。"

处理大量对象时，任何涉及哈希的解决方案都会优于不涉及哈希的解决方案。我认为你只是看到了误用Java语言特性的结果。Interning并不是为了充当您使用的字符串映射。您应该使用Map来实现这一点（或者根据情况使用Set）。字符串表是在语言级别上进行优化，而不是应用程序级别。

- Ryan Stewart

---

但是内置的 intern 方法难道不会使用 map 来确定池中是否已经包含该字符串吗？（如果没有，似乎这是一个明显的低效率问题，可以进行改进） - Jason S

实习并不是为了充当您使用的字符串映射。String.intern是公共的，因此可以说它确实是为您使用而设计的。也许OP使用它不正确，但是您的答案并没有真正说明他的用法有什么问题。 - Laurence Gonsalves

HashMap也使用equals()方法，我敢打赌100美元，intern()最终使用了某种哈希表。 - Michael Borgwardt

@Michael Borgwardt 你应该更像个赌徒 :) 我刚看了一下热点VM中的.cpp文件，它肯定使用了某种形式的哈希表。 - John Vint

@John：那你认为intern()为什么表现如此糟糕？你在源代码中找到了相关信息吗？ - alexkelbo