En C ++, est-il pratique encore mal à retourner un vecteur d'une fonction?

Question

Version courte: Il est fréquent de retourner des objets volumineux tels que des vecteurs / tableaux-dans de nombreux langages de programmation. Est-ce style maintenant acceptable dans C ++ 0x si la classe a un constructeur de déplacer ou faire les programmeurs C ++ considèrent abomination / étrange / laid?

Version longue: En C ++ 0x est-ce toujours considéré comme mauvaise forme

std::vector<std::string> BuildLargeVector();
...
std::vector<std::string> v = BuildLargeVector();

La version traditionnelle ressemblerait à ceci:

void BuildLargeVector(std::vector<std::string>& result);
...
std::vector<std::string> v;
BuildLargeVector(v);

Dans la nouvelle version, la valeur retournée par BuildLargeVector est un rvalue, donc v serait construit en utilisant le constructeur de déplacement de std::vector, en supposant (N) RVO ne se fait pas.

Même avant C ++ 0x la première forme serait souvent « efficace » en raison de (N) RVO. Cependant, (N) RVO est à la discrétion du compilateur. Maintenant que nous avons des références rvalue est garantie qui ne copie en profondeur aura lieu.

Modifier : La question est vraiment pas sur l'optimisation. Les deux formes représentées ont des performances quasi identiques dans les programmes réels. Considérant que, dans le passé, la première forme aurait eu ordre de grandeur de moins bonnes performances. En conséquence, la première forme était une odeur de code majeur dans la programmation de C pendant une longue période. Plus maintenant, je l'espère?

Answer 1

Dave Abrahams a une jolie analyse complète de

Answer 2

Au moins l'OMI, il est généralement une mauvaise idée, mais pas pour des raisons d'efficacité. C'est une mauvaise idée parce que la fonction en question devrait normalement être écrit comme un algorithme générique qui produit sa sortie via un itérateur. Presque tout code qui accepte ou retourne un contenant au lieu d'opérer sur itérateurs doit être considéré comme suspect.

Ne vous méprenez pas. Il y a des moments, il est logique de passer autour de collection comme des objets (par exemple, des chaînes), mais pour l'exemple cité, je considérerais passer et retourner le vecteur d'une mauvaise idée

L'essentiel est:

Copier Elision et RVO peuvent éviter les « copies effrayantes » (le compilateur n'est pas nécessaire de mettre en œuvre ces optimisations, et dans certaines situations, il ne peut pas être appliquée)

références C ++ 0x rvalue allow une chaîne implémentations / vecteur que garanties .

Si vous pouvez abandonner les compilateurs anciens / implémentations STL, vecteurs de retour librement (et assurez-vous que vos propres objets prennent en charge, aussi). Si vos besoins de base de code pour soutenir compilateurs « moins », bâton à l'ancien style.

Malheureusement, cela a une influence majeure sur vos interfaces. Si C ++ 0x est pas une option, et vous avez besoin de garanties, vous pouvez utiliser à la place le comptage de références ou d'objets copy-on-write dans certains scénarios. Ils ont des inconvénients avec multithreading, cependant.

(je veux juste une réponse en C ++ serait simple et directe et sans conditions).

En effet, depuis C ++ 11, le coût de copier le std::vector a disparu dans la plupart des cas.

Cependant, il faut garder à l'esprit que le coût de la construction le nouveau vecteur (puis destructing il) existe toujours, et en utilisant des paramètres de sortie au lieu de retourner par la valeur est toujours utile lorsque vous désirez réutiliser la capacité du vecteur. Ceci est documenté comme une exception dans F.20 des C ++ de base Directives.

Soit de comparer:

std::vector<int> BuildLargeVector1(size_t vecSize) {
    return std::vector<int>(vecSize, 1);
}

avec:

void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
    v.assign(vecSize, 1);
}

Maintenant, supposons que nous devons appeler ces méthodes temps de numIter dans une boucle serrée et effectuer une action. Par exemple, nous allons calculer la somme de tous les éléments.

Utilisation BuildLargeVector1, vous feriez:

size_t sum1 = 0;
for (int i = 0; i < numIter; ++i) {
    std::vector<int> v = BuildLargeVector1(vecSize);
    sum1 = std::accumulate(v.begin(), v.end(), sum1);
}

