Производительность shared_ptr и C++11: почему я не верю библиотекам

    Здравствуйте!

    Оптимизировал я однажды критический участок кода, и был там boost::shared_ptr… И понял я: не верю я библиотекам, хоть и пишут их дядьки умные.

    Детали под катом.

    Так вот, оптимизировал я код, и был там такой участок:
    auto pRes = boost::static_pointer_cast< TBase >( boost::allocate_shared< TDerived >( TAllocator() ) );
    // ... Doing something with pRes
    return std::move( pRes )

    Оптимизация подходила к концу, поэтому был собран релиз, а я решил посмотреть в дизассемблере чего же мне накомпилировала там любимая студия, ожидая увидеть что-то красивое и быстрое. Вот только увиденное повергло меня в шок:
    ; ---------------------------------------------------------------------------------------------
    ; Line 76: auto pRes = boost::static_pointer_cast< CBase >( boost::make_shared< CDerived >() );
     
      ; ... ничего интересного - готовят параметры
      call boost::make_shared<CDerived> (0D211D0h)  
      ; ... опять ничего интересного - готовят параметры
      call boost::static_pointer_cast<CBase,CDerived> (0D212F0h)
      ; ... снова ничего интересного - прием результата вызова
     
      ; похоже на проверку if( pRes ), на деле не важно. Важно что je НЕ ВЫПОЛНЯЕТСЯ
      test eax, eax
      je `anonymous namespace`::f+7Ah (0D210CAh) ; -> никуда не прыгаем, у нас pRes != 0
      ; ... ничего интересного
     
      ; Epic fail #1 - Interlocked Cmp Exchange
      ; Этот блок фактически выполняет удаление временного shared_ptr, созданного в результате
      ; вызова make_shared: тут уменьшают счетчик ссылок а потом делают условный jump,
      ; переход выполняется, если счетчик ссылок не ноль (что, очевидно, наш вариант,
      ; т.к. мы ведь создаем указатель).
      lock xadd dword ptr [eax],ecx  
      jne `anonymous namespace`::f+7Ah (0D210CAh) ; -> прыгаем на следующую строку в с++ коде
     
      ; ... тут еще есть потенциальное удаление указателя, но это dead code
     
    ; ---------------------------------------------------------------------------------------------
    ; Line 78: return std::move( pRes );
     
      ; Ассемблером, я, наверное, утомил.
      ; В этом блоке сначала вызывается Epic Fail #2 - Interlocked Increment, т.к. мы копируем
      ; pRes, чтобы вернуть значение. Затем Epic Fail #3 - Interlocked Cmp Exchange как результат
      ; удаления указателя pRes (освобождение памяти, естественно, не происходит)

    Добавлю, что я умолчал, про еще 3 interlocked инструкции внутри вызовов make_shared и static_pointer_cast… Посмотрел я на это и стало мне плохеть на глазах. Это что же получается? Я тут специально move конструкторы вызываю, а они мне счетчик ссылок туда-сюда крутят?

    * Лирическое отступление: чем это так плохо.
    Я думаю все знают, что штуковина под названием умный указатель shared_ptr имеет внутри себя указатель на количество shared pointer-ов, ссылающихся на один и тот же хранимый объект. Когда мы копируем shared_ptr это самое количество увеличивается, а когда разрушаем — уменьшается. Во время разрушаения последнего shared pointer-а, количество ссылок становится ноль и вместе с ним удаляется и хранимый объект. Так вот, чтобы это все нормально работало в многопоточной среде, изменять количество ссылок нужно атомарными операциями, теми самыми, с ассемблерным префиксом lock: этот префикс гарантирует, что процессор точно-точно сделает все как надо, и никакие кеши не будут мешать нам жить. Префикс хороший, вот только медленный, очень медленный. Он замедляет команду приблизительно на 2 порядка, т.к. требует сброса кеш линии, а значит использовать его нужно как можно реже.

    * Лирическое отступление 2: как так получилось и почему никаких атомарных инструкций быть не должно.
    С++11 дал нам очень вкусную штуку, под названием move семантика. Теперь можно определить «перемещающие» конструкторы, которые перемещают данные из одного объекта в другой, вместо создания их копии. Такой конструктор, например, перемещает указатель на внутренний строковый буфер из одной std::string в другую, позволяя переместить строку из одного объекта в другой, не выделяя заново память. Точно также можно (и нужно!) перемещать счетчик ссылок из одного shared_ptr в другой. Действительно, в таком случае нам не нужно никаких атомарных операций, ведь мы не изменяем количество указателей. Мы всего лишь «переносим» все внутренние данные из одного в другой (при этом тот указатель из которого мы данные забрали больше уже никуда не указывает).

    Так как же оно так получилось… Вероятно, недосмотрели. Хотел я написать в буст слезное письмо, уже даже начал это делать… Но тут нашел то, что сразило меня окончательно. Во время создания boost::shared_ptr функция get_deleter вызывает сравнение типов через typeid (о Боги!). Не знаю, как там у них, а мой компилятор делает это через strcmp (грустно, не правда ли?).

    Тогда решил я измерить скорость стандартной библиотеки в сравнении с бустом. 2 раза! boost::make_shared медленнее std::make_shared в 2 раза! Почему, спросите Вы? Все просто, буст выделяет память под 2 объекта — счетчик ссылок и собственно хранимый объект. А вот стандартная библиотека — только под один, это объект содержит и то и другое. А выделение памяти — оно мееедленное. Устный плюс ушел в майкрософт, еще один попал туда же за то, что в стандартной библиотеки умные указатели работают как надо — move конструктор не делает никаких атомарных операций. Создание указателя проходит в lock free режиме… Ну, почти. static_pointer_cast все-таки не осилили они: он копирует указатель не смотря на то, что мог бы и переместить. Эта проблема решилась «допиливанием» библиотеки. не переносимым на другую платформу допиливанием, но зато соответствующим стандарту, можно скачать его здесь: pastebin.com/XZaE2cnW — работает в MSVC2010.

    P.S.

    Итак наш сегодняшний победитель — std от MSVC2010: имеет в сумме один плюсик
    А вот бусту не повезло: -1

    Ну а я прощаюсь, надеюсь, хоть кому-то эта информация была полезна. Используйте std::shared_ptr, выделяете память через make/allocate shared и будьте счастливы :)
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 49

      +7
      буст вообще гиганское непонятно что

      но такое удобное
        +47
        Суровый язык этот с++ Можно не то что в ногу себе выстрелить, а запросто повеситься в абсолютно пустой комнате
          +16
          Язык содержит слишком много возможностей, они могут быть опасны. © Википедия
          +17
          Вы сравниваете внешнюю библиотеку (буст) со встроенными средствами языка в конкретном компиляторе, это несколько некорректно. Бусту нужно быть совместимым с кучей компиляторов и платформ, наверняка у него есть причины на такую вот чушь. Вы еще сравните реализацию лямбд в бусте и С++11. Конечно, конкретная реализация std::shared_ptr в новейшем стандарте будет работать быстрее общей невесть-когда написанной реализацией в библиотеке.
            +5
            Хотя общий вывод, конечно, верный: "Используйте std::shared_ptr, выделяете память через make/allocate shared и будьте счастливы"
              0
              Вы в целом правы, но не в данном случае. В бусте есть все необходимое для правильной реализации. В частности, там есть move constructor для shared_ptr, но он есть местами, например его нету для aliasing, а должен быть, обычный ведь есть. Кроме того, в бусте есть библиотека MOVE, которая позволяет реализовать rvalue refernce для старых компиляторов. Да, она только недавно появилась, но сам механизм ее работы я видел в бусте еще несколько лет назад. В общем, переносимость не оправдание. Именно в этом случае переносимости действительно можно добиться.

              Да чер с ними, атомарными операциями. Почему boost::make_shared 2 раза выделяет память? Для нормальной реализации даже частичной специализации не надо.

              0
              Хотелось бы узнать версию boost и увидеть ссылку на страницу, указывающую, что эта реализация полностью поддерживает последний стандарт языка. :)
                0
                Проверял на последнем релизе 1.48. Посмотрите в исходники и увидите rvalue references в shared_ptr (я смотрел логи изменений в svn, они там еще в 2009 г. появились).

                Немножко спасает #define BOOST_HAS_RVALUE_REFS, но все равно не до конца (атомарные операции остаются).
                  0
                  По идее BOOST_HAS_RVALUE_REFS должен решить все проблемы. Можно дизассемблированный фрагмент с BOOST_HAS_RVALUE_REFS?

                  BOOST_HAS_RVALUE_REFS должна определятся автоматически для VC++ компилятора версии 1600 (VC++ 2010) и больше (смотри boost\config\compiler\visualc.hpp, дефайн BOOST_NO_RVALUE_REFERENCES). Поэтому строка #define BOOST_HAS_RVALUE_REFS по идее не должна влиять вообще.
                    +1
                    Явно его включил, те же грабли.

                    Вот код:
                    pastebin.com/H0uuHV1p

                    дизассемблированная f() (выполняет одну атомарная операцию)
                    pastebin.com/2vKsJ0Km

                    дизассемблированная boost::make_shared (выполняет две атомарных инструкции)
                    pastebin.com/k6GPa1VP

                    дизассемблированная boost::static_pointer_cast (выполняет одну атомарную операцию)
                    pastebin.com/14MZsWtt

                    на самом деле все очевидно просто:

                    f():
                    static_pointer_cast не умеет принимать rvalue, поэтому происходит копирование временного объекта, созданного make_shared. Когда он удаляется выполняется атомарный cmp exchange

                    make_shared:
                    2 атомарных вызова в
                    return boost::shared_ptr( pt, pt2 ); // Это алиас конструктор копирования
                    Один — создание нового указателя из pt, второй — удаление pt.
                    (shared_ptr в бусте не имеет alias move конструктора)

                    static_pointer_cast:
                    просто не умеет принимать rvalue, поэтому создает новый откастованый указатель методом копирования. во время создания вызывается атомарный инкремент
                      0
                      Спасибо, понятно. По идее у вас тогда BOOST_HAS_RVALUE_REFS вообще не должен влиять ни на что, потому что он уже задефайнин самим бустом.

                      Погляжу потом static_pointer_cast и shared_ptr у буста и Microsoft, может патч отправлю бусту. Главное ничего не сломать с какими-то другими компиляторами :-)
                        0
                        static_pointer_cast в MS реализован неправильно, в конце статьи ссылка на допиленную версию
                        0
                        По идее конечно им нужно баг запостить www.boost.org/support/bugs.html
                      0
                      А можно исходники теста? Хотел бы сам посмотреть под дизассембером.
                    0
                    intrusive_ptr не пользовали?
                      0
                      мне было проще std::shared_ptr, впрочем, думается мне там та же проблема (intrusive_ptr_add_ref/intrusive_ptr_release) вызывается когда надо и когда не надо.
                        0
                        ну в том-то и дело, что вы можете эти функции сами написать как надо. при этом в заведомо однопоточной среде не надо будет заморачиваться с синхронизацией. Но в целом согласен, да, незачем при move дергать счетчик. Ну что ж, стандарт новый, реализация еще не обкатанная)
                          0
                          В однопоточной среде — да. А вот отследить, что intrusive_ptr_add_ref/intrusive_ptr_release вызвалось так «по приколу» потому что буст не имеет все необходимые мув конструкторы нельзя. Впрочем, возможно, что intrusive_ptr этим не страдает, но он неудобный в любом случае. Сейчас std::shared_ptr работает так же быстро при условии, что у вас нету фреймворка, который считает ссылки за вас (как например для COM объектов, но там выигрыш будет слишком незначительным по сравнению с временем выполнения COM)
                      +9
                      Очень интересное выступление, где автор реализации стандартной библиотеки в Microsoft, Stephan T. Lavavej, рассказывает, как ему удалось оптимизировать std::shared_ptr.
                        +1
                        Пойду второй раз посмотрю, он так быстро говорит что не все успеваешь сразу уловить :).
                        +2
                        Вы уверены, что в конфиге для вашего компилятора все нужные define'ы определены? Может, он думает, что какие фичи C++11 им не поддерживаются?

                        PS Можно на код взглянуть? Так, ради интереса… Лучше после препроцессора :)
                          0
                          на код чего? если измерения, то нет я его удалил утром случайно :(

                          ну там все тривиально — 10М раз выполняем
                          boost::static_pointer_cast( boost::allocate_shared( TAllocator() ) );
                          и иже с ним

                          аллокатор — Loki Small Object (без него тоже пробовал)

                          таймер — QueryPerformanceCounter + affinity

                          #define BOOST_HAS_RVALUE_REFS — определял, не помагает
                            0
                            * парсер съел угловые скобки: allocate shared — TDerived, cast — TBase

                            TBase имеет виртуальный деструктор (больше ничего), TDerived пустой.

                            без кастов/make_shared тоже пробовал, std всегда быстрее минимум на 20%
                          +5
                          return std::move( pRes )

                          Возвращается ж всегда и так rvalue — зачем здесь std::move?
                            0
                            не знал, спасибо.
                            впрочем, я все равно буду писать std::move — оно так нагляднее
                            +2
                            Я бы посоветовал поговорить (написать письмо) STL из Microsoft (http://channel9.msdn.com/Tags/stephan-t-lavavej), он эксперт по Boost и его интерпретации в VC++. Он если надо и баг в VC++ откроет.
                              0
                              А не проще для сильно нагруженных участков вообще отказаться от умных указателей? Я обычно так и стараюсь делать, а в умные указатели оборачивать только долгоживущие и гулящие где попало обьекты.
                                +2
                                Если у вас общий объект на несколько потоков — то нет. В общем случае вы не знаете, какой поток закончит работать последним. А именно он должен будет освободить память. Придется либо городить какую-то синхронизацию (и получить тот же shared_ptr, вид сбоку), либо так переворачивать архитектуру приложения, что за создание/удаление объектов отвечает один конкретный поток — но далеко не всегда это можно сделать без существенной потери производительности.
                                  +1
                                  Не проще, потому что проще один раз оптимизировать (найти правильный) указатель за пол дня, чем потом каждый раз думать про освобождение памяти. Эм, поясню. Сильно нагруженый «участок» размазан почти по всему коду, т.к. это механизм передачи данных через мультиметоды на самом деле. А указатель — это указатель на то нечто, которое эти самые данные хранит.

                                  auto pData = CreateData( Component_ID( 4 ), Component_Value( 3. ) );
                                  FireEvent( GetEvent(), std::move( pData ) );

                                  как-то так
                                  +3
                                  Библиотеки с открытым кодом, такие как boost или QT, которые считаются неотъемлемой частью разработки и которые используют огромное количество людей, не лишены ошибок. Но все, кто используют библиотеки, являются одновременно огромной армией тестеров, находящих коллизии и баги. Поэтому используя открытые и широко распространенные библиотеки, мы получаем все таки достаточно надежные инструменты для программирования.
                                    0
                                    Спасибо за инфу, будем знать. Но ты еще напиши в boost developer mailing list, глядишь допилят.
                                      +2
                                      Он замедляет команду приблизительно на 2 порядка, т.к. требует сброса кеш линии, а значит использовать его нужно как можно реже.

                                      Можно с этого места поподробнее? Когда-то я делал тесты, и 2 порядка (напомню, что 2 порядка — это в 100 раз) я там не обнаружил. Т.е. вопрос: откуда там 2 порядка и почему происходит сброс кеш линии?
                                        0
                                        окей, соврал, не на 2 порядка, на 1. На 2 — если учесть что там около 10 лишних локов.

                                        Еще точнее
                                        __asm lock xadd dword ptr[n], eax;
                                        медленнее
                                        __asm xadd dword ptr[n], eax;
                                        в 6-15 раз на моем процессоре в зависимости от того, сколько потоков этим занимаются.

                                        (когда несколько потоков на разных процессорах занимаются атомарными операциями над одним и тем же аргументом им приходится синхронизировать между собой кеш, тогда замедление в 15 раз, когда поток один — тогда в 6 раз)
                                          +1
                                          Согласно пункту 8.1.4 «Effects of a LOCK Operation on Internal Processor Caches» интеловской книжки «Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3A»
                                          сброса кэша не происходит. Наоборот, начиная с P6, сигнал LOCK# может быть не активирован, а вместо него может быть использован механизм аппаратной поддержки когерентности кэша. Сама операция с префиксом LOCK при этом будет выполнена в кэше.
                                            0
                                            В общем:

                                            N = 100 M (операций)
                                            K = 10 (потоков)

                                            На одном ядре ( SetProcessAffinityMask( GetCurrentProcess(), 1 ); раскомментировано )
                                            const of one operation: 1.85526 ns.
                                            const of one operation: 6.47227 ns. (3.5x)

                                            На всех ядрах ( SetProcessAffinityMask( GetCurrentProcess(), 1 ); закомментировано )
                                            const of one operation: 0.721436 ns.
                                            const of one operation: 10.7002 ns. (14.9х)

                                            pastebin.com/Jkpfz4t2

                                            Вы можете сказать, что это не много, но я вам скажу, что 6 ns при общем времени обработки события в 70 ns это дофига как много.
                                              0
                                              А без static_pointer_cast — какие цифры?
                                                0
                                                Вот тесты именно с поинтерами:

                                                x86:
                                                std, make_shared:                 const of one iteration: 79.6456 ns.
                                                boost, make_shared:               const of one iteration: 154.441 ns.
                                                
                                                std, make_shared + cast:          const of one iteration: 96.3465 ns.
                                                std, make_shared + fast cast:     const of one iteration: 88.3443 ns.
                                                boost, make_shared + cast:        const of one iteration: 170.912 ns.
                                                
                                                std, allocate_shared:             const of one iteration: 41.9773 ns.
                                                boost, allocate_shared:           const of one iteration: 106.236 ns.
                                                
                                                std, allocate_shared + cast:      const of one iteration: 51.8958 ns.
                                                std, allocate_shared + fast cast: const of one iteration: 47.2173 ns.
                                                boost, allocate_shared + cast:    const of one iteration: 122.333 ns.
                                                
                                                std, release:                     const of one iteration: 139.189 ns.
                                                boost, release:                   const of one iteration: 136.266 ns.
                                                
                                                std, release + cast:              const of one iteration: 152.798 ns.
                                                std, release + fast cast:         const of one iteration: 147.057 ns.
                                                boost, release + cast:            const of one iteration: 154.359 ns.
                                                

                                                x64:
                                                std, make_shared:                 const of one iteration: 59.2896 ns.
                                                boost, make_shared:               const of one iteration: 111.826 ns.
                                                
                                                std, make_shared + cast:          const of one iteration: 75.6804 ns.
                                                std, make_shared + fast cast:     const of one iteration: 63.9302 ns.
                                                boost, make_shared + cast:        const of one iteration: 127.658 ns.
                                                
                                                std, allocate_shared:             const of one iteration: 52.4064 ns.
                                                boost, allocate_shared:           const of one iteration: 99.92 ns.
                                                
                                                std, allocate_shared + cast:      const of one iteration: 66.9683 ns.
                                                std, allocate_shared + fast cast: const of one iteration: 62.9726 ns.
                                                boost, allocate_shared + cast:    const of one iteration: 114.167 ns.
                                                
                                                std, release:                     const of one iteration: 101.677 ns.
                                                boost, release:                   const of one iteration: 100.807 ns.
                                                
                                                std, release + cast:              const of one iteration: 117.108 ns.
                                                std, release + fast cast:         const of one iteration: 106.495 ns.
                                                boost, release + cast:            const of one iteration: 114.833 ns.
                                                


                                                Код:
                                                pastebin.com/jAKQSZKz
                                                0
                                                Я хочу сказать что этого достаточно чтобы уже пофиксить статью.
                                            +2
                                            Сдаётся мне, что проблема тут не в финальном std::move (его наличии или отсутствии), а в том, что boost::static_pointer_cast (впрочем, как и std::static_pointer_cast) получает свой аргумент по обычной (а не r-value) ссылке. Отсюда и щёлканье счётчиком. Т. е. move-семантика тут (по логике вещей) и не должна работать. Есть предположение (которая подтвердила проверка на компиляторе), что код без static_pointer_cast'а бдут работать так, как ожидает автор — никаких lock xadd не выполняется. Проверялось на таком коде:

                                            class BaseClass
                                            {
                                            public:
                                            virtual ~BaseClass() {;}

                                            void Foo()
                                            {
                                            std::cout << «Foo called» << std::endl;
                                            }
                                            };

                                            class DerivedClass: public BaseClass
                                            {
                                            public:
                                            };

                                            boost::shared_ptr MakeSharedPtr()
                                            {
                                            boost::shared_ptr ptr = boost::make_shared();

                                            return ptr;
                                            }

                                            int main()
                                            {
                                            auto ptr = MakeSharedPtr();

                                            ptr->Foo();
                                            }

                                            При добавлении в этот код boost::static_pointer_cast'а всё начинает работать именно так, как описано топикстартером.
                                              0
                                              Угловые скобки были съедены. MakeSharedPtr должен выглядеть так:
                                              boost::shared_ptr<BaseClass> MakeSharedPtr()
                                              {
                                              boost::shared_ptr<BaseClass> ptr = boost::make_shared<DerivedClass>();

                                              return ptr;
                                              }
                                                0
                                                внутри boost::make_shared уже есть 2е атомарных инструкции,
                                                см. habrahabr.ru/blogs/cpp/138658/#comment_4631952

                                                static_pointer_cast тоже мог бы принять rvalue, т.к. временный неименованый объект это всегда rvalue, но у static_pointer_cast нету соответствующей реализации (в std ее удалось добавить «малой кровью»)
                                                  +1
                                                  std::static_pointer_cast с r-value в качестве параметра — не по стандарту. По крайней мере, документ за номером N3242 такой специализации не специфицирует. Может быть просто забыли, может быть были какие-то глубокие причины.
                                                    0
                                                    Вот это самый логичный аргумент по поводу того, почему этой реализации там нет…
                                                      0
                                                      Это сарказм или ирония? :)
                                                        +1
                                                        эм, а почему вы так решили? :)

                                                        стд от вижуал студии действительно хорошо написана… но вполне возможно, что они не хотят противоречить стандарту.
                                                          0
                                                          И правильно делают, что «не хотят». Иначе зачем эти стандарты нужны? :)
                                              0
                                              Я когда-то писал про cxxtools, может взгляните опытным глазом на их реализации?
                                                0
                                                есть политики, это хорошо: есть, например shared_ptr без поддержки многопоточности

                                                все остальное еще хуже буста:
                                                — нету make/allocate shared, значит на каждый указатель минимум 2 выделения памяти (если не использовать internal ref counting)
                                                — нету кастов (static_pointer_cast и иже с ним)
                                                — полностью отсутствует поддержка rvalue references, в бусте ее немножко есть

                                                  0
                                                  Спасибо за замечания. Я под рабочие проекты его пилю потихоньку. А вот с rvalue references ещё не приходилось сталкиваться.

                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                              Самое читаемое