push_back () и emplace_back () за кадром - PullRequest
0 голосов
/ 05 июня 2018

В настоящее время я изучаю C ++ самостоятельно, и мне любопытно, как push_back() и emplace_back() работают под капотом.Я всегда предполагал, что emplace_back() быстрее, когда вы пытаетесь создать и поместить большой объект в конец контейнера, например, вектор.

Давайте предположим, что у меня есть Student объект, который яхочу добавить к концу вектора студентов.

struct Student {
   string name;
   int student_ID;
   double GPA;
   string favorite_food;
   string favorite_prof;
   int hours_slept;
   int birthyear;
   Student(string name_in, int ID_in, double GPA_in, string food_in, 
           string prof_in, int sleep_in, int birthyear_in) :
           /* initialize member variables */ { }
};

Предположим, я вызываю push_back() и помещаю объект Student в конец вектора:

vector<Student> vec;
vec.push_back(Student("Bob", 123456, 3.89, "pizza", "Smith", 7, 1997));

Насколько я понимаю, push_back создает экземпляр объекта Student вне вектора и затем перемещает его в конец вектора.

Диаграмма: https://ibb.co/hV6Jho

Я также могу использовать вместо push:

vector<Student> vec;
vec.emplace_back("Bob", 123456, 3.89, "pizza", "Smith", 7, 1997);

Насколько я понимаю, объект Student создается в самом конце вектора, поэтому перемещение не требуется.

Диаграмма: enter image description here

Таким образом, будет иметь смысл, что развертывание будет быстрее, особенно если будет добавлено много объектов Student.Однако, когда я рассчитал эти две версии кода:

for (int i = 0; i < 10000000; ++i) {
    vec.push_back(Student("Bob", 123456, 3.89, "pizza", "Smith", 7, 1997));
}

и

for (int i = 0; i < 10000000; ++i) {
    vec.emplace_back("Bob", 123456, 3.89, "pizza", "Smith", 7, 1997);
}

, я ожидал, что последняя будет быстрее, так как большой объект Student не нужно будет перемещать,Как ни странно, версия emplace_back оказалась медленнее (при нескольких попытках).Я также попытался вставить 10000000 объектов Student, где конструктор получает ссылки, а аргументы в push_back() и emplace_back() хранятся в переменных.Это также не сработало, так как emplace был еще медленнее.

Я проверил, чтобы убедиться, что я вставляю одинаковое количество объектов в обоих случаях.Разница во времени не слишком велика, но применение заканчивалось медленнее на несколько секунд.

Что-то не так с моим пониманием того, как работают push_back() и emplace_back()?Большое спасибо за ваше время!

Вот код в соответствии с просьбой.Я использую компилятор g ++.

Откат назад:

struct Student {
   string name;
   int student_ID;
   double GPA;
   string favorite_food;
   string favorite_prof;
   int hours_slept;
   int birthyear;
   Student(string name_in, int ID_in, double GPA_in, string food_in, 
           string prof_in, int sleep_in, int birthyear_in) :
           name(name_in), student_ID(ID_in), GPA(GPA_in), 
           favorite_food(food_in), favorite_prof(prof_in),
           hours_slept(sleep_in), birthyear(birthyear_in) {}
};

int main() {
    vector<Student> vec;
    vec.reserve(10000000);
    for (int i = 0; i < 10000000; ++i) 
         vec.push_back(Student("Bob", 123456, 3.89, "pizza", "Smith", 7, 1997));
    return 0;
}

Возврат:

struct Student {
   string name;
   int student_ID;
   double GPA;
   string favorite_food;
   string favorite_prof;
   int hours_slept;
   int birthyear;
   Student(string name_in, int ID_in, double GPA_in, string food_in, 
           string prof_in, int sleep_in, int birthyear_in) :
           name(name_in), student_ID(ID_in), GPA(GPA_in), 
           favorite_food(food_in), favorite_prof(prof_in),
           hours_slept(sleep_in), birthyear(birthyear_in) {}
};

