Я делаю некоторые тесты, измеряющие производительность стандартных контейнеров при различных условиях, и я наткнулся на что-то странное. Когда я вставляю много элементов в середину std::vector, если я сначала резервирую вызов с точным количеством элементов, которые я буду добавлять, я вижу, по сути, не разница в производительности в большинстве случаев по сравнению с не вызывающим резервом, что удивительно, Однако еще более удивительно, что если я назову резерв с точным количеством элементов, которые мне нужны + 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 |
+---------------+--------+-------------------+-----------------------+
Я проверил реализацию, и она, похоже, не имеет ошибки "один за другим". Затем я дополнительно тестировал, распечатывая размер и емкость сразу после вызова резерва, а затем я распечатывал их снова после заполнения вектора, и все выглядит хорошо.
before:
size: 0
capacity: 10000
after:
size: 10000
capacity: 10000
before:
size: 0
capacity: 20000
after:
size: 20000
capacity: 20000
...
Компилятор - gcc 4.7.2 на Fedora Linux x86_64. Параметры компилятора -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";
}
Я создал версию С++ 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";
}
Линия, которая в настоящее время вызывает резерв, была изменена, чтобы включить + 1 или была полностью удалена, в зависимости от того, какой тест я запускал. Все это было запущено из оболочки script, которая начиналась с 10000 элементов и увеличивалась до 430000 элементов, переходя по одной версии за раз.
Мой процессор - это 4-ядерный процессор Intel i5, и у меня есть 4 гигабайта памяти. Я попытаюсь как можно больше упростить версию кода на С++ 11, чтобы увидеть, могу ли я изолировать проблему.
Кто-нибудь знает, почему резервирование еще одного элемента, чем мне нужно, вызывает это увеличение скорости?
