Quels sont les mécanismes de court optimisation de la chaîne dans la libc++?

Cette réponse donne un bel aperçu de haut niveau de court optimisation de la chaîne d'authentification unique (SSO). Cependant, j'aimerais savoir plus en détail comment cela fonctionne dans la pratique, en particulier dans la libc++ mise en œuvre:

  • Comment ne court la chaîne doivent être afin de se qualifier pour le SSO?
    Fait cela dépend de l'architecture cible?

  • Comment la mise en œuvre de la distinction entre court et long
    les chaînes lors de l'accès à la chaîne de données? Est-ce aussi simple que de m_size <= 16 ou est-il un indicateur qui fait partie d'une autre variable de membre? (Je
    imaginez que m_size ou en partie, il pourrait également être utilisé pour stocker
    chaîne de données).

J'ai posé cette question spécifiquement pour la libc++ parce que je sais qu'il utilise l'authentification unique, c'est même mentionné sur le libc++ page d'accueil.

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

libc++ peut être compilé avec deux légèrement différente de la mémoire des mises en page pour la classe string, elle est régie par la _LIBCPP_ALTERNATE_STRING_LAYOUT drapeau. Les deux mises en page aussi faire la distinction entre little-endian et big-endian machines qui nous laisse avec un total de 4 variantes différentes. Je suppose que le "normal" layout et little-endian dans ce qui suit.

En supposant en outre que size_type est de 4 octets, et que value_type est de 1 octet, c'est ce que les 4 premiers octets d'une chaîne pourrait ressembler à de la 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

Car la taille de la chaîne est dans la partie supérieure de 7 bits, il doit être modifié pour y accéder:

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

De même, les getter et setter pour la capacité d'une longue chaîne utilise __long_mask pour contourner la is_long peu.

Je suis toujours à la recherche d'une réponse à ma première question, c'est à dire la valeur qu'aurait __min_cap, la capacité de chaînes courtes, de prendre pour différentes architectures?

D'autres implémentations de la bibliothèque standard

Cette réponse donne un bel aperçu de std::string mémoire de dispositions dans d'autres implémentations de la bibliothèque standard.

  • libc++ étant open-source, vous pouvez trouver sa string d'en-tête ici, je suis de le vérifier à l'instant 🙂
  • Vous pourriez être intéressé par Petite Optimisation de la Chaîne et les Opérations de Déplacement
  • M.: je l'avais vu avant, malheureusement c'est un très gros fichier, merci pour l'aide à la vérifier.
  • Je suis tombé sur ceci dans googler autour. Cependant, ce blog dit explicitement que c'est seulement une illustration de la SSO et pas très optimisé variante qui serait utilisé dans la pratique.