int main() {
    vector<Student> vec;
    vec.reserve(10000000);
    for (int i = 0; i < 10000000; ++i) 
         vec.emplace_back("Bob", 123456, 3.89, "pizza", "Smith", 7, 1997);
    return 0;
}

1 Ответ

0 голосов
/ 07 июля 2018

Такое поведение связано со сложностью std::string.Здесь взаимодействуют несколько вещей:

  • Оптимизация малых строк (SSO)
  • В версии push_back компилятор может определять длину строки при компиляции-time, тогда как компилятору не удалось сделать это для версии emplace_back.Таким образом, вызов emplace_back требует вызовов на strlen.Кроме того, поскольку компилятор не знает длину строкового литерала, он должен генерировать код для случаев как SSO, так и не-SSO (см. Джейсона Тернера "Инициализированные списки инициализаторов, давайте исправим их" ; это долгий разговор, но он следит за проблемой вставки строк в вектор по всему нему)

Рассмотрим этот более простой тип:

struct type {
  std::string a;
  std::string b;
  std::string c;

  type(std::string a, std::string b, std::string c)
    : a{a}
    , b{b}
    , c{c}
  {}
};

Обратите внимание, как конструктор копии a, b и c.

Если сравнить это с базовым уровнем просто выделения памяти , мы видим, что push_back превосходит emplace_back:

enter image description here

Нажмите на изображение для ссылки быстрого стенда

ПосколькуВсе строки в вашем примере помещаются в буфер SSO, копирование в этом случае так же дешево, как и перемещение.Таким образом, конструктор совершенно эффективен, а улучшения по сравнению с emplace_back имеют меньший эффект.

Кроме того, если мы ищем сборку как для вызова push_back, так и для вызована emplace_back:

// push_back call
void foo(std::vector<type>& vec) {
    vec.push_back({"Bob", "pizza", "Smith"});
}
// emplace_back call
void foo(std::vector<type>& vec) {
    vec.emplace_back("Bob", "pizza", "Smith");
}

(Сборка здесь не копируется. Она массивная. std::string сложная)

Мы видим, что emplace_back имеет вызовы strlen, тогда как push_back нет.Поскольку расстояние между строковым литералом и создаваемым std::string увеличивается, компилятору не удалось оптимизировать вызов strlen.

Явный вызов конструктора std::string приведет к удалению вызовов strlen, но больше не будет создавать их на месте, так что это не сработает для ускорения emplace_back.

Все это говорит: , если мы покинем SSO, используя достаточно длинные строки , стоимость выделения полностью заглушает эти детали, поэтому и emplace_back, и push_back имеют одинаковую производительность:

enter image description here

Нажмите на изображение для быстрой ссылки на стенд


Если вы исправите конструктор type для перемещения его аргументов, emplace_back станет быстрее во всех случаях.

struct type {
  std::string a;
  std::string b;
  std::string c;

  type(std::string a, std::string b, std::string c)
    : a{std::move(a)}
    , b{std::move(b)}
    , c{std::move(c)}
  {}
};

Корпус SSO

enter image description here

Нажмите на изображение, чтобы перейти к ссылке на быстрый стенд

Длинный футляр

enter image description here

Нажмите на изображениедля быстрого-стандартная ссылка

Однако дело SSO push_back замедлилось;кажется, что компилятор создает дополнительные копии.

Оптимальная версия *1126* оптимальной версии *1126* не имеет этого недостатка (обратите внимание на изменение масштаба по вертикальной оси):

struct type {
  std::string a;
  std::string b;
  std::string c;

  template <typename A, typename B, typename C>
  type(A&& a, B&& b, C&& c)
    : a{std::forward<A>(a)}
    , b{std::forward<B>(b)}
    , c{std::forward<C>(c)}
  {}
};

enter image description here

Нажмите на изображение для быстрой ссылки

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...