Comparatif simple entre vecteur standard et tableau brut

Il arrive que des gens se privent de conteneurs standards et d'outils de haut niveau par crainte d'une pénalité sur le plan des performances, en particularité pour ce qui est de la vitesse d'exécution du programme résultant. Pourtant, en C++, il est possible d'atteindre, avec des conteneurs standards, des seuils de performance comparables – parfois même supérieurs! – à ceux des tableaux bruts, dû à l'application de techniques sophistiquées dans le code sous-jacent de même qu'à la qualité des compilateurs optimisants contemporains.

À titre d'exemple, voici quelques petits comparatifs de performance entre des tableaux bruts alloués dynamiquement et gérés manuellement et des vecteurs standards (classe std::vector), les deux pour le même type de données.

Je réaliserai les tests avec la fonction tester() suivante :

#include <chrono>
#include <utility>
template <class F, class ... Args>
   auto tester(F f, Args &&... args) {
      using namespace std;
      using namespace std::chrono;
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return make_pair(res, post - pre);
   }

Allocation et libération seules

Soit les fonctions de test test_tableau() et test_vector montrées à droite. Les deux font une tâche comparable, soit allouer dynamiquement et libérer (ultérieurement) un bloc contigü en mémoire de n instances d'un type T donné.

Dans le cas du tableau, la libération est explicitement exprimée par un appel à l'opérateur delete[] alors que dans le cas du vecteur v, le destructeur de v assure la libération des données.

#include <cstddef>
#include <vector>
template <class T>
   void test_tableau(std::size_t n) {
      auto p = new T[n];
      delete [] p;
   }
template <class T>
   void test_vector(std::size_t n) {
      using std::vector;
      vector<T> v;
      v.reserve(n);
   }

Notre programme (qui peut grandement être simplifié si vous en avez envie) appellera NTESTS fois chacune de ces fonctions en allouant chaque fois un bloc de N instances d'un certain type.

Nous avons délibérément choisi deux types distincts pour les éléments des conteneurs dans ce test, pour que l'un s'applique à des primitifs (des int) pour lesquels il n'y a pas d'initialisation à réaliser, et pour que l'autre s'applique à des instances d'une classe (des std::string) pour lesquels le constructeur n'est pas banal.

Chaque fois, le temps écoulé pendant le test est saisi est affiché sous forme de millisecondes. La mesure saisie est portable, mais n'est pas très précise; elle ne nous permettra pas de départager les deux conteneurs, sauf bien sûr si les écarts sont évidents.

#include <iostream>
#include <chrono>
#include <string>
int main() {
   using namespace std;
   using namespace std::chrono;
   enum { N = 10'000'000, NTESTS = 20 };
   auto r0 = tester([] {
      for (int i = 0; i < NTESTS; ++i)
         test_tableau<int>(N);
      return 0;
   });
   cout << NTESTS << " appels de "
        << "test_tableau<int>(" << N << ") en "
        << duration_cast<milliseconds>(r0.second).count()
        << " ms." << endl;
   auto r1 = tester([] {
      for (int i = 0; i < NTESTS; ++i)
         test_vector<int>(N);
      return 0;
   });
   cout << NTESTS << " appels de "
        << "test_vector<int>(" << N << ") en "
        << duration_cast<milliseconds>(r1.second).count()
        << " ms." << endl;
   auto r2 = tester([] {
      for (int i = 0; i < NTESTS; ++i)
         test_tableau<string>(N);
      return 0;
   });
   cout << NTESTS << " appels de "
        << "test_tableau<string>(" << N << ") en "
        << duration_cast<milliseconds>(r2.second).count()
        << " ms." << endl;
   auto r3 = tester([] {
      for (int i = 0; i < NTESTS; ++i)
         test_vector<string>(N);
      return 0;
   });
   cout << NTESTS << " appels de "
        << "test_vector<string>(" << N << ") en "
        << duration_cast<milliseconds>(r3.second).count()
        << " ms." << endl;
}

