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

Question

我正在考虑使用 Go 编写一个主要处理文本的小程序。我很确定，根据我对 Go 和 Python 的了解，Go 会更快。我实际上并没有特别需要疯狂的速度，但我想了解 Go。“Go 会更快”的想法得到了一个简单的测试的支持：# test.pyprint("Hello world")$ time python dummy.pyHello worldreal    0m0.029suser    0m0.019ssys 0m0.010s// test.gopackage mainimport "fmt"func main() {    fmt.Println("hello world")}$ time ./testhello worldreal    0m0.001suser    0m0.001ssys 0m0.000s在原始启动速度方面看起来不错（这完全在意料之中）。高度非科学的理由：$ strace python test.py 2>&1 | wc -l1223$ strace ./test 2>&1 | wc -l174然而，我的下一个人为测试是 Go 处理字符串时的速度有多快，我期待着同样被 Go 的原始速度所震撼。所以，这令人惊讶：# test2.pys = ""for i in range(1000000):    s += "a"$ time python test2.pyreal    0m0.179suser    0m0.145ssys 0m0.013s// test2.gopackage mainfunc main() {    s := ""    for i:= 0; i < 1000000; i++ {        s += "a";    }}$ time ./test2real    0m56.840suser    1m50.836ssys 0m17.653所以 Go比 Python 慢数百倍。现在，我知道这可能是由于Schlemiel the Painter 的算法，这解释了为什么 Go 实现是二次的i（i10 倍大导致 100 倍减速）。然而，Python 的实现似乎要快得多：10 倍以上的循环只会使其速度减慢两倍。如果你 concatenate str(i)，同样的效果仍然存在，所以我怀疑是否存在某种神奇的 JIT 优化s = 100000 * 'a'。如果我print(s)最后，它不会慢很多，所以变量没有被优化出来。除了连接方法的幼稚（每种语言中肯定有更多的惯用方法），这里有什么我误解了，还是在 Go 中比在 Python 中更容易遇到必须处理 C/C++ 的情况处理字符串时的风格算法问题（在这种情况下，直接的 Go 端口可能不像我希望的那样好用，你知道，想想事情并做功课）？或者我是否遇到过 Python 恰好运行良好但在更复杂的使用下崩溃的情况？使用的版本： Python 3.8.2、Go 1.14.2

Answer 1

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

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

• Go 和 Python 都对字符串进行了计数，即字符串被实现为包含长度（字节数，或者对于 Python 3 字符串，Unicode 字符数）和数据指针的双元素标头。

• 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)变大），我们得到了对分配器的 log 2 (n) 次调用，其中 n 是您执行的次数s += "a"。n 为 1000000（一百万），这大约是我们实际上必须调用make_new_string函数并释放（出于 gc 目的，因为收集器使用 refcounts 作为第一遍）旧字符串的 20 倍s。

[编辑：您的源考古导致提交 2c9c7a5f33d，这表明不到一倍，但仍然是乘法增加。对于其他读者，请参阅评论。]

当前的 Go 实现分配的字符串没有单独的容量标头字段（请参阅reflect.StringHeader并注意“不要依赖于此，它在未来的实现中可能会有所不同”）。在缺少引用计数（我们无法在添加两个字符串的运行时例程中判断目标只有一个引用）和无法观察到cap(s)(or 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 的 refcounting 特性使其永不停止：即使 refcount 为 2，refcount ont下降到 1，然后 next assignment tot将其下降到 0，释放内存块以供下一次通过主循环。所以它可能一遍又一遍地拾取同一个内存块。

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

Answer 2

出色地。你永远不应该以这种方式使用字符串连接:-)

在去，试试strings.Buider

package main

import (

 "strings"

)

func main() {

    var b1 strings.Builder

    for i:= 0; i < 1000000; i++ {

        b1.WriteString("a");

    }

}