Utilisation BuildLargeVector2, vous feriez:

size_t sum2 = 0;
std::vector<int> v;
for (int i = 0; i < numIter; ++i) {
    BuildLargeVector2(/*out*/ v, vecSize);
    sum2 = std::accumulate(v.begin(), v.end(), sum2);
}

Dans le premier exemple, il existe de nombreuses allocations de dynamiques inutiles / désallocations qui se produisent, qui sont empêchés dans le second exemple en utilisant une sortie paramètre à l'ancienne, la réutilisation mémoire déjà allouée. Si oui ou non cette optimisation vaut la peine dépend du coût relatif de l'allocation / désallocation par rapport au coût de calcul / valeurs muter.

Indice de référence

Le jeu Let avec les valeurs de vecSize et numIter. Nous garderons vecSize * numIter constante, de sorte que « en théorie », il faut prendre en même temps (= il y a le même nombre de missions et additions, avec les valeurs exactes mêmes), et la différence de temps ne peut venir que du coût de allocations, désallocations, et une meilleure utilisation du cache.

Plus précisément, nous allons utiliser vecSize * numIter = 2 ^ 31 = 2147483648, parce que j'ai 16 Go de RAM et ce nombre assure que pas plus de 8 Go AFFECTÉ (sizeof (int) = 4), en veillant à ce que je ne suis pas swapping sur le disque (tous les autres programmes ont été fermés, j'avais ~ 15 Go disponible lors du test).

Voici le code:

#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

class Timer {
    using clock = std::chrono::steady_clock;
    using seconds = std::chrono::duration<double>;
    clock::time_point t_;

public:
    void tic() { t_ = clock::now(); }
    double toc() const { return seconds(clock::now() - t_).count(); }
};

std::vector<int> BuildLargeVector1(size_t vecSize) {
    return std::vector<int>(vecSize, 1);
}

void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
    v.assign(vecSize, 1);
}

int main() {
    Timer t;

    size_t vecSize = size_t(1) << 31;
    size_t numIter = 1;

    std::cout << std::setw(10) << "vecSize" << ", "
              << std::setw(10) << "numIter" << ", "
              << std::setw(10) << "time1" << ", "
              << std::setw(10) << "time2" << ", "
              << std::setw(10) << "sum1" << ", "
              << std::setw(10) << "sum2" << "\n";

    while (vecSize > 0) {

        t.tic();
        size_t sum1 = 0;
        {
            for (int i = 0; i < numIter; ++i) {
                std::vector<int> v = BuildLargeVector1(vecSize);
                sum1 = std::accumulate(v.begin(), v.end(), sum1);
            }
        }
        double time1 = t.toc();

        t.tic();
        size_t sum2 = 0;
        {
            std::vector<int> v;
            for (int i = 0; i < numIter; ++i) {
                BuildLargeVector2(/*out*/ v, vecSize);
                sum2 = std::accumulate(v.begin(), v.end(), sum2);
            }
        } // deallocate v
        double time2 = t.toc();

        std::cout << std::setw(10) << vecSize << ", "
                  << std::setw(10) << numIter << ", "
                  << std::setw(10) << std::fixed << time1 << ", "
                  << std::setw(10) << std::fixed << time2 << ", "
                  << std::setw(10) << sum1 << ", "
                  << std::setw(10) << sum2 << "\n";

        vecSize /= 2;
        numIter *= 2;
    }

    return 0;
}

Et voici le résultat:

$ g++ -std=c++11 -O3 main.cpp && ./a.out
   vecSize,    numIter,      time1,      time2,       sum1,       sum2