InformationsquelleAutor ValarDohaeris | 2014-02-11
  1. 105

    La libc++ basic_string est conçu pour avoir une sizeof 3 mots sur toutes les architectures, où sizeof(word) == sizeof(void*). Vous avez bien disséqué le long/short drapeau, et la taille du champ dans le formulaire court.

    quelle valeur auraient __min_cap, la capacité de chaînes courtes, de prendre pour différentes architectures?

    Dans le court formulaire, il y a 3 mots de travailler avec:

    • 1 morceau va à la longue/courte drapeau.
    • 7 bits va à la taille.
    • En supposant char, 1 octet va à l'null de fin (libc++ sera toujours stocker un null de fin derrière les données).

    Ce qui laisse 3 mots moins 2 octets pour stocker une chaîne courte (c'est à dire plus grand capacity() sans affectation).

    Sur un ordinateur 32 bits, 10 caractères dans la chaîne. sizeof(string) est de 12.

    Sur un ordinateur 64 bits, 22 caractères dans la chaîne. sizeof(string) est de 24.

    L'un des principaux objectifs de la conception était de minimiser les sizeof(string), tout en faisant de la mémoire tampon interne aussi grande que possible. La raison en est à la vitesse de déplacement de la construction et de l'assignation de déplacement. La plus grande de la sizeof, le plus de mots vous devez vous déplacer pendant le déplacement d'une construction ou d'assignation de déplacement.

    La forme longue a besoin d'un minimum de 3 mots pour stocker le pointeur de données, de la taille et de la capacité. Donc j'ai limité la forme courte à ces 3 mots. Il a été suggéré qu'un 4 mot sizeof ont de meilleures performances. Je n'ai pas testé que les choix de conception.

    _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

    Il y a un indicateur de configuration appelé _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT qui réorganise les données des membres tels que la "longue" mise en page des changements à partir 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 croyance que la mise __data_ première aura certains avantages en matière de performances grâce à une meilleure harmonisation. Une tentative a été faite pour mesurer les avantages de performance, et il est difficile de mesurer. Il ne fera pas le rendement pire, et il peut faire un peu mieux.

    L'indicateur doit être utilisé avec soin. Il est un autre ABI, et si, par mégarde, mélangé avec une libc++ std::string compilé avec un réglage différent de _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT permettra de créer les erreurs d'exécution.

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

    • Ne sais pas si c'est la licence de la compatibilité entre la libc++ et Facebook Folie, mais la FBstring gère pour stocker un supplément de char (p. 23) par la modification de la taille de la capacité restante, de sorte qu'il peut faire double devoir, comme le terminateur null pour une courte chaîne de 23 caractères.
    • C'est intelligent. Toutefois, si la libc++ adopte elle aurait besoin de la libc++ pour donner une autre caractéristique que j'aime à propos de ses std::string: Un défaut construit string est tous 0 bits. Qui fait défaut de construction super efficace. Et si vous êtes prêts à se plier aux règles, parfois même gratuitement. E. g. vous pourriez calloc mémoire et il suffit de déclarer qu'il soit plein de défaut construit des chaînes de caractères.
    • Ah, 0-init est joli, en effet! BTW, FBstring a 2 drapeau bits, indiquant court, moyen et des grandes chaînes. Il utilise l'authentification unique pour les chaînes jusqu'à 23 caractères, et puis utilise un malloc-ed région de mémoire pour cordes jusqu'à 254 caractères et au delà de ce qu'ils font de la VACHE (qui n'est plus juridique en C++11, je sais).
    • Pourquoi on ne peut pas la taille et la capacité d'être stockées dans ints de sorte que la classe peuvent être emballés à seulement 16 octets sur des architectures 64 bits?
    • Je voulais permettre à des chaînes de plus de 2 go sur 64 bits. Le coût est certes plus sizeof. Mais dans le même temps, la mémoire tampon interne pour char va de 14 à 22, qui est un très bon avantage.
    • Merci! N'avez-vous pas également obtenir un octet supplémentaire de cette nouvelle mise en page, parce que le terminal null pouvez maintenant double comme le drapeau à court?
    • Cela sonne comme une bonne idée, mais à ma connaissance, n'a pas été mis en œuvre. Au moins, je ne l'ai pas fait quand j'ai ajouté _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT en 2013. Si mis en œuvre, il devrait être reflété dans __min_cap (ce qui n'est pas actuellement).
    • Merci pour les explications, c'est vraiment utile. Une question cependant... pourquoi ne pas utiliser le MSBit court / long drapeau? Ne serait-ce pas libérer plus de 7 bits pour de la longue chaîne de la capacité de...? Accordé, c'est surtout sur le plan théorique que l'OS ne sera probablement pas en charge les allocations de tas de la taille. Je me demandais juste si il me manque un point en quelque sorte.
    • Il y a en fait un labyrinthe sinueux des options entre _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT et big/little endian où que court/long bits saute autour de entre le MSB et LSB et honnêtement, je ne me souviens pas des détails.

    InformationsquelleAutor Howard Hinnant
  2. 19

    La libc++ mise en œuvre est un peu compliqué, je vais ignorer son suppléant conception et suppose une little endian ordinateur:

    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_pair est essentiellement une paire optimisé pour le Vide Optimisation De La Base, aka template <T1, T2> struct __compressed_pair: T1, T2 {};; pour toutes fins utiles, vous pouvez le considérer comme un régulier de la paire. Son importance vient juste parce que std::allocator est apatride et donc vide.

    Bon d'accord, c'est assez cru, intéressons-nous donc à la mécanique! En interne, de nombreuses fonctions d'appel __get_pointer() qui elle-même appelle __is_long afin de déterminer si la chaîne est à l'aide de la __long ou __short représentation:

    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 que c'est la Norme C++ (je sais que l'initiale de la disposition en union mais ne savez pas comment il se mêle à un anonyme de l'union et de l'aliasing jetés ensemble), mais une Bibliothèque Standard est autorisé à prendre avantage de la mise en œuvre défini le comportement de toute façon.

    • Merci pour cette réponse détaillée! La seule pièce que je suis en manque, c'est ce que __min_cap serait d'évaluer les différentes architectures, je ne suis pas sûr de ce que sizeof() sera de retour et comment elle est influencée par l'aliasing.
    • elle est définie par l'implémentation. généralement, vous vous en doutez 3 * the size of one pointer dans ce cas, qui serait de 12 octets sur un 32 bits arc et 24 sur 64 bits arch.
    InformationsquelleAutor Matthieu M.