Объединение строк намного быстрее в Python, чем Go

Question

Я использую Go, чтобы написать небольшую программу, которая в основном обрабатывает текст. Я почти уверен, исходя из того, что я слышал о Go и Python, что Go будет значительно быстрее. На самом деле у меня нет конкретной потребности в c безумных скоростях, но я бы хотел узнать 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

Выглядит неплохо с точки зрения сырой скорости запуска (что вполне ожидаемо). Высоко ненаучное обоснование c:

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

---

Тем не менее, мой следующий надуманный тест состоял в том, насколько быстрым будет Go при игре с струнами, и я ожидал, что он будет так же поражен * Сырая скорость 1054 *. Итак, это было удивительно:

# 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 в 1021 * сотни раз медленнее, чем Python.

Теперь я знаю, что это, вероятно, связано с алгоритмом Шлемеля Пейнтера , который объясняет, почему реализация Go является квадратичной c в i (i в 10 раз больше приводит к Замедление в 100 раз).

Однако реализация Python выглядит намного быстрее: увеличение в 10 раз циклов только замедляет его вдвое. Тот же эффект сохраняется, если вы объединяете str(i), поэтому я сомневаюсь, что происходит какая-то магическая оптимизация JIT до s = 100000 * 'a'. И это не намного медленнее, если I print(s) в конце, поэтому переменная не оптимизируется.

Наивность методов конкатенации в стороне (несомненно, есть идиоматические c пути в каждом языке) Есть ли здесь что-то, что я неправильно понял, или просто в Go, чем в Python, проще столкнуться с случаями, когда вам приходится иметь дело с проблемами алгоритмического стиля C / C ++ c при обработке строк (в которых если прямой Go порт может быть не таким ... 1036 * может -зенять, как я могу надеяться, не думая о чем-то и не выполняя мою домашнюю работу)?

или сталкивался ли я с случаем, когда Python работает хорошо, но разваливается при более сложном использовании?

Используемые версии: Python 3.8.2, Go 1.14. 2

Answer 1

TL; Сводка DR: в основном вы тестируете два средства реализации / сборщика мусора и сильно взвешиваете масштаб на стороне Python (как бы случайно, но это то, что оптимизировали люди Python в некоторый момент).

Чтобы развернуть мои комментарии в реальный ответ:

• И Go, и Python имеют подсчитанные строки, т.е. строки реализованы как заголовок из двух элементов, содержащий длину (количество байтов или, для Python 3 строк, количество символов Unicode) и указатель данных.

• Оба Go и Python являются мусором -собранные (GCed) языки. То есть на обоих языках вы можете выделить память, не беспокоясь об ее освобождении самостоятельно: система автоматически об этом позаботится.

• Но базовые реализации отличаются, довольно немного этот конкретный важный способ: используемая вами версия Python имеет счетчик ссылок G C. Используемая вами система Go этого не делает.

При подсчете ссылок внутренние биты обработчика строки Python могут сделать это. Я express обозначу как Go (или, по крайней мере, псевдо- Go), хотя фактическая реализация Python находится в C, и я не сделал все детали правильно выстроенными:

// 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 ₂ (n) обращений к распределителю, где n - количество раз Вы делаете s += "a". При n, равном 1000000 (миллиону), это примерно в 20 раз больше, чем нужно для вызова функции make_new_string и освобождения (для целей g c, поскольку сборщик использует refcounts в качестве первого прохода) старой строки s.

[Редактировать: исходная археология привела к commit 2c9c7a5f33d , что предполагает меньшее удвоение, но все же мультипликативное увеличение. Для других читателей см. комментарий .]

Текущая реализация Go выделяет строки без отдельного поля заголовка емкости (см. reflect.StringHeader и обратите внимание на большое предупреждение который говорит "не зависит от этого, он может отличаться в будущих реализациях"). Между отсутствием refcount - мы не можем сказать в подпрограмме времени выполнения, которая добавляет две строки, что у цели есть только одна ссылка - и неспособностью наблюдать эквивалент cap(s) (или cap(s.data)), Go среда выполнения должна каждый раз создавать новую строку. Это один миллион выделенных памяти.

Чтобы показать, что код Python действительно использует refcount, возьмите исходный 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 G C работает более агрессивно, чем Python. Go G C внутренне сильно отличается, требуя барьеров записи и случайного поведения "остановить мир" (из всех программ, которые не выполняют работу G C). Характер перерасчета Python G C позволяет ему никогда не останавливаться: даже при пересчете 2, пересчет по t падает до 1, а затем следующее присвоение t сбрасывает его до нуля, освобождая память блок для повторного использования в следующей поездке через основной l oop. Так что, вероятно, он снова и снова забирает один и тот же блок памяти.

(Если моя память верна, Python 'перераспределяет строки и проверяет refcount, чтобы разрешить трюк с расширением на месте) было не во всех версиях Python. Возможно, впервые оно было добавлено около Python 2.4 или около того. Эта память чрезвычайно расплывчата, и быстрый поиск в Google не обнаружил никаких доказательств тем или иным способом. [Редактировать: Python 2.7.4, по-видимому.])

Answer 2

Хорошо. Никогда не используйте конкатенацию строк таким образом: -)

в go, попробуйте strings.Buider

package main

import (
 "strings"
)

func main() {

    var b1 strings.Builder

    for i:= 0; i < 1000000; i++ {
        b1.WriteString("a");
    }
}