Apakah kode yang ditunjukkan di bawah ini setara dengan kinerja?

// (A).  HasPrefix  . return strings.HasPrefix(s, "#") // (B).    HasPrefix. return len(s) >= len("#") && s[:len("#")] == "#" 

Jawabannya adalah tidak .

Untuk detail dan penjelasan, saya bertanya di bawah kucing.

Selamat siang, sebelum Anda membuka topik, saya ingin memperkenalkan diri.
Nama saya Iskander dan dari waktu ke waktu saya mengirim komit ke repositori golang / go .

Saya dulu melakukan ini atas nama tim Intel Go , tetapi jalur kami berbeda dan sekarang saya adalah kontributor independen. Baru-baru ini saya telah bekerja di vk di tim infrastruktur.

Di waktu senggang, saya membuat berbagai alat untuk Go, seperti go-critic dan go-konsisten . Saya juga menggambar akan menghubungkan .

Ukur itu!

Segera lanjutkan ke perbandingan dan garis besar tolok ukur:

 package benchmark import ( "strings" "testing" ) var s = "#string" func BenchmarkHasPrefixCall(b *testing.B) { for i := 0; i < bN; i++ { _ = strings.HasPrefix(s, "#") _ = strings.HasPrefix(s, "x") } } func BenchmarkHasPrefixInlined(b *testing.B) { for i := 0; i < bN; i++ { _ = len(s) >= len("#") && s[:len("#")] == "#" _ = len(s) >= len("x") && s[:len("x")] == "x" } } 

Alih-alih merekomendasikan benchstat kepada Anda, saya akan menunjukkan benchrun kepada Anda.

Dengan satu perintah, kita dapat menjalankan kedua tolok ukur dan mendapatkan perbandingan:

 go-benchrun HasPrefixCall HasPrefixInlined -v -count=10 . Benchstat results: name old time/op new time/op delta HasPrefixCall-8 9.15ns ± 1% 0.36ns ± 3% -96.09% (p=0.000 n=10+9) 

Opsi dengan embedding manual jauh lebih cepat daripada kode yang diperoleh dengan menanamkan fungsi tubuh dengan kompiler. Mari kita coba mencari tahu mengapa ini terjadi.

strings.HasPrefix

Ingat implementasi strings.HasPrefix :

 // HasPrefix tests whether the string s begins with prefix. func HasPrefix(s, prefix string) bool { return len(s) >= len(prefix) && s[0:len(prefix)] == prefix } 

Fungsi HasPrefix dibangun oleh kompiler.
Anda dapat memverifikasi ini sebagai berikut:

 go build -gcflags='-m=2' strings 2>&1 | grep 'can inline HasPrefix' 

Untuk memanggil strings.HasPrefix dari opsi (A) kita mendapatkan kode mesin berikut:

  MOVQ (TLS), CX CMPQ SP, 16(CX) JLS more_stack fn_body: SUBQ $40, SP MOVQ BP, 32(SP) LEAQ 32(SP), BP XCHGL AX, AX MOVQ s+56(SP), AX CMPQ AX, $1 JGE compare_strings XORL AX, AX MOVB AL, ~ret1+64(SP) MOVQ 32(SP), BP ADDQ $40, SP return: RET compare_strings: MOVQ s+48(SP), AX MOVQ AX, (SP) LEAQ go.string."#"(SB), AX MOVQ AX, 8(SP) MOVQ $1, 16(SP) CALL runtime.memequal(SB) MOVBLZX 24(SP), AX JMP return more_stack: CALL runtime.morestack_noctxt(SB) JMP fn_body 

Abaikan fakta bahwa kode tersebut terlihat seperti mie.

Apa yang harus Anda perhatikan:

• strings.HasPrefix benar-benar dimasukkan, tidak ada panggilan.
• Untuk membandingkan string, runtime.memequal .

Tapi apa yang kemudian dihasilkan untuk versi built-in secara manual, kode dari example (B) ?

  MOVQ s+16(SP), AX CMPQ AX, $1 JLT different_length MOVQ s+8(SP), AX CMPB (AX), $35 // 35 -   "#" SETEQ AL return: MOVB AL, "".~ret1+24(SP) RET different_length: XORL AX, AX JMP 22 

Dan di sini kompiler tidak menghasilkan panggilan ke runtime.memequal dan satu karakter dibandingkan secara langsung. Idealnya, dia seharusnya melakukan hal yang sama untuk opsi pertama.

Kami mengamati sisi lemah pengoptimal Go, dan kami akan menganalisisnya.

Optimasi Ekspresi Konstan