2147483648,          1,   2.360384,   2.356355, 2147483648, 2147483648
1073741824,          2,   2.365807,   1.732609, 2147483648, 2147483648
 536870912,          4,   2.373231,   1.420104, 2147483648, 2147483648
 268435456,          8,   2.383480,   1.261789, 2147483648, 2147483648
 134217728,         16,   2.395904,   1.179340, 2147483648, 2147483648
  67108864,         32,   2.408513,   1.131662, 2147483648, 2147483648
  33554432,         64,   2.416114,   1.097719, 2147483648, 2147483648
  16777216,        128,   2.431061,   1.060238, 2147483648, 2147483648
   8388608,        256,   2.448200,   0.998743, 2147483648, 2147483648
   4194304,        512,   0.884540,   0.875196, 2147483648, 2147483648
   2097152,       1024,   0.712911,   0.716124, 2147483648, 2147483648
   1048576,       2048,   0.552157,   0.603028, 2147483648, 2147483648
    524288,       4096,   0.549749,   0.602881, 2147483648, 2147483648
    262144,       8192,   0.547767,   0.604248, 2147483648, 2147483648
    131072,      16384,   0.537548,   0.603802, 2147483648, 2147483648
     65536,      32768,   0.524037,   0.600768, 2147483648, 2147483648
     32768,      65536,   0.526727,   0.598521, 2147483648, 2147483648
     16384,     131072,   0.515227,   0.599254, 2147483648, 2147483648
      8192,     262144,   0.540541,   0.600642, 2147483648, 2147483648
      4096,     524288,   0.495638,   0.603396, 2147483648, 2147483648
      2048,    1048576,   0.512905,   0.609594, 2147483648, 2147483648
      1024,    2097152,   0.548257,   0.622393, 2147483648, 2147483648
       512,    4194304,   0.616906,   0.647442, 2147483648, 2147483648
       256,    8388608,   0.571628,   0.629563, 2147483648, 2147483648
       128,   16777216,   0.846666,   0.657051, 2147483648, 2147483648
        64,   33554432,   0.853286,   0.724897, 2147483648, 2147483648
        32,   67108864,   1.232520,   0.851337, 2147483648, 2147483648
        16,  134217728,   1.982755,   1.079628, 2147483648, 2147483648
         8,  268435456,   3.483588,   1.673199, 2147483648, 2147483648
         4,  536870912,   5.724022,   2.150334, 2147483648, 2147483648
         2, 1073741824,  10.285453,   3.583777, 2147483648, 2147483648
         1, 2147483648,  20.552860,   6.214054, 2147483648, 2147483648

(Intel i7-7700K @ 4.20GHz, 16 Go DDR4 2400MHz, Kubuntu 18.04)

Notation:. Mem (v) = V.SIZE () * sizeof (int) = V.SIZE () * 4 sur ma plate-forme

Evidemment, lorsque numIter = 1 (à savoir, mem (v) = 8 Go), les temps sont parfaitement identiques. En effet, dans les deux cas, nous ne faisons que allouons une fois un grand vecteur de 8 Go en mémoire. Cela prouve aussi que aucune copie est arrivé lors de l'utilisation BuildLargeVector1 (): je n'aurais pas assez de RAM pour faire la copie

Lorsque numIter = 2, réutiliser la capacité de vecteur au lieu de réattribuer un second vecteur est 1.37x plus rapide.

