Apakah tidak efisien untuk menggabungkan string satu per satu?

Saya ingat kembali dari hari-hari saya pemrograman di C bahwa ketika dua string bergabung, OS harus mengalokasikan memori untuk string yang bergabung, maka program dapat menyalin semua teks string ke area baru dalam memori, maka memori lama harus secara manual dilepaskan. Jadi, jika ini dilakukan beberapa kali seperti dalam kasus bergabung dalam daftar, OS harus terus mengalokasikan lebih banyak memori, hanya untuk itu dirilis setelah penggabungan berikutnya. Cara yang jauh lebih baik untuk melakukan ini dalam C adalah menentukan ukuran total string gabungan dan mengalokasikan memori yang diperlukan untuk seluruh daftar string yang digabungkan.

Sekarang dalam bahasa pemrograman modern (C # misalnya), saya biasanya melihat konten koleksi yang digabungkan bersama dengan mengulangi koleksi dan menambahkan semua string, satu per satu, ke referensi string tunggal. Apakah ini tidak efisien, bahkan dengan kekuatan komputasi modern?

Penjelasan Anda mengapa tidak efisien itu akurat, setidaknya dalam bahasa yang saya kenal (C, Java, C #), meskipun saya tidak setuju bahwa secara umum lazim untuk melakukan penggabungan string dalam jumlah besar. Dalam C # kode saya bekerja, ada penggunaan berlebihan StringBuilder, String.Format, dll yang semuanya menyimpan techiniques untuk menghindari over-realokasi memori.

Jadi untuk mendapatkan jawaban atas pertanyaan Anda, kami harus mengajukan pertanyaan lain: jika tidak pernah benar-benar masalah untuk merangkai string, mengapa kelas suka StringBuilderdan StringBufferada ? Mengapa penggunaan kelas semacam itu termasuk dalam buku dan kelas pemrograman semi-pemula? Mengapa saran pengoptimalan yang tampaknya pra-matang begitu menonjol?

Jika sebagian besar pengembang penggabung string mendasarkan jawaban mereka semata-mata pada pengalaman, sebagian besar akan mengatakan itu tidak akan membuat perbedaan dan akan menghindari penggunaan alat-alat seperti itu demi "lebih mudah dibaca" for (int i=0; i<1000; i++) { strA += strB; }. Tetapi mereka tidak pernah mengukurnya.

Jawaban sebenarnya untuk pertanyaan ini dapat ditemukan dalam jawaban SO ini , yang mengungkapkan bahwa dalam satu contoh, ketika menggabungkan 50.000 string (yang tergantung pada aplikasi Anda, mungkin merupakan kejadian umum), bahkan yang kecil, menghasilkan hit performa 1000x .

Jika kinerja secara harfiah tidak berarti apa-apa, tentu saja disatukan. Tetapi saya akan tidak setuju bahwa menggunakan alternatif (StringBuilder) sulit atau kurang dapat dibaca , dan oleh karena itu akan menjadi praktik pemrograman yang masuk akal yang seharusnya tidak meminta pertahanan "optimasi prematur".

MEMPERBARUI:

Saya pikir apa yang terjadi, mengetahui platform Anda dan mengikuti praktik terbaiknya, yang sayangnya tidak universal . Dua contoh dari dua "bahasa modern" yang berbeda:

1. Dalam jawaban SO yang lain , karakteristik kinerja sebaliknya yang tepat (array.join vs + =) ditemukan terkadang benar dalam JavaScript . Di beberapa browser, rangkaian string tampaknya dioptimalkan secara otomatis, dan dalam kasus lain tidak. Jadi rekomendasinya (setidaknya dalam pertanyaan SO), adalah untuk menyatukan dan tidak khawatir tentang hal itu.
2. Dalam kasus lain, kompiler Java dapat secara otomatis mengganti concatenation dengan konstruk yang lebih efisien seperti StringBuilder. Namun, seperti yang orang lain tunjukkan, ini tidak pasti, tidak dijamin, dan menggunakan StringBuilder tidak mengganggu keterbacaan. Dalam kasus khusus ini, saya cenderung merekomendasikan untuk tidak menggunakan penggabungan untuk koleksi besar atau mengandalkan perilaku kompiler Java indeterministik. Demikian pula, di .NET, tidak ada optimasi semacam itu dilakukan , pernah.

Ini bukan dosa utama untuk tidak mengetahui setiap nuansa dari setiap platform segera, tetapi mengabaikan masalah platform penting seperti ini hampir akan seperti pindah dari Jawa ke C ++ dan tidak peduli tentang deallocating memori.

Itu tidak efisien, kira-kira untuk alasan yang Anda jelaskan. String dalam C # dan Java tidak dapat diubah. Operasi pada string mengembalikan instance terpisah alih-alih memodifikasi yang asli, tidak seperti di C. Ketika menggabungkan beberapa string, instance terpisah dibuat pada setiap langkah. Mengalokasikan dan kemudian mengumpulkan sampah contoh yang tidak terpakai dapat menyebabkan kinerja hit. Hanya kali ini manajemen memori ditangani oleh pengumpul sampah untuk Anda.

Baik C # dan Java memperkenalkan kelas StringBuilder sebagai string yang bisa berubah-ubah khusus untuk jenis tugas ini. Persamaan dalam C akan menggunakan daftar tautan string terkonvergensi alih-alih bergabung dengan mereka dalam array. C # juga menawarkan metode Gabung yang mudah pada string untuk bergabung dengan koleksi string.

Sebenarnya itu adalah penggunaan siklus CPU yang kurang efisien, jadi Anda benar. Tetapi bagaimana dengan waktu pengembang, biaya perawatan, dll. Jika Anda menambahkan biaya waktu ke persamaan, hampir selalu lebih efisien untuk melakukan yang termudah, lalu jika perlu, profil dan optimalkan bit yang lambat.
"Aturan Pertama Optimalisasi Program: Jangan lakukan itu. Aturan Kedua Optimalisasi Program (hanya untuk para ahli!): Jangan lakukan itu dulu."

Sangat sulit untuk mengatakan apa pun tentang kinerja tanpa tes praktis. Baru-baru ini saya sangat terkejut mengetahui bahwa dalam JavaScript gabungan string naif biasanya lebih cepat daripada solusi "make list and join" yang direkomendasikan (uji di sini , bandingkan t1 dengan t4). Saya masih bingung mengapa itu terjadi.

Beberapa pertanyaan yang mungkin Anda tanyakan ketika beralasan tentang kinerja (terutama terkait penggunaan memori) adalah: 1) seberapa besar input saya? 2) seberapa pintar kompiler saya? 3) bagaimana cara runtime saya mengelola memori? Ini tidak lengkap, tetapi ini adalah titik awal.

