Pourquoi appeler vector.reserve (obligatoire + 1) plus rapidement que vector.reserve (obligatoire)?

Question

Je suis en train de faire quelques tests de mesure de la performance de conteneurs standard dans des conditions différentes, et je suis tombé sur quelque chose de bizarre. Quand je suis en insérant de nombreux éléments dans le milieu d'un std::vector, si j'ai d'abord appel réserve avec le nombre exact d'éléments que je vais être en ajoutant, je ne vois pratiquement pas de différence de performances dans la plupart des cas, comparativement à ne pas appeler de réserve, ce qui est surprenant. Plus surprenant, cependant, est que si je l'appelle, réserve avec le nombre exact d'éléments que j'ai besoin d' + 1,, puis-je obtenir une amélioration significative des performances. Ceci est un exemple de tableau de résultats que je viens d' (tous les temps en secondes):

+---------------+--------+-------------------+-----------------------+
| # of elements | vector | vector (reserved) | vector (reserved + 1) |
+---------------+--------+-------------------+-----------------------+
|         10000 | 0.04   | 0.04              | 0.03                  |
|         20000 | 0.14   | 0.14              | 0.11                  |
|         30000 | 0.32   | 0.32              | 0.25                  |
|         40000 | 0.55   | 0.55              | 0.44                  |
|         50000 | 0.87   | 0.85              | 0.66                  |
|         60000 | 1.24   | 1.24              | 0.96                  |
|         70000 | 1.69   | 1.68              | 1.31                  |
|         80000 | 2.17   | 2.21              | 1.71                  |
|         90000 | 2.78   | 2.75              | 2.16                  |
|        100000 | 3.43   | 3.44              | 2.68                  |
|        110000 | 4.13   | 4.15              | 3.23                  |
|        120000 | 4.88   | 4.89              | 3.86                  |
|        130000 | 5.79   | 5.8               | 4.51                  |
|        140000 | 6.71   | 6.71              | 5.24                  |
|        150000 | 7.7    | 7.7               | 6.02                  |
|        160000 | 8.76   | 8.67              | 6.86                  |
|        170000 | 9.9    | 9.91              | 7.74                  |
|        180000 | 11.07  | 10.98             | 8.64                  |
|        190000 | 12.34  | 12.35             | 9.64                  |
|        200000 | 13.64  | 13.56             | 10.72                 |
|        210000 | 15.1   | 15.04             | 11.67                 |
|        220000 | 16.59  | 16.41             | 12.89                 |
|        230000 | 18.05  | 18.06             | 14.13                 |
|        240000 | 19.64  | 19.74             | 15.36                 |
|        250000 | 21.34  | 21.17             | 16.66                 |
|        260000 | 23.08  | 23.06             | 18.02                 |
|        270000 | 24.87  | 24.89             | 19.42                 |
|        280000 | 26.5   | 26.58             | 20.9                  |
|        290000 | 28.51  | 28.69             | 22.4                  |
|        300000 | 30.69  | 30.74             | 23.97                 |
|        310000 | 32.73  | 32.81             | 25.57                 |
|        320000 | 34.63  | 34.99             | 27.28                 |
|        330000 | 37.12  | 37.17             | 28.99                 |
|        340000 | 39.36  | 39.43             | 30.83                 |
|        350000 | 41.7   | 41.48             | 32.45                 |
|        360000 | 44.11  | 44.22             | 34.55                 |
|        370000 | 46.62  | 46.71             | 36.22                 |
|        380000 | 49.09  | 48.91             | 38.46                 |
|        390000 | 51.71  | 51.98             | 40.22                 |
|        400000 | 54.45  | 54.56             | 43.03                 |
|        410000 | 57.23  | 57.29             | 44.84                 |
|        420000 | 60     | 59.73             | 46.67                 |
|        430000 | 62.9   | 63.03             | 49.3                  |
+---------------+--------+-------------------+-----------------------+

J'ai vérifié la mise en œuvre, et il ne semble pas avoir un tout-en-un message d'erreur. J'ai ensuite testé par l'impression de la taille et de la capacité immédiatement après l'appel de la réserve, et puis j'ai imprimé de nouveau après remplissage du vecteur, et tout semble bon.

before:
    size: 0
    capacity: 10000
after:
    size: 10000
    capacity: 10000

before:
    size: 0
    capacity: 20000
after:
    size: 20000
    capacity: 20000

...

Compilateur est gcc 4.7.2 sur Fedora Linux x86_64. Options du compilateur sont -std=c++11 -Ofast -march=native -funsafe-loop-optimizations -flto=4 - fwhole-program

Le code est ci-dessous.

#include <algorithm>
#include <array>
#include <cstdint>
#include <vector>
#include <random>
#include <string>
#include <iostream>
#include <fstream>

#include <boost/timer.hpp>

namespace {
constexpr size_t array_size = 1;

unsigned number() {
        static std::random_device rd;
        static std::mt19937 random_engine(rd());
        static std::uniform_int_distribution<uint32_t> distribution(0, std::numeric_limits<uint32_t>::max());
        return distribution(random_engine);
}

class Class {
        public:
                Class() {
                        x[0] = number();
                }
                std::string to_string() const {
                        return std::to_string(x[0]);
                }
                inline friend bool operator<=(Class const & lhs, Class const & rhs) {
                        return lhs.x[0] <= rhs.x[0];
                }
        private:
                std::array<uint32_t, array_size> x;
};

template<typename Container>
void add(Container & container, Class const & value) {
        auto const it = std::find_if(std::begin(container), std::end(container), [&](Class const & c) {
                return value <= c;
        });
        container.emplace(it, value);
}

// Do something with the result
template<typename Container>
void insert_to_file(Container const & container) {
        std::fstream file("file.txt");
        for (auto const & value : container) {
                file << value.to_string() << '\n';
        }
}

template<typename Container>
void f(std::vector<Class> const & values) {
        Container container;
        container.reserve(values.size());
        for (auto const & value : values) {
                add(container, value);
        }
        insert_to_file(container);
}

}

