Блог компании Журнал Хакер
C++
Программирование
Совершенный код
18 мая 2015

Размещай и властвуй! Используем размещающий new для оптимизации кода на C++

Tutorial


Создавая объект за объектом, мы часто не обращаем внимания на такую «мелочь», как динамическое выделение памяти. Наравне с копированием и сериализацией, выделение памяти из кучи через new постепенно сводит на нет преимущества C++ в скорости. Чем интенсивнее мы пользуемся заветным new, тем сложнее становится приложению, поскольку память кончается, фрагментируется и всячески стремится утекать. Эта участь уже постигла удобные, но неявно опасные для производительности контейнеры STL: vector, string, deque, map. Особенно обидно терять скорость на выделении небольших объектов в больших количествах. Но есть способ обработать размещение памяти таких объектов на стеке, при этом скрывая детали реализации в специальный класс данных. В этом нам поможет механизм размещающего new — непревзойденный способ оптимизации приложения, полного частых и мелких выделений памяти из кучи.

В прошлом уроке мы делали поразительные вещи: работали с объектами C++ как с контейнерами, содержащими значения типа, вычисленного на этапе выполнения и заполненного динамически. Мы активно использовали надстройку Copy-on-Write над std::shared_ptr, которым ссылались на реальный тип данных, при заполнении объекта. При этом подразумевалось, что память под любую инициализацию данных мы будем выделять также динамически, вызывая new каждый раз, как только нам понадобятся новые данные произвольного типа.

Такой подход имеет свои преимущества. Данные можно разделять между несколькими объектами, откладывая копирование. Можно, в принципе, ничего не знать заранее о типе данных. Однако есть у этого метода и ряд недостатков, из-за которого Copy-on-Write используется, как правило, для объектов, потенциально довольно больших.

Первый недостаток выясняется сразу же. Массовое динамическое выделение памяти серьезно замедляет выполнение программы, особенно массовое неявное выделение памяти через new. Да, я в курсе и про std::string, и про std::vector, которые зачастую, не спрашивая программиста, начинают перераспределять память, вызывая один new за другим (причем про переразмещение данных в std::vector мы еще поговорим). Хороший специалист в C++ разработке всегда знает об этих забавных особенностях стандартных контейнеров и понимает, как избежать лишних затрат на выделение новых сегментов памяти. Чем всегда был хорош чистый си, так это именно тем, что любая работа с памятью выполнялась прозрачно, в C++ всегда нужно держать в голове целый ряд случаев неявной работы с памятью.

Второй недостаток является следствием первого. Частое выделение небольших сегментов памяти в больших количествах приведет к жуткой фрагментации памяти и невозможности выделить даже довольно небольшой блок памяти единым куском, например для инициализации того же std::vector или std::string. В результате мы получаем bad_alloc безо всяких видимых причин. Памяти намного больше, чем нужно, а выделить непрерывный блок даже небольшого размера в условиях сильно фрагментированной памяти не получится.

Таким образом, для небольших объектов, сравнимых с int64_t, которые можно спокойно размещать на стеке, можно и нужно использовать другую технику обработки данных. Такие объекты можно передавать по значению, можно сколько угодно раз копировать, не откладывая до первого изменения, поскольку банально копируется один-два регистра.

При этом мы не должны отходить от практики объявления деталей данных в реализации. Но кое-чем придется пожертвовать: нам нужно будет заранее знать точный размер данных в байтах. Он потребуется для того, чтобы вместе с обычным указателем на данные держать в классе буфер для размещения данных объекта. Теперь подробнее.

Первый класс


Внешне почти ничего не меняется. Все тот же класс, обеспечивающий API объектов. Класс содержит ссылку на данные, класс которых объявлен через forward declaration и будет вынесен в детали реализации. Из-за этого поле класса нельзя объявить объектом данного типа, однако на тип данных можно сослаться простым указателем и заранее завести буфер для хранения данных объекта в самом же объекте. Если объект будет создан, например, на стеке, то и все данные будут храниться на стеке как часть объекта. Теперь рассмотрим пример, чтобы все встало на свои места:

class object
{
public:
    ...
protected:
    // Объявление класса данных
    class data;
    // Заранее известное количество байтов под данные
    static const size_t max_data_size = N;
private:
    // Указатель на данные
    data* m_data;
    // Буфер памяти, где будут храниться данные
    char m_buffer[max_data_size];
};

