为什么可变字符串比不可变字符串慢？

Question

为什么可变字符串比不可变字符串慢呢？

补充说明：

>>> import UserString
... def test():
...     s = UserString.MutableString('Python')
...     for i in range(3):
...         s[0] = 'a'
... 
... if __name__=='__main__':
...     from timeit import Timer
...     t = Timer("test()", "from __main__ import test")
...     print t.timeit()
13.5236170292



>>> import UserString
... def test():
...     s = UserString.MutableString('Python')
...     s = 'abcd'
...     for i in range(3):
...         s = 'a' + s[1:]
... 
... if __name__=='__main__':
...     from timeit import Timer
...     t = Timer("test()", "from __main__ import test")
...     print t.timeit()
6.24725079536


>>> import UserString
... def test():
...     s = UserString.MutableString('Python')
...     for i in range(3):
...         s = 'a' + s[1:]
... 
... if __name__=='__main__':
...     from timeit import Timer
...     t = Timer("test()", "from __main__ import test")
...     print t.timeit()
38.6385951042

我觉得我在第二个测试中使用 s = UserString.MutableString('Python') 的原因很明显。

Answer 1

我不知道不可变对象（比如字符串）是否真的慢很多，但它们在编程时让思考变得简单，因为对象或字符串的状态是不能改变的。这对我来说是不可变性最重要的特点。

此外，你可能会认为不可变字符串会更快，因为它们的状态较少（也就是不容易改变），这可能意味着它们占用的内存更少，处理器的运算周期也更少。

我在网上搜索时发现了一篇有趣的文章，想引用其中的一段：

知道一个字符串是不可变的 让我们在构建时就能轻松安排它—— 固定且不变的存储需求

Answer 2

在Python中，如果字符串是不可变的，系统可以把它存储起来，并通过它在内存中的地址来引用。这意味着，当比较两个字符串时，Python只需要比较它们在内存中的地址（除非其中一个字符串没有被存储）。另外，要注意并不是所有的字符串都是被存储的。我见过一些构造出来的字符串，它们并没有被存储。

而对于可变字符串，比较字符串就需要逐个字符地进行比较，并且还需要在不同的位置存储相同的字符串（因为内存分配是有成本的），或者添加一些逻辑来跟踪一个字符串被引用了多少次，如果有多个地方在使用这个字符串，就得在每次修改时都复制一份。

看起来Python在字符串比较方面做了优化。这是有道理的，因为在大多数情况下，字符串操作都涉及到字符串比较，所以对于大多数使用场景来说，这是一种最低的共同需求。

不可变字符串的另一个好处是，它们可以被用作哈希值，这对于用作字典的键是必要的。想象一下，如果字符串是可变的，会发生什么情况：

s = 'a'
d = {s : 1}
s = s + 'b'
d[s] = ?

我想Python可以跟踪哪些字典使用了哪些字符串作为键，并在字符串被修改时更新它们的哈希表，但这会给字典的插入带来额外的负担。可以说，在Python中几乎所有操作都离不开字典的插入或查找，这样的话就会非常糟糕。这也会增加字符串操作的负担。

Answer 3

在一个假设的编程语言中，如果有可变和不可变的字符串类型（其实我想不出有什么语言是这样的，比如Python和Java只有不可变字符串，想要可变字符串就得通过其他方式，这样会增加复杂性，可能会稍微影响性能），那么在性能上就没有太大区别。例如，在C++中，使用std::string和const std::string应该不会影响性能（当然，编译器可能会因为不可变性而更好地优化代码，但我不知道现实中有没有编译器真的这样做过）。

不可变字符串在Java和Python中确实可以带来很大的优化。例如，如果字符串被哈希处理，哈希值可以被缓存，这样就不需要重新计算（因为字符串不会改变）——这在Python中特别重要，因为Python大量使用哈希字符串（用于集合和字典的查找），甚至在“幕后”也在使用。这样就不需要为了防止之前的字符串改变而重新创建新的副本——每次需要这个字符串时，都可以直接引用同一个副本。Python还大量使用“字符串驻留”，这可能让比较操作变得非常快速——可以把它想象成一种更高级的方式，利用字符串的不可变性来缓存常见操作的结果。

当然，这并不是说每个编译器都会利用所有可能的优化。例如，当请求字符串的一部分时，其实没有必要创建一个新对象并复制数据——新的部分可以引用旧的部分，只需加个偏移量（和独立存储的长度），这对处理大字符串时的多个部分提取来说可能是个很好的优化。Python并没有这样做，因为如果不特别注意内存管理，可能会导致“大的”字符串在内存中一直存在，而实际上只需要其中的一小部分——但这是一种权衡，其他实现可能会选择这样做（当然，这样会增加内存管理的复杂性，编译器和运行时的代码也会变得更复杂，更难调试）。

我只是简单提了一下这些内容——如果可变和不可变的字符串类型都可以互换使用，很多这些优势就很难保持（我猜这也是为什么，至少根据我目前的了解，C++编译器实际上并不去做这样的优化，尽管它们通常非常关注性能）。但是，通过只提供不可变字符串作为基本数据类型（因此在需要可变字符串时会隐含接受一些缺点），像Java和Python这样的语言可以获得各种各样的好处——性能问题只是其中一部分（例如，Python选择只允许不可变的基本类型可哈希，这并不是为了性能，而是为了集合和字典的行为更加清晰和可预测！）。