36 votes

Remplacement C ++ pour les VLA C99 (objectif: préserver les performances)

Je suis de portage de certaines C99 code qui fait un usage intensif de la longueur variable des tableaux (VLA) à C++.

J'ai remplacé le VLAs (allocation de pile) avec un tableau de classe qui alloue de la mémoire sur le tas. La performance succès a été énorme, un ralentissement d'un facteur d'au moins 3,2 (voir les repères ci-dessous). Ce rapide VLA remplacement puis-je utiliser en C++? Mon objectif est de minimiser le gain de performance lors de la réécriture du code pour C++.

Une idée qui m'a été suggéré de préparer une classe array qui contient une taille fixe de stockage au sein de la classe (c'est à dire peut être pile-alloués) et l'utilise pour les petits tableaux, et passe automatiquement à l'allocation de tas pour les grandes baies. Mon implémentation est à la fin du post. Il fonctionne assez bien, mais je ne peut toujours pas atteindre la performance de l'original C99 code. Pour venir près d'elle, je dois augmenter cette taille fixe de stockage (MSL ci-dessous) pour les tailles dont je ne suis pas à l'aise avec. Je ne veux pas allouer trop de tableaux de grande sur la pile de même pour les nombreux petits tableaux qui n'en ont pas besoin parce que j'ai peur qu'il va déclencher un débordement de pile. Un C99 VLA est en fait de moins en moins enclins à présent, car il ne sera jamais utiliser plus d'espace de stockage que nécessaire.

Je suis tombé sur std::dynarray, mais ma compréhension est qu'il n'a pas été acceptée dans la norme (encore?).

Je sais que clang et gcc soutien VLAs en C++, mais j'en ai besoin pour travailler avec MSVC trop. En fait, une meilleure portabilité est l'un des principaux objectifs de la réécriture en C++ (l'autre objectif étant de rendre le programme, qui était à l'origine un outil de ligne de commande, dans une bibliothèque réutilisable).


Référence

MSL se réfère à la taille du tableau ci-dessus qui j'ai passer de tas de répartition. J'ai utiliser des valeurs différentes pour les codes 1D et 2D tableaux.

Original C99 code: 115 secondes.
MSL = 0 (c'est à dire d'allocation de tas): 367 secondes (3,2 x).
1D-MSL = 50, 2D-MSL = 1000: 187 secondes (1.63 x).
1D-MSL = 200, 2D-MSL = 4000: 143 secondes (1,24 x).
1D-MSL = 1000, 2D-MSL = 20000: 131 (1.14 x).

L'augmentation de MSL améliore encore les performances de plus, mais finalement, le programme va commencer à retourner des résultats faux (je suppose en raison d'un débordement de pile).

Ces points de référence sont avec clang 3.7 sur OS X, mais gcc 5 montre des résultats très similaires.


Code

C'est l'actuel "smallvector" mise en œuvre que j'utilise. J'ai besoin de 1D et 2D vecteurs. - Je passer en tas-de l'allocation au-dessus de la taille de l' MSL.

template<typename T, size_t MSL=50>
class lad_vector {
    const size_t len;
    T sdata[MSL];
    T *data;
public:
    explicit lad_vector(size_t len_) : len(len_) {
        if (len <= MSL)
            data = &sdata[0];
        else
            data = new T[len];
    }

    ~lad_vector() {
        if (len > MSL)
            delete [] data;
    }

    const T &operator [] (size_t i) const { return data[i]; }
    T &operator [] (size_t i) { return data[i]; }

    operator T * () { return data; }
};


template<typename T, size_t MSL=1000>
class lad_matrix {
    const size_t rows, cols;
    T sdata[MSL];
    T *data;

public:
    explicit lad_matrix(size_t rows_, size_t cols_) : rows(rows_), cols(cols_) {
        if (rows*cols <= MSL)
            data = &sdata[0];
        else
            data = new T[rows*cols];
    }

    ~lad_matrix() {
        if (rows*cols > MSL)
            delete [] data;
    }

    T const * operator[] (size_t i) const { return &data[cols*i]; }
    T * operator[] (size_t i) { return &data[cols*i]; }
};

38voto

Yakk Points 31636

Créer une mémoire tampon de grande taille (MO+) dans le thread de stockage local. (Mémoire sur le tas, la gestion, TLS).

Permettent aux clients de demander la mémoire de FILO manière (similaire à la pile). (il imite la façon dont il fonctionne dans C VLAs; et il est efficace, car chaque demande/retour est juste un entier addition/soustraction).

Obtenez votre VLA le stockage à partir d'elle.

L'envelopper assez, de sorte que vous pouvez dire stack_array<T> x(1024);, et stack_array traitent de construction/destruction (à noter qu' ->~T()T est int juridique est une noop, et de la construction peut également être un noop), ou faire stack_array<T> envelopper std::vector<T, TLS_stack_allocator>.

Les données seront pas aussi local que le C VLA données est parce qu'il sera efficace sur une pile séparée. Vous pouvez utiliser SBO (petit tampon de l'optimisation), ce qui est quand localité qui compte vraiment.

Une SBO stack_array<T> peut être mis en œuvre avec une allocation et un std vecteur fusionné avec un std tableau, ou avec un unique ptr et personnalisé destroyer, ou une myriade d'autres moyens. Vous pouvez probablement de rénover votre solution, en remplacement de votre nouveau/malloc/free/delete avec les appels à la ci-dessus TLS de stockage.

Je dis aller avec TLS comme qui supprime la nécessité pour la synchronisation de frais généraux, tout en permettant une utilisation multithread, et reflète le fait que la pile elle-même est implicitement TLS.