Alasan yang memanggil strings.HasPrefix(s, "#") dapat dioptimalkan adalah karena argumen awalan adalah konstan. Kami tahu panjang dan isinya. Tidak masuk akal untuk memanggil runtime.memequal untuk string pendek, lebih cepat untuk membuat perbandingan karakter "di tempat", menghindari panggilan tambahan.

Seperti yang Anda ketahui, kompiler biasanya memiliki setidaknya dua bagian: compiler frontend dan compiler backend . Yang pertama bekerja dengan tampilan tingkat yang lebih tinggi, yang kedua lebih dekat ke mesin dan tampilan perantara akan terlihat seperti aliran instruksi. Beberapa versi Go telah menggunakan representasi SSA untuk optimisasi di bagian backend dari kompiler.

Lipat konstan, seperti {10*2 => 20} , diterapkan di backend. Secara umum, sebagian besar operasi yang terkait dengan penurunan biaya komputasi ekspresi terletak di bagian kompiler ini. Namun ada beberapa pengecualian.

Satu pengecualian adalah optimalisasi perbandingan string konstan. Ketika kompiler melihat perbandingan string (atau substring) di mana satu atau kedua operan adalah konstanta, kode yang lebih efisien dihasilkan daripada panggilan ke runtime.memequal .

Anda dapat melihat kode sumber yang bertanggung jawab untuk ini di file cmd / compile / internal / gc / walk.go: 3362 .

Penyisipan fungsi terjadi sebelum optimasi ini diluncurkan, tetapi juga di bagian frontend dari kompiler.

Tampaknya semua sama tidak memungkinkan pengoptimalan ini berfungsi dalam kasus kami?

How Go Embeds Function Memanggil

Begini cara penyematan akan terjadi:

 //    : return strings.HasPrefix(s, "#") //  : func HasPrefix(s, prefix string) bool //    : _s, _prefix := s, "#" return len(s) >= len(prefix) && s[:len(prefix)] == prefix 

Ketika menyematkan fungsi, kompiler memberikan argumen ke variabel sementara, yang memecah optimasi, karena algoritma di walk.go tidak melihat konstanta, tetapi argumen dengan variabel. Itu masalahnya.

Omong-omong, ini tidak mengganggu optimasi backend yang dimiliki SSA. Tetapi ada masalah lain di sana, misalnya, ketidakmampuan untuk mengembalikan konstruksi bahasa tingkat tinggi untuk perbandingan efektif mereka (pekerjaan untuk menghilangkan kelemahan ini telah "direncanakan" selama beberapa tahun).

Contoh lain: analisis pelarian

