Оптимизируем код, или перегоним Огнелиса в скорости

    Почитал топик об новых супероптимизациях в Огнелисе и долго думал.
    Для меня не очень понятно, почему вокруг такого рода работы устроен праздник с феерверком и снегурочкой. Давайте подробнее рассмотрим что же было сделано.

    * Function Inlining: Removing the overhead of function calls by simply replacing them with their resulting native code.
    Инлайнинг функций умеют делать практически все компиляторы. Это очень простой и можно сказать бесплатный способ ускорения программы. У него есть определенные ограничения:
    1) Избыточный инланинг ведет к раздуванию кода. Это сейчас практически не проблема — памяти ощутимо много, но компилятор имеет ограничение сверху на размер включаемой ф-ции.
    2) Компилятор НЕ умеет инлайнить функции из соседнего модуля, из системных библиотек, а так из динамических библиотек.

    Кроме того нормальный (современный) компилятор умеет работать с так называемыми «интринсиками» — функциями, которые он распознает по табличке и имеет готовый код для них. Это обычно математические функции, такие как sin(). Так вот, этот самый синус будет сделан не как call sin(), а будет вставлен куском кода, т.е. автоматически заинлайнен.

    * Type Inference: Removing checks surrounding common operators (like «+») when the types contained within a variable are already known. This means that the engine will have already pre-determined, for example, that two strings need to be concated when it sees the «+» operator.

    Ну эт обычно называется RTTI skip — выбросили проверку типов там где она не нужна… Возможно для JIT компилятора это и суперкруто, однако обычные умеют делать такое уже давно. Естественно вся ответственность за типы, а точнее их возможное несоответствие ложится на программиста :)

    * Looping: The overhead of looping has been grossly diminished. It's one of the most common areas of overhead in JavaScript applications (common repetition of a task) and the constant determining of bounds and the resulting inner code is made negligible.
    9 из 10 что был сделан простой анролл цикла. Unrolling представляет собой дублирование тела цикла N раз:
    for (int i=0; i<maxI; i++){
    a[i] = b[i]+c[i];
    }


    если unroll на 4 то получаем:
    for (int i=0; i<maxI; i+=4){
    a[i] = b[i]+c[i];
    a[i+1] = b[i+1]+c[i+1];
    a[i+2] = b[i+2]+c[i+2];
    a[i+3] = b[i+3]+c[i+3];
    }

    Ну и плюс доппроверку, что maxI кратно 4 :)

    Теперь берем нашу программу, Intel C Compiler (или Intel Fortran Compiler — кому что нравится) и собираем проект со следующими ключами:
    -O3 (да, агрессивная оптимизация);
    -axT (включаем векторизацию, т.е использование SSEx + генерация общего кода для тяжелых случаев);
    -ip (межпроцедурная оптимизация, включая частичный инлайнинг. для фанатов есть опция -ipo — межмодульная оптимизация, не портабельно!!!);
    -ansi-alias -fno-alias (улучшает векторизируемость :) циклов)

    Плюс ко всему этому получаем: автоматический анролл циклов как минимум на 4, инлайнинг и интринсики всех математических функций.
    И огнелис не догонит ;)
    Да, и в общем случае есть разница между обычным и JIT компилятором, но она не настолько велика, чтобы выдавать давно известные фичи за открытия (типа: «О! Мы придумали инлайнинг!»)

    PS. Первый блин, просьба комом не бить по лицу.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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

      +5
      Если это не шутка, то придется немного побить. В статьях речь шла об увеличении скорости интерпретации JavaScript. Ясно, что таже программа на C/C++ будет в разы быстрее. Если напишите более быстрый js-интерпретатор, то тогда можете написать что что-то обогнали.
        0
        «Муза — это женщина, она никогда не признается, кто был первым» =)
          0
          Шутка только в названии.
          Принципы оптимизации — те же самые, что и было рассмотрено.
            +2
            Пожалуйста прежде чем комменитровать что-либо походите по ссылкам и ознакомьтесь с первоисточником.

            Там все эти оптимизации сделаны иначе, чем они делаются в классическом компиляторе для языка со статической типизацией (а-ля Intel C Compiler). Я позволю себе прокоментировать ваши комментарии с учетом этой разницы.

            Это сейчас практически не проблема — памяти ощутимо много


            Классический подход: Проблема с открытой подстановкой (инлайном) в том, что она в общем случае увеличивает давление на регистры. А регистров никогда не бывает много =). В общем случае задача инлайна представляет собой разновидность задачи о ранце, которая как известно NP-полна. Поэтому что бы определить какой метод в какой подставлять обычно используют разного вида эвристики и явные флаги (always inline). Реже profile guided optimization: делается тестовый прогон и собирается информация о горячих методах, далее эвристики учитывают эту информацию. Как показывают исследования наибольший прирост производительности даёт как раз использование одновременно и профиля и эвристик на основе статического анализа.

            Подход трассирующего JIT: Мы сразу получаем информацию о горячих точках и начинаем записывать трассу именно с горячей точки. Поэтому получается что трассирующий JIT фактически «на халяву» учитывает профиль программы.

            Компилятор НЕ умеет инлайнить функции из соседнего модуля, из системных библиотек, а так из динамических библиотек


            Классический подход: Проблема межмодульного инлайна сейчас начинает решаться, компиляторы () обзаводятся оптимизациями на этапе компоновки. Плюс есть ряд компиляторов, в которых межмодульный инлайн поддерживался изначально (i.e. Excelsior JET).

            Подход трассирующего JIT: Запись трассы ведётся во время исполнения и не прекращается во время вызова. Поэтому никакой проблемы межмодульного инлайна нет.

              +2
              Ну эт обычно называется RTTI skip — выбросили проверку типов там где она не нужна…


              RTTI skip = Run-time type information skip довольно странно звучащее название. Переводится как «Пропуск Информации о Типах Времени Исполнения». Кажется, вы его сами придумали.

              Даже в статическом языке что бы выкинуть проверку типа компилятору надо основательно глобально подумать. Представьте себе функцию

              А вы попробуйте

              Естественно вся ответственность за типы, а точнее их возможное несоответствие ложится на программиста :)

                +3
                Ну что я за кнопку опять нажал, растяпа?

                Продолжим.

                Легко выкидывать проверки в C++, который позволяет портить память.

                В любом типо-безопасном (type safe) языке, что бы выкинуть проверку типа компилятору надо основательно глобально подумать. Представьте себе функцию на языке Java:

                void f(BaseClass o) {
                ((ChildClass)o).foo();
                }

                Компилятору что бы выкинуть проверку надо доказать, что любое o является экземпляром ChildClass и никак иначе.

                А теперь представьте, что типов вообще нет. Что есть замыкания (closures) и ассоциативные массивы. Это сущий ад для классического глобального анализа. Конечно, корифеи собаку на это съели, когда оптимизировали программы на Smalltalk подобных языках. Но трассирующий JIT предоставляет элегантное и что самое главное дешевое (т.е. быстрое и потребляющее мало памяти) решение данной проблемы.

                Естественно вся ответственность за типы, а точнее их возможное несоответствие ложится на программиста :)


                Компилятор для type safe языка не имеет права такого делать. Ответственность исключительно на компиляторе и только на нём.
                  +1
                  был сделан простой анролл цикла. Unrolling представляет собой дублирование тела цикла N раз:


                  Опять же таже проблема, что и с инлайном. Как определить, где делать unroll и где не делать? Не тривиальный вопрос на самом деле.

                  Но на самом деле unroll здесь не причем. Трассирующий JIT по своей структуре завязан собственно на оптимизацию горячих путей, т.е. путей по которым много ходят. А это как раз циклы. Поэтому циклы и оптимизируются.
                    +1
                    Давайте тогда по пунктам :)
                    1. По поводу RTTI. Если информация о типе известна в момент компилирования, то такая информация в рантайме будет избыточна, и соответсвующие проверки можно удалить. Такая штука может называется по другому — а skipping — это наш местный жаргон.

                    2.Проблема межмодульного инлайна сейчас начинает решаться, компиляторы () обзаводятся оптимизациями на этапе компоновки.
                    Ну вот тот флажок -ipo и есть межмодульный инлайнер. Только нужно не забывать, что в этом

                    3. Как определить, где делать unroll и где не делать?
                    Там все просто — сейчас анролл делается всегда. Более того, еще иногда делается versioning — в коде создается несколько циклов, один вариант для выровненных данных, а другой — для невыровненных (к примеру).

                      +1
                      1. а если не известна? её же насчитать надо. а насчитывать для языка типа JS её можно ой как долго.

                      2. ну понятное дело, что совместимость на объектном уровне. главное в том, что проблема для классических компиляторов решается. а для JIT её вообще не существует.

                      3. Там — это где? И что даже нет ограничений на размер тела цикла?
                      0
                      *Только нужно не забывать, что в этом
                      в этом случае теряется совместимость на объектном уровне.
                        0
                        я что-то не понял, в каком смысле теряется. и о какой совместимости идёт речь?

                        я о другом видимо подумал, вас не понял.
                        +1
                        >Это сейчас практически не проблема — памяти ощутимо много

                        Нет, это проблема. Инлайнинг и анлоллинг ведёт к дублированию кода. Большой код может хуже помещаться в кеш инструкций и поэтому его выполнение будет медленнее. Например, ядро Linux сейчас по умолчанию компилируется с -Os, а не -O2 (опция CONFIG_CC_OPTIMIZE_FOR_SIZE).
                          0
                          Вообщем по первым двум пунктам более менее понятно. Объектная несовместимость IPO состоит в том, что объетные файлы получаются в специальном формате. Там включается дополнительная информация об типах, функциях и параметрах. Я про *.o (*.obj).

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

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

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