В этом фрагменте кода мы продолжаем идеологию сокрытия данных в реализации, все, что мы знаем о данных класса, — это имя класса и наличие указателя на данные. Однако теперь у нас есть возможность не лезть за памятью в heap. Класс в терминологии C++ все так же хранит данные в виде своих полей. По сути, данные разместятся в буфере m_buffer, память под который выделена уже при создании класса. Осталось лишь объяснить детали, как разместить данные в буфер байт.

Размещающий new


Как правило, немногие вспоминают про такое полезное свойство оператора new, как возможность указать готовую область памяти для размещения создаваемого объекта. Все, что нам потребуется, — это написать new(m_buffer) для создания любого типа объекта в выделенном буфере. Звучит просто, однако нужно помнить, что платим мы высокую цену: заранее указывая максимальный размер буфера. Мало того, размер буфера попадает в заголовочный файл и явно участвует в объявлении API.

Зато мы выигрываем в скорости. Если, выделяя данные в куче на каждую инициализацию, мы рискуем отстать от Java, то, размещая все данные в стеке, мы имеем скорость чистого си, недостижимую скорость для почти любого языка высокого уровня, кроме C++. При этом уровень абстракции крайне высок, мы выстраиваем API на обычных объектах C++, скрывая детали реализации. Единственное ограничение — размер, который мы задаем; мы уже не можем запросто менять в реализации набор полей у класса данных, всегда нужно помнить о размере. Мало того, нам необходимо проверять размер данных, описанных в реализации, на соответствие с указанным в заголовочном файле. Просто потому, что сборка библиотеки может расходиться с версией заголовочных файлов, например при получении из различных источников. Рассмотрим пример, как должна выглядеть подобная проверка, как и создание объекта в подготовленной памяти размещающим new.

object::object()
    : m_data(new(m_buffer) object::data)
{
    static_assert(sizeof(object::data) <= max_data_size, "...");
}

Здесь static_assert фактически выполнится на этапе компиляции, поэтому инициализация m_data будет выполнена, только если для object::data достаточно памяти в буфере m_buffer. Аналогично у класса-наследника, например flower, класса object данные также не должны превышать заданную планку, поскольку данные мы храним в реализации базового класса.

flower::flower(std::string const& name)
    : object(new(get_buffer()) flower::data(name))
{
    static_assert(sizeof(flower::data) < max_data_size, "..." );
}

Очевидно, что для этого нужен protected-метод get_buffer() для получения адреса m_buffer в базовом классе, а также protected-конструктор object от object::data*. Так же, как и в прошлом выпуске, мы наследуем данные наследников от данных базового класса, поэтому flower::data* совместим с object::data*. Для безопасности стоит в базовый конструктор от object::data* добавить проверку на то, что передан адрес именно заранее выделенного буфера:

object::object(object::data* data_ptr)
{
    if (static_cast<void*>(data_ptr) != static_cast<void*>(m_buffer))
        throw some_exception(...);
    m_data = data_ptr;
}

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

object rose = flower("rose");

Объекты с данными большого размера


Осталось выяснить, что делать с объектами, чей размер данных выходит за рамки обозначенного максимума. На самом деле и здесь все довольно просто. Достаточно, чтобы в лимит вписывался размер copy_on_write<data::impl>, который по сути является надстройкой над std::shared_ptr<data::impl>, где impl — реализация класса данных произвольного размера. Поскольку размер std::shared_ptr<data::impl> не зависит от размера самих объектов класса data::impl, мы получаем универсальный способ хранения данных с переходом от хранения по значению к хранению по ссылке.

class huge
{
public:
    ...
protected:
    class data;
};

class huge::data
{
public:
    ...
protected:
    class impl;
private:
    copy_on_write<impl> m_impl;
};

Однако отвлечемся от решения проблемы единого API для объектов с динамической типизацией и рассмотрим другой пример оптимизации через размещающий new.

copy_on_write::flashback


Если кто-то пропустил прошлый выпуск, то класс copy_on_write — это шаблонный класс для хранения данных с оптимизацией копирования. Эмулируя указатель, этот класс имеет хитрую перегрузку operator-> для const и non-const случаев. При копировании объектов мы ссылаемся на одни и те же данные, не вызывая дорогостоящего копирования. Однако, как только мы вызываем неконстантный метод класса данных, потенциально изменяющий данные, мы отцепляем для текущего объекта свою копию данных. Упрощенно реализация выглядит примерно так:

