Является ли std :: push_back относительно дорогим в использовании?

Question

Я хочу улучшить производительность следующего кода.Какой аспект может повлиять на производительность кода при его выполнении?

Кроме того, учитывая, что нет ограничений на количество объектов, которые вы можете добавить в контейнер, какие улучшения можно было бы внести в «Object» или «addToContainer» для повышения производительности программы?

Мне было интересно, влияет ли std :: push_back в C ++ на производительность кода каким-либо образом?Особенно, если нет ограничений на добавление в список.

struct Object{
    string name;
    string description;
};

vector<Object> container;
void addToContainer(Object object) {
    container.push_back(object);
}

int main() {
    addToContainer({ "Fira", "+5 ATTACK" });
    addToContainer({ "Potion", "+10 HP" });
}

Answer 1

push_back может быть очень дорогим, но как и все, это зависит от контекста.Возьмем, к примеру, этот ужасный код:

std::vector<float> slow_func(const float* ptr)
{
   std::vector<float> v;
   for(size_t i = 0; i < 256; ++i)
     v.push_back(ptr[i]);
   return v;
}

каждый вызов push_back должен выполнять следующее:

1. Проверьте, достаточно ли места в векторе
2. Если нет, выделите новую память и скопируйте старые значения в новый вектор
3. скопируйте новый элемент в конец вектора
4. конец приращения

Здесь есть две большие проблемы с производительностью.Во-первых, каждая операция push_back зависит от предыдущей операции (так как предыдущая операция изменила конец, и, возможно, все содержимое массива, если его нужно было изменить размер).Это в значительной степени разрушает любые возможности векторизации в коде.Взгляните сюда:

https://godbolt.org/z/RU2tM0

Функцию, которая использует push_back, не очень приятно.По сути, он вынужден копировать по одному поплавку за раз.Теперь, если вы сравните это с альтернативным подходом, где вы сначала изменяете размер, а затем назначаете;компилятор просто заменяет весь лот вызовом new и вызовом memcpy.Это будет на несколько порядков быстрее, чем в предыдущем методе.

std::vector<float> fast_func(const float* ptr)
{
   std::vector<float> v(256);
   for(size_t i = 0; i < 256; ++i)
     v[i] = ptr[i];
   return v;
}

НО, и это большое, но относительная производительность push_back очень сильно зависит от того, можно ли тривиально скопировать элементы в массиве(или переехал).Если в качестве примера вы делаете что-то глупое, например:

struct Vec3 {
   float x = 0;
   float y = 0;
   float z = 0;
};

Хорошо, теперь, когда мы сделали это:

std::vector<Vec3> v(256);

Компилятор выделит память, но также будет вынужден установить все значения вноль (что бессмысленно, если вы собираетесь перезаписать их снова!).Очевидный способ обойти это - использовать другой конструктор:

std::vector<Vec3> v(ptr, ptr + 256);

Так что, на самом деле, используйте только push_back (ну, в действительности, вы должны предпочесть emplace_back в большинстве случаев), когда либо:

1. дополнительные элементы добавляются в ваш вектор время от времени
2. или, объекты, которые вы добавляете, сложны для построения (в этом случае используйте emplace_back!)

Answer 2

Прежде чем делать НИЧЕГО, профилируйте код и получите эталонный тест. После того, как вы внесете изменения в профиль, получите код и получите тест. Сравните показатели. Если вы этого не сделаете, вы бросаете кости. Это быстрее? Кто знает.

профиль профиль профиль.

С push_back у вас есть две основные проблемы:

1. Изменение размера vector при заполнении и
2. Копирование объекта в vector.

Существует ряд улучшений, которые можно внести в стоимость изменения размера push_back в зависимости от того, как добавляются элементы.

Стратегическое использование reserve, например, для минимизации размера изменения размера. Если вы знаете, сколько элементов будет добавлено, вы можете проверить capacity и size, чтобы узнать, стоит ли вам потратить время на reserve, чтобы избежать многократного изменения размера. Обратите внимание, что для этого требуется знание стратегии расширения vector, которая зависит от конкретной реализации. Оптимизация для одной vector реализации может быть ужасной ошибкой для другой.

Вы можете использовать insert для добавления нескольких элементов одновременно. Конечно, это почти бесполезно, если вам нужно добавить еще один контейнер в код для массовой вставки.

Если вы не знаете, сколько элементов поступает, вы можете также позволить vector выполнить свою работу и оптимизировать, КАК элементы добавляются.

Например

void addToContainer(Object object) // pass by value. Possible copy 
{
    container.push_back(object); // copy
}

Эти копии могут быть дорогими. Избавься от них.

void addToContainer(Object && object) //no copy and can still handle temporaries
{
    container.push_back(std::move(object)); // moves rather than copies 
}

std::string часто очень дешево перемещать.

Этот вариант addToContainer можно использовать с

addToContainer({ "Fira", "+5 ATTACK" });
addToContainer({ "Potion", "+10 HP" });

и может просто перенести указатель и как можно меньше учетных переменных на string. Они временные люди, поэтому никому нет дела, если они вырвут их кишки и выбросят трупы.

Что касается существующих Object s

Object o{"Pizza pop", "+5 food"};
addToContainer(std::move(o));

Если они расходуются, они также перемещаются. Если они не расходуются ...

void addToContainer(const Object & object) // no copy
{
    container.push_back(object); // copy
}

У вас перегрузка, которая делает это нелегко.

Подбрасывание этого

Если у вас уже есть несколько элементов, которые, как вы знаете, будут в списке, вместо добавления их всех по одному, используйте список инициализации:

vector<Object> container{
    {"Vorpal Cheese Grater", "Many little pieces"},
    {"Holy Hand Grenade", "OMG Damage"}
};

Answer 3

без каких-либо других требований, к сожалению, это наиболее эффективно:

 void addToContainer(Object) { } 

чтобы ответить на остальную часть вашего вопроса. В общем случае push_back будет просто добавлять в конец выделенный вектор O (1), но иногда потребуется увеличивать вектор, который можно амортизировать, но равен O (N)

также, вероятно, было бы более эффективно не использовать string, а сохранить char *, хотя управление памятью может быть сложным, если оно не всегда добавляется буквально