La pile de la mémoire tampon en fonction de la STL allocateur? est un Q&A avec au moins deux "pile" allocateurs dans les réponses. Ils auront besoin de certaines adaptations afin d'obtenir automatiquement leur tampon de TLS.

Notez que le TLS être une grande mémoire tampon est dans un sens un détail d'implémentation. Vous pourriez faire de grandes allocations, et quand vous manquez d'espace pour faire un autre grand de l'allocation. Vous avez juste besoin de garder une trace de chaque pile "à la page" la capacité actuelle et une liste de pages de pile, de sorte que lorsque vous videz un, vous pouvez passer à une autre. Qui vous permet d'être un peu plus prudent dans vos TLS allocation initiale sans se soucier de l'exécution de OOM; l'important, c'est que vous êtes FILO et allouer rarement, non pas que l'ensemble de la pâte FILO tampon est contigu, une.

17voto

5gon12eder Points 2904

Je pense que vous avez déjà énuméré la plupart des options dans votre question et les commentaires.

  • Utiliser std::vector. C'est le plus évident, le plus sans tracas, mais peut-être aussi le plus lent de la solution.
  • L'utilisation de la plate-forme d'extensions spécifiques sur ces plates-formes qui les fournissent. Par exemple, GCC supporte à longueur variable des tableaux en C++ comme une extension. POSIX spécifie alloca ce qui est largement prise en charge d'allouer de la mémoire sur la pile. Même Microsoft Windows fournit _malloca, une rapide recherche sur le web m'a dit.

    Afin d'éviter l'entretien des cauchemars, vous aurez vraiment envie d'encapsuler ces plate-forme de dépendances dans une interface abstraite automatiquement et de manière transparente choisit le mécanisme approprié pour la plate-forme actuelle. La mise en œuvre de ce pour toutes les plates-formes sera un peu de travail, mais si cette fonctionnalité unique représente 3 × différences de vitesse comme vous le signalez, il pourrait être en vaut la peine. Comme un secours pour l'inconnu plates-formes, je garderais std::vector en réserve comme un dernier recours. Il est préférable d'exécuter lentement mais correctement que de se comporter erratique ou pas du tout.

  • Construire votre propre tableau de taille variable type qui implémente un "petit tableau" optimisation intégré comme un tampon à l'intérieur de l'objet lui-même, comme vous l'avez indiqué dans votre question. Je vais prendre note que je préfère essayer d'utiliser un union d'un std::array et std::vector au lieu de rouler mon propre conteneur.

    Une fois que vous avez un type personnalisé en place, vous pouvez faire des choses intéressantes profilage comme le maintien d'un mondial de la table de hachage de toutes les occurrences de ce type (par code-source de l'emplacement) et l'enregistrement de chaque taille d'allocation au cours d'un test de stress de votre programme. Vous pouvez ensuite faire un dump de la table de hachage à la sortie du programme et tracer les distributions dans l'allocation des tailles pour les des tableaux individuels. Cela pourrait vous aider à affiner le réglage de la quantité de stockage de réserve pour chaque tableau individuellement sur la pile.

  • Utiliser un std::vector avec un allocateur personnalisé. Au démarrage du programme, d'allouer quelques mégaoctets de mémoire et le donner à une simple pile de l'allocateur. Pour une pile d'allocation, l'allocation est juste la comparaison et l'ajout de deux entiers et de désallocation est tout simplement une soustraction. Je doute que le compilateur a généré l'allocation de pile peut être beaucoup plus rapide. Votre "tableau de la pile" serait alors vibrer corrélée à votre "programme de la pile". Cette conception aurait également l'avantage accidentelles des dépassements de mémoire tampon, tout en invoquant un comportement indéfini, dénigrer des données aléatoires et tous que les mauvaises choses – ne serait pas aussi facilement corrompre le programme de la pile (adresse de retour), comme ils le feraient avec des natifs VLAs.

    Personnalisé allocateurs en C++ sont un peu sale, mais certaines personnes n'ont rapport qu'ils l'utilisent avec succès. (Je n'ai pas beaucoup d'expérience avec l'aide de moi-même.) Vous voudrez peut-être commencer à regarder cppreference. Alisdair Meredith qui est l'un de ceux qui en promouvoir l'utilisation de la coutume allocateurs a donné une double session de parler à CppCon'14 intitulé "Faire des Allocateurs de Travail" (partie 1, partie 2) que vous pourriez trouver intéressant. Si l' std::allocator interface trop difficile à utiliser pour vous, la mise en œuvre de votre propre variable (par opposition à dynamiquement) tableau de taille classe avec votre propre allocateur devrait être faisable aussi.

8voto

Matt McNabb Points 14273

Concernant le soutien à l'MSVC:

MSVC a _alloca qui alloue de l'espace de pile. Il dispose également d' _malloca qui alloue de l'espace de pile si il y a assez d'espace libre pile, autrement revient à l'allocation dynamique.

Vous ne pouvez pas profiter de la VLA type de système, de sorte que vous aurez à changer votre code de travail en fonction un pointeur vers le premier élément d'un tableau.

Vous pouvez finir par avoir à utiliser une macro qui a des définitions différentes selon la plate-forme. E. g. invoquer _alloca ou _malloca sur MSVC, et sur g++ ou d'autres compilateurs, soit des appels alloca (si ils le supportent), ou fait un ALTO et un pointeur.


Envisager de trouver des moyens de réécrire le code sans avoir besoin d'allouer un montant inconnu de la pile. Une option consiste à allouer une taille fixe de la mémoire tampon qui est le maximum que vous aurez besoin. (Si cela peut provoquer un débordement de pile cela signifie que votre code est buggé de toute façon).

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X