Quels sont les mécanismes d'optimisation des chaînes courtes dans libc ++?

102

Cette réponse donne un bel aperçu de haut niveau de l'optimisation des chaînes courtes (SSO). Cependant, j'aimerais savoir plus en détail comment cela fonctionne dans la pratique, en particulier dans l'implémentation libc ++:

  • Quelle doit être la longueur de la chaîne pour être éligible au SSO? Cela dépend-il de l'architecture cible?

  • Comment l'implémentation distingue-t-elle les chaînes courtes et longues lors de l'accès aux données de chaîne? Est-ce aussi simple m_size <= 16ou s'agit-il d'un indicateur faisant partie d'une autre variable membre? (J'imagine que m_sizeou une partie de celui-ci pourrait également être utilisé pour stocker des données de chaîne).

J'ai posé cette question spécifiquement pour libc ++ parce que je sais qu'il utilise SSO, cela est même mentionné sur la page d'accueil de libc ++ .

Voici quelques observations après avoir regardé la source :

libc ++ peut être compilée avec deux dispositions de mémoire légèrement différentes pour la classe string, ceci est régi par l' _LIBCPP_ALTERNATE_STRING_LAYOUTindicateur. Les deux configurations distinguent également les machines petit-boutiste et grand-boutiste, ce qui nous laisse un total de 4 variantes différentes. Je vais supposer la mise en page "normale" et little-endian dans ce qui suit.

En supposant en outre que size_type4 octets et value_type1 octet, voici à quoi ressembleraient les 4 premiers octets d'une chaîne en mémoire:

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

Étant donné que la taille de la chaîne courte est dans les 7 bits supérieurs, elle doit être décalée lors de l'accès:

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

De même, le getter et le setter pour la capacité d'une longue chaîne utilisent __long_maskpour contourner le is_longbit.

Je cherche toujours une réponse à ma première question, à savoir quelle valeur __min_capla capacité des chaînes courtes prendrait pour différentes architectures?

Autres implémentations de bibliothèques standard

Cette réponse donne un bon aperçu des std::stringdispositions de mémoire dans d'autres implémentations de bibliothèques standard.

Valar Dohaeris
la source
libc ++ étant open-source, vous pouvez trouver son en- stringtête ici , je le vérifie en ce moment :)
Matthieu M.
@Matthieu M.: J'avais déjà vu ça, malheureusement c'est un très gros fichier, merci pour l'aide à l'extraction.
ValarDohaeris
@Ali: J'ai trébuché dessus en cherchant sur Google. Cependant, cet article de blog dit explicitement qu'il ne s'agit que d'une illustration de SSO et non d'une variante hautement optimisée qui serait utilisée dans la pratique.
ValarDohaeris

Réponses:

120

La libc ++ basic_stringest conçue pour avoir sizeof3 mots sur toutes les architectures, où sizeof(word) == sizeof(void*). Vous avez correctement disséqué le drapeau long / court et le champ de taille dans le formulaire court.

quelle valeur __min_cap, la capacité des chaînes courtes, prendrait-il pour différentes architectures?

Dans la forme courte, il y a 3 mots avec lesquels travailler:

  • 1 bit va au drapeau long / court.
  • 7 bits correspond à la taille.
  • En supposant char, 1 octet va au null de fin (la libc ++ stockera toujours un null de fin derrière les données).

Cela laisse 3 mots moins 2 octets pour stocker une courte chaîne (c.-à-d. capacity() sans allocation).

Sur une machine 32 bits, 10 caractères rentreront dans la chaîne courte. sizeof (chaîne) est 12.

Sur une machine 64 bits, 22 caractères rentreront dans la chaîne courte. sizeof (chaîne) est 24.

Un objectif majeur de la conception était de minimiser sizeof(string), tout en rendant le tampon interne aussi grand que possible. La justification est d'accélérer la construction du déménagement et l'attribution du déménagement. Plus lesizeof , plus vous devez déplacer de mots pendant une construction de mouvement ou une affectation de mouvement.

La forme longue nécessite un minimum de 3 mots pour stocker le pointeur de données, la taille et la capacité. Par conséquent, j'ai limité la forme courte à ces 3 mêmes mots. Il a été suggéré qu'une taille de 4 mots pourrait avoir de meilleures performances. Je n'ai pas testé ce choix de conception.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Il existe un indicateur de configuration appelé _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTqui réorganise les membres de données de telle sorte que la "mise en page longue" change de:

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

