Historia pytania.
Przed C++11 wiele implementacji std::string wykorzystywało zliczanie referencji (Copy-on-Write), aby dzielić dane łańcucha między instancjami, co redukowało zajętość pamięci dla kopii. Jednakże podejście to powodowało problemy z bezpieczeństwem wątków, gdzie równoległe odczyty mogły wywołać nieważność iteratorów lub referencji w momencie, gdy wewnętrzny licznik referencji był modyfikowany. C++11 wyraźnie zakazał tej optymalizacji, wymagając, aby funkcje członkowskie const nie unieważniały referencji ani iteratorów, co wymusiło nową strategię optymalizacyjną w celu złagodzenia kosztów wydajności alokacji na stercie dla krótkich łańcuchów.
Problem.
Alokacja na stercie jest kosztowna z powodu narzutu synchronizacji w alokatorach i problemów z lokalnością pamięci podręcznej. W aplikacjach przetwarzających miliardy małych łańcuchów, takich jak analizatory JSON lub obsługiwacze protokołów sieciowych, alokacja pamięci dla sekwencji 5-15 znaków dominuje czas wykonania. Wyzwanie polega na przechowywaniu małych łańcuchów wewnątrz obiektu std::string — zazwyczaj ograniczonego do 32 bajtów na systemach 64-bitowych — bez łamania kompatybilności ABI ani naruszania silnych gwarancji bezpieczeństwa wyjątków wymaganych przez standard.
Rozwiązanie.
Implementacje zazwyczaj używają unii trzech członów dla bufora pamięci: char* ptr_ dla tablicy alokowanej na stercie, size_t capacity_, oraz char local_buffer_[N] dla osadzonej tablicy. Dyskryminator, często zakodowany w najmniej znaczącym bicie członu size_ lub przy użyciu określonej wartości pojemności, określa, czy łańcuch znajduje się w "trybie SSO" czy "trybie sterty". Gdy size() < SSO_CAPACITY, znaki są przechowywane w local_buffer_, z null terminatorem na local_buffer_[size()], całkowicie unikając alokacji na stercie. Dla większych łańcuchów, ptr_ wskazuje na pamięć na stercie, a local_buffer_ jest wykorzystywane do przechowywania metadanych pojemności lub pozostaje nieużywane.
// Koncepcyjna implementacja (uproszczona) class string { union { struct { char* ptr; size_t size; size_t cap; } heap; // Aktywny, gdy cap >= SSO_CAP struct { char buffer[15]; // 15 znaków + null terminator unsigned char size; // Spakowane metadane, MSB wskazuje na stertę } sso; // Aktywny, gdy size < 15 } data; bool is_sso() const { return (data.sso.size & 0x80) == 0; } };
Rozważ aplikację handlu wysokich częstotliwości przetwarzającą wiadomości protokołu FIX zawierające liczne małe tagi (np. "35=D", "150=2"). Początkowa implementacja używała std::string do przechowywania każdej wartości tagu, co skutkowało milionami alokacji na stercie na sekundę i poważną kontencją alokatora, która ograniczała przepływ danych rynkowych.
Rozwiązanie A: Surowe wskaźniki do bufora. Użycie wskaźników char* do oryginalnego bufora wiadomości oferuje zerowy narzut alokacji i maksymalną wydajność. Jednakże podejście to wprowadza niebezpieczne problemy z zarządzaniem czasem życia; jeśli oryginalny bufor jest ponownie używany lub zwolniony, gdy dane łańcucha są wciąż potrzebne, prowadzi to do błędów związanych z użyciem po zwolnieniu. Dodatkowo, wymaga to ręcznego śledzenia długości łańcuchów, co zwiększa złożoność kodu i potencjał błędów.
Rozwiązanie B: Niestandardowy alokator z pulami pamięci. Implementacja lokalnych pul pamięci zmniejsza kontencję alokatora poprzez grupowanie alokacji. Jednakże dodaje to znaczną złożoność szablonów lub wymaga polimorficznych alokatorów w całej bazie kodu. Również nie eliminuje całkowicie narzutu alokacji, jedynie rozkładając koszt na wiele łańcuchów.
Rozwiązanie C: std::string_view i SSO. Wykorzystanie std::string_view do przetwarzania tylko do odczytu unika kopii, podczas gdy poleganie na automatycznym SSO std::string dla przechowywanych wartości zapewnia bezpieczeństwo przy minimalnym narzucie. Główną wadą jest spadek wydajności, gdy łańcuchy przekraczają próg SSO (15-22 znaki), co nagle wywołuje kosztowne alokacje na stercie. Dodatkowo, przenoszenie małych łańcuchów kopiuje dane, a nie przekazuje wskaźników, co może zaskoczyć deweloperów oczekujących semantyki przenoszenia O(1).
Zespół zdecydował się na Rozwiązanie C, refaktoryzując parser, aby używał std::string_view do tymczasowych referencji i std::string tylko wtedy, gdy była wymagana trwałość. To zmniejszyło alokacje na stercie o 95% dla typowych wiadomości FIX, poprawiając przepustowość z 50,000 do 800,000 wiadomości na sekundę, zachowując jednocześnie bezpieczeństwo pamięci.
Dlaczego przenoszenie krótkiego łańcucha, który wewnętrznie wykorzystuje SSO, wykonuje kopiowanie znaków, a nie transfer wskaźników, i jak to wpływa na stan obiektu przeniesionego?
W trybie SSO tablica znaków znajduje się bezpośrednio w obiekcie std::string (zazwyczaj jako członek wewnętrznej unii). W przeciwieństwie do łańcuchów alokowanych na stercie, gdzie konstruktor przenoszący po prostu przenosi wskaźnik char* i ustawia źródło na null, przenoszenie łańcucha SSO wymaga kopiowania znaków z wewnętrznego bufora źródła do wewnętrznego bufora docelowego. Jest to konieczne, ponieważ obiekt źródłowy zostanie zniszczony, a jego wewnętrzny bufor wraz z nim; cel nie może wskazywać na pamięć wewnątrz obiektu źródłowego, który wkrótce zostanie zniszczony. W związku z tym przenoszenie małego łańcucha ma złożoność O(N) zamiast O(1), a obiekt przeniesiony pozostaje w ważnym, ale nieokreślonym stanie (niepustym), wciąż zawierając swoje oryginalne znaki do momentu zniszczenia lub ponownego przypisania.
Jak std::string spełnia wymóg C++11, że c_str() i data() zwracają tablice znaków zakończone null, podczas gdy operuje w trybie SSO, biorąc pod uwagę, że rozmiar wewnętrznego bufora jest stały?
Implementacja zapewnia, że bufor SSO jest zawsze o jeden bajt większy niż maksymalna pojemność SSO (np. 16 bajtów łącznie dla 15-znakowego łańcucha). Przy przechowywaniu łańcucha o długości N (gdzie N < SSO_CAPACITY), implementacja zapisuje null terminator na pozycji N w lokalnym buforze. Metody data() i c_str() zwracają wskaźnik do początku tego lokalnego bufora, gdy są w trybie SSO, a nie wskaźnika do sterty. To zapewnia zakończenie null bez dodatkowej alokacji, spełniając wymagania standardu, że c_str() zwraca const char* do łańcucha zakończonego null, a od C++11 również, że data() wskazuje na tablicę zakończoną null.
Dlaczego capacity() pustego std::string może się różnić między różnymi implementacjami standardowej biblioteki (np. 15 vs 22), i jakie mają implikacje ABI dla mieszania wersji standardowej biblioteki?
Rozmiar bufora SSO jest szczegółem implementacyjnym (libc++ zazwyczaj wykorzystuje 22 znaki na systemach 64-bitowych, wykorzystując wyrównanie, podczas gdy libstdc++ używa 15). Rozmiar ten zależy od sposobu, w jaki implementacja pakuje metadane pojemności/rozmiaru obok lokalnego bufora w układzie obiektu std::string (zazwyczaj 32 bajty łącznie). Ponieważ nie jest to standaryzowane, mieszanie binariów skompilowanych z różnymi implementacjami standardowej biblioteki (np. przekazywanie std::string z biblioteki skompilowanej GCC do aplikacji skompilowanej w Clang) skutkuje niezdefiniowanym zachowaniem z powodu niekompatybilnych układów pamięci. Kandydaci często zakładają, że std::string ma standardowe ABI, ale jest jednym z najmniej przenośnych typów na granicach biblioteki.