Copy elision (RVO & NRVO)

Оптимизация возвращаемого значений (RVO), оптимизация именованного возвращаемого значения (NRVO) и Copy-Elision появились в C++ начиная с C++98. Ниже я объясню, что означают эти концепции и как они помогают улучшить производительность во время выполнения.

Для тестирования напишем структуру, которая будет выводить информацию на ключевых этапах жизни объекта:

struct Printer { // Заметьте, что у всех методов есть сайт эффект
    Printer() {  cout << "Default constructor\n"; }
    ~Printer() { cout << "Desctructor\n"; }

    Printer(const Printer&) { cout << "Copy constructor\n"; }
    Printer(Printer&&) { cout << "Move constructor\n"; }

    Printer& operator=(const Printer&) {
        cout << "Copy assignment\n";
        return *this;
    }

    Printer& operator=(Printer&&) {
        cout << "Move assignment\n";
        return *this;
    }
};

Оптимизация возвращаемого значения (RVO)

В основном RVO означает, что компилятору разрешено избегать создания временных объектов для возвращаемых значений, даже если они имеют сайд эфекты. Вот простой пример:

Printer getPrinter() {
    return Printer{};
}

int main() {
    Printer printer = getPrinter();
}

Результат работы (флаг -fno-elide-constructors отключает RVO в g++):

$ g++ -std=c++11 main.cpp && ./a.out
Default constructor
Desctructor

$ g++ -std=c++11 -fno-elide-constructors main.cpp && ./a.out
Default constructor
Move constructor
Desctructor
Move constructor
Desctructor
Desctructor

При первом запуске (без флага -fno-elide-constructors) компилятор не стал строго следовать написанному коду, несмотря на то, что код имел явный побочный эффект (вывод текста в консоль). Это также показывает, что по умолчанию программы компилируются с RVO.

Без RVO компилятор создает 3 объекта типа Printer:

  1. Временный объект внутри функции getPrinter()
    Вывод: Default constructor
  2. Временный объект для возвращаемого объекта внутри main()
    Вывод: Move constructor
  3. Именованный объект printer
    Вывод: Move constructor

Производительность RVO

Особенность в том, что эта оптимизация делает возврат объектов бесплатным. Это работает из-за того, что памяти для возвращаемого объекта выделяется в кадре стека вызывающей стороны (т.е. память под возвращаемый объект выделяется в функции main(), а не в getPrinter()). Функция, возвращающая объект, затем использует эту память так же, как если бы она выделялась внутри этой функции.

Давайте напишем простую программу для оценки влияния RVO на время выполнения программы:

#include <vector>

std::vector<int> getVector() {
    return std::vector<int>(1, 1);
}

int main() {
    for (int i = 0; i < 1000000000; ++i) {
        getVector();
    }
}

Результат работы программы:

$ g++ -fno-elide-constructors -std=c++98 -O3 main.cpp && time ./a.out
real    0m12,713s
user    0m12,647s
sys     0m0,040s

g++ -std=c++98 -O3 main.cpp && time ./a.out
real    0m26,306s
user    0m26,040s
sys     0m0,131s

Разница больше чем в два раза, просто избегая копирования вектора. В средах C++11 (или новее) при отключении RVO время будет примерно одинаковое, но это связанно с Move семантикой, которая является темой следующего поста.

Подробнее об этом…

Move семантика позволяет переместить объект вместо его копирования для увеличения производительности. Например, при перемещении строки достаточно переместить указатель на память, выделенную под строку (вместо выделения памяти под новую строку и копирование старой строки в новую).

Для оценки производительности программы с использованием move конструктора, но без RVO запустим ту же программу используя C++11 стандарт:

$  g++ -fno-elide-constructors -std=c++11 -O3 main.cpp && time ./a.out
real    0m13,670s
user    0m13,467s
sys     0m0,100s

$ g++ -std=c++11 -O3 main.cpp && time ./a.out
real    0m14,501s
user    0m14,357s
sys     0m0,092s

Оптимизация именованного возвращаемого значения (NRVO)

Именованный RVO – это когда объект с именем возвращается, но не копируется. Простой пример:

Printer getPrinter() {
    Printer printer;
    return printer;
}

int main() {
    getPrinter();
}

Вывод такой же, что и у getPrinter() в первом примере:

$ g++ -std=c++11 main.cpp && ./a.out
Default constructor
Desctructor

NRVO Background

Возврат объекта встроенного типа (bool, char, int, и т.д.) из функции обычно приводит к очень небольшим временным издержкам, т.к. объект передается через регистр.
Но возврат большого объекта требует более дорогого копирования из одной области памяти в другую. Чтобы избежать этого, реализация может создать скрытый объект в кадре стека вызывающей стороны и передать этот адрес объекта функции. Возвращаемый объект затем копируется в скрытый объект. Например код:

Printer getPrinter() {
    Printer printer;
    return printer;
}

int main() {
    Printer printer = getPrinter();
}

может сгенерировать подобный код:

Printer* getPrinter(Printer* _hiddenAddress) {
    Printer result;
    // Результат копируется в скрытый объект
    *_hiddenAddress = result;
    return _hiddenAddress;
}

int main() {
    Printer _hidden; // Создание скрытого объекта
    Printer printer = *getPrinter(&_hidden); // Копирование результата
}

что приводит к двойному копированию объекта Printer (строки 4 и 10)

На ранней стадии развития языка C++ считалось, что неспособность эффективно возвращать нетривиальные объекты считалось слабостью. Но в 1991 году Уолтер Брайт внедрил метод минимизации копирования, эффективно заменив скрытый и именованный объект внутри функции другим объектом, используемым для хранения результата:

void getPrinter(Printer* printer) {
    // Создаем результат прямиком в *printer
}

int main() {
    Printer printer;
    getPrinter(&printer);
}

Когда RVO не происходит

RVO – это оптимизация, которую разрешено применять компилятору (начиная с С++17 в некоторых случаях применять RVO обязательно). Однако даже в С++17 применение RVO не всегда гарантировано. Давайте рассмотрим несколько примеров:

Выбор экземпляра во время выполнения

Printer getPrinter(bool runtime_condition) {
    Printer first, second;
    // !! Когда компилятор не может узнать какой экземпляр
    // !! будет возвращен, он должен отключить RVO
    if (runtime_condition) {
        return first;
    } else {
        return second;
    }
}

int main() {
    Printer snitch = getPrinter(true);
}

Возврат глобального параметра

Printer global_printer;

Printer getPrinter() {
    // !! При возврате глобального объекта
    // !! не существует способа применить RVO
    return global_printer;
}

int main() {
    Printer printer = getPrinter();
}

Вывод

Хотя мы не можем рассчитывать на то, что RVO будет применяться всегда, в большинстве случаев так и будет. Для остальных случаев у нас есть Move семантика.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *