Амперка corporate blog
C++
Compilers
ООP
August 2015 3

Сделаем 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.
+27
18k 112
Comments 14
Top of the day