Hari ini kita akan mempercepat ikatan garis pendek di Go sebesar 30%. Dan untuk ini kita tidak perlu memodifikasi Go sendiri, semua ini akan diimplementasikan sebagai perpustakaan pihak ketiga .

Di bawah potongan Anda sedang menunggu:

• Membandingkan + , fungsi strings.Builder . strings.Builder dan fungsi gabungan asli
• Buka detail baris internal
• Cukup banyak assembler

Artikel ini juga dapat dianggap sebagai alasan untuk membahas CL123256: runtime, cmd / compile: mengkhususkan concatstring2 . Gagasan untuk memperbaiki daftar perubahan ini dipersilakan.

Segera Hasil

Perbandingan dibuat dengan versi go tip (master) dari kompiler. Anda bisa mendapatkan hasil yang serupa pada versi di sekitar Go 1.5. Perubahan signifikan terakhir pada fungsi concatstrings adalah CL3120: cmd / gc: mengalokasikan buffer untuk string non-escaped pada stack .

 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 menggunakan + .
ConcatBuilder menggunakan strings.Builder dengan pra-alokasi yang benar.
Concat menggunakan fungsi yang kami terapkan sebagai bagian dari cerita ini.

Perbandingan melalui benchstat :

 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) 

Implementasi assembler di bawah GOARCH=AMD64 sedikit lebih cepat dan memiliki optimasi tambahan, yang ada di operator + built-in, tetapi lebih dari itu di bawah ini:

 name old time/op new time/op delta Concat2-8 84.2ns ± 1% 57.1ns ± 3% -32.20% (p=0.000 n=9+9) 

Kami akan mengambil fungsi assembler sebagai kinerja 100% (relatif terhadap seluruh implementasi yang dipertimbangkan).

Hasil untuk garis yang lebih panjang dapat dilihat di README.md . Semakin panjang string, semakin sedikit perbedaan antara implementasi.

Rangkaian naif

Solusi termudah adalah menggunakan operator + .

Semantik dari pernyataan ini adalah sebagai berikut: ambil dua baris dan kembalikan string hasil yang berisi penggabungan kedua baris. Tidak ada jaminan bahwa saluran baru akan dikembalikan. Misalnya, jika ada rangkaian string kosong dan lainnya, runtime dapat mengembalikan argumen yang tidak kosong, menghindari kebutuhan untuk mengalokasikan memori baru dan menyalin data di sana.

Tapi, seperti yang bisa dilihat dari hasil di awal artikel, ini adalah cara paling lambat.

 func concat2operator(x, y string) string { return x + y } 

Peringkat kinerja: 67,8% .

string. Builder

Belum lama ini, tipe baru telah ditambahkan ke Go - string . Builder . Ini adalah analog dari bytes.Buffer . bytes.Buffer , tetapi ketika memanggil metode String() , memori tidak dialokasikan kembali dan data tidak disalin.

Tidak seperti bytes.Buffer , builder tidak mengoptimalkan buffer kecil dan karenanya di bawah pra-mengalokasikan string memori. Jika Anda tidak menggunakan metode Grow , kinerja akan lebih buruk daripada dengan bytes.Buffer . Beberapa regresi di Go 1.11 disebabkan oleh fitur khusus ini (lihat CL113235 ).

Dalam kode kami, untuk kemurnian percobaan, kami akan menghindari kesalahan ini.

 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() } 

Peringkat kinerja: 80,5% (+12,7).

Pembuatan Kode untuk Rangkaian

Jika Anda melihat kode apa yang dihasilkan kompiler untuk operator + , kita akan melihat panggilan ke fungsi concatstring2 , concatstring3 dan sebagainya (hingga concatstring5 inklusif).

 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) 

Lihatlah runtime / string.go sendiri :

 func concatstring2(buf *tmpBuf, a [2]string) string { return concatstrings(buf, a[:]) } func concatstring3(buf *tmpBuf, a [3]string) string { return concatstrings(buf, a[:]) } 

Jadi, tetap mempelajari fungsi concatstrings .
Daftar lengkap tersedia di bawah ini di bawah spoiler, tetapi di sini adalah deskripsi tingkat tinggi:

1. Parameter buf mungkin nil . Buffer ini dialokasikan oleh kompiler jika garis tidak "keluar" dari definisinya. Jika string hidup lebih lama dari bingkai, maka buffer ini akan selalu nil (seperti yang paling sering terjadi). Namun, jika buffer ini tersedia, akan dimungkinkan untuk menghindari alokasi jika hasilnya masuk ke dalamnya (ukurannya adalah 32 byte).
2. Jika semua baris kecuali satu kosong, fungsi akan mengembalikan baris ini. Tetapi pada saat yang sama, garis-garis yang dipilih pada tumpukan dan meninggalkan frame mereka memotong optimasi ini sehingga penelepon tidak menerima memori yang sudah dibebaskan.
3. Selanjutnya, semua baris disalin ke memori baru.

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