1. Seberapa besar input saya?

   Solusi yang kompleks sering kali memiliki overhead tetap, mungkin dalam bentuk operasi tambahan yang harus dilakukan, atau mungkin dalam memori tambahan yang diperlukan. Karena solusi-solusi tersebut dirancang untuk menangani kasus-kasus besar, para pelaksana biasanya tidak memiliki masalah untuk memperkenalkan biaya tambahan tersebut, karena keuntungan bersih lebih penting daripada mengoptimalkan kode secara mikro. Jadi, jika input Anda cukup kecil, solusi naif mungkin memiliki kinerja yang lebih baik daripada yang kompleks, jika hanya untuk menghindari overhead ini. (menentukan apa yang "cukup kecil" adalah bagian yang sulit)

2. Seberapa pintar kompiler saya?

   Banyak kompiler cukup pintar untuk "mengoptimalkan" variabel yang ditulis, tetapi tidak pernah membaca. Demikian juga, kompiler yang baik mungkin juga dapat mengubah rangkaian string naif ke penggunaan (inti) pustaka dan, jika banyak dari mereka dibuat tanpa bacaan, tidak perlu mengubahnya kembali menjadi string di antara operasi tersebut (bahkan jika kode sumber Anda tampaknya melakukan hal itu). Saya tidak tahu apakah ada kompiler di luar sana yang melakukan itu, atau sejauh mana hal itu dilakukan (AFAIK Java setidaknya mengganti beberapa concat dalam ekspresi yang sama dengan urutan operasi StringBuffer), tetapi itu kemungkinan.

3. Bagaimana cara kerja runtime saya mengelola memori?

   Dalam CPU modern, bottleneck biasanya bukan prosesor, tetapi cache; jika kode Anda mengakses banyak alamat memori "jauh" dalam waktu singkat, waktu yang diperlukan untuk memindahkan semua memori antara tingkat cache melebihi sebagian besar optimisasi dalam instruksi yang digunakan. Itu sangat penting dalam runtime dengan pengumpul sampah generasi, karena variabel yang paling baru dibuat (di dalam lingkup fungsi yang sama, misalnya) biasanya akan berada di alamat memori yang berdekatan. Runtime itu juga secara rutin memindahkan memori bolak-balik antara panggilan metode.

   Salah satu cara itu dapat mempengaruhi rangkaian string (disclaimer: ini adalah tebakan liar, saya tidak tahu cukup banyak untuk mengatakan dengan pasti) akan jika memori untuk yang naif dialokasikan dekat dengan sisa kode yang menggunakannya (bahkan jika itu mengalokasikan dan melepaskannya beberapa kali), sementara memori untuk objek perpustakaan dialokasikan jauh dari itu (sehingga banyak konteks berubah ketika kode Anda menghitung, perpustakaan mengkonsumsi, kode Anda menghitung lebih, dll akan menghasilkan banyak kesalahan cache). Tentu saja untuk input besar OTOH, cache yang hilang akan terjadi, sehingga masalah alokasi ganda menjadi lebih jelas.

Yang mengatakan, saya tidak menganjurkan penggunaan metode ini atau itu, hanya pengujian dan profiling dan benchmarking harus mendahului setiap analisis teoritis tentang kinerja, karena sebagian besar sistem saat ini terlalu rumit untuk sepenuhnya dipahami tanpa keahlian yang mendalam dalam subjek.

Joel menulis artikel yang bagus tentang hal ini beberapa waktu lalu. Seperti yang ditunjukkan beberapa orang lain, ini sangat tergantung pada bahasa. Karena cara string diimplementasikan dalam C (nol diakhiri, tanpa bidang panjang), rutin perpustakaan strcat standar sangat tidak efisien. Joel menghadirkan alternatif hanya dengan perubahan kecil yang jauh lebih efisien.

Apakah tidak efisien untuk menggabungkan string satu per satu?

Tidak.

Sudahkah Anda membaca 'Tragedi Sedih Teater Mikro-Optimalisasi' ?