XakepRU May 18 2015 at 09:09

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

14 min

46K

Журнал Хакер corporate blogProgramming*Perfect code*C++*

Tutorial

+17

Comments 31

QtRoS May 18 2015 at 11:10

то, размещая все данные в стеке, мы имеем скорость чистого си

Разрешите уточнить — без применения размещающего new у Вас возникала ситуация, когда независимо от расположения объекта (в стеке или куче) реальные данные всегда были в куче? Такой подход в Qt'e активно используется, концепция d-pointer'ов, и определенные преимущества есть — бинарная совместимость не ломается, данные качественно сокрыты и т.д.

Qualab May 18 2015 at 13:28

Тут тоже не ломается бинарная совместимость и о классе с данными мы знаем только то, что он есть, в API вынесен только указатель на него. Мало того, этот подход позволяет не принудительно использовать D-pointer'ы, а применять их только для больших объектов.

FoxCanFly May 18 2015 at 11:43

Как быть с тем, что размер стека обычно очень ограничен?

Qualab May 18 2015 at 13:26

Большие объекты не обязательно пихать в стек, для этого есть куча и copy-on-write из прошлой статьи. А вот множество операций над маленькими объектами, теми же скалярами и небольшими составными типами, лучше всего делать на стеке, на это его хватает.

monah_tuk May 19 2015 at 05:34

Больше всего с проблемой нехватки стека приходится сталкиваться в embedded, на одном нашем проекте просто память была поделена на несколько пулов. Среди которых был блочный, байтовый (для generic аллокаций) и два варианта small-пулов для размещения маленьких объектов. Где аллоцировать память решала реализация аллокатора. Да временами приходилось перекраивать пулы, но проблем с фрагментацией стало значительно меньше.

Qualab May 19 2015 at 13:36

Можно использовать не обязательно память стека. Память можно изначально подготовить в куче, как это делает std::vector для своих элементов.

monah_tuk May 19 2015 at 16:07

Собственно примерное про это же я и написал. Просто со стековой памятью проще.

MaxFactor May 18 2015 at 12:04

А в Delphi давно (этак с версии Delphi 7 точно) нет проблем с частыми мелкими выделениями частей памяти, там свой менеджер памяти, а многие ругают его за это. Т.е. я так понимаю, что превращают C++ в Delphi

-7

DmitryMe May 18 2015 at 14:11

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

Неправильно отработает, если попытаться присвоить объект самому себе (явно написать a=a или, что потом сложнее искать, использовать два указателя, привязанные к одному и тому же объекту).

Qualab May 18 2015 at 18:10

Ну страшного ничего не будет, поскольку std::move выполняет перенос поэлементно. Другое дело, что по-хорошему нужен другой метод для оператора копирования copy_data_to, а move_data_to должен переехать в оператор переноса operator = (object&& temporary), ну и обычная проверка на &another != this явно не помешает.

DmitryMe May 18 2015 at 22:02

страшного ничего не будет

destruct_data() приведет к вызову m_data->~data(), в результате объект по адресу m_data будет разрушен, далее вызовется another.move_data_to(m_buffer), а это приведет к вызову m_data->move_to(address). Поскольку объект один и тот же, m_data содержит адрес только что разрушенного объекта. Вызов нестатического метода ранее разрушенного объекта приводит к неопределенному поведению (за редкими исключениями, например, случая, когда деструктор тривиальный, но тут, очевидно, не тот случай).

Не стоит характеризовать неопределенное поведение словами «ничего страшного не будет»? Вот пример того, как компиляторы используют неопределенное поведение для оптимизации и в результате «ломают» (на самом деле — доламывают изначально сломанный) код.

Qualab May 19 2015 at 13:08

Мы с Вами знаем, что приведённый код имеет академическое назначение. Ничего страшного не будет означает то, что любой косяк в приведённом коде обнаружит первый же юнит-тест при написании продукта на основе данного подхода.

-2

DmitryMe May 19 2015 at 13:34

