python - Python 中的字符串连接比 Go 快得多

Question

我正在考虑使用 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

// 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

在原始启动速度方面看起来不错(这完全在意料之中)。高度非科学的理由:

$ strace python test.py 2>&1 | wc -l
1223
$ strace ./test 2>&1 | wc -l
174

然而，我的下一个人为测试是 Go 处理字符串时的速度有多快，我期待着同样被 Go 的原始速度所震撼。所以，这令人惊讶:

# test2.py
s = ""

for i in range(1000000):
    s += "a"

$ time python test2.py
real    0m0.179s
user    0m0.145s
sys 0m0.013s

// test2.go
package main

func main() {

    s := ""

    for i:= 0; i < 1000000; i++ {
        s += "a";
    }
}

$ time ./test2
real    0m56.840s
user    1m50.836s
sys 0m17.653

所以 Go 比 Python 慢数百倍。

现在，我知道这可能是由于 Schlemiel the Painter's algorithm ，这就解释了为什么 Go 实现在 i 中是二次方的。 (i 大 10 倍导致减速 100 倍)。

然而，Python 的实现似乎要快得多:10 倍以上的循环只会使其速度减慢两倍。如果您连接 str(i)，同样的效果仍然存在，所以我怀疑 s = 100000 * 'a' 是否存在某种神奇的 JIT 优化继续。如果我 print(s) 也不会慢很多最后，所以变量没有被优化。

除了连接方法的幼稚(每种语言中肯定有更多的惯用方法)，这里有什么我误解了，还是在 Go 中比在 Python 中更容易遇到必须处理 C/C++ 的情况处理字符串时的风格算法问题(在这种情况下，直接的 Go 端口可能不像我希望的那样好，你知道，想想事情并做功课)？

或者我是否遇到过 Python 恰好运行良好但在更复杂的使用下崩溃的情况？

使用的版本:Python 3.8.2、Go 1.14.2

Answer 1

TL；DR 总结:基本上，您正在测试两个实现的分配器/垃圾收集器，并在 Python 端对规模进行加权(偶然，但这是 Python 人员在某些时候优化的东西)。

要将我的评论扩展为真正的答案:

Go 和 Python 都计算了字符串，即字符串被实现为一个包含长度(字节数，或者对于 Python 3 字符串，Unicode 字符数)和数据指针的双元素 header 。

Go 和 Python 都是垃圾收集 (GCed) 语言。也就是说，在这两种语言中，您都可以分配内存而不必担心自己释放它:系统会自动处理。

但是底层实现不同，在这个特殊的一个重要方面有很大不同:你使用的 Python 版本有一个引用计数 GC。您使用的 Go 系统没有。

通过引用计数，Python 字符串处理程序的内部位可以做到这一点。尽管实际的 Python 实现是用 C 语言实现的，而且我还没有正确排列所有细节，但我会将其表示为 Go(或至少是伪 Go):

// add (append) new string t to existing string s
func add_to_string(s, t string_header) string_header {
    need = s.len + t.len
    if s.refcount == 1 { // can modify string in-place
        data = s.data
        if cap(data) >= need {
            copy_into(data + s.len, t.data, t.len)
            return s
        }
    }
    // s is shared or s.cap < need

    new_s := make_new_string(roundup(need))
    // important: new_s has extra space for the next call to add_to_string

    copy_into(new_s.data, s.data, s.len)
    copy_into(new_s.data + s.len, t.data, t.len)
    s.refcount--
    if s.refcount == 0 {
        gc_release_string(s)
    }
    return new_s
}

通过超额分配——四舍五入 need值使得 cap(new_s)很大——我们得到了对分配器的 log2(n) 调用，其中 n 是你执行的次数 s += "a" . n 为 1000000(一百万)，这大约是我们实际调用 make_new_string 的 20 倍。函数和释放(出于 gc 目的，因为收集器使用引用计数作为第一遍)旧字符串 s .

[编辑:你的源考古导致commit 2c9c7a5f33d ，这表明增长不到一倍，但仍然是乘法增长。对于其他读者，请参阅 comment .]

当前的 Go 实现分配的字符串没有单独的容量头字段(参见 reflect.StringHeader 并注意“不要依赖于此，在 future 的实现中可能会有所不同”)。在缺少引用计数(我们无法在添加两个字符串的运行时例程中判断目标只有一个引用)和无法观察到 cap(s) 的等价物之间。 (或 cap(s.data) )，Go 运行时每次都必须创建一个新字符串。那是一百万个内存分配。

为了证明 Python 代码确实使用了引用计数，请使用您原来的 Python:

s = ""

for i in range(1000000):
    s += "a"

并添加第二个变量 t像这样:

s = ""
t = s

for i in range(1000000):
    s += "a"
    t = s

执行时间的差异令人印象深刻:

$ time python test2.py
        0.68 real         0.65 user         0.03 sys
$ time python test3.py
       34.60 real        34.08 user         0.51 sys

修改后的 Python 程序在同一系统上仍然胜过 Go (1.13.5):

$ time ./test2
       67.32 real       103.27 user        13.60 sys

我还没有进一步深入细节，但我怀疑 Go GC 比 Python 运行得更积极。 Go GC 在内部非常不同，需要写入障碍和偶尔的“停止世界”行为(所有不执行 GC 工作的 goroutine)。 Python GC 的引用计数特性使其永不停止:即使引用计数为 2，t 上的引用计数下降到 1，然后下一个分配到 t将其降至零，释放内存块以在下一次通过主循环时重复使用。所以它可能一遍又一遍地拾取同一个内存块。

(如果我的内存是正确的，Python 的“过度分配字符串并检查引用计数以允许就地扩展”技巧并非在所有版本的 Python 中。它可能首先在 Python 2.4 左右添加。这个内存非常模糊和快速的谷歌搜索并没有以任何方式找到任何证据。[编辑:显然是 Python 2.7.4。])