À l'exécution, sur mon ordinateur, nous obtenons ce qui suit.

20 appels de test_tableau<int>(10000000) en 2 ms.
20 appels de test_vector<int>(10000000) en 2 ms.
20 appels de test_tableau<string>(10000000) en 2762 ms.
20 appels de test_vector<string>(10000000) en 15 ms.
Appuyez sur une touche pour continuer...

Remarquez que les allocations en bloc sur des int prennent un temps négligeable à se réaliser. Les opérations d'allocation et de libération de mémoire sont rapides du fait qu'elles se font sur des blocs chaque fois de même taille, ce qui permet sans doute à la prochaine allocation de récupérer ce qui a été libéré lors de la plus récente libération.

Remarquez aussi que dans le cas de l'allocation d'objets munis d'un constructeur, le vecteur standard est considérablement plus rapide que ne l'est le tableau.

Ce qui se produit ici est que, lors de l'appel à new T[n], le tableau nouvellement créé est alloué puis le constructeur par défaut de T est invoqué pour chaque élément.

Dans le cas de v.reserve(n), le vecteur de T a l'intelligence d'allouer l'espace requis pour n instances contiguës en mémoire du type T, mais sans toutefois l'initialiser. La méthode reserve() a ici un niveau de sophistication plus élevé que le simple new[] naïf. On aurait pu en arriver à de tels résultats manuellement, mais cela nous aurait demandé du code bien plus pointu qu'une simple instanciation comme dans ces exemples.

auto p = new T[n];
// ...
vector<T> v;
v.reserve(n);

Notez que, si nous avions réalisé le test sur le vecteur à l'aide du code proposé à droite, alors nous aurions eu des performances comparables avec celles du tableau car nous aurions sollicité indirectement le constructeur par défaut de T dans chaque cas. En pratique, avec ce code, j'obtiens :

20 appels de test_tableau<int>(10000000) en 8 ms.
20 appels de test_vector<int>(10000000) en 297 ms.
20 appels de test_tableau<string>(10000000) en 2999 ms.
20 appels de test_vector<string>(10000000) en 2185 ms.

...ce qui met en relief qu'il y aurait un coût de base au recours (mal géré) à un vecteur d'objets de type primitif, mais que même avec une utilisation discutable, le vecteur fait bonne figure face au tableau quand le type des éléments est plus complexe.

vector<T> v(n);

Allocation, initialisation, libération

Reprenons la même structure de test mais ajoutons cette fois un parcours naïf du conteneur nouvellement créé, parcours permettant d'intialiser chaque élément du conteneur avec une même valeur.

Nous examinerons plus loin des variantes plus sophistiquées et plus efficaces du même code.

#include <cstddef>
#include <vector>
template <class T>
   void test_tableau(std::size_t n, const T &val) {
      using namespace std;
      auto p = new T[n];
      for (size_t i = 0; i != n; ++i)
         p[i] = val;
      delete [] p;
   }
template <class T>
   void test_vector(std::size_t n, const T &val) {
      using namespace std;
      vector<T> v;
      v.reserve(n);
      for (size_t i = 0; i != n; ++i)
         v.push_back(val);
   }

Le code de test sera sensiblement le même que dans la version précédente, à ceci près que nous passerons en paramètre à chaque fonction de test la valeur qui servira à l'initialisation des éléments.

Évidemment, les valeurs d'initialisation seront les mêmes pour chaque conteneur d'un type donné. Ne pas agir ainsi fausserait les résultats.