Di sini kita melihat beberapa tempat sekaligus yang dapat dioptimalkan untuk kasus tertentu:

• buf paling sering kosong. Ketika kompiler tidak dapat membuktikan bahwa string aman untuk ditempatkan di stack, melewati parameter tambahan dan memeriksa nil di dalam fungsi hanya memberikan overhead.
• Untuk kasus khusus dengan len(a) == 2 kita tidak perlu siklus dan perhitungannya dapat disederhanakan. Dan ini adalah bentuk penggabungan yang paling umum.

Versi untuk semua arsitektur

Untuk mengimplementasikan spesialisasi, kita perlu tahu bagaimana garis direpresentasikan dalam Go. Kompatibilitas biner penting bagi kami, sementara unsafe.Pointer dapat diganti dengan *byte tanpa pengorbanan.

 type stringStruct struct { str *byte len int } 

Kesimpulan penting kedua yang dapat kita tarik dari runtime: baris memulai kehidupannya bisa berubah. Dialokasikan sepotong memori yang direferensikan oleh []byte , yang mencatat isi baris baru, dan hanya setelah itu []byte dibuang, dan memori yang diacunya, disimpan dalam stringStruct .

Bagi yang menginginkan lebih detail, disarankan untuk mempelajari fungsi rawstringtmp dan 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 } 

Kita dapat memutar hampir sama, menggunakan sisi gelap dari paket 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) } 

Kami menyoroti []byte , yang kami gunakan untuk membentuk konten baris baru. Kemudian kita hanya bisa menyelesaikan garis dengan membawanya ke representasi runtime yang diharapkan. Fungsi goString bertanggung jawab untuk ini:

 func goString(ptr *byte, length int) string { s := stringStruct{str: ptr, len: length} return *(*string)(unsafe.Pointer(&s)) } 

Peringkat kinerja: 91.9% (+10.9).

Versi AMD64

Sayangnya, versi sebelumnya dari fungsi tidak memiliki optimasi untuk penggabungan dengan string kosong, dan kami juga melakukan sejumlah perhitungan yang tidak perlu karena ketidakmampuan untuk mengalokasikan memori secara langsung, kami harus bekerja dengan byte slice.

Salah satu fitur menarik dari assembler Go adalah memungkinkan Anda untuk memanggil, misalnya, fungsi runtime yang tidak dapat diekspor. Kita dapat memanggil runtime·mallocgc dari kode assembly walaupun itu bukan bagian dari paket runtime . Kami akan menggunakan properti ini.

Kami juga dapat memeriksa kepemilikan garis memori stack, yang membuatnya aman untuk mengoptimalkan pengembalian salah satu argumen sebagai hasilnya.

Misalkan suatu fungsi dipanggil dengan argumen concat2("", "123") . x adalah string kosong, dan jika y tidak dialokasikan pada stack, kita dapat mengembalikannya sebagai hasil penggabungan.

 //; ,  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 memindahkan * g ke register AX . Membaca di nol offset akan memberikan bidang g.stack.lo , dan g.stack.hi dimulai dengan byte ke-8 (untuk platform 64-bit).

 type g struct { stack struct { lo uintptr // 0(AX) hi uintptr // 8(AX) } stackguard0 uintptr // 16(AX) stackguard1 uintptr // 24(AX) // ...   } 

Badan concatenate mengalokasikan memori, mengisinya dengan kedua baris, dan mengembalikan baris baru.

 #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 

Peringkat kinerja: 100% (+8.6).

Kesimpulannya

Semua kode disediakan sebagai paket khusus.

Apakah dunia siap untuk penggabungan cepat seperti itu? Siapa tahu.

Di awal artikel, CL123256 disebutkan. Dia memiliki beberapa jalur pengembangan:

1. Spesialisasi variasi untuk kasus ketika kompiler tidak mengalokasikan buffer sementara. Ada sedikit pertumbuhan untuk setiap kasus, tetapi mencakup lebih banyak jenis rangkaian dan praktis tidak menambah ukuran kode (baik mesin dan kode Go).
2. Lebih banyak spesialisasi untuk kasus khusus. Keuntungan yang lebih tinggi, tetapi lebih banyak kode mesin, dapat merusak cache instruksi.
3. Banyak kode mesin, untuk setiap kasus khusus dan memmove khusus, dengan cara bagaimana hal ini dilakukan dalam glibc. Di sini terutama muncul pertanyaan tentang kemanfaatan.

Opsi yang diajukan saat ini hanya mempercepat kasus penggabungan sepasang string yang paling umum dan paling sederhana (arity = 2).

Jika Go tidak menerima perubahan ini, maka akselerasi yang sebanding dapat dicapai dengan menerapkan operasi string dalam bentuk perpustakaan pihak ketiga. Kurang nyaman, cantik, dan elegan, tetapi berhasil.