Bayangkan sebuah fungsi yang penting untuk mengalokasikan buffer sementara pada stack:

 func businessLogic() error { buf := make([]byte, 0, 16) // buf    //    . return nil } 

Karena buf tidak "lari", kompiler akan dapat mengalokasikan 16 byte ini di stack, tanpa alokasi di heap. Sekali lagi, semua berkat nilai konstan saat menelepon make . Untuk mengalokasikan memori pada stack, penting bagi kita untuk mengetahui ukuran yang diperlukan, yang akan menjadi bagian dari frame yang dialokasikan untuk pemanggilan fungsi.

Misalkan di masa depan kami ingin mengalokasikan buffer sementara dari berbagai ukuran dan merangkum beberapa logika dalam metode. Kami memperkenalkan abstraksi baru dan memutuskan untuk menggunakan tipe tmpBuf baru di tmpBuf . Fungsi desainnya sangat sederhana:

 func newTmpBuf(sizeHint int) tmpBuf { return tmpBuf{buf: make([]byte, 0, sizeHint)} } 

Mengadaptasi contoh asli:

 func businessLogic() error { - buf := make([]byte, 0, 16) + buf := newTmpBuf(16) // buf    //    . return nil } 

Konstruktor akan disematkan, tetapi alokasi sekarang akan selalu berada di heap, karena alasan yang sama bahwa argumen dilewatkan melalui variabel sementara. Analisis melarikan diri akan melihat make([]byte, 0, _sizeHint) yang tidak termasuk dalam pola pengenalannya untuk make panggilan yang dioptimalkan.

Jika kita memiliki "semuanya seperti manusia", masalahnya tidak akan ada, setelah menanamkan konstruktor newTmpBuf akan jelas bahwa ukurannya masih diketahui pada tahap kompilasi.

Ini mengganggu hampir lebih dari situasi dengan membandingkan string.

Horizons Go 1.13

Situasinya dapat dengan mudah diperbaiki dan saya sudah mengirim bagian pertama dari keputusan .

Jika Anda berpikir bahwa masalah yang dijelaskan dalam artikel tersebut benar-benar membutuhkan solusi, harap acungkan jempol dalam masalah yang terkait .

Posisi saya adalah bahwa menanamkan kode dengan tangan Anda hanya karena itu bekerja lebih cepat di versi Go saat ini salah. Penting untuk memperbaiki cacat ini di pengoptimal, setidaknya ke titik di mana contoh yang dijelaskan di atas berfungsi tanpa regresi kinerja yang tidak terduga.

Jika semuanya berjalan sesuai rencana, optimasi ini akan disertakan dalam rilis Go 1.13.

Terima kasih atas perhatian anda

Tambahan: solusi yang diusulkan

Bagian ini untuk yang paling berani, mereka yang tidak bosan membaca.

Jadi, kami memiliki beberapa tempat yang bekerja lebih buruk ketika menggunakan variabel alih-alih nilainya secara langsung. Solusi yang diusulkan adalah untuk memperkenalkan fungsi baru di frontend bagian compiler, yang memungkinkan Anda untuk mendapatkan nilai terikat terakhir dengan nama. Setelah itu, dalam setiap optimisasi yang mengharapkan nilai konstan, jangan menyerah ketika suatu variabel terdeteksi, tetapi terima status yang disimpan sebelumnya ini.

Tanda tangan fitur baru kami mungkin terlihat seperti ini:

 func getConstValue(n *Node) *Node 

Definisi Node dapat ditemukan di file syntax.go .

Setiap definisi variabel memiliki tag Node dengan tag ONAME . Di dalam Node.Name.Defn sebagian besar variabel ini memiliki nilai inisialisasi.

Jika Node sudah menjadi literal, Anda tidak perlu melakukan apa pun dan kami hanya mengembalikan n . Jika ini ONAME (variabel), maka Anda dapat mencoba mengekstrak nilai inisialisasi yang sama dari n.Name.Defn .

Tapi bagaimana dengan modifikasi antara mendeklarasikan dan membaca variabel yang kita sebut getConstValue ? Jika kita membatasi diri hanya untuk variabel read-only, maka tidak ada masalah. Frontend Go telah memiliki tanda simpul khusus yang menandai nama yang mirip. Jika variabel telah dimodifikasi, getConstValue tidak akan mengembalikan nilai inisialisasi.

Programmer, sebagai suatu peraturan, tidak memodifikasi argumen input tipe numerik dan string, dan ini memungkinkan untuk mencakup sejumlah besar kasus dengan algoritma primitif ini.

Sekarang kami siap mempertimbangkan implementasinya:

 func getConstValue(n *Node) *Node { //    ONAME    definition. if n.Op != ONAME || n.Name.Defn == nil { return n } //   ,     . // ,    ,     //      escape analysis' . maybeModified := n.Assigned() || n.Name.Defn.Assigned() || n.Addrtaken() if maybeModified { return n } // OAS - Node  . // n.Name.Defn.Left -  LHS. // n.Name.Defn.Right -  RHS. // consttype(v)     . //   CTxxx,      . if n.Name.Defn.Op == OAS { v := n.Name.Defn.Right if v != nil && consttype(v) != CTxxx { return v } } return n } 

Berikut cara perubahan kode, yang bergantung pada konstanta:

 - i := indexconst(r) + i := indexconst(getConstValue(r)) 

Hebat, dan bahkan berfungsi:

 n := 10 xs := make([]int, n) //     ! 

Sebelum perubahan ini, analisis pelarian tidak bisa mendapatkan nilai 10 hingga n , itulah sebabnya saya membuat asumsi tentang perlunya menempatkan xs di heap.

Kode di atas secara sintaksis mirip dengan situasi yang diamati selama penyematan. n mungkin variabel sementara yang ditambahkan ketika argumen dilewatkan.

Sayangnya, ada nuansa.

Kami memecahkan masalah untuk variabel lokal yang diperkenalkan melalui OAS , tetapi Go menginisialisasi variabel untuk fungsi bawaan melalui OAS2 . Karena itu, kita perlu perubahan kedua yang memperluas fungsi getConstValue dan sedikit memodifikasi kode inliner itu sendiri, karena, di antara hal-hal lain, OAS2 tidak memiliki bidang OAS2 yang sesuai.

Itu berita buruk. Berita bagus: Saluran #gocontributing muncul di slack berbahasa Rusia , tempat Anda dapat berbagi ide dan rencana, mengajukan pertanyaan, dan mendiskusikan segala sesuatu yang berkaitan dengan berpartisipasi dalam pengembangan Go.