#include <iostream>
#include <chrono>
#include <string>
int main() {
   using namespace std;
   using namespace std::chrono;
   enum { N = 10'000'000, NTESTS = 20 };
   auto r0 = tester([] {
      for (int i = 0; i < NTESTS; ++i)
         test_tableau<int>(N, 3);
      return 0;
   });
   cout << NTESTS << " appels de "
        << "test_tableau<int>(" << N << ") en "
        << duration_cast<milliseconds>(r0.second).count()
        << " ms." << endl;
   auto r1 = tester([] {
      for (int i = 0; i < NTESTS; ++i)
         test_vector<int>(N, 3);
      return 0;
   });
   cout << NTESTS << " appels de "
        << "test_vector<int>(" << N << ") en "
        << duration_cast<milliseconds>(r1.second).count()
        << " ms." << endl;
   const string value = "J'aime mon prof";
   auto r2 = tester([&] {
      for (int i = 0; i < NTESTS; ++i)
         test_tableau<string>(N, value);
      return 0;
   });
   cout << NTESTS << " appels de "
        << "test_tableau<string>(" << N << ") en "
        << duration_cast<milliseconds>(r2.second).count()
        << " ms." << endl;
   auto r3 = tester([&] {
      for (int i = 0; i < NTESTS; ++i)
         test_vector<string>(N, value);
      return 0;
   });
   cout << NTESTS << " appels de "
        << "test_vector<string>(" << N << ") en "
        << duration_cast<milliseconds>(r3.second).count()
        << " ms." << endl;
}

À l'exécution, sur mon ordinateur, nous obtenons ce qui suit.

20 appels de test_tableau<int>(10000000) en 273 ms.
20 appels de test_vector<int>(10000000) en 810 ms.
20 appels de test_tableau<string>(10000000) en 4954 ms.
20 appels de test_vector<string>(10000000) en 4252 ms.
Appuyez sur une touche pour continuer...

En ajoutant un parcours d'initialisation, le tableau emporte la mise.

Cependant, le code manque de sophistication. Examinons une variante utilisant l'algorithme standard std::fill() dans chaque cas.

Notez que j'ai utilisé de construire v avec le constructeur de vector<T> qui accepte un nombre d'éléments à la construction, dans le but de m'assurer que v contienne bel et bien des éléments suite à sa construction; ces éléments seront des T par défaut (pour les primitifs, on parlera du zéro du type, donc 0 pour un int, 0.0 pour un double, nullptr pour un pointeur, etc.). La méthode reserve(), utilisée plus haut, se limite à réserver de l'espace, sans l'initialiser.

L'idée ici est que l'algorithme std::fill() que j'utilise de part et d'autre utilise, pour faire son travail, l'affectation d'une valeur de type T à une séquence d'éléments existants de type T; l'utiliser sur de la mémoire allouée mais non-initialisée aurait été dommageable pour un type T qui ne serait pas un primitif (en pratique, ce sera sans doute été inoffensif si T est int, mais ce sera très dommageable si T est std::string).

#include <cstddef>
#include <algorithm>
#include <vector>
template <class T>
   void test_tableau(std::size_t n, const T &val) {
      using namespace std;
      auto p = new T[n];
      fill(p, p + n, val);
      delete [] p;
   }
template <class T>
   void test_vector(std::size_t n, const T &val) {
      using namespace std;
      vector<T> v(n);
      fill(begin(v), end(v), val);
   }

À l'exécution, sur mon ordinateur, nous obtenons cette fois ce qui suit.

20 appels de test_tableau<int>(10000000) en 271 ms.
20 appels de test_vector<int>(10000000) en 311 ms.
20 appels de test_tableau<string>(10000000) en 4930 ms.
20 appels de test_vector<string>(10000000) en 4056 ms.
Appuyez sur une touche pour continuer...

Les différences entre les tests sont légèrement significatives pour un outil de mesure de la précision utilisée. Les résultats ici sont essentiellement les mêmes que dans le test précédent; le principal gain ici est un gain d'élégance.

Maintenant, constatons qu'un conteneur standard comme std::vector offre des constructeurs particuliers, capables par exemple d'initialiser directement une plage de mémoire avec une valeur spécifique. Sachant cela, il est possible que le remplissage par std::fill() suivant une construction invoquant d'ores et déjà un constructeur par défaut pour chaque élément soit redondante, et que l'intelligence sous-jacente au conteneur standard puisse être utilisée à bon escient.

