c++ - 为什么调用 vector.reserve(required + 1) 比 vector.reserve(required) 快？

Question

我正在做一些测试来测量标准容器在各种条件下的性能，我遇到了一些奇怪的事情。当我在 std::vector 的中间插入许多项目时，如果我首先使用要添加的元素的确切数量调用 reserve，我发现在大多数情况下比较基本上没有性能差异没有调用储备，这是令人惊讶的。然而，更令人惊讶的是，如果我使用 + 1 所需的确切元素数量调用 Reserve，那么我会获得显着的性能提升。这是我刚刚得到的结果示例表(所有时间都以秒为单位):

+---------------+--------+-------------------+-----------------------+
| # 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                  |
+---------------+--------+-------------------+-----------------------+

我检查了实现，它似乎没有错误。然后我在调用reserve后立即打印大小和容量进一步测试，然后在填充 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";
}

我创建了一个 C++03 版本来尝试帮助其他人重现它，但我无法在这个版本中重现它，尽管我试图通过使其尽可能直接的翻译来显示问题:

#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";
}

当前调用 reserve 的行已更改为包含 + 1 或完全删除，具体取决于我正在运行的测试。整个过程是从一个 shell 脚本运行的，该脚本从 10000 个元素开始，增加到 430000 个元素，一次一个版本。

我的处理器是 Intel i5 4 核处理器，我有 4 GiB 的内存。我会尽量简化C++11版本的代码，看看能不能隔离问题。

有谁知道为什么比我需要的多保留一个元素会导致速度提高？

Answer 1

我对程序做了如下修改:

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

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

现在，无论 a 是 0 还是 1，性能都是相同的(快速)。结论必须是额外项目的预订对性能没有影响(问题中假设了这一点)。此外，对源代码或编译器标志的其他小改动会在快慢之间切换性能，因此看起来代码优化器在某些情况下比在其他情况下运气更好。

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);
}