Категорически с вами не согласен, что нужно в «академическом» коде оставлять типичные ошибки вроде неправильной работы оператора присванивания при присваивании объекта самому себе. Тем более не стоит оправдывать их сферическими юнит-тестами в вакууме, которые вряд ли будут отдельно проверять, что присваивание объекта самому себе правильно работает, — хотя бы потому что в случае непрохождения более сложного теста поиск ошибки может занять довольно много времени. Наконец, если вы так легко относитесь к неопределенному поведению, компилятор может с одинаковым удовольствием доломать и ваш код, и юнит-тест, который вы написали к этому коду.

Qualab May 19 2015 at 13:40

Никто не относится легко к неопределённому поведению. Фактически после уничтожения объекта считывать его нельзя. Вы правы. Посыпаю голову пеплом, за косяк к коде Академии C++. Фактически в operator = (object const&) должен быть принципиально другой код, копирующий, а не мувающий, с проверкой на this, как я и писал выше.

OlegMax May 18 2015 at 15:43

Пока в статье нет сравнения производительности предложенного примера в вариантах с placement new и с достаточно современным memory manager, эта статья скорее вредна, чем полезна.

Qualab May 18 2015 at 18:00

Это что такой за современный memory manager, что сгоняет в кучу за памятью, а потом заполнит эту память объектом, который делает это быстрее чем просто заполнение памятью объектом без первого шага?

-1

OlegMax May 18 2015 at 22:08

А зачем быстрее? Не достаточно, чтобы было одинаково? Заодно посмотрим на «сумасшедший прирост производительности» (tm), посмеемся вместе.

Qualab May 19 2015 at 13:11

Какие милые детские мечты об идеальном memory manager, даже жаль разбивать веру человека в высшие силы, но мы представители точных наук. Вот тебе тест, можешь баловаться на любой машине:
http://pastebin.com/GxvMkeEt
Не забудь выставить оптимизацию. Получается вот такое соотношение:
TEST STARTED WITH COUNT = 1234567
…
placement new: 0.011
heap new: 0.082
placement free: 0.005
heap free: 0.048
…
P.S. Вообще странно доказывать такие вещи программисту C++, обычно про идеально быстрое выделение памяти пишут программисты Java, у них это какая-то навязчивая идея.

-1

OlegMax May 19 2015 at 14:10

Вообще-то я имел в виду сравнение чуть более комплексных задач. Например, упомянутые в статье записи SQL, где сама запись выделяется в куче, а поля — в буфере.
Но даже на таком синтетическом тесте получается интересный результат. Практически ничего (placement new) сравнивается со сложным алгоритмом (полномасштабный heap с thread safety и т.д.) и получется разница на один порядок. 10 раз, Карл!
Вот теперь читатель статьи может прикинуть, стоит ли геморрой выделки.

Qualab May 19 2015 at 14:22

То есть для тебя 13 секунд простоя на каждые 100 млн объектов вообще не показатель? Я как бы напомню, что результат выборки SQL-запроса может быть весьма немалой таблицей разнотипных данных с кучей скаляров и NULL-значений. Это ещё однопоточный тест, здесь куча ещё более-менее в комфортной ситуации. Про Debug-режим, где каждый delete отзывается резкой болью и приводит к висякам при отладке, я даже не упоминаю. Если учесть, что рабочее высоконагруженное приложение в несколько потоков параллельно перелопачивает многие миллионы объектов на каждую операцию, то эти лишние секунды приведут к покупке новых серверов, вместо того, чтобы взять одного толкового программиста.

OlegMax May 19 2015 at 14:58

Нет, 13 секунд простоя на каждые 100 млн объектов для меня вообще не показатель. Объяснить почему или догадаешься?
Пример системы (взят с потолка): в malloc/free тратится 5% времени, из всех malloc/free 50% более-менее можно переделать на placement new/delete. Итого 2.3% экономии. И куча проблем с отладкой. «Сумасшедший прирост производительности», однако!

-1

Qualab May 19 2015 at 15:24