Examinons les résultats avec le code de test suivant. Celui sur les tableaux demeurera tel quel (on ne peut guère faire mieux en général – même pas avec std::memset(), qui ne serait applicable qu'à des types T qui seraient des POD, pour Plain Old Datatypes, un terme désuet sur le plan du texte du standard, mais qui demeure d'usage courant).

#include <cstddef>
#include <algorithm>
#include <vector>
template <class T>
   void test_tableau(std::size_t n, const T &val) {
      using namespace std;
      auto p = new T[n];
      fill(p, p + n, val);
      delete [] p;
   }
template <class T>
   void test_vector(std::size_t n, const T &val) {
      using namespace std;
      vector<T> v(n, val);
   }

À l'exécution, sur mon ordinateur, nous obtenons ceci :

20 appels de test_tableau<int>(10000000) en 272 ms.
20 appels de test_vector<int>(10000000) en 262 ms.
20 appels de test_tableau<string>(10000000) en 4818 ms.
20 appels de test_vector<string>(10000000) en 2625 ms.
Appuyez sur une touche pour continuer...

Bien utilisé, le conteneur standard est plus rapide que notre version manuelle applicable à un tableau brut. La différence dans ce test est de l'ordre de la seconde, ce qui n'est pas négligeable.

Allocation, initialisation, parcours et libération

Réalisons enfin un petit test combinant initialisation avec une séquence de valeurs, puis parcours de la séquence initialisée (pour rechercher un élément).

Comme dans les cas précédents, nous utiliserons la généricité pour réaliser les tests sur divers types (et couvrir au moins un type primitif et une classe).

Dans les deux cas, nous vérifierons la présence d'un élément donné à l'aide de l'algorithme standard std::find(), qui réalise une recherche linéaire (complexité algorithmique ).

Pour cette version naïve, la copie des valeurs initiales dans le conteneur qui sera testé se fera avec l'algorithme standard std::copy(), lui aussi de complexité linéaire (manifestement).

Remarquez tout de suite que, même dans le cas naïf proposé ici, le code reposant sur un vecteur standard est plus simple que celui reposant sur un tableau car il nous permet d'éviter une variable temporaire booléenne (dans le cas du tableau, pour éviter une fuite de ressources, il nous fait récupérer le fruit de la recherche dans une variable temporaire pour être en mesure de finaliser le tableau avant de conclure l'exécution de la fonction).

De même, le vecteur connaissant sa propre taille (contrairement au tableau brut), nous n'avons pas besoin de conserver cette taille dans une variable locale.

#include <algorithm>
#include <iterator>
#include <vector>
template <class T, class It>
   bool test_tableau(It debut, It fin, const T &val) {
      using namespace std;
      const auto n = distance(debut, fin);
      auto p = new T[n];
      copy (debut, fin, p);
      bool trouve = find(p, p + n, val) != p + n;
      delete [] p;
      return trouve;
   }
template <class T, class It>
   bool test_vector(It debut, It fin, const T &val) {
      using namespace std;
      vector<T> v(distance(debut, fin));
      copy (debut, fin, begin(v));
      return find(begin(v), end(v), val) != end(v);
   }

Le test en soit utilisera des séquences de grande taille.

Pour que le test soit significatif, les valeurs utilisées pour initialiser les séquences seront chaque fois les mêmes, et nous placerons volontairement l'élément à rechercher en toute fin de séquence, pour forcer un parcours complet.