int main(int argc, char ** argv) {
        std::size_t const size = (argc == 1) ? 1 : std::stoul(argv[1]);
        // Default constructor of Class fills in values here
        std::vector<Class> const values_to_be_copied(size);
        typedef std::vector<Class> Container;
        boost::timer timer;
        f<Container>(values_to_be_copied);
        std::cerr << "Finished in " << timer.elapsed() << " seconds.\n";
}

J'ai créé un C++03 version de l'essayer et aider d'autres personnes à le reproduire, mais je ne peux pas le reproduire dans cette version, même si on essaie d'en faire apparaître le problème de la rendre aussi directe d'une traduction possible:

#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <vector>
#include <string>
#include <iostream>

#include <boost/array.hpp>
#include <boost/cstdint.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int_distribution.hpp>
#include <boost/timer.hpp>

namespace {
unsigned number() {
        static boost::random::mt19937 random_engine;
        static boost::random::uniform_int_distribution<boost::uint32_t> distribution(0, std::numeric_limits<boost::uint32_t>::max());
        return distribution(random_engine);
}

class Class {
        public:
                Class() {
                        x[0] = number();
                }
                inline friend bool operator<=(Class const & lhs, Class const & rhs) {
                        return lhs.x[0] <= rhs.x[0];
                }
                std::string to_string() const {
                        return boost::lexical_cast<std::string>(x[0]);
                }
        private:
                boost::array<boost::uint32_t, 1> x;
};

class Less {
public:
        Less(Class const & c):
                value(c) {
        }
        bool operator()(Class const & c) const {
                return value <= c;
        }
private:
        Class value;
};

void add(std::vector<Class> & container, Class const & value) {
        std::vector<Class>::iterator it = std::find_if(container.begin(), container.end(), Less(value));
        container.insert(it, value);
}

// Do something with the result
void insert_to_file(std::vector<Class> const & container) {
        std::fstream file("file.txt");
        for (std::vector<Class>::const_iterator it = container.begin(); it != container.end(); ++it) {
                file << it->to_string() << '\n';
        }
}

void f(std::vector<Class> const & values) {
        std::vector<Class> container;
        container.reserve(values.size() + 1);
        for (std::vector<Class>::const_iterator it = values.begin(); it != values.end(); ++it) {
                add(container, *it);
        }
        insert_to_file(container);
}

}

int main(int argc, char ** argv) {
        std::size_t const size = (argc == 1) ? 1 : boost::lexical_cast<std::size_t>(argv[1]);
        // Default constructor of Class fills in values here
        std::vector<Class> const values_to_be_copied(size);
        boost::timer timer;
        f(values_to_be_copied);
        std::cerr << "Finished in " << timer.elapsed() << " seconds.\n";
}

La ligne qui prévoit la réserve a été modifiée pour inclure un + 1 ou a été entièrement supprimée, selon le test, j'ai été en cours d'exécution. La chose entière a été exécuté à partir d'un script shell qui a commencé à 10000 éléments et augmentée jusqu'à 430000 éléments, passant d'une version à la fois.

Mon processeur est un Intel i5 4-core processeur, et j'ai 4 Go de mémoire. Je vais essayer de simplifier le C++11 version du code, autant que possible, pour voir si je peux isoler le problème.

Personne ne sait pourquoi réserver un élément de plus que j'ai besoin est à l'origine de cette augmentation de la vitesse?

Answer 1

J'ai fait la modification ci-après le programme:

size_t a = getenv("A") ? 1 : 0;

void f(std::vector<Class> const & values) {
    ...
    container.reserve(values.size() + a);
    ...
}

Maintenant, la performance est la même (rapide), peu importe si a est 0 ou 1. La conclusion doit être que la réservation d'un élément supplémentaire n'a aucun impact sur les performances (ce qui a été supposé dans la question). Aussi d'autres petits changements dans le code source ou les drapeaux de compilation permet de basculer de la performance entre rapide et lent, de sorte qu'il ressemble le code de l'optimiseur a juste la chance de mieux dans certains cas que dans d'autres.

La suite de la mise en œuvre de f() déclenche l'opposé du comportement avec les mêmes options de compilation, donc il est plus rapide lorsque la taille exacte est réservé et lent quand un élément supplémentaire est réservé:

template<typename Container>
void f(std::vector<Class> const & values) {
    Container container;
    container.reserve(values.size());
    for (auto it = values.begin(); it != values.end(); ++it) {
        add(container, *it);
    }
    insert_to_file(container);
}

Answer 2

Je crois que la différence entre reserve de la taille exacte vs un élément supplémentaire dans votre cas spécifique est absolument négligeable. En outre, certaines implémentations peuvent tronquer la taille demandée pour certains nombre (comme la puissance de 2), donc il n'y aura pas de différence du tout.

Otoh, que le goulot d'étranglement des performances de votre programme semble être quelque chose d'autre. Vous effectuez deux coûteuses opérations de matrice:

• Recherche de l'endroit le plus approprié pour un élément d'insertion
• Insérer un élément unique "dans le milieu"

Comme vous l'avez probablement remarqué, votre programme dépend random. Il est facile de voir que, dans votre cas particulier, si les nombres aléatoires sont de plus en plus - votre programme courir plus vite, otoh, que si ils shrink - vous aurez à effectuer plus "coûteux" insertions.

Je suppose que de subtiles modifications de code de déclenchement différents génération de nombre aléatoire.