Пример из статьи сильно упрощённый вариант реально произведённой оптимизации кода, который за каждым полем для хранения лазил в кучу, на продакшн версии. В результате оптимизации выделений памяти код обработки результатов запроса стал работать в среднем в 5 раз быстрее, так как львиную долю съедала именно работа с кучей из нескольких потоков одновременно.
P.S. Посмотри в конце концов на std::vector, его реализация не лазит за каждым элементов в кучу — он выполняет placement new. Ведь ты утверждаешь, что зря он это делает.

OlegMax May 19 2015 at 15:28

Какой использовался heap manager и были ли испробованы другие реализации heap manager?

Qualab May 19 2015 at 15:35

Для std::vector? Никакой не используется. Этот код одинаково алгоритмически эффективен для любой системы. Равно как и после оптимизации число выделений памяти в коде стало столь мало, что перестало иметь смысл искать «серебрянный» heap manager. Код просто стал работать быстро, независимо от менеджмента памяти в куче. Так и должен работать программист C++, его код либо эффективен, либо ему пора в Java.

OlegMax May 19 2015 at 16:05

Убедительно)
Нам же платят за то, что мы пишем код, а не за то, что мы не пишем код.

aclex Jun 3 2015 at 13:14

По опыту своих недавних экспериментов с похожим примером склонен с Вами согласиться. В общем случае, если мы не говорим о хранении в выделенном буфере значений только тривиально копируемых типов, выигрыш при выделении памяти, как это ни странно, с запасом компенсируется потерями на обслуживание нетривиально копируемых значений вместо дешёвых манипуляций с указателем. По моим наблюдениям, наибольшую проблему составляет потеря дешевизны сдвигающих конструктора и присваивания, да и swap превращается в довольно громоздкую операцию (частично этот вопрос поднимается Скотом Мейерсом здесь: std::string, SSO, and Move Semantics).

Чтобы не быть голословным и проиллюстрировать выводы примером, с которым я экспериментировал, приведу ссылку на код, благо он открыт. Здесь в ветке master реализовано type erasure-хранение в динамической памяти, а в compact_storage — во внутреннем буфере с использованием std::aligned_storage. Эквивалентный тест в этом файле (собирается при сборке проекта). Производительность и профили можете сравнить в своих условиях, на моей машине (GCC 4.8.2, GNU/Linux, x86_64) версия с внутренним хранением несколько менее производительна как в отладочной, так и в оптимизированной сборках.

tridemax May 18 2015 at 19:02

Потратив достаточно большое количество времени на борьбу с фрагментацией в процессе работы в игровой индустрии, я бы порекомендовал вместо этого решения просто использовать TBB scalable allocator (https://www.threadingbuildingblocks.org/docs/help/tbb_userguide/Memory_Allocation.htm#tutorial_Memory_Allocation).

Эффективно борется с фрагментацией, масштабируется (100 потоков, постоянно выделяющие память, поставят msvcr120.dll:malloc на колени из-за мьютекса). При этом не нужно ничего менять в своем коде. =)

Для дебага я порекоммендовал бы остаться на дефолтном аллокаторе (диагностика leaks and overrun), прибегая к помощи Александреску и его small object allocator в особо запущеных случаях, когда хочется скорости даже в дебаге.

Qualab May 19 2015 at 13:15

Зато приведённое решение позволяет сочетать динамическую типизацию и лёгкую замену имплементации (все данные спрятаны). Причём внешне программист работает с объектами по значению.

tridemax May 19 2015 at 13:52

Динамическая типизация ведет к лишнему cache miss при доступе к данным. Не то, чтобы это сильно пугало для имплементации логики (cache miss виртуальной таблицы нас ведь не смущает), но при работе с гигабайтами данными может вполне ощутимое количество циклов съесть, потому как каждый мисс может стоить очень дорого.

OlegMax May 19 2015 at 14:16

поставят msvcr120.dll:malloc на колени из-за мьютекса

У меня было впечатление, что CRT использует напрямую системный heap, который реализован довольно прилично в Win7. Меня TBB malloc как-то особо не впечатлил. Может для WinXP имеет смысл, так как там системный heap тупее.

yomayo May 20 2015 at 09:23

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