template <typename impl_type>
class copy_on_write
{
public:
    copy_on_write(impl_type* pimpl)
        : m_pimpl(pimpl) {
    }
    impl_type* operator -> () {
        if (!m_pimpl.unique())
            m_pimpl.reset(new impl_type(*m_pimpl));
        return m_pimpl.get();
    }
    impl_type const* operator -> () const {
        return m_pimpl.get();
    }
private:
    std::shared_ptr<impl_type> m_pimpl;
};

Таким образом, при выборе максимального размера данных для встроенного буфера стоит учесть размер класса, содержащего copy_on_write в качестве поля.

Поля выборки данных


Самый мощный способ оптимизации через размещающий new — это поля записей выборки в результате SQL-запроса. Выборка запрашивает набор данных самых разнообразных типов, от целочисленных и вещественных до строк и массивов. Хотя сами данные получаются динамически и типы полей, полученные со стороны базы данных, приходится инициализировать с эмуляцией динамической типизации, но зато все записи содержат один и тот же набор типов полей, по которому можно определить общий размер данных для каждой записи. Это позволяет нам выделить память под поля записи лишь однажды, вычислив размер по типам полей, входящим в каждую запись выборки. Можно также выделить память однажды для всех записей единым блоком, однако, как правило, после выборки над записями производят всевозможные операции, в том числе фильтруя и сортируя их, поэтому сами записи имеет смысл описать в виде Copy-on-Write объектов для удобства последующих операций. Выделять же для каждого поля память из кучи неоправданно дорого.

Так будет выглядеть наш класс запись, если упростить объявление и использовать copy_on_write напрямую от класса данных:

class record
{
public:
    record(std::vector<field::type> const& types);
    ...
protected:
    class data;
private:
    copy_on_write<data> m_data;
};

class record::data
{
public:
    data(std::vector<field::type> const& types);
    ...
private:
    std::vector<char> m_buffer;
    std::vector<field*> m_fields;
};

Здесь для упрощения пояснения введен вектор типов полей std::vector<field::type>, массив enum-значений. На самом деле этот массив следует набрать из аргументов через boost::fusion либо, используя Boost.Preprocessor, набрать массив из обобщенных объектов типа object от любого типа аргументов. Нам сейчас важен сам механизм однократного выделения памяти из кучи для каждой записи.

record::data::data(std::vector<field::type> const& types)
    : m_buffer(field::calc_size(types)),
      m_fields(types.size())
{
    size_t offset = 0;
    std::transform(types.begin(), types.end(), m_fields.begin(),
        [&offset](field::type type, field*& field_ptr) {
           field_ptr = new(m_buffer + offset) field(type);
           offset += field::size(type);
        }
    );
}

где field::size вычисляет размер данных по переданному field::type, а field::calc_size вычисляет уже суммарный размер, необходимый под весь набор типов записи, переданный как std::vector<field::type>.

Поле field реализуется аналогично типу object, по сути контейнер динамического содержимого. Большая часть типов: int64_t, bool, double — скаляры и хранятся по значению. Тип std::string также может храниться по значению, однако стоит учитывать то, что почти наверняка данные строки будут храниться в куче и выделяться динамически. Если хочется поддержать некий varchar определенной длины, то здесь, скорее всего, нужен будет свой тип copy_on_write с массивом символов фиксированной длины.

Различные типы полей аналогичны различным типам объектов, унаследованных от класса object. Можно даже не использовать enum, а завязаться напрямую на типы, но, как правило, разбор результата SQL-запроса влечет за собой десериализацию пакета байтов с данными, где все типы полей заранее известны, поэтому enum для удобства здесь никаких ограничений не влечет. Тем более что метапрограммирование — стезя не для слабонервных, и MPL и Boost.Fusion мы здесь рассматривать не будем.

Осталось затронуть последний важный аспект использования размещающего new — пул однотипных объектов в C++.

Пул однотипных объектов


