Quali sono i meccanismi di ottimizzazione della stringa corta in libc ++?

Questa risposta fornisce una buona panoramica di alto livello sull’ottimizzazione della stringa corta (SSO). Tuttavia, mi piacerebbe sapere più in dettaglio come funziona in pratica, in particolare nell’implementazione di libc ++:

Ho fatto questa domanda specificamente per libc ++ perché so che usa SSO, questo è anche menzionato sulla home page di libc ++ .

Ecco alcune osservazioni dopo aver guardato la fonte :

libc ++ può essere compilato con due layout di memoria leggermente diversi per la class string, questo è governato dal flag _LIBCPP_ALTERNATE_STRING_LAYOUT . Entrambi i layout distinguono anche tra macchine little-endian e big-endian che ci lasciano un totale di 4 varianti differenti. Assumerò il layout “normale” e little-endian in ciò che segue.

Supponendo inoltre che size_type sia di 4 byte e che value_type sia di 1 byte, questo è come dovrebbero apparire i primi 4 byte di una stringa in memoria:

 // 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 

Poiché la dimensione della stringa breve si trova nei 7 bit superiori, è necessario spostarla quando si accede ad essa:

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

Allo stesso modo, getter e setter per la capacità di una stringa lunga usano __long_mask per aggirare il bit is_long .

Sto ancora cercando una risposta alla mia prima domanda, cioè quale valore avrebbe __min_cap , la capacità delle stringhe corte, assumere per architetture diverse?

Altre implementazioni di libreria standard

Questa risposta fornisce una buona panoramica dei layout di memoria std::string in altre implementazioni di librerie standard.

La libc ++ basic_string è progettata per avere una dimensione di 3 parole su tutte le architetture, dove sizeof(word) == sizeof(void*) . Hai sezionato correttamente il flag long / short e il campo size nel formato breve.

quale valore sarebbe __min_cap, la capacità delle stringhe corte, assumere per architetture diverse?

Nella forma abbreviata, ci sono 3 parole con cui lavorare:

  • 1 bit va alla bandiera lunga / corta.
  • 7 bit vanno alla dimensione.
  • Assumendo char , 1 byte va al trailing null (libc ++ memorizzerà sempre un valore finale null dietro i dati).

Questo lascia 3 parole meno 2 byte per memorizzare una stringa breve (cioè più grande capacity() senza un’assegnazione).

Su una macchina a 32 bit, 10 caratteri si inseriranno nella stringa breve. sizeof (stringa) è 12.

Su una macchina a 64 bit, 22 caratteri si inseriranno nella stringa breve. sizeof (stringa) è 24.

Uno degli obiettivi principali della progettazione era ridurre al minimo sizeof(string) , rendendo il buffer interno il più ampio ansible. La logica è quella di accelerare la costruzione delle mosse e spostare l’incarico. Più grande è il sizeof , più parole devi muovere durante una costruzione di movimento o spostare l’incarico.

Il modulo lungo necessita di almeno 3 parole per memorizzare il puntatore, le dimensioni e la capacità dei dati. Pertanto ho limitato il modulo breve a quelle stesse 3 parole. È stato suggerito che una dimensione di 4 parole potrebbe avere prestazioni migliori. Non ho provato quella scelta di design.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Esiste un flag di configurazione chiamato _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT che riorganizza i membri dati in modo tale che il “layout lungo” cambi da:

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

a:

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

La motivazione per questo cambiamento è la convinzione che mettere __data_ primo avrà alcuni vantaggi in termini di prestazioni grazie ad un migliore allineamento. È stato effettuato un tentativo di misurare i vantaggi in termini di prestazioni ed è stato difficile misurarlo. Non peggiorerà le prestazioni e potrebbe migliorare leggermente.

La bandiera dovrebbe essere usata con attenzione. È un ABI diverso e, se accidentalmente mescolato con una libc ++ std::string compilata con un’impostazione diversa di _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT creerà errori di runtime.

Raccomando che questo flag venga modificato solo da un venditore di libc ++.

L’ implementazione di libc ++ è un po ‘complicata, ignorerò il suo design alternativo e supponiamo che un computer little endian:

 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 

Nota: __compressed_pair è essenzialmente una coppia ottimizzata per Empty Base Optimization , alias template struct __compressed_pair: T1, T2 {}; ; a tutti gli effetti si può considerare una coppia regolare. La sua importanza si presenta solo perché std::allocator è stateless e quindi vuoto.

Ok, questo è piuttosto grezzo, quindi controlliamo i meccanismi! Internamente, molte funzioni chiameranno __get_pointer() che a sua volta chiama __is_long per determinare se la stringa sta usando la rappresentazione __long o __short :

 bool __is_long() const _NOEXCEPT { return bool(__r_.first().__s.__size_ & __short_mask); } // __r_.first() -> __rep const& // .__s -> __short const& // .__size_ -> unsigned char 

Per essere onesti, non sono troppo sicuro che questo sia lo standard C ++ (conosco la disposizione di sequenziamento iniziale union ma non so come si configura con un sindacato anonimo e aliasing gettato insieme), ma una libreria standard può trarre vantaggio dall’implementazione comportamento definito comunque.