Сделаем GCC C++ для AVR и Arduino лучше?



    Привет хабраплюсплюсовцам!

    Хочу разобрать проблему компилятора avr-g++, из-за которой в разных дискуссиях про AVR и Arduino звучит «С++ — это не для микроконтроллеров, C++ жрёт память, C++ генерирует раздутый код — пишите на голом C, а лучше на ASM».

    Для начала давайте разберёмся, в чём же преимущество C++ перед C. Концепций, которые добавляет C++ много, но самая значимая и самая эксплуатируемая — это поддержка ООП. Что такое ООП?
    • Инкапсуляция
    • Наследование
    • Полиморфизм


    Использование первых двух пунктов в C++ «бесплатно». Никакого преимущества программа на чистом C перед программой на C++ с инкапсуляцией и наследованием не имеет. Картина меняется, когда мы подключаем к действу полиморфизм. Полиморфизм бывает разным: compile-time, link-time, run-time. Я говорю о классическом run-time, т.е. о виртуальных функциях. Как только в своих классах вы начинаете добавлять виртуальные методы, чудесным образом растёт потребление как Flash-памяти, так и SRAM.

    Почему так происходит и, что с этим можно было бы сделать, расскажу под катом.

    Пример без виртуальных функций


    Давайте посмотрим на программу с одним базовым классом и двумя наследниками:

    volatile unsigned char var;
    
    class Base
    {
        public:
            void foo() { var += 19; }
            void bar() { var += 29; }
            void baz() { var += 39; }
    };
    
    class DerivedOne : public Base
    {
        public:
            void foo() { var += 17; }
            void bar() { var += 27; }
            void baz() { var += 37; }
    };
    
    class DerivedTwo : public Base
    {
        public:
            void foo() { var += 18; }
            void bar() { var += 28; }
            void baz() { var += 38; }
    };
    
    DerivedOne dOne = DerivedOne();
    DerivedTwo dTwo = DerivedTwo();
    
    int main()
    {
        Base* b;
        if (var)
            b = &dOne;
        else
            b = &dTwo;
    
        asm("nop");
        b->foo();
    
        for (;;)
            ;
    
        return 0;
    }
    


    В функции `main` на основе значения `var`, которое компилятору заведомо не известно, мы назначаем указателю на базовый класс `b` ссылку либо на объект первого унаследованного класса, либо ссылку на объект второго. А затем вызываем метод `foo` по указателю на базовый класс.

    Этот пример глуповат, т.к. вне зависимости от нашей возни с дочерними классами, будет вызвана реализация `foo` от базового класса `Base`. Пример полезен, как отправная точка.

    $ avr-g++ -O0 -c novirtual.cpp -o novirtual.o
    $ avr-gcc -O0 novirtual.o -o novirtual.elf
    $ avr-size -C --format=avr novirtual.elf
    AVR Memory Usage
    ----------------
    Device: Unknown
    
    Program:     104 bytes
    (.text + .data + .bootloader)
    
    Data:          3 bytes
    (.data + .bss + .noinit)
    


    Итак, программа использует 104 байта Flash-памяти и 3 байта SRAM. 104+3 байт при использовании флагов оптимизации усыхают до 34+3, а при использовании флагов очистки мёртвого кода и вовсе — 16+0 байт.

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

    	ldd r24,Y+1
    	ldd r25,Y+2
    	rcall _ZN4Base3fooEv
    


    В регистры `r24:r25` загоняется значение `this` и делается непосредственный вызов `Base::foo`. Просто, эффективно. Конечно, оптимизатор заметит ненужность this и вообще узрит возможность inline’а, но мы давайте рассуждать на неоптимизированном уровне.

    Добавляем virtual


    Теперь давайте добавим полиморфизма. Сделаем наши методы виртуальными:

    volatile unsigned char var;
    
    class Base
    {
        public:
            virtual void foo() { var += 19; }
            virtual void bar() { var += 29; }
            virtual void baz() { var += 39; }
    };
    
    class DerivedOne : public Base
    {
        public:
            virtual void foo() { var += 17; }
            virtual void bar() { var += 27; }
            //virtual void baz() { var += 37; }
    };
    
    class DerivedTwo : public Base
    {
        public:
            virtual void foo() { var += 18; }
            //virtual void bar() { var += 28; }
            virtual void baz() { var += 38; }
    };
    
    DerivedOne dOne = DerivedOne();
    DerivedTwo dTwo = DerivedTwo();
    
    int main()
    {
        Base* b;
        if (var)
            b = &dOne;
        else
            b = &dTwo;
    
        asm("nop");
        b->foo();
    
        for (;;)
            ;
    
        return 0;
    }
    


    Проверяем:

    AVR Memory Usage
    ----------------
    Device: Unknown
    
    Program:     312 bytes
    (.text + .data + .bootloader)
    
    Data:         25 bytes
    (.data + .bss + .noinit)
    


    Ого-го! 25 байт SRAM как не бывало. Легко проверить, что создание очередного экземпляра класса съест ещё 2 байта. Эти 2 байта — указатель на таблицу виртуальных функций, которая и позволяет при вызове метода по указателю на базовый класс исполнять конкретную реализацию номинального дочернего класса.

    Но ведь у нас всего 2 глобальных объекта и одна несчастная переменная на 1 байт. Кто сожрал всю остальную память? Вот мы и подошли к сути проблемы. Это сами виртуальные таблицы. По штуке на каждый класс. Размер каждой линейно зависит от количества виртуальных функций.

    Цена полиморфизма


    Давайте схематично изобразим таблицы виртуальных функций. В нашем примере их 3, по одной на каждый класс:

    vtable for Base:
      foo -> Base::foo
      bar -> Base::bar
      baz -> Base::baz
    
    vtable for DerivedOne:
      foo -> DerivedOne::foo
      bar -> DerivedOne::bar
      baz -> Base::baz
    
    vtable for DerivedTwo:
      foo -> DerivedTwo::foo
      bar -> Base::bar
      baz -> DerivedTwo::baz
    
    

    Каждый указатель на 8-bit AVR — это 2 байта. Достаточно единожды создать такие таблицы для каждого класса в иерархии, а затем в конкретных экземплярах добавлять одно скрытое поле `__vtbl*`, которое указывает на конкретную таблицу. Так каждый экземпляр будет «знать кто он» вне зависимости от того, по указателю какого типа вызывают его методы. Т.е. оверхед полиморфизма для одного объекта — это лишь +2 байта на `__vtbl*` и затраты на косвенный вызов. Метод вызывается не напрямую, а сначала подтягивается его адрес из таблицы, а затем идёт вызов.

    	ldd r24,Y+1
    	ldd r25,Y+2
    	mov r30,r24
    	mov r31,r25
    	ld r24,Z
    	ldd r25,Z+1
    	mov r30,r24
    	mov r31,r25
    	ld r18,Z
    	ldd r19,Z+1
    	ldd r24,Y+1
    	ldd r25,Y+2
    	mov r30,r18
    	mov r31,r19
    	icall
    

    Дополнительные затраты на косвенный вызов важны, если речь идёт о многочисленных вызовах в коде, который очень критичен к времени исполнения. Но тогда возникает вопрос: что делает полиморфизм в таком коде? Каждой задаче — свой инструмент. Для решения задач высокого уровня ООП — благо.

    Где avr-gcc не прав


    Я показал, что реальные пенальти по SRAM от активного использования виртуальных функций — это 2 байта на экземпляр. Очень адекватно за столь богатые возможности. Но что делает avr-gcc? Он пихает сами виртуальные таблицы в SRAM! Из-за этого появление каждого нового класса с виртуальными функциями, его наследника или даже интерфейса (pure abstract class) приводит к увеличению потребляемой SRAM.

    Это совершенно не обоснованно, т.к. виртуальные таблицы не могут меняться по ходу исполнения программы. Им самое место в Flash-памяти, которая обычно «заканчивается» куда позже, чем SRAM. Это тема 100 раз поднималась в разных сообществах.

    Ирония в том, что эти таблицы и так уже размещаются в Flash, а в момент старта контроллера копируются ещё и в SRAM. В генерируемом ASM для получения адреса реализации функции нужно «просто» использовать не `ldd`, а `lpm`, т.е. ходить за адресом не в копию таблицы в SRAM, а в её оригинал на Flash.

    Почему сей оптимизации ещё никто не сделал? Всё как всегда упирается не в технику, а в людей. GCC — по-настоящему большой open source проект, за которым не стоит большого папы с деньгами. GCC очень большой, со своей культурой, структурой, чемоданом знаний и т.д. На фоне его кучка людей, кричащих о том, что хотят C++ на каких-то штуках с какой-то гарвардской архитектурой, очень мала. Ещё не нашлось человека, который принадлежал бы обоим мирам и был достаточно замотивирован на доработку.

    Что же делать?


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

    Я очень надеюсь, что такой человек есть. Очень хочется, чтобы такой плагин появился и стал доступен сообществу, сделав нашу жизнь чуть приятнее. Амперка готова поддержать разработку рублём… 150 килорублями за плагин, который привёл бы к усушиванию программы из примера с 25 байт SRAM до 7 байт.

    Если вы знаете человека, который уже собирал грабли в GCC, пожалуйста, обратите его внимание на этот пост. Заранее вам спасибо! Пишите в комменты, в личку или на victor[собака]amperka.ru.
    Амперка
    40.18
    Company
    Share post

    Comments 14

      +6
      Что-то мне кажется, что быстрее будет clang+llvm допилить, там и api плагинов нормальное и процесс разработки более публичный.
        +5
        Привет. Недавно я собирал грабли в gcc добавляя в него поддержку для процессора из esp8266. Могу посмотреть на ваш случай.
          +1
          Было бы отлично, если посмотрите: нужно, чтобы родилась уверенность в том, что эта задача для вас решаема.

          С esp’шкой всё получилось? Правильно я понимаю, что вы для неё добавляли перевод из glimpified tree в её собственный asm?
            +5
            нужно, чтобы родилась уверенность в том, что эта задача для вас решаема.

            Ок. Вопросы:
            — всё описанное происходит с mainline gcc или с какой-то avr-специфичной веткой/репозиторием?
            — обязательно ли это должен быть плагин? Может быть добавить опцию и попробовать закоммитить в транк gcc (или avr-специфичной ветки)?

            С esp’шкой всё получилось? Правильно я понимаю, что вы для неё добавляли перевод из glimpified tree в её собственный asm?

            Всё получилось. Поддержка xtensa уже была в gcc, я расширил её на ABI call0. Это выразилось в основном в генерации специфических прологов и эпилогов для функций. Результат.
              0
              — всё описанное происходит с mainline gcc или с какой-то avr-специфичной веткой/репозиторием?


              Рискую сейчас глупость сказать, но разве в mainline gcc нет таргета avr? avr-gcc, avr-g++ и прочие avr-* — это ж просто врапперы над каноническими gcc, g++ и т.д. Или я не прав? Если всё так, то да, стоит добавлять функционал в mainline.

              — обязательно ли это должен быть плагин? Может быть добавить опцию и попробовать закоммитить в транк gcc (или avr-специфичной ветки)?


              Совсем не обязательно. Даже лучше если у gcc появится какие-нибудь `-fflash-vtbl -fno-pure-vtable`. Я думал о плагине, т.к. он будет работать вне зависимости от решений людей-меинтейнеров. «Попробовать закоммитить в транк» звучит опасно. А если попытка не пройдёт? Т.е. всё работает, но просто флаг не хотят принимать по политическим причинам?

              Я не знаком с настроениями среди разработчиков GCC. Быть может мои опасения напрасны?

              Всё получилось.


              Супер! Покопал ваши коммиты. Внушает доверие. А патч приняли в итоге в trunk?
                +2
                Рискую сейчас глупость сказать, но разве в mainline gcc нет таргета avr? avr-gcc, avr-g++ и прочие avr-* — это ж просто врапперы над каноническими gcc, g++ и т.д. Или я не прав?
                А вот про это, собственно, и спрашивают. Так бывает, что в upstream что-то такое живёт, но реально люди пользуются каким-то форком, про который upstream ничего не знает.

                «Попробовать закоммитить в транк» звучит опасно. А если попытка не пройдёт? Т.е. всё работает, но просто флаг не хотят принимать по политическим причинам?

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

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

                  +3
                  разве в mainline gcc нет таргета avr?

                  Таргет есть, вопрос — им ли вы пользуетесь.

                  «Попробовать закоммитить в транк» звучит опасно. А если попытка не пройдёт? Т.е. всё работает, но просто флаг не хотят принимать по политическим причинам?

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

                  А патч приняли в итоге в trunk?

                  Да, он попал в релиз 5.1. Ссылочка — как раз на официальное git-зеркало gcc на gcc.gnu.org.
                    +2
                    Пошерстил сейчас, что за toolset кладут в Arduino IDE под Windows, какие зависимости Arduino IDE от gcc в Linux. Не вижу причин, по которым нужно что-то отличное от меинстрима. Стало быть делаем на нём.

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


                    Надежды, мечты… :) В общем да, вселяет оптимизм.

                    Да, он попал


                    Классно! Вселяет ещё больше.
            +1
            Интересуюсь на всякий случай: шаманство с linker script (разместить все vtable в ROM, тем самым обязав конпелятор генерировть соответствующий код) не даёт результата? Или размещением vtable нельзя управлять в линкере?
              +4
              Сам спросил сам отвечу. Не получится. Хотя можно (если постараться) сказать линкеру размещать vtables в ROM ничо это не меняет, инструкция ldd генерируется на этапе компиляции. Всё таки нужно в кишки gcc лезть и делать опцию.
                +5
                Написал в личку, но, похоже, стоит продублировать и здесь. На ваше счастье три года назад этот туннель прокопали почти что до самого конца. Начиная с GCC 4.7 avg-gcc поддерживает ссылки на объекты в флеше (и даже 24-битные «ссылки куда угодно», хотя это вроде как тут не нужно).

                Остаётся сделать опцию, которая на «невидимую» ссылку, указывающую на vtable повесит нужный атрибут. В backend'е ничего править не придётся: теоретически он сам должен будет разобраться какой командой что читать, если атрибуты будут правильно указаны. В принципе можно даже сделать версию, которая для части объектов будет держать vtable в памяти, а для части — во флеше. А можно ещё поддержку разных моделей (вспомним C/С++ в DOS, да: small/medium/compact/large вполне прозрачно накладываются на AVR, tiny и huge, понятно, смысла не имеют). Но, конечно, так широко сразу шагать не стоит — как бы штаны не порвать.

                P.S. Скорее всего начать стоит именно с опции, а не с расширения N1275 для C++. А то дело увязнет на год, который уйдёт на то, чтобы придумать — как, чёрт побери, «правильно» расширить именованные адресные пространства с учётом «невидимых» указателей в C++ и что делать когда, скажем, один и тот же указатель должен бы получить два разных аттрибута (в случае одиночного наследования большинство компиляторов, в том числе GCC, делают «униварсальную» vtable которую «можно читать» как vtable для предка и для потомка… а если они должны «жить» в разных местах — как быть?).
              +4
              На прошедших выходных у меня нахардкодился вот такой прототип: github.com/jcmvbkbc/gcc-avr/commit/a83ac3ebaed7737cbdca19b513a55911a1ff8c35
              Он не валится на тривиальных примерах и вроде делает то что нужно. Продолжаем?
                0
                Круть. Увы, умотал в отпуск, поэтому не смогу взглянуть на всё это на протяжении ближайших 2 недель. По возвращению обязательно вам напишу.

                Only users with full accounts can post comments. Log in, please.