Эффективность C++ на современных ПК

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

    Со времён, когда проектировался С++, относительная (к скорости оперативной памяти) скорость процессора выросла в 400 раз. Плюс к тому, у процессора появились большие кэши и предсказание ветвлений в коде. Всё это вместе самым серьёзным образом сказывается на эффективности С++ на современных платформах. Ниже даю аннотацию и пару ссылок, где предлагается использовать эти факты для повышения эффективности кода.


    Постановка задачи была встречена мною вот в этой статье:
    solid-angle.blogspot.com/2010/02/musings-on-data-oriented-design.html

    Рекомендую также внимательно ознакомиться с докладом и статьями, ссылки на которые публикует автор в начале. Доклад наиболее информативен и показателен в плане конкретных цифр:
    research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf
    На примере объектов трёхмерной графики показано, как простейшими с точки зрения С++ изменениями (например перераспределение объявлений в заголовке класса) получено серьёзное повышение скорости работы кода.

    Автор статьи говорит о необходимости создавать код на основе данных, а уже потом абстракций ООП (Data-Oriented design). С учётом изменившейся разницы в быстродействии памяти и процессора (напоминаю: в сотни раз!), это может глобально ускорить работу кода на современных системах. Если говорить простым языком, подход предлагает:
    1) отказ от функций, работающих с единственным элементом данных в тех случаях, где подобных элементов много
    2) организацию этих элементов в качестве отдельного непрерывного массива в памяти, плюс функций-членов, работающих непосредственно с этим массивом.

    С точки зрения ПК, как пишут авторы, информация разных видов должна быть организована в гомогенные массивы, по одному на каждый тип данных. На уровне ассемблера (либо другого низкоуровневого языка) функции должны быть сгенерированы таким образом, что единицей обработки должен быть массив или их набор. При этом, для человека (например, в ходе отладки), эти данные должны быть сгруппированы по классам (т.е. обычным для современного С++ образом), данные которых представляют собой гетерогенный набор элементов низкоуровневых гомогенных массивов. Это может ускорить работу кода на порядок (или больше в отдельных случаях).

    P.S. Для некоторых понятие data-oriented design может оказаться не новым. Вполне возможно, у Вас есть опыт реализации данного подхода и конкретные результаты его применения. Было бы очень интересно, если бы Вы поделились своим опытом подобной оптимизации в комментариях.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 49
    • +13
      Это проблема должна решаться программистами или разработчиками компилятора?
      • +28
        Я программист. И хотел бы, в идеале, чтобы за меня эту проблему решал компилятор.
        Пока конкретных предложений со стороны разработчиков с++ компиляторов не поступало, я ищу способы делать программы эффективнее самому. С учётом, разумеется, того, что оптимизировать, тем более агрессивно, следует лишь часто исполняемые участки кода.
        • +59
          Я компилятор. И хотел бы, в идеале, чтобы за меня эту проблему решал программист.
          • +25
            Я процессор. Ребята, вы о чем?
            • +22
              Я электрический заряд. Хватит уже меня туда-сюда гонять, а то как вдарю…
              • +32
                А я томат…
                • +23
                  А я гашиш… Я слова забыл
                  • +12
                    Осторожно, одно неловкое движение и ты кетчуп.
                    • +13
                      А я специально нашел ваши комментарии через поиск чтобы убедиться, что на башорге не врут.
                • +10
                  Давно это с вами?:)
                  • +8
                    У памяти спроси — напомнит.

                    (выпадение строки из кэша, как оно есть)
                • +1
                  Я бы предпочел понимать и даже контролировать что там за меня придумал компилятор. Ситуации когда интеловский компилятор тормозит код при выполнении на процессоре АМД меня не устраивают.

                  Наверно нужен режим «оптимизации» по умолчанию, а также возможность прагмами настраивать определенные ситуации.
                  • +2
                    Это как раз та причина, по которой ничего подобного нет в С++0х и вряд ли будет в следующих версиях. Векторизация данных и функций-членов будет либо реализована в другом языке, который не гарантирует соответствие объявлений классов и их представления в памяти, либо появится какой-то новый подход к написанию программ под С++.
                • +3
                  Впрочем, это может предполагать и другой подход к написанию кода самим программистом. Поскольку тема для меня новая, могу лишь предполагать.
                  Насколько будет читаем такой код? Вот интересный вопрос.
                  • +2
                    наверное все-таки решать задачу оптимизации исполняемого на процессоре кода — это задача компилятора.
                    а задача прикладных программистов — решать прикладные задачи
                    • +4
                      Разумеется, хорошо бы, чтобы компилятор решал за меня эту, а вместе с ней и ещё пару десятков задач. Но когда это будет — неизвестно, и будет ли вообще.

                      Моя статья — для тех, кого интересует повышение эффективности кода «здесь и сейчас».
                • +12
                  Ну если компилятор говно, то, очевидно, разработчиками.

                  Тут есть один момент, который фанатики не учитывают. Простой переход на новую версию компилятора (MSVC или GCC, не суть) уже позволяет всё ускорить на 10-15%. Переход на STLPort опять же положительно сказывается. Новая версия компилятора выходит, скажем, раз в пять лет, на самом деле чаще.
                  1) Сможете ли вы за пять лет изуродовать своё код низкоуровневыми оптимизациями настолько, чтобы выигрыш стал больше?
                  2) Насколько это удорожит поддержку кода в дальнешейшем?
                  3) Не будет ли новый код медленее неоптимизированного кода на новых процессорах, которых у вас не было на момент начала написания программы?

                  Кстати в вопросе доступа к памяти Intel Atom vs Code 2 Duo. Атом сливает всего два раза при чтении 200Мб массива из памяти. Это потому что есть кеши процессора, а авторы всё стали для абстрактных процессоров без кеша в вакууме.
                  • +1
                    Самый «сильный» комментарий к статье на данный момент, спасибо. Всё написано здраво. Добавить могу лишь следующее.
                    1. Под Win32 плотно пользуюсь компилятором от M$ начиная с 2003 версии (на самом деле и раньше, но там был небольшой перерыв). Так вот, мои замеры изменения производительности показывают мало заметный прирост скорости при переходе на новую версию компилятора, при этом объём оперативной памяти, который кушает программа, непрерывно увеличивается от версии к версии. И дело здесь не в новых версиях STL (которые, кстати, тоже становятся всё более монструозными от версии к версии; как бы там ни было — я STL не пользуюсь вообще, пользуюсь другим фреймворком). То есть, компилятор особо не спасает в плане скорости.
                    2. Что касается уродования низкоуровневыми оптимизациями и удорожание поддержки кода — согласен на 100%. Как раз думаю о том, как сделать их максимально прозрачно.
                    3. По поводу будущих архитектур ПК, могу лишь предположить что всё пока движется ортогонально к тематике статьи: скорее всего, будут повышать параллелизм и увеличивать кэши, так что код по идее не должен тормозить сильнее. Параллелизм будет увеличивать «отрыв» асинхронной и многоядерной структуры ЦП от непараллельной памяти.
                    Что касается кешей процессора, про это очень хорошо написал автор доклада, ссылку на который я также привёл.
                    • +7
                      Я не против MS или ее технологий. Но на школах по параллельным вычислениям, на которых я был, от слова КОМПИЛЯТОР С++ ОТ MS лекторов бросало просто в жар, правда как и от GCC.
                      Самый яркий пример в проекте создания медианного фильтра, который мы там делали дало ускорение в 4 раза при замене стандартного компилятора из vs2005 на intel компилятор. Задача конечно весьма специфическая была, обработка массива и сортировка, но результат очевиден. Компилятор все векторизовал хорошо без нас.
                      Не кто не сделает компилятор для intel архитектуры чем сама intel.

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

                      Третье и самое важное — если производительность не критична то и забейте на нее. Оптимизировать неделю код, которыйр аботает 2 минуты в месяц -пустая трата времени.

                      А то, что программист должен понимать всю архитектуру системы на которой работает программа- это нормально. Из личного опыта могу сказать, что переписав программу с C# объектно-ориентированного(каждый узел- объект. инкапсуляция. проверка входных значений и прочие радости C#) на С++ процедурный(десять расчетных функций, openmp ) я ускорил расчеты модели сети раз так в 12.

                      Так что если хотите производительность-боритесь, изучайте.
                      Хотите писать быстро -привем C#, Java
                    • +1
                      1. Основная проблемма в современных процессорах — медленный доступ к основной памяти (L2 cache miss* стоит сотни циклов). Всевозможные приемы, как out-of-order execution, branch prediction и т.п. предназначены в первую очередь именно для того чтобы угадать где в будущем будет этот-самый miss и начать копировать память в cache. Современные компиляторы не способны особо помочь в этой ситуации (кроме как на совсем микро-уровне scheduling-а инструкций). Негативный эффект от L2 промаха может замедлить самый алгоритмически оптимальный, векторизированый (simd) код в 10 раз! Никакой апгрейд компилятора не поможет если вы прыгаете по памяти.
                      Так что ответ — ДА, реорганизация данных для оптимального использования L2 будет выиграшем.

                      2. Обычно такие трансформации *упрощают* код, т.к. отдается предпочтение более простым структурам (или нескольким массивам из простых структур). Функции, обрабатывающие эти структуры так-же становятся более простыми.

                      3. Нет, не будет. Будет только быстрее. В обозримом будущем память будет всё более дорогим ресурсом, т.к. будет всё больше ядер которые борятся за одновременный доступ.

                      Авторы статей — широко известные (в узких кругах геймдева) программисты. Они знают о чем говорят.

                      * для справки: кэш процессора организован в несколько уровней (обычно L1, L2 и L3). Каждый уровень разбит на мелкие участки — cache lines (обычно в 64 байта). В каждом участке хранится копия данных из основной памяти. Кроме кэша, у процессора есть регисры. Для маппинга физических адресов основной памяти используется совсем-совсем простая hash-функция (обычно бит-маска и сдвиг). Когда все вычисления происходят с регистрами — мы получаем оптимальную скорость. В этом случае компилятор это наш лучший друг и его качество сильно влияет здесь на производительность. Когда нужно записать новую информацию в регистр, процессор идет в L1. Если там есть данные — cache hit, всё хорошо и быстро (несколько циклов на i7). Если данных нет — cache miss, процессор идет в L2. Если нужные данные там есть (cache hit) — всё не плохо (десяток-другой циклов). А если данных нет — cache line запрашивается из основной памяти (. Это уже стоит сотни циклов.
                      Cache line это минимальное количество памяти, которую процессор может запросить. Поэтому если даже вы трогаете всего один байт в вашей структуре, из памяти будет передано 64. Кроме того, если суммарный размер вашей структуры, скажем, 65 байт — будет передано 128. И это еще не всё! Если у вас есть динамический массив из данных в которых каждый элемент 64б — у вас всё равно есть шанс передавать две кэш-линии при доступе к одному элементу. Это происходит изза выравнивания памяти.

                      Я мог бы продолжать еще очень долго. Возможно это была бы хорошая тема для отдельного хабратопика?
                      • 0
                        1. Меня интересовал этот вопрос и провёл следующий простой тест. Взял массив числе размером примерно 100Мб и сложил их несколько раз. Каждый раз я шагал через разное количество элементов. То есть порядки обхода были такие
                        1 2 3 4 5 6 7 8 9
                        1 3 5 7 9… 2 4 6 8
                        1 4 7… 2 5 8… 3 6 9
                        результаты конечно же очень отличались, аж в 4 раза, так что ваш аргумент про кеш в кассу. Однако дальше вы что-то непонятное говорите. SIMD это уже крайне низкоуровневый код, то есть не тема данной статьи, так как речь о переписывании высокоуровневого кода на ассемблер.

                        2. Более простые не значит более понятные.

                        3. Видите ли, вы мягко говоря не правы. Нельзя всё сводить к кешу. Разные ядра по-разному выполняют (разбирают) инструкции.
                        • +1
                          1. Разница в 4 раза это еще хорошо. Здесь работает автоматический префетчинг. На PC, современные процессоры умеют предсказывать какие кэш линии будут скоро необходимы. Это работает даже при прыжке в несколько кэш линий. Необходимо только чтобы вы шли в одном направлении по памяти, с одинаковым шагом. Можно еще самому поставить hint-ы для префетчинга, но здесь необходимо очень аккуратно проверять результаты, скажем, VTune-ом. Попробуйте создать массив индексов для выших 100мб данных, отсортировать его случайным образом и потом опять сложить данные, используя случайные переходы.

                          Про SIMD — современные компиляторы умеют самостоятельно векторизировать ваш скалярный код. С тем или иным успехом. Intel C++ compiler умеет это делать лучше чем MSVC. Никакого ассемблера не ребуется.

                          2. В большинстве практических случаев это именно так, как я сказал.

                          3. Можно. Разные процессоры умеют по разному предсказывать где произойдет cache miss. Но инструкции они выполняют более-менее одинаково.
                          Cache-efficient код будет работать на порядок быстрее на любом современном процессоре.
                          • 0
                            В современных процессорах еще есть такая штука как pipelining и register renaming. Благодаря этому, процессор может одновременно выполнять несколько операций если между ними нет зависимостей. Это, опять-же, помогает спрятать доступ к памяти.
                            Сами инструкции выполняются примерно с одинаковой скоростью (обычно 1 инструкция за цикл). Но благодаря глубокому пайплайнингу, хороший код будет выполняться со скоростью ~2-3 инструкции/цикл.
                      • 0
                        ИМХО должна решаться компиляторами. Программисты в последнее время ленивы и толпой уходят вообще в дотнет и ему подобные.
                        Да и подобные оптимизации требуют серьезной переработки проекта и, скорее всего, обойдутся слишком дорого.
                        Для PC проще и дешевле вписать в требования более мощное железо.
                        Для PS3 так не сделаешь, приходится оптимизировать и оптимизировать чтобы устаревшее железо и через пять лет выдавало приемлимую картинку.
                        • +1
                          К сожалению, это опять не про С++, поскольку он гарантирует соответствие между описание класса и его байтовым представлением в памяти. За счёт этого ему удаётся усидеть сразу на двух стульях «достаточно системного» и «объектно-ориентированного» языка.
                        • 0
                          1) отказ от функций, работающих с единственным элементом данных в тех случаях, где подобных элементов много.

                          Это вполне может решить программист, не создавая функций вроде parseElement(e), а непосредственно проводить операции над элементом в цикле, в общем сократить число_вызывов_функций_на_объём_данных.
                          В идеале, конечно, с этим может справиться какой нибудь прекомпилятор или как лучший вариант, непосредственно компилятор.

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

                          Имхо, программист тут может только накорячить какое то подобие низкоуровневых гомогенных массивов :D
                          • 0
                            1) Это понятно. Вопрос в том, что такое программирование может убить читаемость.
                        • 0
                          а статья разве не про ps3? там, насколько я знаю, все может работать по другому. может кто-нибудь проведет аналогичные тесты на нормальном компьютере?
                          • +1
                            Отсюда ( habrahabr.ru/blogs/development/43905/ ):
                            «Memory latency (cycles) 1.4 210 -150x (!!!!!!).

                            Из таблички хорошо видно, что процессор хорошо растет, размер памяти хорошо растет, bandwidth памяти опять же зашибато, а вот latency со времен VAX — стало всего в три раза лучше. В расчете на такты (последняя строка) — ухудшилось в 150 раз.

                            Напоследок, краткие медитативные цифирки (я брал у себя на домашней машине):

                            floating point mul: 0.5-4 cycles (на одном ядре)
                            L1 access (~16-32 kb): ~2-3 cycles
                            L2 access (~2-4 mb): ~15 cycles
                            Random Memory Access: ~200 cycles < — !!(прим. mt_)
                            Sequential Access with Prefetch: ~2 bytes/cycle»
                          • 0
                            Спасибо, действительно серьёзный прирост в презентации :)
                            • НЛО прилетело и опубликовало эту надпись здесь
                              • –2
                                Пишите на С! он предполагает Data-Oriented design.
                                • –8
                                  Статью не читал; плюсы не нужны.
                                  • 0
                                    «Слава ресету!» кричат тролли… (
                                  • +1
                                    По-моему пост ни о чем.

                                    В С++ программах и так любой вменяемый программист обрабатывает гомогенные массивы данных в тех случаях когда нужна производительность.

                                    Например — при обработке изображений никому не приходит в голову делать каждый пиксель отдельным объектом.
                                    • 0
                                      Много вы видели гомогенных массивов и их обработчиков в классических гуишных приложениях? Авторы утверждают, что это позволит сэкономить массу тактов процессора даже для «обычных» программ. Весь вопрос в том, чтобы не превратить код в трудночитаемую кашу.
                                      • 0
                                        В обычных гуишных программах как правило не надо ничего экономить на таком низком уровне, так как большую часть времени они не используют процессор вообще.
                                        • +3
                                          В Cocoa есть несколько примеров решения подобной задачи:

                                          1. NSTableView создает столько строк, сколько помещается на экране, и переиспользует их при прокрутке. Данные для каждой видимой строки выдает объект-источник данных.

                                          2. Для некоторых объектов тяжелого класса NSView используются легковесные объекты класса NSCell, которые отвечают лишь за отрисовку содержимого. Например, матрица 10x10 является объектом NSView, а отрисовкой занимаются 100 клеток NSCell. Во время какого-нибудь события ОС не должна сообщать о нем каждой ячейки, а только одной матрице. А она уже сама разберется что с ним делать.

                                          3. Если в окошке присутствует 100 текстовых полей, было бы неэффективно создавать объект-редактор для каждого поля (тормоза при создании + использование памяти). Вместо этого, окно содержит единственный редактор текста, а каждое поле при получении фокуса спрашивает его, размещает как следует и принимает данные.

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

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

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

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


                                        • 0
                                          > Например — при обработке изображений никому не
                                          > приходит в голову делать каждый пиксель отдельным объектом.
                                          Почему нет? Это никак не повлияет на производительность, если в классе не будет виртуальных функций, все функции будут встраиваемыми, и будет использоваться массив объектов, а не указателей на них.
                                        • 0
                                          То, что вы говорите очень похоже не функциональные языки.
                                          Там масса операций со списками: свертки, фильтры, мапы.
                                          Берете функцию, натравливаете на блок данных — самые data-oriented подходы.
                                          • 0
                                            Проблема в том, что все пытаются усидеть на двух стульях
                                            и получить вкусности функционального языка, оставаясь в рамках C++
                                            Компиляторы же безуспешно пытаются выжать остатки семантики из невыразительной записи на этом языке. От этого все беды и невозможность качественной автоматической векторизации.
                                          • +1
                                            Есть очень простое правило.
                                            Если на этому участке программы важна производительность, то используйте структуры (объекты) массивов, а не массивы структур.

                                            Все.

                                            Дальше можно только сильно поизвращаться убивая перформанс: использовать смешанные типы, рекурсию, косвенную адресацию…
                                            • +3
                                              Непонятно одно — зачем? Многолетняя практика показывает что эффективнее всего вначале писать вообще без оптимизации, затем запускать под профайлером на тесткейсах и смотреть где тормозит. Далее наблюдать чудеса — либо алгоритмы сложности O( n^n^n ) которые не тормозят потому что данных нету, либо тормоза в месте, на которое мы бы никогда не подумали. Если вдруг где тормозит — конкретное место оптимизируется, для этого есть куча инструментов от того же интела которые по тикам распишут где что неэффективно. Зачем гомогенные массивы данных? О_О
                                              • +2
                                                Ну если в приложении есть вычисления и есть подозрение что это будет узким местом — лучше подумать заранее как сделать доступ к данным как можно проще и прямее.
                                                Иначе потом много чего переписывать придется.
                                                Так что в архитектуру лучше заложить заранее гомогенность основных структур данных.

                                                Ну и понятно, если вы пасьянс пишете — то какие тут оптимизации…
                                                • 0
                                                  Ну если в приложении есть вычисления и есть подозрение что это будет узким местом — лучше подумать заранее как сделать доступ к данным как можно проще и прямее.


                                                  Позволю себе с Вами немного не согласиться. Тоесть в целом я с Вами согласен — если заранее известно что и где тормозить будет и тормозить там не должно, то оптимизировать, конечно, надо. Но практика настойчиво говорит, что пока не готов прототип системы и он не проверен на реальной жизни — очень трудно угадать заранее где будет тормозить :(. Если, конечно, не пасьянс пишете :). На практике это выливается в следующее — тратятся недели чтобы оптимизировать узкие места «по подозрениям». После тестовых запусков оказывается, что в этих местах программа проводит пару процентов времени, а все тормоза на каком-нибудь blocking i/o или вызовах API O_O. Результат — более трудночитаемый код и потеряное время.

                                                  Иначе потом много чего переписывать придется.


                                                  Как раз чтобы такого не было уже многие десятки лет бьемся над разделением программы на модули, компоненты, кусочки и уменьшение зависимостей между ними. Если изменение математики приводит к «много чего переписывать» — то тут уже не проблемы оптимизации а проблемы архитектуры. ИМХО, конечно. Сам с таким сталкивался лет десять назад. После того как стал все мелко дробить и делегатами соединять, волшебные «god object» куда-то делись и смена одной сортировки на другую уже не приводит к печальному переписыванию всего и вся ^_^.
                                                • 0
                                                  "… а уже потом абстракций ООП (Data-Oriented design)..."
                                                  ООП и DOD это разные вещи, или я не прав? О_о
                                                  • 0
                                                    «Автор статьи говорит о необходимости создавать код на основе данных, а уже потом абстракций ООП (такой подход называется Data-Oriented design).»

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