为什么要调用vector.reserve（required + 1）比vector.reserve（required）要快？
我正在做一些testing标准容器在各种条件下的性能的testing，我遇到了一些奇怪的事情。 当我向std::vector中插入多个项目时，如果我首先调用reserve来确定要添加的元素的确切数目，那么在大多数情况下，我看不出与不调用reserve的性能差别，奇怪。 然而，更令人惊讶的是，如果我将所需要的元素的确切数量加上保留数+ 1 ，那么我将得到显着的性能提升。 这是我刚刚得到的结果样本表（所有时间都是在几秒钟内）：
+---------------+--------+-------------------+-----------------------+ | # 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 | +---------------+--------+-------------------+-----------------------+
我检查了实现，并没有出现一个错误。 然后我打电话预约后立即打印尺寸和容量进行了进一步testing，然后在填充vector后再打印出来，一切都看起来不错。
before: size: 0 capacity: 10000 after: size: 10000 capacity: 10000 before: size: 0 capacity: 20000 after: size: 20000 capacity: 20000 ...
编译器是Fedora Linux x86_64上的gcc 4.7.2。 编译器选项是-std=c++11 -Ofast -march=native -funsafe-loop-optimizations -flto=4 - fwhole-program
代码如下。
#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"; }
我创build了一个C ++ 03版本来试图帮助其他人重现它，但是我不能在这个版本中重现它，尽pipe试图通过使它直接作为翻译来显示问题：
#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"; }
当前调用保留的行被更改为包含+ 1或完全删除，这取决于我正在运行的testing。 整个事情是从一个shell脚本运行的，这个脚本从10000个元素开始，增加到430000个元素，一次只能运行一个版本。
我的处理器是一个英特尔i5 4核心处理器，我有4 GiB的内存。 我会尝试尽可能简化C ++ 11版本的代码，以查看是否可以隔离问题。
有谁知道为什么保留一个比我需要的元素是造成这种速度的增加？
我对程序做了以下修改：
size_t a = getenv("A") ? 1 : 0; void f(std::vector<Class> const & values) { ... container.reserve(values.size() + a); ... }
现在，无论a是0还是1，performance都是一样的（快）。结论必须是保留一个额外的项目没有性能影响（这是在问题中假定的）。 对源代码或编译器标志进行的其他小改动也可以在快慢之间切换，所以看起来代码优化器在某些情况下比其他情况下运行得更好。
下面的f（）的实现触发相同的编译器标志的相反的行为，因此当保留精确的大小时它是快的，而当保留一个额外的项时它是慢的。
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); }
我相信在您的具体情况下准确大小的reserve与一个额外项目之间的差异是绝对可以忽略不计的。 而且，一些实现可能会将请求的大小截断为某个数字（比如2的幂），因此根本就没有任何区别。
OTOH你的程序的性能瓶颈似乎是别的。 你执行两个昂贵的数组操作：
- search元素插入的适当位置
- 在“中间”插入一个元素
正如你可能注意到的，你的程序依赖于random 。 很容易看到，在你的具体情况下，如果随机数字越来越多 – 你的程序运行得更快，OTOH缩小 – 你将不得不执行更多的“昂贵”的插入。
我猜这些细微的代码更改可能会触发不同的随机数生成。