#include <iostream>
#include <chrono>
#include <string>
int main() {
   using namespace std;
   using namespace std::chrono;
   enum { N = 10'000'000, NTESTS = 20 };
   {
      vector<int> src(N, 3);
      src.back() = 4;
      auto r0 = tester([&] {
         for (int i = 0; i < NTESTS; ++i)
            test_tableau<int>(begin(src), end(src), src.back());
         return 0;
      });
      cout << NTESTS << " appels de "
           << "test_tableau<int>(" << N << ") en "
           << duration_cast<milliseconds>(r0.second).count()
           << " ms." << endl;
      auto r1 = tester([&]{
         for (int i = 0; i < NTESTS; ++i)
            test_vector<int>(begin(src), end(src), src.back());
         return 0;
      });
      cout << NTESTS << " appels de "
          << "test_vector<int>(" << N << ") en "
          << duration_cast<milliseconds>(r1.second).count()
          << " ms." << endl;
   }
   const string value = "J'aime mon prof";
   vector<string> src(N, value);
   src.back() = "Patate";
   auto r0 = tester([&] {
      for (int i = 0; i < NTESTS; ++i)
         test_tableau<string>(begin(src), end(src), src.back());
      return 0;
   });
   cout << NTESTS << " appels de "
        << "test_tableau<string>(" << N << ") en "
        << duration_cast<milliseconds>(r0.second).count()
        << " ms." << endl;
   auto r1 = tester([&] {
      for (int i = 0; i < NTESTS; ++i)
         test_vector<string>(begin(src), end(src), src.back());
      return 0;
   });
    cout << NTESTS << " appels de "
         << "test_vector<string>(" << N << ") en "
         << duration_cast<milliseconds>(r1.second).count()
         << " ms." << endl;
}

À l'exécution, sur mon ordinateur, nous obtenons ce qui suit.

20 appels de test_tableau<int>(10000000) en 407 ms.
20 appels de test_vector<int>(10000000) en 432 ms.
20 appels de test_tableau<string>(10000000) en 5418 ms.
20 appels de test_vector<string>(10000000) en 4554 ms.
Appuyez sur une touche pour continuer...

Dans la version naïve du test, les opérations sur le tableau brut sont plus comparables à celles sur le conteneur standard.

Constatons cependant que nous réalisions, dans cette première version, une première initialisation (implicite) des éléments du vecteur avec des valeurs par défaut est réalisée, suite à quoi une copie des valeurs de la séquence source est réalisée.

En examinant la documentation, on constatera l'existence d'un constructeur de séquence dans le vecteur, comme d'ailleurs dans tous les conteneurs standards. Utiliser ce constructeur, plus à propos, nous permettra d'éviter une première initialisation bidon. Nous ne pouvons évidemment pas faire de même sur le tableau brut (du moins pas sans avoir recours à des techniques plus sophistiquées, ce qui équivaudrait en quelque sorte à réimplémenter le vecteur).

#include <algorithm>
#include <iterator>
#include <vector>
template <class T, class It>
   bool test_tableau(It debut, It fin, const T &val) {
      using namespace std;
      const auto n = distance(debut, fin);
      auto p = new T[n];
      copy (debut, fin, p);
      bool trouve = find(p, p + n, val) != p + n;
      delete [] p;
      return trouve;
   }
template <class T, class It>
   bool test_vector(It debut, It fin, const T &val) {
      using namespace std;
      vector<T> v(debut, fin);
      return find(begin(v), end(v), val) != end(v);
   }

à l'exécution, sur mon ordinateur, suite à cet ajustement (qui correspond simplement à une utilisation plus idiomatique de notre conteneur), nous obtenons maintenant ce qui suit :

20 appels de test_tableau<int>(10000000) en 404 ms.
20 appels de test_vector<int>(10000000) en 401 ms.
20 appels de test_tableau<string>(10000000) en 5277 ms.
20 appels de test_vector<string>(10000000) en 3400 ms.
Appuyez sur une touche pour continuer...

Encore une fois, lorsqu'il est bien utilisé, le conteneur standard permet la rédaction de code à la fois plus robuste (car moins susceptible de mener à des fuites de ressources, par imprudence ou par accident), plus concis (comme le montrent les sources du code de test) et plus rapide.

Lectures complémentaires

Pour enrichir votre compréhension de ce sujet, quelques liens.


Valid XHTML 1.0 Transitional

CSS Valide !