Pertanyaan Apa mekanisme optimasi string pendek di libc ++?


Jawaban ini memberikan gambaran tingkat tinggi yang bagus tentang optimasi string pendek (SSO). Namun, saya ingin tahu lebih detail cara kerjanya dalam praktik, khususnya di implementasi libc ++:

  • Seberapa singkat string harus agar memenuhi syarat untuk SSO? Apakah ini tergantung pada arsitektur target?

  • Bagaimana penerapannya membedakan antara pendek dan panjang string saat mengakses data string? Apakah sesederhana itu m_size <= 16 atau apakah itu bendera yang merupakan bagian dari beberapa variabel anggota lainnya? (SAYA bayangkan itu m_size atau sebagian mungkin juga digunakan untuk menyimpan data string).

Saya menanyakan pertanyaan ini khusus untuk libc ++ karena saya tahu bahwa itu menggunakan SSO, ini bahkan disebutkan di halaman web libc ++.

Berikut beberapa pengamatan setelah melihat sumber:

libc ++ dapat dikompilasi dengan dua layout memori yang sedikit berbeda untuk kelas string, ini diatur oleh _LIBCPP_ALTERNATE_STRING_LAYOUT bendera. Kedua tata letak juga membedakan antara mesin little-endian dan big-endian yang meninggalkan kita dengan total 4 varian berbeda. Saya akan menganggap tata letak "normal" dan little-endian dalam apa yang berikut.

Dengan asumsi lebih lanjut itu size_type adalah 4 byte dan itu value_type adalah 1 byte, ini adalah apa yang pertama 4 byte string akan terlihat seperti 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 di atas 7 bit, itu perlu digeser ketika mengaksesnya:

size_type __get_short_size() const {
    return __r_.first().__s.__size_ >> 1;
}

Demikian pula, pengambil dan penyetel untuk kapasitas penggunaan string panjang __long_mask untuk bekerja di sekitar is_long sedikit.

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

Implementasi perpustakaan standar lainnya

Jawaban ini memberikan gambaran yang bagus tentang std::string layout memori dalam implementasi perpustakaan standar lainnya.


76
2018-02-11 06:01


asal


Jawaban:


The libc ++ basic_string dirancang untuk memiliki sizeof 3 kata di semua arsitektur, di mana sizeof(word) == sizeof(void*). Anda telah membedah dengan benar bendera panjang / pendek, dan bidang ukuran dalam bentuk singkat.

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

Dalam bentuk singkat, ada 3 kata untuk bekerja dengan:

  • 1 bit pergi ke bendera panjang / pendek.
  • 7 bit pergi ke ukuran.
  • Asumsi char, 1 byte pergi ke null trailing (libc ++ akan selalu menyimpan null di belakang belakang data).

Ini menyisakan 3 kata minus 2 byte untuk menyimpan string pendek (yaitu terbesar capacity() tanpa alokasi).

Pada mesin 32 bit, 10 karakter akan cocok dalam string pendek. sizeof (string) adalah 12.

Pada mesin 64 bit, 22 karakter akan cocok dengan string pendek. sizeof (string) adalah 24.

Tujuan desain utama adalah meminimalkan sizeof(string), sambil membuat buffer internal seluas mungkin. Alasannya adalah untuk mempercepat konstruksi bergerak dan memindahkan tugas. Semakin besar sizeof, semakin banyak kata yang harus Anda pindahkan saat memindahkan konstruksi atau memindahkan tugas.

Bentuk panjang membutuhkan minimal 3 kata untuk menyimpan penunjuk data, ukuran dan kapasitas. Oleh karena itu saya membatasi bentuk pendek ke 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 bendera konfigurasi yang disebut _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT yang menata 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 yang menempatkan __data_ pertama akan memiliki beberapa keunggulan kinerja karena keselarasan yang lebih baik. Suatu usaha dilakukan untuk mengukur keunggulan kinerja, dan itu sulit untuk diukur. Ini 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 tidak sengaja dicampur dengan libc ++ std::string dikompilasi dengan pengaturan yang berbeda _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT akan membuat kesalahan waktu proses.

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


89
2018-02-11 18:25



Itu implementasi libc ++ agak rumit, saya akan mengabaikan desain alternatifnya dan misalkan 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_pair pada dasarnya adalah sepasang yang dioptimalkan untuk Optimalisasi Basis Kosong, aka template <T1, T2> struct __compressed_pair: T1, T2 {};; untuk semua maksud dan tujuan Anda dapat menganggapnya sebagai pasangan reguler. Kepentingannya muncul begitu saja karena std::allocator tidak bernegara dan kosong.

Oke, ini agak mentah, jadi mari kita periksa mekanika! Secara internal, banyak fungsi yang akan dipanggil __get_pointer() yang itu sendiri memanggil __is_long untuk menentukan apakah string menggunakan __long atau __short perwakilan:

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 Standard C ++ (saya tahu ketentuan awal subsequence di union tetapi tidak tahu bagaimana jala dengan serikat anonim dan aliasing dilemparkan bersama-sama), tetapi Perpustakaan Standar diperbolehkan untuk mengambil keuntungan dari implementasi perilaku yang ditetapkan pula.


16
2018-02-11 08:30