Arti akronim SSO dalam konteks std :: string

Dalam pertanyaan C ++ tentang pengoptimalan dan gaya kode , beberapa jawaban merujuk ke "SSO" dalam konteks mengoptimalkan salinan std::string. Apa arti SSO dalam konteks itu?

Jelas bukan "single sign on". "Optimasi string bersama", mungkin?

Latar Belakang / Gambaran Umum

Operasi pada variabel otomatis ("dari tumpukan", yang merupakan variabel yang Anda buat tanpa memanggil malloc/ new) umumnya jauh lebih cepat daripada yang melibatkan toko gratis ("tumpukan", yang merupakan variabel yang dibuat menggunakan menggunakan new). Namun, ukuran array otomatis tetap pada waktu kompilasi, tetapi ukuran array dari toko gratis tidak. Selain itu, ukuran tumpukan terbatas (biasanya beberapa MiB), sedangkan penyimpanan gratis hanya dibatasi oleh memori sistem Anda.

SSO adalah Optimasi String Pendek / Kecil. A std::stringbiasanya menyimpan string sebagai penunjuk ke free store ("the heap"), yang memberikan karakteristik kinerja yang sama seperti jika Anda menelepon new char [size]. Ini mencegah stack overflow untuk string yang sangat besar, tetapi bisa lebih lambat, terutama dengan operasi penyalinan. Sebagai optimasi, banyak implementasi std::stringmembuat array otomatis kecil, seperti char [20]. Jika Anda memiliki string yang 20 karakter atau lebih kecil (diberikan contoh ini, ukuran sebenarnya bervariasi), ia menyimpannya secara langsung dalam array itu. Ini menghindari kebutuhan untuk menelepon newsama sekali, yang mempercepat segalanya.

EDIT:

Saya tidak berharap jawaban ini menjadi sangat populer, tetapi karena itu, izinkan saya memberikan implementasi yang lebih realistis, dengan peringatan bahwa saya tidak pernah benar-benar membaca implementasi SSO "di alam liar".

Detail implementasi

Minimal, std::stringkebutuhan untuk menyimpan informasi berikut:

• Ukuran
• Kapasitas
• Lokasi data

Ukurannya bisa disimpan sebagai std::string::size_typeatau sebagai penunjuk hingga akhir. Satu-satunya perbedaan adalah apakah Anda ingin mengurangi dua pointer ketika pengguna memanggil sizeatau menambahkan size_typeke pointer ketika pengguna memanggil end. Kapasitas dapat disimpan dengan cara baik juga.

Anda tidak membayar apa yang tidak Anda gunakan.

Pertama, pertimbangkan implementasi naif berdasarkan apa yang saya uraikan di atas:

class string {
public:
    // all 83 member functions
private:
    std::unique_ptr<char[]> m_data;
    size_type m_size;
    size_type m_capacity;
    std::array<char, 16> m_sso;
};

Untuk sistem 64-bit, itu umumnya berarti std::stringmemiliki 24 byte 'overhead' per string, ditambah 16 byte untuk buffer SSO (16 dipilih di sini bukan 20 karena persyaratan padding). Tidaklah masuk akal untuk menyimpan ketiga anggota data tersebut ditambah sejumlah karakter lokal, seperti dalam contoh sederhana saya. Jika m_size <= 16, maka saya akan memasukkan semua data m_sso, jadi saya sudah tahu kapasitasnya dan saya tidak perlu pointer ke data. Jika m_size > 16, maka saya tidak perlu m_sso. Sama sekali tidak ada tumpang tindih di mana saya membutuhkan semuanya. Solusi cerdas yang tidak membuang ruang akan terlihat sedikit lebih seperti ini (hanya untuk tujuan yang belum teruji, contohnya):

class string {
public:
    // all 83 member functions
private:
    size_type m_size;
    union {
        class {
            // This is probably better designed as an array-like class
            std::unique_ptr<char[]> m_data;
            size_type m_capacity;
        } m_large;
        std::array<char, sizeof(m_large)> m_small;
    };
};

Saya berasumsi bahwa sebagian besar implementasi lebih terlihat seperti ini.

SSO adalah singkatan untuk "Small String Optimization", sebuah teknik di mana string kecil tertanam dalam tubuh kelas string daripada menggunakan buffer yang dialokasikan secara terpisah.

Seperti yang sudah dijelaskan oleh jawaban lain, SSO berarti Optimasi String Kecil / Pendek . Motivasi di balik optimasi ini adalah bukti yang tidak dapat disangkal bahwa aplikasi pada umumnya menangani string yang jauh lebih pendek daripada string yang lebih panjang.

Seperti yang dijelaskan oleh David Stone dalam jawabannya di atas , std::stringkelas menggunakan buffer internal untuk menyimpan konten hingga panjang tertentu, dan ini menghilangkan kebutuhan untuk mengalokasikan memori secara dinamis. Ini membuat kode lebih efisien dan lebih cepat .

Jawaban terkait lainnya ini dengan jelas menunjukkan bahwa ukuran buffer internal tergantung pada std::stringimplementasi, yang bervariasi dari platform ke platform (lihat hasil benchmark di bawah).

Tolak ukur

Berikut ini adalah program kecil yang menandai operasi penyalinan banyak string dengan panjang yang sama. Ia mulai mencetak waktu untuk menyalin 10 juta string dengan panjang = 1. Kemudian berulang dengan string panjang = 2. Terus berlanjut hingga panjangnya 50.

#include <string>
#include <iostream>
#include <vector>
#include <chrono>

static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
static const int ARRAY_SIZE = sizeof(CHARS) - 1;

static const int BENCHMARK_SIZE = 10000000;
static const int MAX_STRING_LENGTH = 50;

using time_point = std::chrono::high_resolution_clock::time_point;

void benchmark(std::vector<std::string>& list) {
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();

    // force a copy of each string in the loop iteration
    for (const auto s : list) {
        std::cout << s;
    }

    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
    const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    std::cerr << list[0].length() << ',' << duration << '\n';
}

void addRandomString(std::vector<std::string>& list, const int length) {
    std::string s(length, 0);
    for (int i = 0; i < length; ++i) {
        s[i] = CHARS[rand() % ARRAY_SIZE];
    }
    list.push_back(s);
}

int main() {
    std::cerr << "length,time\n";

    for (int length = 1; length <= MAX_STRING_LENGTH; length++) {
        std::vector<std::string> list;
        for (int i = 0; i < BENCHMARK_SIZE; i++) {
            addRandomString(list, length);
        }
        benchmark(list);
    }

    return 0;
}

Jika Anda ingin menjalankan program ini, Anda harus melakukannya seperti ./a.out > /dev/nullsehingga waktu untuk mencetak string tidak dihitung. Angka-angka yang penting dicetakstderr , sehingga mereka akan muncul di konsol.

Saya telah membuat grafik dengan output dari mesin MacBook dan Ubuntu saya. Perhatikan bahwa ada lompatan besar dalam waktu untuk menyalin string ketika panjangnya mencapai titik tertentu. Itulah saat ketika string tidak lagi sesuai dengan buffer internal dan alokasi memori harus digunakan.

Perhatikan juga bahwa pada mesin linux, lompatan terjadi ketika panjang string mencapai 16. Pada macbook, lompatan terjadi ketika panjangnya mencapai 23. Ini menegaskan bahwa SSO tergantung pada implementasi platform.

Ubuntu

Macbook Pro