à:

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

La motivation de ce changement est la conviction que mettre __data_ avant aura certains avantages en termes de performances en raison d'un meilleur alignement. Une tentative a été faite pour mesurer les avantages de performance, et il était difficile de les mesurer. Cela n'aggravera pas les performances et pourrait les rendre légèrement meilleures.

Le drapeau doit être utilisé avec précaution. C'est un ABI différent, et s'il est mélangé accidentellement avec une libc ++ std::stringcompilée avec un paramètre différent de _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTcréera des erreurs d'exécution.

Je recommande que cet indicateur ne soit modifié que par un fournisseur de libc ++.

Howard Hinnant
la source
17
Je ne sais pas s'il existe une compatibilité de licence entre libc ++ et Facebook Folly, mais la FBstring parvient à stocker un caractère supplémentaire (c'est-à-dire 23) en changeant la taille en capacité restante , de sorte qu'il puisse faire un double devoir en tant que terminateur nul pour une courte chaîne de 23 caractères .
TemplateRex
20
@TemplateRex: C'est intelligent. Cependant, si libc ++ l'adopte, il faudrait que libc ++ renonce à une autre caractéristique que j'aime à propos de son std :: string: Une valeur par défaut construite stringest de 0 bits. Cela rend la construction par défaut très efficace. Et si vous êtes prêt à contourner les règles, parfois même gratuitement. Par exemple, vous pouvez callocutiliser de la mémoire et simplement déclarer qu'elle est pleine de chaînes construites par défaut.
Howard Hinnant
6
Ah, 0-init est vraiment sympa! BTW, FBstring a 2 bits d'indicateur, indiquant des chaînes courtes, intermédiaires et grandes. Il utilise le SSO pour les chaînes jusqu'à 23 caractères, puis utilise une région de mémoire malloc-ed pour les chaînes jusqu'à 254 caractères et au-delà, ils font COW (plus légal en C ++ 11, je sais).
TemplateRex
Pourquoi la taille et la capacité ne peuvent-elles pas être stockées dans ints afin que la classe puisse être compressée à seulement 16 octets sur des architectures 64 bits?
phuclv
@ LưuVĩnhPhúc: Je voulais autoriser les chaînes supérieures à 2 Go sur 64 bits. Le coût est certes plus élevé sizeof. Mais en même temps, le tampon interne pour charpasse de 14 à 22, ce qui est un très bon avantage.
Howard Hinnant
21

L' implémentation de libc ++ est un peu compliquée, je vais ignorer sa conception alternative et supposer un petit ordinateur 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

Remarque: __compressed_pairest essentiellement une paire optimisée pour l'optimisation de la base vide , aka template <T1, T2> struct __compressed_pair: T1, T2 {};; à toutes fins utiles, vous pouvez le considérer comme une paire régulière. Son importance vient juste parce qu'elle std::allocatorest apatride et donc vide.

D'accord, c'est plutôt brut, alors vérifions la mécanique! En interne, de nombreuses fonctions appelleront__get_pointer() qui elle-même appelle __is_longpour déterminer si la chaîne utilise la représentation __longou __short:

bool __is_long() const _NOEXCEPT
    { return bool(__r_.first().__s.__size_ & __short_mask); }

// __r_.first() -> __rep const&
//     .__s     -> __short const&
//     .__size_ -> unsigned char

Pour être honnête, je ne suis pas trop sûr qu'il s'agisse de C ++ standard (je connais la disposition de sous-séquence initiale dans union qu'il s'agisse de mais je ne sais pas comment elle s'accorde avec une union anonyme et un aliasing jeté ensemble), mais une bibliothèque standard est autorisée à tirer parti de l'implémentation définie comportement de toute façon.

Matthieu M.
la source
Merci pour cette réponse détaillée! Le seul élément qui me manque est ce qui __min_capserait évalué pour différentes architectures, je ne suis pas sûr de ce sizeof()qui reviendra et comment il est influencé par l'aliasing.
ValarDohaeris
1
@ValarDohaerest son implémentation définie. généralement, vous vous attendez 3 * the size of one pointerdans ce cas, qui serait de 12 octets sur un arc de 32 bits et de 24 sur un arc de 64 bits.
justin le