Znaczenie akronimu SSO w kontekście std :: string

W pytaniu C ++ dotyczącym optymalizacji i stylu kodu kilka odpowiedzi odnosiło się do „logowania jednokrotnego” w kontekście optymalizacji kopii std::string. Co w tym kontekście oznacza SSO?

Oczywiście nie jest to „pojedyncze logowanie”. Może „optymalizacja współdzielonych ciągów”?

Tło / przegląd

Operacje na zmiennych automatycznych („ze stosu”, które są zmiennymi tworzonymi bez wywoływania malloc/ new) są generalnie znacznie szybsze niż operacje dotyczące wolnego magazynu („sterty”, czyli zmiennych tworzonych za pomocą new). Jednak rozmiar tablic automatycznych jest ustalany w czasie kompilacji, ale rozmiar tablic z bezpłatnego magazynu nie. Co więcej, rozmiar stosu jest ograniczony (zwykle kilka MiB), podczas gdy wolny magazyn jest ograniczony tylko pamięcią systemu.

SSO to optymalizacja krótkich / małych ciągów. A std::stringzazwyczaj przechowuje ciąg jako wskaźnik do wolnego magazynu („sterty”), co daje podobną charakterystykę wydajności, jak w przypadku wywołania new char [size]. Zapobiega to przepełnieniu stosu w przypadku bardzo dużych ciągów, ale może być wolniejsze, zwłaszcza w przypadku operacji kopiowania. W ramach optymalizacji wiele implementacji std::stringtworzy małą automatyczną tablicę, coś w rodzaju char [20]. Jeśli masz ciąg o długości 20 znaków lub mniejszy (w tym przykładzie rzeczywisty rozmiar jest różny), zapisuje go bezpośrednio w tej tablicy. Dzięki temu neww ogóle nie trzeba dzwonić , co nieco przyspiesza.

EDYTOWAĆ:

Nie spodziewałem się, że ta odpowiedź będzie tak popularna, ale skoro tak, przedstawię bardziej realistyczną implementację, z zastrzeżeniem, że nigdy nie czytałem żadnej implementacji SSO „na wolności”.

Szczegóły dotyczące wdrożenia

Należy co najmniej std::stringprzechowywać następujące informacje:

• Rozmiar
• Pojemność
• Lokalizacja danych

Rozmiar może być przechowywany jako a std::string::size_typelub jako wskaźnik do końca. Jedyną różnicą jest to, czy chcesz odjąć dwa wskaźniki, gdy użytkownik wywołuje, sizeczy dodać size_typedo wskaźnika, gdy użytkownik wywołuje end. Pojemność można przechowywać w dowolny sposób.

Nie płacisz za to, czego nie używasz.

Najpierw rozważ naiwną implementację opartą na tym, co opisałem powyżej:

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;
};

W przypadku systemu 64-bitowego oznacza to ogólnie, że std::stringma 24 bajty „narzutu” na łańcuch plus kolejne 16 na bufor SSO (16 wybranych tutaj zamiast 20 ze względu na wymagania dotyczące wypełnienia). Naprawdę nie miałoby sensu przechowywanie tych trzech elementów danych oraz lokalnej tablicy znaków, jak w moim uproszczonym przykładzie. Jeśli m_size <= 16, to umieszczę wszystkie dane m_sso, więc znam już pojemność i nie potrzebuję wskaźnika do danych. Jeśli m_size > 16, to nie potrzebuję m_sso. Tam, gdzie potrzebuję ich wszystkich, nie ma absolutnie żadnego pokrycia. Inteligentniejsze rozwiązanie, które nie marnuje miejsca, wyglądałoby mniej więcej tak (nieprzetestowane, tylko do celów przykładowych):

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;
    };
};

Zakładam, że większość implementacji wygląda bardziej tak.

SSO to skrót od „Small String Optimization”, techniki, w której małe ciągi znaków są osadzane w treści klasy ciągów zamiast używać oddzielnie przydzielanego buforu.

Jak już wyjaśniono w innych odpowiedziach, SSO oznacza optymalizację małych / krótkich ciągów . Motywacją stojącą za tą optymalizacją jest niezaprzeczalny dowód na to, że aplikacje generalnie obsługują znacznie więcej krótszych ciągów niż dłuższe.

Jak wyjaśnił David Stone w swojej odpowiedzi powyżej , std::stringklasa używa wewnętrznego bufora do przechowywania zawartości o określonej długości, co eliminuje potrzebę dynamicznego przydzielania pamięci. Dzięki temu kod jest wydajniejszy i szybszy .

Ta inna powiązana odpowiedź wyraźnie pokazuje, że rozmiar wewnętrznego bufora zależy od std::stringimplementacji, która różni się w zależności od platformy (patrz wyniki testów porównawczych poniżej).

Benchmarki

Oto mały program, który porównuje operacje kopiowania wielu ciągów o tej samej długości. Zaczyna drukować czas kopiowania 10 milionów ciągów o długości = 1. Następnie powtarza się z ciągami o długości = 2. Powtarza się, aż długość wyniesie 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;
}

Jeśli chcesz uruchomić ten program, powinieneś to zrobić ./a.out > /dev/nulltak, aby czas na wydrukowanie łańcuchów nie był liczony. Liczby, które mają znaczenie, są drukowane stderr, więc pojawią się w konsoli.

Stworzyłem wykresy z danymi wyjściowymi z moich komputerów MacBook i Ubuntu. Zauważ, że następuje duży skok w czasie kopiowania ciągów, gdy długość osiągnie określony punkt. To jest moment, w którym ciągi znaków nie mieszczą się już w wewnętrznym buforze i trzeba użyć alokacji pamięci.

Zauważ również, że na komputerze z systemem Linux skok ma miejsce, gdy długość łańcucha osiągnie 16. Na Macbooku skok ma miejsce, gdy długość osiągnie 23. Potwierdza to, że SSO zależy od implementacji platformy.

Ubuntu

Macbook Pro