Ind*_*oad 0 python performance string-concatenation go
我正在考虑使用 Go 编写一个主要处理文本的小程序。根据我对 Go 和 Python 的了解，我非常确定 Go 会更快。我实际上并没有对疯狂速度的具体需求，但我想了解 Go。
“Go 将会变得更快”的想法得到了一个简单测试的支持：
# test.py
print("Hello world")
$ time python dummy.py
Hello world
real 0m0.029s
user 0m0.019s
sys 0m0.010s
$ time python dummy.py
Hello world
real 0m0.029s
user 0m0.019s
sys 0m0.010s
// test.go
package main
import "fmt"
func main() {
fmt.Println("hello world")
}
就原始启动速度而言看起来不错（这完全是预期的）。高度非科学的理由：
$ time ./test
hello world
real 0m0.001s
user 0m0.001s
sys 0m0.000s
然而，我的下一个人为测试是 Go 在处理字符串时的速度有多快，我预计同样会被 Go 的原始速度所震惊。所以，这是令人惊讶的：
$ strace python test.py 2>&1 | wc -l
1223
$ strace ./test 2>&1 | wc -l
174
$ time python test2.py
real 0m0.179s
user 0m0.145s
sys 0m0.013s
# test2.py
s = ""
for i in range(1000000):
s += "a"
$ time python test2.py
real 0m0.179s
user 0m0.145s
sys 0m0.013s
所以 Go比 Python 慢数百倍。
现在，我知道这可能是由于Schlemiel the Painter 的算法，这解释了为什么 Go 的实现是二次的i（i大 10 倍导致速度慢 100 倍）。
然而，Python 实现似乎要快得多：循环 10 倍只会使其速度减慢两倍。如果您连接，同样的效果仍然存在str(i)，所以我怀疑是否存在某种神奇的 JIT 优化s = 100000 * 'a'。如果我在最后，它并没有慢多少print(s)，所以变量没有被优化掉。
撇开连接方法的天真不谈（每种语言肯定有更惯用的方法），这里是否有我误解的地方，或者在 Go 中比在 Python 中更容易遇到必须处理 C/C++ 的情况处理字符串时的算法问题（在这种情况下，直接的 Go 端口可能不会像我希望的那样，而不必，你知道，思考事情并做我的作业）？
或者我是否遇到过 Python 运行良好但在更复杂的使用下崩溃的情况？
使用的版本： Python 3.8.2、Go 1.14.2
TL;DR 摘要：基本上，您正在测试两个实现的分配器/垃圾收集器，并在 Python 端对规模进行很大的权重（可以说是偶然，但这是 Python 人员在某些时候优化的东西） 。
\n\n将我的评论扩展为真正的答案：
\n\nGo 和 Python 都对字符串进行计数，即，字符串被实现为包含长度（字节计数，或者对于 Python 3 字符串，Unicode 字符计数）和数据指针的双元素标头。
Go 和 Python 都是垃圾收集（GCed）语言。也就是说，在两种语言中，您都可以分配内存，而不必担心自己释放内存：系统会自动处理该问题。
但底层实现有所不同，在这一特定的重要方面有很大不同：您使用的 Python 版本具有引用计数GC。您使用的 Go 系统没有。
通过引用计数，Python 字符串处理程序的内部位可以做到这一点。我将其表示为 Go（或至少是伪 Go），尽管实际的 Python 实现是用 C 编写的，而且我还没有正确排列所有细节：
\n\n// add (append) new string t to existing string s\nfunc add_to_string(s, t string_header) string_header {\n need = s.len + t.len\n if s.refcount == 1 { // can modify string in-place\n data = s.data\n if cap(data) >= need {\n copy_into(data + s.len, t.data, t.len)\n return s\n }\n }\n // s is shared or s.cap < need\n\n new_s := make_new_string(roundup(need))\n // important: new_s has extra space for the next call to add_to_string\n\n copy_into(new_s.data, s.data, s.len)\n copy_into(new_s.data + s.len, t.data, t.len)\n s.refcount--\n if s.refcount == 0 {\n gc_release_string(s)\n }\n return new_s\n}\n通过过度分配\xe2\x80\x94对need值进行四舍五入，使其cap(new_s)变得很大\xe2\x80\x94，我们得到了对分配器的log 2 (n)次调用，其中n是你执行的次数s += "a"。当 n 为 1000000（一百万）时，这大约是我们实际上必须调用该make_new_string函数并释放（出于 gc 目的，因为收集器使用引用计数作为第一遍）旧 string 的 20倍s。
[编辑：你的源考古导致提交 2c9c7a5f33d，这表明不到一倍，但仍然是乘法增长。其他读者请参阅评论。]
\n\n当前的 Go 实现分配字符串时没有单独的容量标头字段（请参阅reflect.StringHeader并注意“不要依赖于此，在未来的实现中可能会有所不同”的重要警告）。由于缺乏引用计数\xe2\x80\x94，我们无法在添加两个字符串的运行时例程中判断目标只有一个引用\xe2\x80\x94，并且无法观察到cap(s)（或cap(s.data)) 的等价物， Go 运行时每次都必须创建一个新字符串。那是一百万个内存分配。
为了证明 Python 代码确实使用了引用计数，请使用原始 Python：
\n\ns = ""\n\nfor i in range(1000000):\n s += "a"\n并添加第二个变量，t如下所示：
s = ""\nt = s\n\nfor i in range(1000000):\n s += "a"\n t = s\n执行时间的差异令人印象深刻：
\n\n$ time python test2.py\n 0.68 real 0.65 user 0.03 sys\n$ time python test3.py\n 34.60 real 34.08 user 0.51 sys\n修改后的 Python 程序在同一系统上仍然击败 Go (1.13.5)：
\n\n$ time ./test2\n 67.32 real 103.27 user 13.60 sys\n我没有进一步探究细节，但我怀疑Go GC 的运行速度比 Python 更积极。Go GC 内部非常不同，需要写屏障和偶尔的“停止世界”行为（所有不执行 GC 工作的 goroutine）。Python GC 的引用计数性质使其永远不会停止：即使引用计数为 2，引用计数也会下降t到 1，然后下一次赋值将t其降至零，从而释放内存块，以便在下一次循环中重新使用主循环。所以它可能会一遍又一遍地获取相同的内存块。
（如果我没记错的话，Python 的“过度分配字符串并检查引用计数以允许就地扩展”技巧并不存在于所有版本的 Python 中。它可能首先是在 Python 2.4 左右添加的。这个记忆极其模糊，谷歌快速搜索并没有以任何方式找到任何证据。[编辑：Python 2.7.4，显然。]）
\n