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

Je fais des tests mesurant les performances de conteneurs standard dans diverses conditions et je suis tombé sur quelque chose de bizarre. Lorsque j’insère de nombreux éléments au milieu d’un std::vector , si je commence par appeler reserve avec le nombre exact d’éléments que j’appendai, je ne vois pratiquement pas de différence de performance dans la plupart des cas par rapport à surprenant. Plus surprenant, cependant, si j’appelle reserve avec le nombre exact d’éléments dont j’ai besoin + 1 , alors j’ai une amélioration significative des performances. Ceci est un exemple de tableau de résultats que je viens de recevoir (tous les temps sont 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é l’implémentation, et il ne semble pas y avoir d’erreur un à un. J’ai ensuite testé en imprimant la taille et la capacité immédiatement après avoir appelé reserve, puis je les ai imprimées à nouveau après avoir rempli le 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 ... 

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

Le code est ci-dessous.

 #include  #include  #include  #include  #include  #include  #include  #include  #include  namespace { constexpr size_t array_size = 1; unsigned number() { static std::random_device rd; static std::mt19937 random_engine(rd()); static std::uniform_int_dissortingbution dissortingbution(0, std::numeric_limits::max()); return dissortingbution(random_engine); } class Class { public: Class() { x[0] = number(); } std::ssortingng to_ssortingng() const { return std::to_ssortingng(x[0]); } inline friend bool operator<=(Class const & lhs, Class const & rhs) { return lhs.x[0] <= rhs.x[0]; } private: std::array x; }; template 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 void insert_to_file(Container const & container) { std::fstream file("file.txt"); for (auto const & value : container) { file << value.to_string() << '\n'; } } template void f(std::vector 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 const values_to_be_copied(size); typedef std::vector Container; boost::timer timer; f(values_to_be_copied); std::cerr << "Finished in " << timer.elapsed() << " seconds.\n"; } 

J’ai créé une version C ++ 03 pour essayer d’aider d’autres personnes à la reproduire, mais je ne peux pas la reproduire dans cette version, bien qu’elle tente de montrer le problème en le rendant aussi direct que possible d’une traduction:

 #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  namespace { unsigned number() { static boost::random::mt19937 random_engine; static boost::random::uniform_int_dissortingbution dissortingbution(0, std::numeric_limits::max()); return dissortingbution(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(x[0]); } private: boost::array 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 & container, Class const & value) { std::vector::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 const & container) { std::fstream file("file.txt"); for (std::vector::const_iterator it = container.begin(); it != container.end(); ++it) { file <to_ssortingng() << '\n'; } } void f(std::vector const & values) { std::vector container; container.reserve(values.size() + 1); for (std::vector::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(argv[1]); // Default constructor of Class fills in values here std::vector 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 appelle actuellement la réserve a été modifiée pour inclure un + 1 ou a été complètement supprimée, selon le test que je exécutais. La totalité du processus a été exécutée à partir d’un script shell qui a démarré à 10000 éléments et a augmenté jusqu’à 430000 éléments, allant d’une version à la fois.

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

Est-ce que quelqu’un sait pourquoi réserver un élément de plus que ce qui est nécessaire provoque cette augmentation de la vitesse?

    J’ai apporté les modifications suivantes au programme:

     size_t a = getenv("A") ? 1 : 0; void f(std::vector const & values) { ... container.reserve(values.size() + a); ... } 

    Maintenant, la performance est la même (rapide) indépendamment du fait que a est égal à 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 était supposé dans la question). D’autres modifications mineures apscopes au code source ou aux indicateurs du compilateur font basculer les performances entre rapide et lent, de sorte qu’il semble que l’optimiseur de code ait plus de chance dans certains cas que dans d’autres.

    L’implémentation suivante de f () déclenche le comportement opposé avec les mêmes indicateurs du compilateur. Il est donc rapide lorsque la taille exacte est réservée et lente lorsqu’un élément supplémentaire est réservé:

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

    Je crois que la différence entre une reserve de taille exacte et un élément supplémentaire dans votre cas particulier est absolument négligeable. De plus, certaines implémentations peuvent tronquer la taille demandée à un certain nombre (comme la puissance de 2), il n’y aura donc aucune différence.

    OTOH le goulot d’étranglement de votre programme semble être autre chose. Vous effectuez deux opérations de tableau onéreuses:

    • Rechercher le lieu approprié pour une insertion d’élément
    • Insérer un seul élément “au milieu”

    Comme vous l’avez probablement remarqué, votre programme dépend du random . Il est facile de voir que dans votre cas particulier, si les nombres aléatoires augmentent – votre programme s’exécutera plus vite, OTOH s’ils diminuent – vous devrez effectuer des insertions plus “coûteuses”.

    Je suppose que les changements de code subtils peuvent déclencher une génération de nombres aléatoires différente.