Как и прежде, мы оптимизируем динамическое выделение памяти. Что такое пул объектов? Это заранее выделяемый большим скопом массив заготовок для инициализации определенного типа. В некотором смысле record выше был пулом для объектов field. Также ты наверняка встречал пул объектов, если работал с высокоуровневыми языками (C#, Python, Java), ведь для выделения новых объектов они используют заготовленные сегменты памяти, в которых размещают объекты, по сути тип object. После того как один из объектов пула становится не нужен, иными словами на него перестали ссылаться, он либо сразу деинициализируется, либо ждет своей печальной участи в виде очередного обхода Garbage Collector’а — сборщика мусора — специального механизма удаления бесхозного добра. Вообще говоря, деинициализация объектов в пуле — его слабое место. Зато мы получаем скоростное выделение объектов, как правило либо уже инициализированных, либо подготовленных для инициализации. Если делать на основе нашего типа object полноценный пул объектов с деинициализацией по счетчику ссылок и с Garbage Collector’ом, то мы получим Java или Python. Если тебе потребовалось что-то подобное, может, не стоит городить огород и взять готовый язык со сборкой мусора? Однако если для оптимизации однотипных объектов потребовалось выделить заранее большой сегмент памяти и задача действительно требует массовой инициализации большого числа объектов с неким базовым классом, то пул объектов позволит избежать массы динамических выделений памяти.

Чтобы разобраться, нам потребуется понятное прикладное объяснение. Как насчет собственно выборки в результате SQL-запроса с пулом для записей? Это позволит оптимизировать массу выделений памяти для построения объектов записей выборки.

class selection
{
public:
    selection(std::vector<field::type> const& types,
              size_t row_count);
    ...
protected:
    class data;
private:
    copy_on_write<data> m_data;
};

class selection::data
{
public:
    data(std::vector<field::type> const& types,
         size_t row_count);
    ...
private:
    std::vector<field::type> m_types;
    std::vector<char> m_buffer;
    std::vector<record> m_rows;
};

selection::data::data(std::vector<field::type> const& types,
                      size_t row_count)
    : m_types(types)
{
    if (!row_count) return;
    m_rows.reserve(row_count);
    size_t row_data_size = field::calc_size(types);
    m_buffer.resize(row_count * row_data_size);
    char* offset = m_buffer
    for (size_t i = 0; i < row_count; ++i)
    {
        m_rows.push_back(record::inplace(offset, types));
        offset += row_data_size;
    }
}

Где record::inplace по сути создает данные записи не в куче, а по заданному адресу.

record record::inplace(void* address,
                       std::vector<field::type> const& types)
{
    return record(new(address) record::data(types));
}

Нам потребуется конструктор record с инициализацией и специальный деструктор, об этом далее. Данный вариант инициализации record делает невозможным использование его в предыдущем варианте, то есть в виде класса, содержащего лишь поле copy_on_write. Мы не сможем, спокойно понадеявшись на динамическое выделение данных в куче, ворочать записями как хотим. С другой стороны, мы получаем сумасшедший прирост производительности при большом наборе данных. Однако есть в размещающем new подвох, о котором следует знать.

Явный вызов деструктора


WARNING


Если кто-то имеет привычку не дочитывать до конца либо читать по диагонали — очень зря. Пропустив этот важный раздел, можно наплодить memory leak’ов — утечек памяти, причем в больших количествах.

Есть еще одно «но» при использовании размещающего new — придется вызывать деструктор самим, вручную, поскольку delete не сделает ровным счетом ничего. Поэтому класс, содержащий данные, выделяющиеся в заранее подготовленную память, должен в деструкторе явно вызвать деструктор созданного в памяти класса. Так, деструктор класса object::~object должен явно вызвать деструктор object::data::~data, а деструктор record::data::~data должен будет позвать целый ряд деструкторов field::~field — по одному на каждое поле. Для того чтобы наглядно показать, как это должно происходить, я более детально распишу класс object.

class object
{
public:
    object();
    virtual ~object();
    ...
protected:
    class data;
    char* get_buffer();
    object(data* derived_data);
    static const size_t max_data_size = N;
private:
    data* m_data;
    char m_buffer[max_data_size];
};

object::object()
    : m_data(new(m_buffer) data)
{
    static_assert(sizeof(data) <= max_data_size, "...");
}

object::~object()
{
    m_data->~data();
}

Поскольку деструктор у класса данных должен быть описан как virtual, то и деинициализация данных пройдет успешно, какой бы наследник object::data ни использовался.

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

object::object(object const& another)
    : m_buffer(max_data_size),
      m_data(another.clone_data_at(m_buffer))
{
}

object& object::operator = (object const& another)
{
    destruct_data(); // здесь нужно вызвать деструктор
    m_data = another.clone_data_at(m_buffer);
    return *this;
}

object::data* object::clone_data_at(void* address)
{
    return m_data->clone_at(address);
}

// Этот метод должен быть перегружен
// для каждого наследуемого типа данных
object::data* object::data::clone_at(void* address)
{
    return new(address) data(*this);
}

void object::destruct_data()
{
    m_data->~data();
}

Здесь наш новый метод desctuct_data() так и просится в деструктор object::~object. Раз просится, значит, там ему самое место. Для конструктора и оператора перемещения поведение похожее:

object::object(object&& another)
    : m_data(another.move_data_to(m_buffer))
{
}

object& object::operator = (object const& another)
{
    destruct_data(); // здесь нужно вызвать деструктор
    m_data = another.move_data_to(m_buffer);
    return *this;
}

object::data* object::move_data_to(void* address)
{
    return m_data->move_to(address);
}

// Этот метод должен быть перегружен
// для каждого наследуемого типа данных
object::data* object::data::move_to(void* address)
{
    return new(address) data(std::move(*this));
}

object::~object()
{
    destruct_data();
}

Итак, опасность memory leak’ов ликвидирована. Пользователи твоего API могут разрабатывать спокойно.

Размещающий new против new в куче


Как ты уже успел заметить, классы, использующие размещающий new, намного сложнее в реализации. Каждый аспект использования класса, реализованного на технике размещения объекта в подготовленную память, должен всесторонне тестироваться. Сложность же обычного new любого класса, как правило, сводится к обертке умного указателя. В чем же тогда выгода, если даже эмуляция динамической типизации усложняется явным указанием максимального размера типа данных?

Выгода в скорости. Сила C++ по сравнению с более удобными C#, Java и Python — в скорости выполнения. Здесь мы достигаем наивысших скоростей, поскольку не идем в кучу за новыми объектами. И не замедляем приложение в дальнейшей перспективе, избегая фрагментации памяти. Фрагментированная память как сыр: полна дырок, и в сумме размер этих дырок позволяет запихать туда апельсин, но на самом деле апельсин не поместится ни в одну из дыр, каждая из них слишком мала. Так и std::vector, как и std::string, требующие сегмент непрерывной памяти, могут в один прекрасный момент получить std::bad_alloc при перераспределении элементов.

Размещающий new в стандартной библиотеке


Помнишь, я обещал тебе рассказать про размещающий new в std::vector в начале статьи? Так вот, все конструкторы элементов в std::vector вызываются в подготовленной памяти. И так же активно для элементов вызываются деструкторы. Это не принципиально для векторов от простых POD-типов вроде int или char, но если мы хотим выделить std::vector, причем custom обладает нетривиальным и тяжелым конструктором по умолчанию и не менее тяжелым конструктором копирования, то мы получим массу неприятностей, если не будем знать, как работает std::vector со своими данными.

Итак, что же происходит, когда мы просим вектор изменить размер? Для начала вектор смотрит, что еще не зарезервировал нужное число байтов (буфер вектор всегда выделяет с запасом), после чего выделяет новый буфер. Все существующие элементы переносятся в новый буфер конструктором перемещения через размещающий new по соответствующему адресу. В результате все элементы стоят на своих местах. После чего вектор добирает нужное число элементов в конец массива, создавая каждый размещающим new и конструктором по умолчанию. Так же и в обратную сторону — уменьшение количества элементов вызовет деструкторы «вручную» при удалении элементов.

В отличие от std::vector, контейнер std::string не занимается placement new просто потому, что хранит всегда char, не нуждающийся в конструкторах или деструкторах. Зато целый ряд контейнеров стандартной библиотеки: deque, list, map и другие шаблоны классов для хранения произвольных данных — активно используют размещающий new в своей реализации.

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

Что в итоге?


Конечно, умение пользоваться размещающим new там, где надо, и только тогда, когда это действительно нужно, эффективно и оправданно, приходит не сразу. Одни до последнего отбиваются вредом предварительной оптимизации, другие, наоборот, только прочитав статью, бросятся встраивать new(m_buffer), где надо и где не надо. Со временем и те и другие приходят к золотой середине.

Суть метода проста — если есть возможность и необходимость разместить объект класса в заранее приготовленную память, сделать это относительно просто, если помнить пару несложных правил:

  • память должна жить все время, пока в ней живет объект, если память потрут, то объект начнет ссылаться на битый сегмент памяти;
  • деструктор класса для объекта, выделенного размещающим new, должен быть вызван вручную, это печально, но delete не делает с памятью по указателю ровным счетом ничего.

Все остальное ограничивается лишь аккуратностью и безграничной фантазией разработчика. То есть тебя.

image

Впервые опубликовано в журнале Хакер #190.
Автор: Владимир Qualab Керимов, ведущий С++ разработчик компании Parallels


Подпишись на «Хакер»
+17
33,1k 220
Комментарии 31
Похожие публикации
Популярное за сутки