- PVSM.RU - https://www.pvsm.ru -
Сегодня мы будем разгонять склеивание коротких строк в Go на 30%. Причём для этого нам не нужно будет модифицировать сам Go, всё это будет реализованно в виде сторонней библиотеки [1].
Под катом вас ждут:
+
, strings.Builder
и собственной функции конкатенацииДанную статью можно также считать предлогом обсудить CL123256: runtime,cmd/compile: specialize concatstring2 [2]. Идеи по улучшению этого change list'а приветствуются.
BenchmarkConcat2Operator-8 20000000 83.8 ns/op
BenchmarkConcat2Builder-8 20000000 70.9 ns/op
BenchmarkConcat2-8 20000000 62.1 ns/op
BenchmarkConcat3Operator-8 20000000 104 ns/op
BenchmarkConcat3Builder-8 20000000 89.9 ns/op
BenchmarkConcat3-8 20000000 82.1 ns/op
ConcatOperator
использует +
.
ConcatBuilder
использует strings.Builder
с правильной пред-аллокацией.
Concat
использует функцию, которую мы реализуем в рамках этой истории.
Сравнение через benchstat [3]:
name old time/op new time/op delta
Concat2-8 84.2ns ± 1% 62.7ns ± 2% -25.49% (p=0.000 n=9+10)
Concat3-8 103ns ± 3% 83ns ± 4% -19.83% (p=0.000 n=10+9)
Ассемблерная реализация под GOARCH=AMD64
немного быстрее и обладает дополнительной оптимизацией, которая присутствует у встроенного оператора +
, но об этом ниже:
name old time/op new time/op delta
Concat2-8 84.2ns ± 1% 57.1ns ± 3% -32.20% (p=0.000 n=9+9)
Ассемблерную функцию будем брать как 100% производительности (относительно остальных рассматриваемых реализаций).
Результаты для более длинных строк можно увидеть в README.md [1]. Чем длиннее строка, тем менее выражена разница между реализациями.
Самым простым решением является использование оператора +
.
Семантика этого оператора такая: взять две строки и вернуть строку-результат, которая содержит сцепление обеих строк. При этом нет гарантии, что будет возвращена новая строка. Например, если происходит сцепление пустой строки и любой другой, runtime может вернуть непустой аргумент, избегая необходимости выделять новую память и копировать туда данные.
Но, как видно из результатов в начале статьи, это самый медленный способ.
func concat2operator(x, y string) string {
return x + y
}
Оценка производительности: 67.8%.
Не так давно в Go добавили новый тип — strings.Builder [4]. Это аналог bytes.Buffer
, но при вызове метода String()
не происходит повторного выделения памяти и копирования данных.
В отличие от bytes.Buffer
, builder не имеет оптимизации малого буфера [5] и, следовательно, предварительно аллоцированной памяти под строку. Если не использовать метод Grow
, производительность будет хуже, чем в случае с bytes.Buffer
. Несколько регрессий в Go 1.11 вызваны именно этой особенностью (см. CL113235 [6]).
В нашем коде, для чистоты эксперимента, мы будем избегать этой ошибки.
func concat2builder(x, y string) string {
var builder strings.Builder
builder.Grow(len(x) + len(y)) // Только эта строка выделяет память
builder.WriteString(x)
builder.WriteString(y)
return builder.String()
}
Оценка производительности: 80.5% (+12.7).
Если посмотреть, какой код генерирует компилятор для оператора +
, мы увидим вызовы функций concatstring2
, concatstring3
и так далее (до concatstring5
включительно).
func concat2codegen(x, y) string { return x + y }
// => CALL runtime.concatstring2(SB)
func concat3codegen(x, y, z) string { return x + y + z }
// => CALL runtime.concatstring3(SB)
Заглянем в сам runtime/string.go [7]:
func concatstring2(buf *tmpBuf, a [2]string) string {
return concatstrings(buf, a[:])
}
func concatstring3(buf *tmpBuf, a [3]string) string {
return concatstrings(buf, a[:])
}
Значит, осталось изучить функцию concatstrings
.
Полный листинг доступен ниже под спойлером, а вот высокоуровневое описание:
buf
может быть nil
. Этот буфер выделяется компилятором, если строка не "убегает" из области своего определения. Если же строка живёт дольше, чем фрейм, то этот буфер всегда будет nil
(как чаще всего и происходит). Однако если этот буфер доступен, получится избежать аллокации в случае, если результат в него влезает (его размер — 32 байта).// concatstrings implements a Go string concatenation x+y+z+...
// The operands are passed in the slice a.
// If buf != nil, the compiler has determined that the result does not
// escape the calling function, so the string data can be stored in buf
// if small enough.
func concatstrings(buf *tmpBuf, a []string) string {
idx := 0
l := 0
count := 0
for i, x := range a {
n := len(x)
if n == 0 {
continue
}
if l+n < l {
throw("string concatenation too long")
}
l += n
count++
idx = i
}
if count == 0 {
return ""
}
// If there is just one string and either it is not on the stack
// or our result does not escape the calling frame (buf != nil),
// then we can return that string directly.
if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
return a[idx]
}
s, b := rawstringtmp(buf, l)
for _, x := range a {
copy(b, x)
b = b[len(x):]
}
return s
}
Здесь мы видим сразу несколько мест, которые могут быть оптимизированы для частного случая:
buf
чаще всего пустой. Когда компилятор не смог доказать, что строку безопасно размещать на стеке, передача лишнего параметра и проверка его на nil
внутри функции дают лишь накладные расходы.len(a) == 2
нам не нужен цикл и вычисления можно упростить. А это самый распространённый вид конкатенации.При выполнении ./make.bash
(сборка Go компилятора и stdlib) видим 445 конкатенаций с двумя операндами:
Итого 89% конкатенаций от двух аргументов попадают пот оптимизацию.
Для утилиты go
имеем:
Для реализации специализации нам потребуется знать, как в Go представлены строки. Нам важна бинарная совместимость, при этом unsafe.Pointer
можно заменить на *byte
без каких-либо жертв.
type stringStruct struct {
str *byte
len int
}
Второй важный вывод, который мы можем сделать из рантайма: строки начинают свою жизнь мутабельными. Выделяется участок памяти, на который ссылается []byte
, в который записывается содержимое новой строки, и только после этого []byte
выбрасывается, а память, на которую он ссылался, сохраняется в stringStruct
.
Для тех, кому хочется больше деталей, предлагается изучить функции rawstringtmp
и rawstring
.
// rawstring allocates storage for a new string. The returned
// string and byte slice both refer to the same storage.
// The storage is not zeroed. Callers should use
// b to set the string contents and then drop b.
func rawstring(size int) (s string, b []byte) {
p := mallocgc(uintptr(size), nil, false)
stringStructOf(&s).str = p
stringStructOf(&s).len = size
*(*slice)(unsafe.Pointer(&b)) = slice{p, size, size}
return
}
Мы можем провернуть примерно то же самое, воспользовавшись тёмной стороной пакета unsafe
:
func concat2(x, y string) string {
length := len(x) + len(y)
if length == 0 {
return ""
}
b := make([]byte, length)
copy(b, x)
copy(b[len(x):], y)
return goString(&b[0], length)
}
Мы выделяем []byte
, который используем для формирования содержимого новой строки. Затем нам остаётся лишь финализировать строку приведением её к ожидаемому рантаймом представлению. За это отвечает функция goString
:
func goString(ptr *byte, length int) string {
s := stringStruct{str: ptr, len: length}
return *(*string)(unsafe.Pointer(&s))
}
Оценка производительности: 91.9% (+10.9).
К сожалению, предыдущая версия функции не имеет оптимизации для конкатенации с пустой строкой, а ещё мы выполняем некоторое количество лишних вычислений из-за невозможности выделить память напрямую, приходится работать со слайсом байт.
Одной из интересных особенностей Go ассемблера является то, что он позволяет вызывать, например, неэкспортируемые функции рантайма. Мы можем вызвать runtime·mallocgc
из ассемблерного кода даже если он не является частью пакета runtime
. Этим свойством мы и воспользуемся.
Также мы можем проверять принадлежность строк стековой памяти, что делает безопасной оптимизацию возврата одного из аргументов в качестве результата.
Допустим, функция вызвана с аргументами concat2("", "123")
. x
— пустая строка, и если y
не выделен на стеке, мы можем вернуть его в качестве результата конкатенации.
//; Считаем, что x и y имеют тип stringStruct.
//; CX - y.str.
//; SI - y.len.
maybe_return_y:
//; Проверка на вхождения указателя в стек.
MOVQ (TLS), AX //; *g
CMPQ CX, (AX)
JL return_y //; если y_str < g.stack.lo
CMPQ CX, 8(AX)
JGE return_y //; если y_str >= g.stack.hi
JMP concatenate //; y на стеке, нужна новая аллокация
return_y:
MOVQ CX, ret+32(FP) //; stringStruct.len
MOVQ SI, ret+40(FP) //; stringStruct.str
RET
MOVQ (TLS), AX
переместит *g [8] в регистр AX
. Чтение по нулевому смещению даст поле g.stack.lo
, а с 8-го байта начинается g.stack.hi
(для 64-битной платформы).
Тело concatenate
выделяет память, заполняет его обеими строками, и возвращает новую строку.
#include "textflag.h"
#include "funcdata.h"
TEXT ·Strings(SB), 0, $48-48
NO_LOCAL_POINTERS // Костыль для избежания ошибки.
MOVQ x+0(FP), DX
MOVQ x+8(FP), DI
MOVQ y+16(FP), CX
MOVQ y+24(FP), SI
TESTQ DI, DI
JZ maybe_return_y // x - пустая строка, попробуем вернуть y
TESTQ SI, SI
JZ maybe_return_x // y - пустая строка, попробуем вернуть x
concatenate:
LEAQ (DI)(SI*1), R8 // len(x) + len(y)
// Выделяем память для новой строки.
MOVQ R8, 0(SP)
MOVQ $0, 8(SP)
MOVB $0, 16(SP)
CALL runtime·mallocgc(SB)
MOVQ 24(SP), AX // Указатель на выделенную память
MOVQ AX, newstr-8(SP)
// Копируем x.
MOVQ x+0(FP), DX
MOVQ x+8(FP), DI
MOVQ AX, 0(SP)
MOVQ DX, 8(SP)
MOVQ DI, 16(SP)
CALL runtime·memmove(SB)
// Копируем y со смещения len(x).
MOVQ x+8(FP), DI
MOVQ y+16(FP), CX
MOVQ y+24(FP), SI
MOVQ newstr-8(SP), AX
LEAQ (AX)(DI*1), BX
MOVQ BX, 0(SP)
MOVQ CX, 8(SP)
MOVQ SI, 16(SP)
CALL runtime·memmove(SB)
// Возврат новой строки.
MOVQ newstr-8(SP), AX
MOVQ x+8(FP), R8
ADDQ y+24(FP), R8
MOVQ AX, ret+32(FP)
MOVQ R8, ret+40(FP)
RET
maybe_return_y:
// Проверка на вхождения указателя в стек.
MOVQ (TLS), AX // *g
CMPQ CX, (AX)
JL return_y // если y_ptr < stk.lo
CMPQ CX, 8(AX)
JGE return_y // если y_ptr >= stk.hi
JMP concatenate // y на стеке, нужна новая аллокация
return_y:
MOVQ CX, ret+32(FP)
MOVQ SI, ret+40(FP)
RET
maybe_return_x:
// Проверка на вхождения указателя в стек.
MOVQ (TLS), AX // *g
CMPQ DX, (AX)
JL return_x // если x_ptr < stk.lo
CMPQ DX, 8(AX)
JGE return_x // если x_ptr >= stk.hi
JMP concatenate // x на стеке, нужна новая аллокация
return_x:
MOVQ DX, ret+32(FP)
MOVQ DI, ret+40(FP)
RET
Если вам интересна природа NO_LOCAL_POINTERS
в этом коде, можете почитать Calling a Go function from asm ("fatal error: missing stackmap") [9].
Оценка производительности: 100% (+8.6).
Весь код предоставлен в качестве пакета concat [1].
Готов ли мир к такой быстрой конкатенации? Who knows.
В начале статьи был упомянут CL123256 [2]. У него есть несколько путей развития:
Текущий предложенный вариант ускоряет только наиболее частый и простой случай конкатенации пары строк (арность=2).
Если в Go не примут это изменение, то сравнимого ускорения можно будет добиться с помощью реализации операций над строками в виде сторонней библиотеки. Менее удобно, красиво и элегантно, но зато работает.
Автор: quasilyte
Источник [10]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/286363
Ссылки в тексте:
[1] сторонней библиотеки: https://github.com/Quasilyte/concat
[2] CL123256: runtime,cmd/compile: specialize concatstring2: https://go-review.googlesource.com/c/go/+/123256
[3] benchstat: https://godoc.org/golang.org/x/perf/cmd/benchstat
[4] strings.Builder: https://golang.org/src/strings/builder.go
[5] малого буфера: https://github.com/golang/go/blob/3a28a711db15efd97c7675fccf0d2d0f2245a99b/src/bytes/buffer.go#L20
[6] CL113235: https://go-review.googlesource.com/c/go/+/113235
[7] runtime/string.go: https://github.com/golang/go/blob/master/src/runtime/string.go
[8] *g: https://github.com/golang/go/blob/a80a7f0e77fab42cebe61c43b98e0959b740def2/src/runtime/runtime2.go#L338
[9] Calling a Go function from asm ("fatal error: missing stackmap"): https://groups.google.com/forum/#!topic/golang-nuts/a6NKBbL9fX0
[10] Источник: https://habr.com/post/417479/?utm_campaign=417479
Нажмите здесь для печати.