Apa mekanisme pengoptimalan string pendek di libc ++?

102

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 <= 16atau itu sebuah bendera yang merupakan bagian dari variabel anggota lainnya? (Saya membayangkan itu m_sizeatau 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_LAYOUTflag. 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_typeadalah 4 byte dan itu value_typeadalah 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_maskuntuk mengatasi is_longbit.

Saya masih mencari jawaban untuk pertanyaan pertama saya, yaitu nilai apa yang akan __min_capdiambil, kapasitas string pendek, untuk arsitektur yang berbeda?

Implementasi perpustakaan standar lainnya

Jawaban ini memberikan gambaran bagus tentang std::stringtata letak memori dalam implementasi pustaka standar lainnya.

ValarDohaeris
sumber
libc ++ menjadi open-source, Anda dapat menemukan stringheadernya di sini , saya sedang memeriksanya saat ini :)
Matthieu M.
Anda mungkin tertarik dengan Pengoptimalan String Kecil dan Operasi Pindahkan
Ali
@ Matthieu M .: Saya pernah melihatnya sebelumnya, sayangnya ini adalah file yang sangat besar, terima kasih atas bantuannya untuk memeriksanya.
ValarDohaeris
@ Ali: Saya telah tersandung dalam hal ini saat mencari di Google. Namun, posting blog ini secara eksplisit mengatakan bahwa itu hanya ilustrasi SSO dan bukan varian yang sangat dioptimalkan yang akan digunakan dalam praktiknya.
ValarDohaeris

Jawaban:

120

Libc ++ basic_stringdirancang untuk memiliki sizeof3 kata pada semua arsitektur, yaitu sizeof(word) == sizeof(void*). Anda telah dengan benar membedah bendera panjang / pendek, dan bidang ukuran dalam bentuk pendek.

nilai apa yang akan digunakan __min_cap, kapasitas string pendek untuk arsitektur yang berbeda?

Dalam bentuk singkat, ada 3 kata untuk dikerjakan:

  • 1 bit untuk bendera panjang / pendek.
  • 7 bit untuk ukuran.
  • Dengan asumsi 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 besar sizeof, 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_LAYOUTyang mengatur ulang anggota data sedemikian rupa sehingga "tata letak panjang" berubah dari:

struct __long
{
    size_type __cap_;
    size_type __size_;
    pointer   __data_;
};

untuk:

struct __long
{
    pointer   __data_;
    size_type __size_;
    size_type __cap_;
};

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::stringdikompilasi dengan pengaturan berbeda _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTakan membuat kesalahan waktu proses.

Saya merekomendasikan flag ini hanya diubah oleh vendor libc ++.

Howard Hinnant
sumber
17
Tidak yakin apakah ada kompatibilitas lisensi antara libc ++ dan Facebook Folly, tetapi FBstring berhasil menyimpan karakter tambahan (yaitu 23) dengan mengubah ukuran ke kapasitas yang tersisa , sehingga dapat melakukan tugas ganda sebagai terminator null untuk string pendek 23 karakter .
TemplateRex
20
@TemplateRex: Itu pintar. Namun jika libc ++ mengadopsinya akan membutuhkan libc ++ untuk melepaskan satu karakteristik lain yang saya suka tentang std :: string: Default yang dibangun stringadalah semua 0 bit. Itu membuat konstruksi default menjadi sangat efisien. Dan jika Anda bersedia melanggar aturan, terkadang bahkan gratis. Misalnya Anda dapat callocmengingat dan hanya mendeklarasikannya penuh dengan string yang dibangun default.
Howard Hinnant
6
Ah, 0-init memang bagus! BTW, FBstring memiliki 2 bit flag, yang menunjukkan string pendek, menengah dan besar. Ini menggunakan SSO untuk string hingga 23 karakter, dan kemudian menggunakan wilayah memori malloc-ed untuk string hingga 254 karakter dan lebih dari itu mereka melakukan COW (tidak lagi legal di C ++ 11, saya tahu).
TemplateRex
Mengapa ukuran dan kapasitas tidak dapat disimpan dalam ints sehingga kelas hanya dapat dikemas menjadi 16 byte pada arsitektur 64-bit?
phuclv
@ LưuVĩnhPhúc: Saya ingin mengizinkan string yang lebih besar dari 2Gb pada 64-bit. Biayanya memang lebih besar sizeof. Tetapi pada saat yang sama buffer internal untuk charpergi dari 14 menjadi 22, yang merupakan manfaat yang cukup bagus.
Howard Hinnant
21

The libc ++ pelaksanaan yang agak rumit, saya akan mengabaikan desain alternatif dan kira komputer endian kecil:

template <...>
class basic_string {
/* many many things */

    struct __long
    {
        size_type __cap_;
        size_type __size_;
        pointer   __data_;
    };

    enum {__short_mask = 0x01};
    enum {__long_mask  = 0x1ul};

    enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
                      (sizeof(__long) - 1)/sizeof(value_type) : 2};

    struct __short
    {
        union
        {
            unsigned char __size_;
            value_type __lx;
        };
        value_type __data_[__min_cap];
    };

    union __ulx{__long __lx; __short __lxx;};

    enum {__n_words = sizeof(__ulx) / sizeof(size_type)};

    struct __raw
    {
        size_type __words[__n_words];
    };

    struct __rep
    {
        union
        {
            __long  __l;
            __short __s;
            __raw   __r;
        };
    };

    __compressed_pair<__rep, allocator_type> __r_;
}; // basic_string

Catatan: __compressed_pairpada dasarnya adalah pasangan yang dioptimalkan untuk Optimasi Basis Kosong , alias template <T1, T2> struct __compressed_pair: T1, T2 {};; untuk semua maksud dan tujuan Anda dapat menganggapnya sebagai pasangan biasa. Kepentingannya muncul begitu saja karena std::allocatortidak 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_longuntuk menentukan apakah string menggunakan representasi __longatau __short:

bool __is_long() const _NOEXCEPT
    { return bool(__r_.first().__s.__size_ & __short_mask); }

// __r_.first() -> __rep const&
//     .__s     -> __short const&
//     .__size_ -> unsigned char

Sejujurnya, saya tidak terlalu yakin ini adalah Standar C ++ (Saya tahu ketentuan awal selanjutnya uniontetapi tidak tahu bagaimana itu menyatu dengan penyatuan anonim dan aliasing dilemparkan bersama), tetapi Perpustakaan Standar diizinkan untuk memanfaatkan penerapan yang ditentukan perilaku.

Matthieu M.
sumber
Terima kasih atas jawaban mendetail ini! Satu-satunya bagian yang saya lewatkan adalah apa yang __min_capakan dievaluasi untuk arsitektur yang berbeda, saya tidak yakin apa yang sizeof()akan kembali dan bagaimana hal itu dipengaruhi oleh aliasing.
ValarDohaeris
1
@ValarDohaeris penerapannya telah ditentukan. biasanya, Anda akan mengharapkan 3 * the size of one pointerdalam kasus ini, yang akan menjadi 12 oktet pada lengkungan 32 bit dan 24 pada lengkungan 64 bit.
justin