Lorsque numIter = 256, la réutilisation de la capacité vectorielle (au lieu d'allouer / désallouer un vecteur encore et encore 256 fois ...) est plus rapide 2.45x :)

On peut remarquer que time1 est à peu près constant de numIter = 1 à numIter = 256, ce qui signifie que l'attribution d'un grand vecteur de 8 Go est à peu près aussi cher que l'allocation de 256 vecteurs de 32Mo. Cependant, attribution d'un grand vecteur de 8 Go est definitly plus cher que l'allocation d'un vecteur de 32MB, donc la réutilisation de la capacité du vecteur fournit des gains de performance.

De numIter = 512 (mem (v) = 16Mo) à numIter = 8M (mem (v) = 1 Ko) est l'endroit doux: les deux méthodes sont exactement aussi vite, et plus vite que toutes les autres combinaisons de numIter et vecSize. Cela a probablement à voir avec le fait que la taille du cache L3 de mon processeur est 8MB, de sorte que le vecteur à peu près complètement emboîtée dans le cache. Je ne l'explique pas vraiment pourquoi le saut soudain de time1 est pour mem (v) = 16Mo, il semble plus logique de se produire juste après, quand mem (v) = 8MB. Notez que surprisingly, dans cet endroit doux, pas réutilisant la capacité est légèrement plus rapide en fait! Je ne l'explique pas vraiment.

Quand les choses commencent à numIter > 8M devenir laid. Les deux méthodes se retourner plus lent, mais le vecteur par la valeur devient encore plus lent. Dans le pire des cas, avec un vecteur contenant qu'un seul int, la capacité de réutiliser au lieu de retourner en valeur est 3,3x plus rapide. On peut supposer que cela est dû aux coûts fixes de malloc () qui commencent à dominer.

Notez comment la courbe pour time2 est plus lisse que la courbe time1:. Non seulement, il est à nouveau en utilisant la capacité vectorielle est généralement plus rapide, mais peut-être plus important encore plus prévisible

Notez également que dans le sweet spot, nous avons pu réaliser 2 milliards additions d'entiers de 64 bits dans ~ 0,5s, ce qui est tout à fait optimale sur un processeur 64 bits 4.2GHz. Nous pourrions faire mieux en paralléliser le calcul afin d'utiliser tous les 8 cœurs (le test ci-dessus utilise un seul noyau à la fois, que j'ai vérifié en relançant le test tout en surveillant l'utilisation du processeur). La meilleure performance est obtenue lorsque mem (v) = 16 Ko, ce qui est l'ordre de grandeur de cache L1 (cache de données L1 pour la i7-7700K est 4x32kB).

Bien sûr, les différences deviennent de moins en moins pertinentes plus calcul que vous avez réellement à faire sur les données. Voici les résultats si nous remplaçons sum = std::accumulate(v.begin(), v.end(), sum); par for (int k : v) sum += std::sqrt(2.0*k);:

Conclusions

1. Utilisation des paramètres de sortie au lieu de retourner en valeur peut fournir des gains de performance par la capacité de réutilisation.
2. Sur un ordinateur de bureau moderne, cela ne semble applicable aux grands vecteurs (> 16 Mo) et de petits vecteurs (<1 Ko).
3. éviter d'allouer des millions / milliards de petits vecteurs (<1 Ko). Si possible, la capacité de réutilisation, ou mieux encore, la conception de votre architecture différente.

Les résultats peuvent différer sur d'autres plates-formes. Comme d'habitude, si les questions de performance, des critères d'écriture pour votre cas d'utilisation spécifique.

Je pense toujours qu'il est une mauvaise pratique, mais il est intéressant de noter que mon équipe utilise MSVC 2008 et GCC 4.1, donc nous ne sommes pas en utilisant les derniers compilateurs.

Auparavant, beaucoup de points chauds indiqués dans vtune avec MSVC 2008 est descendu à la copie de chaîne. Nous avions un code comme ceci:

String Something::id() const
{
    return valid() ? m_id: "";
}

... Notez que nous avons utilisé notre propre type String (ce qui était nécessaire parce que nous fournissons un kit de développement logiciel où les auteurs de plugins pourraient utiliser différents compilateurs et donc différentes implémentations incompatibles de std :: string / std :: wstring).

J'ai fait un simple changement en réponse à la session de profilage d'échantillonnage graphique d'appel montrant être prendre une quantité importante de temps String :: String (const String &). Les méthodes comme dans l'exemple ci-dessus ont été les plus grands contributeurs (en fait la session de profilage a montré l'allocation de mémoire et désallocation d'être l'un des plus grands points chauds, avec le constructeur de copie de chaîne étant le principal contributeur pour les allocations).

Le changement que j'ai fait était simple:

static String null_string;
const String& Something::id() const
{
    return valid() ? m_id: null_string;
}

Pourtant, ce fait un monde de différence! Le point chaud est parti lors des sessions ultérieures profileurs, et en plus de cela, nous faisons beaucoup de tests unitaires en profondeur pour assurer le suivi de notre performance d'application. Tous les types de temps de test de performance a considérablement diminué après ces changements simples.

Conclusion: nous ne sommes pas en utilisant les derniers compilateurs absolus, mais il semble que nous ne pouvons toujours pas dépendre du compilateur optimisant l'écart de la copie pour le retour en termes de valeur fiable (au moins pas dans tous les cas). Cela peut ne pas être le cas pour ceux qui utilisent de nouveaux compilateurs comme MSVC 2010. Je suis impatient quand on peut utiliser C ++ 0x et utiliser simplement des références rvalue et ne jamais avoir à craindre que nous pessimizing notre code en retournant complexe les classes en valeur.

[Modifier] Comme Nate a fait remarquer, RVO applique au retour créés à l'intérieur de temporaires en fonction. Dans mon cas, il n'y avait pas de telles temporaires (à l'exception de la branche non valide où nous construisons une chaîne vide) et donc RVO n'aurait pas été le cas.

Juste pour pinailler un peu: il est rare dans de nombreux langages de programmation pour renvoyer des tableaux de fonctions. Dans la plupart d'entre eux, une référence au tableau est retourné. En C ++, le plus proche analogie serait de retour boost::shared_array

Si la performance est un problème réel, vous devez comprendre que la sémantique de déplacement ne sont pas toujours plus rapide que la copie. Par exemple, si vous avez une chaîne qui utilise le petite optimisation chaîne puis pour les petites chaînes d'un constructeur de déplacement doit faire le montant exact même du travail en tant que constructeur de copie régulière.

Answer 3

Au moins l'OMI, il est généralement une mauvaise idée, mais pas pour des raisons d'efficacité. C'est une mauvaise idée parce que la fonction en question devrait normalement être écrit comme un algorithme générique qui produit sa sortie via un itérateur. Presque tout code qui accepte ou retourne un contenant au lieu d'opérer sur itérateurs doit être considéré comme suspect.

Ne vous méprenez pas. Il y a des moments, il est logique de passer autour de collection comme des objets (par exemple, des chaînes), mais pour l'exemple cité, je considérerais passer et retourner le vecteur d'une mauvaise idée

Answer 4

L'essentiel est:

Copier Elision et RVO peuvent éviter les « copies effrayantes » (le compilateur n'est pas nécessaire de mettre en œuvre ces optimisations, et dans certaines situations, il ne peut pas être appliquée)

références C ++ 0x rvalue allow une chaîne implémentations / vecteur que garanties .

Si vous pouvez abandonner les compilateurs anciens / implémentations STL, vecteurs de retour librement (et assurez-vous que vos propres objets prennent en charge, aussi). Si vos besoins de base de code pour soutenir compilateurs « moins », bâton à l'ancien style.

Malheureusement, cela a une influence majeure sur vos interfaces. Si C ++ 0x est pas une option, et vous avez besoin de garanties, vous pouvez utiliser à la place le comptage de références ou d'objets copy-on-write dans certains scénarios. Ils ont des inconvénients avec multithreading, cependant.

(je veux juste une réponse en C ++ serait simple et directe et sans conditions).

Answer 5

En effet, depuis C ++ 11, le coût de copier le std::vector a disparu dans la plupart des cas.

Cependant, il faut garder à l'esprit que le coût de la construction le nouveau vecteur (puis destructing il) existe toujours, et en utilisant des paramètres de sortie au lieu de retourner par la valeur est toujours utile lorsque vous désirez réutiliser la capacité du vecteur. Ceci est documenté comme une exception dans F.20 des C ++ de base Directives.

Soit de comparer:

std::vector<int> BuildLargeVector1(size_t vecSize) {
    return std::vector<int>(vecSize, 1);
}

avec:

void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
    v.assign(vecSize, 1);
}

Maintenant, supposons que nous devons appeler ces méthodes temps de numIter dans une boucle serrée et effectuer une action. Par exemple, nous allons calculer la somme de tous les éléments.

Utilisation BuildLargeVector1, vous feriez:

size_t sum1 = 0;
for (int i = 0; i < numIter; ++i) {
    std::vector<int> v = BuildLargeVector1(vecSize);
    sum1 = std::accumulate(v.begin(), v.end(), sum1);
}

Utilisation BuildLargeVector2, vous feriez:

size_t sum2 = 0;
std::vector<int> v;
for (int i = 0; i < numIter; ++i) {
    BuildLargeVector2(/*out*/ v, vecSize);
    sum2 = std::accumulate(v.begin(), v.end(), sum2);
}

Dans le premier exemple, il existe de nombreuses allocations de dynamiques inutiles / désallocations qui se produisent, qui sont empêchés dans le second exemple en utilisant une sortie paramètre à l'ancienne, la réutilisation mémoire déjà allouée. Si oui ou non cette optimisation vaut la peine dépend du coût relatif de l'allocation / désallocation par rapport au coût de calcul / valeurs muter.

Indice de référence

Le jeu Let avec les valeurs de vecSize et numIter. Nous garderons vecSize * numIter constante, de sorte que « en théorie », il faut prendre en même temps (= il y a le même nombre de missions et additions, avec les valeurs exactes mêmes), et la différence de temps ne peut venir que du coût de allocations, désallocations, et une meilleure utilisation du cache.

Plus précisément, nous allons utiliser vecSize * numIter = 2 ^ 31 = 2147483648, parce que j'ai 16 Go de RAM et ce nombre assure que pas plus de 8 Go AFFECTÉ (sizeof (int) = 4), en veillant à ce que je ne suis pas swapping sur le disque (tous les autres programmes ont été fermés, j'avais ~ 15 Go disponible lors du test).

Voici le code:

#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

class Timer {
    using clock = std::chrono::steady_clock;
    using seconds = std::chrono::duration<double>;
    clock::time_point t_;

public:
    void tic() { t_ = clock::now(); }
    double toc() const { return seconds(clock::now() - t_).count(); }
};

std::vector<int> BuildLargeVector1(size_t vecSize) {
    return std::vector<int>(vecSize, 1);
}

void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
    v.assign(vecSize, 1);
}

int main() {
    Timer t;

    size_t vecSize = size_t(1) << 31;
    size_t numIter = 1;

    std::cout << std::setw(10) << "vecSize" << ", "
              << std::setw(10) << "numIter" << ", "
              << std::setw(10) << "time1" << ", "
              << std::setw(10) << "time2" << ", "
              << std::setw(10) << "sum1" << ", "
              << std::setw(10) << "sum2" << "\n";

    while (vecSize > 0) {

        t.tic();
        size_t sum1 = 0;
        {
            for (int i = 0; i < numIter; ++i) {
                std::vector<int> v = BuildLargeVector1(vecSize);
                sum1 = std::accumulate(v.begin(), v.end(), sum1);
            }
        }
        double time1 = t.toc();

        t.tic();
        size_t sum2 = 0;
        {
            std::vector<int> v;
            for (int i = 0; i < numIter; ++i) {
                BuildLargeVector2(/*out*/ v, vecSize);
                sum2 = std::accumulate(v.begin(), v.end(), sum2);
            }
        } // deallocate v
        double time2 = t.toc();

        std::cout << std::setw(10) << vecSize << ", "
                  << std::setw(10) << numIter << ", "
                  << std::setw(10) << std::fixed << time1 << ", "
                  << std::setw(10) << std::fixed << time2 << ", "
                  << std::setw(10) << sum1 << ", "
                  << std::setw(10) << sum2 << "\n";

        vecSize /= 2;
        numIter *= 2;
    }

    return 0;
}

Et voici le résultat:

$ g++ -std=c++11 -O3 main.cpp && ./a.out
   vecSize,    numIter,      time1,      time2,       sum1,       sum2
2147483648,          1,   2.360384,   2.356355, 2147483648, 2147483648
1073741824,          2,   2.365807,   1.732609, 2147483648, 2147483648
 536870912,          4,   2.373231,   1.420104, 2147483648, 2147483648
 268435456,          8,   2.383480,   1.261789, 2147483648, 2147483648
 134217728,         16,   2.395904,   1.179340, 2147483648, 2147483648
  67108864,         32,   2.408513,   1.131662, 2147483648, 2147483648
  33554432,         64,   2.416114,   1.097719, 2147483648, 2147483648
  16777216,        128,   2.431061,   1.060238, 2147483648, 2147483648
   8388608,        256,   2.448200,   0.998743, 2147483648, 2147483648
   4194304,        512,   0.884540,   0.875196, 2147483648, 2147483648
   2097152,       1024,   0.712911,   0.716124, 2147483648, 2147483648
   1048576,       2048,   0.552157,   0.603028, 2147483648, 2147483648
    524288,       4096,   0.549749,   0.602881, 2147483648, 2147483648
    262144,       8192,   0.547767,   0.604248, 2147483648, 2147483648
    131072,      16384,   0.537548,   0.603802, 2147483648, 2147483648
     65536,      32768,   0.524037,   0.600768, 2147483648, 2147483648
     32768,      65536,   0.526727,   0.598521, 2147483648, 2147483648
     16384,     131072,   0.515227,   0.599254, 2147483648, 2147483648
      8192,     262144,   0.540541,   0.600642, 2147483648, 2147483648
      4096,     524288,   0.495638,   0.603396, 2147483648, 2147483648
      2048,    1048576,   0.512905,   0.609594, 2147483648, 2147483648
      1024,    2097152,   0.548257,   0.622393, 2147483648, 2147483648
       512,    4194304,   0.616906,   0.647442, 2147483648, 2147483648
       256,    8388608,   0.571628,   0.629563, 2147483648, 2147483648
       128,   16777216,   0.846666,   0.657051, 2147483648, 2147483648
        64,   33554432,   0.853286,   0.724897, 2147483648, 2147483648
        32,   67108864,   1.232520,   0.851337, 2147483648, 2147483648
        16,  134217728,   1.982755,   1.079628, 2147483648, 2147483648
         8,  268435456,   3.483588,   1.673199, 2147483648, 2147483648
         4,  536870912,   5.724022,   2.150334, 2147483648, 2147483648
         2, 1073741824,  10.285453,   3.583777, 2147483648, 2147483648
         1, 2147483648,  20.552860,   6.214054, 2147483648, 2147483648

(Intel i7-7700K @ 4.20GHz, 16 Go DDR4 2400MHz, Kubuntu 18.04)

Notation:. Mem (v) = V.SIZE () * sizeof (int) = V.SIZE () * 4 sur ma plate-forme

Evidemment, lorsque numIter = 1 (à savoir, mem (v) = 8 Go), les temps sont parfaitement identiques. En effet, dans les deux cas, nous ne faisons que allouons une fois un grand vecteur de 8 Go en mémoire. Cela prouve aussi que aucune copie est arrivé lors de l'utilisation BuildLargeVector1 (): je n'aurais pas assez de RAM pour faire la copie

Lorsque numIter = 2, réutiliser la capacité de vecteur au lieu de réattribuer un second vecteur est 1.37x plus rapide.

Lorsque numIter = 256, la réutilisation de la capacité vectorielle (au lieu d'allouer / désallouer un vecteur encore et encore 256 fois ...) est plus rapide 2.45x :)

On peut remarquer que time1 est à peu près constant de numIter = 1 à numIter = 256, ce qui signifie que l'attribution d'un grand vecteur de 8 Go est à peu près aussi cher que l'allocation de 256 vecteurs de 32Mo. Cependant, attribution d'un grand vecteur de 8 Go est definitly plus cher que l'allocation d'un vecteur de 32MB, donc la réutilisation de la capacité du vecteur fournit des gains de performance.

De numIter = 512 (mem (v) = 16Mo) à numIter = 8M (mem (v) = 1 Ko) est l'endroit doux: les deux méthodes sont exactement aussi vite, et plus vite que toutes les autres combinaisons de numIter et vecSize. Cela a probablement à voir avec le fait que la taille du cache L3 de mon processeur est 8MB, de sorte que le vecteur à peu près complètement emboîtée dans le cache. Je ne l'explique pas vraiment pourquoi le saut soudain de time1 est pour mem (v) = 16Mo, il semble plus logique de se produire juste après, quand mem (v) = 8MB. Notez que surprisingly, dans cet endroit doux, pas réutilisant la capacité est légèrement plus rapide en fait! Je ne l'explique pas vraiment.

Quand les choses commencent à numIter > 8M devenir laid. Les deux méthodes se retourner plus lent, mais le vecteur par la valeur devient encore plus lent. Dans le pire des cas, avec un vecteur contenant qu'un seul int, la capacité de réutiliser au lieu de retourner en valeur est 3,3x plus rapide. On peut supposer que cela est dû aux coûts fixes de malloc () qui commencent à dominer.

Notez comment la courbe pour time2 est plus lisse que la courbe time1:. Non seulement, il est à nouveau en utilisant la capacité vectorielle est généralement plus rapide, mais peut-être plus important encore plus prévisible

Notez également que dans le sweet spot, nous avons pu réaliser 2 milliards additions d'entiers de 64 bits dans ~ 0,5s, ce qui est tout à fait optimale sur un processeur 64 bits 4.2GHz. Nous pourrions faire mieux en paralléliser le calcul afin d'utiliser tous les 8 cœurs (le test ci-dessus utilise un seul noyau à la fois, que j'ai vérifié en relançant le test tout en surveillant l'utilisation du processeur). La meilleure performance est obtenue lorsque mem (v) = 16 Ko, ce qui est l'ordre de grandeur de cache L1 (cache de données L1 pour la i7-7700K est 4x32kB).

Bien sûr, les différences deviennent de moins en moins pertinentes plus calcul que vous avez réellement à faire sur les données. Voici les résultats si nous remplaçons sum = std::accumulate(v.begin(), v.end(), sum); par for (int k : v) sum += std::sqrt(2.0*k);:

Conclusions

1. Utilisation des paramètres de sortie au lieu de retourner en valeur peut fournir des gains de performance par la capacité de réutilisation.
2. Sur un ordinateur de bureau moderne, cela ne semble applicable aux grands vecteurs (> 16 Mo) et de petits vecteurs (<1 Ko).
3. éviter d'allouer des millions / milliards de petits vecteurs (<1 Ko). Si possible, la capacité de réutilisation, ou mieux encore, la conception de votre architecture différente.

Les résultats peuvent différer sur d'autres plates-formes. Comme d'habitude, si les questions de performance, des critères d'écriture pour votre cas d'utilisation spécifique.

Answer 6

Je pense toujours qu'il est une mauvaise pratique, mais il est intéressant de noter que mon équipe utilise MSVC 2008 et GCC 4.1, donc nous ne sommes pas en utilisant les derniers compilateurs.

Auparavant, beaucoup de points chauds indiqués dans vtune avec MSVC 2008 est descendu à la copie de chaîne. Nous avions un code comme ceci:

String Something::id() const
{
    return valid() ? m_id: "";
}

... Notez que nous avons utilisé notre propre type String (ce qui était nécessaire parce que nous fournissons un kit de développement logiciel où les auteurs de plugins pourraient utiliser différents compilateurs et donc différentes implémentations incompatibles de std :: string / std :: wstring).

J'ai fait un simple changement en réponse à la session de profilage d'échantillonnage graphique d'appel montrant être prendre une quantité importante de temps String :: String (const String &). Les méthodes comme dans l'exemple ci-dessus ont été les plus grands contributeurs (en fait la session de profilage a montré l'allocation de mémoire et désallocation d'être l'un des plus grands points chauds, avec le constructeur de copie de chaîne étant le principal contributeur pour les allocations).

Le changement que j'ai fait était simple:

static String null_string;
const String& Something::id() const
{
    return valid() ? m_id: null_string;
}

Pourtant, ce fait un monde de différence! Le point chaud est parti lors des sessions ultérieures profileurs, et en plus de cela, nous faisons beaucoup de tests unitaires en profondeur pour assurer le suivi de notre performance d'application. Tous les types de temps de test de performance a considérablement diminué après ces changements simples.

Conclusion: nous ne sommes pas en utilisant les derniers compilateurs absolus, mais il semble que nous ne pouvons toujours pas dépendre du compilateur optimisant l'écart de la copie pour le retour en termes de valeur fiable (au moins pas dans tous les cas). Cela peut ne pas être le cas pour ceux qui utilisent de nouveaux compilateurs comme MSVC 2010. Je suis impatient quand on peut utiliser C ++ 0x et utiliser simplement des références rvalue et ne jamais avoir à craindre que nous pessimizing notre code en retournant complexe les classes en valeur.

[Modifier] Comme Nate a fait remarquer, RVO applique au retour créés à l'intérieur de temporaires en fonction. Dans mon cas, il n'y avait pas de telles temporaires (à l'exception de la branche non valide où nous construisons une chaîne vide) et donc RVO n'aurait pas été le cas.

Answer 7

Juste pour pinailler un peu: il est rare dans de nombreux langages de programmation pour renvoyer des tableaux de fonctions. Dans la plupart d'entre eux, une référence au tableau est retourné. En C ++, le plus proche analogie serait de retour boost::shared_array

Answer 8

Si la performance est un problème réel, vous devez comprendre que la sémantique de déplacement ne sont pas toujours plus rapide que la copie. Par exemple, si vous avez une chaîne qui utilise le petite optimisation chaîne puis pour les petites chaînes d'un constructeur de déplacement doit faire le montant exact même du travail en tant que constructeur de copie régulière.