Jawaban ini memberikan ikhtisar tingkat tinggi yang bagus tentang pengoptimalan string pendek (SSO). Namun, saya ingin mengetahui lebih detail cara kerjanya dalam praktik, khususnya dalam implementasi libc ++:
Seberapa pendek string harus agar memenuhi syarat untuk SSO? Apakah ini bergantung pada arsitektur target?
Bagaimana implementasi membedakan antara string pendek dan panjang saat mengakses data string? Apakah itu sesederhana
m_size <= 16
atau itu sebuah bendera yang merupakan bagian dari variabel anggota lainnya? (Saya membayangkan itum_size
atau sebagian darinya mungkin juga digunakan untuk menyimpan data string).
Saya menanyakan pertanyaan ini khusus untuk libc ++ karena saya tahu bahwa ini menggunakan SSO, ini bahkan disebutkan di beranda libc ++ .
Berikut beberapa pengamatan setelah melihat sumbernya :
libc ++ bisa dikompilasi dengan dua layout memori yang sedikit berbeda untuk kelas string, ini diatur oleh _LIBCPP_ALTERNATE_STRING_LAYOUT
flag. Kedua tata letak juga membedakan antara mesin little-endian dan big-endian yang membuat kita memiliki total 4 varian berbeda. Saya akan menganggap tata letak "normal" dan little-endian sebagai berikut.
Dengan asumsi lebih lanjut itu size_type
adalah 4 byte dan itu value_type
adalah 1 byte, seperti inilah 4 byte pertama dari sebuah string akan terlihat di memori:
// short string: (s)ize and 3 bytes of char (d)ata
sssssss0;dddddddd;dddddddd;dddddddd
^- is_long = 0
// long string: (c)apacity
ccccccc1;cccccccc;cccccccc;cccccccc
^- is_long = 1
Karena ukuran string pendek berada di atas 7 bit, maka perlu digeser saat mengaksesnya:
size_type __get_short_size() const {
return __r_.first().__s.__size_ >> 1;
}
Demikian pula, pengambil dan penyetel untuk kapasitas string panjang digunakan __long_mask
untuk mengatasi is_long
bit.
Saya masih mencari jawaban untuk pertanyaan pertama saya, yaitu nilai apa yang akan __min_cap
diambil, kapasitas string pendek, untuk arsitektur yang berbeda?
Implementasi perpustakaan standar lainnya
Jawaban ini memberikan gambaran bagus tentang std::string
tata letak memori dalam implementasi pustaka standar lainnya.
sumber
string
headernya di sini , saya sedang memeriksanya saat ini :)Jawaban:
Libc ++
basic_string
dirancang untuk memilikisizeof
3 kata pada semua arsitektur, yaitusizeof(word) == sizeof(void*)
. Anda telah dengan benar membedah bendera panjang / pendek, dan bidang ukuran dalam bentuk pendek.Dalam bentuk singkat, ada 3 kata untuk dikerjakan:
char
, 1 byte menuju ke nol di belakang (libc ++ akan selalu menyimpan nol di belakang data).Ini menyisakan 3 kata dikurangi 2 byte untuk menyimpan string pendek (yaitu terbesar
capacity()
tanpa alokasi).Pada mesin 32 bit, 10 karakter akan masuk ke dalam string pendek. sizeof (string) adalah 12.
Pada mesin 64 bit, 22 karakter akan masuk ke string pendek. sizeof (string) adalah 24.
Tujuan desain utama adalah meminimalkan
sizeof(string)
, sekaligus membuat penyangga internal sebesar mungkin. Alasannya adalah untuk mempercepat konstruksi bergerak dan memindahkan tugas. Semakin besarsizeof
, semakin banyak kata yang harus Anda pindahkan selama pekerjaan konstruksi atau tugas pindah.Bentuk panjang membutuhkan minimal 3 kata untuk menyimpan penunjuk data, ukuran dan kapasitas. Oleh karena itu saya membatasi bentuk pendek untuk 3 kata yang sama. Telah disarankan bahwa ukuran 4 kata mungkin memiliki kinerja yang lebih baik. Saya belum menguji pilihan desain itu.
_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
Ada tanda konfigurasi yang disebut
_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
yang mengatur ulang anggota data sedemikian rupa sehingga "tata letak panjang" berubah dari:untuk:
Motivasi untuk perubahan ini adalah keyakinan bahwa mengutamakan
__data_
akan memiliki beberapa keuntungan kinerja karena penyelarasan yang lebih baik. Upaya telah dilakukan untuk mengukur keunggulan kinerja, dan sulit untuk diukur. Itu tidak akan membuat kinerja lebih buruk, dan mungkin membuatnya sedikit lebih baik.Bendera harus digunakan dengan hati-hati. Ini adalah ABI yang berbeda, dan jika secara tidak sengaja tercampur dengan libc ++ yang
std::string
dikompilasi dengan pengaturan berbeda_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
akan membuat kesalahan waktu proses.Saya merekomendasikan flag ini hanya diubah oleh vendor libc ++.
sumber
string
adalah semua 0 bit. Itu membuat konstruksi default menjadi sangat efisien. Dan jika Anda bersedia melanggar aturan, terkadang bahkan gratis. Misalnya Anda dapatcalloc
mengingat dan hanya mendeklarasikannya penuh dengan string yang dibangun default.int
s sehingga kelas hanya dapat dikemas menjadi 16 byte pada arsitektur 64-bit?sizeof
. Tetapi pada saat yang sama buffer internal untukchar
pergi dari 14 menjadi 22, yang merupakan manfaat yang cukup bagus.The libc ++ pelaksanaan yang agak rumit, saya akan mengabaikan desain alternatif dan kira komputer endian kecil:
Catatan:
__compressed_pair
pada dasarnya adalah pasangan yang dioptimalkan untuk Optimasi Basis Kosong , aliastemplate <T1, T2> struct __compressed_pair: T1, T2 {};
; untuk semua maksud dan tujuan Anda dapat menganggapnya sebagai pasangan biasa. Kepentingannya muncul begitu saja karenastd::allocator
tidak memiliki kewarganegaraan dan karenanya kosong.Oke, ini agak mentah, jadi mari kita periksa mekaniknya! Secara internal, banyak fungsi akan memanggil
__get_pointer()
yang memanggilnya sendiri__is_long
untuk menentukan apakah string menggunakan representasi__long
atau__short
:Sejujurnya, saya tidak terlalu yakin ini adalah Standar C ++ (Saya tahu ketentuan awal selanjutnya
union
tetapi tidak tahu bagaimana itu menyatu dengan penyatuan anonim dan aliasing dilemparkan bersama), tetapi Perpustakaan Standar diizinkan untuk memanfaatkan penerapan yang ditentukan perilaku.sumber
__min_cap
akan dievaluasi untuk arsitektur yang berbeda, saya tidak yakin apa yangsizeof()
akan kembali dan bagaimana hal itu dipengaruhi oleh aliasing.3 * the size of one pointer
dalam kasus ini, yang akan menjadi 12 oktet pada lengkungan 32 bit dan 24 pada lengkungan 64 bit.