Привет хабраплюсплюсовцам!
Хочу разобрать проблему компилятора 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.
Комментарии (13)
jcmvbkbc
03.08.2015 16:09+5Привет. Недавно я собирал грабли в gcc добавляя в него поддержку для процессора из esp8266. Могу посмотреть на ваш случай.
nailxx
03.08.2015 16:42+1Было бы отлично, если посмотрите: нужно, чтобы родилась уверенность в том, что эта задача для вас решаема.
С esp’шкой всё получилось? Правильно я понимаю, что вы для неё добавляли перевод из glimpified tree в её собственный asm?jcmvbkbc
03.08.2015 17:01+5нужно, чтобы родилась уверенность в том, что эта задача для вас решаема.
Ок. Вопросы:
— всё описанное происходит с mainline gcc или с какой-то avr-специфичной веткой/репозиторием?
— обязательно ли это должен быть плагин? Может быть добавить опцию и попробовать закоммитить в транк gcc (или avr-специфичной ветки)?
С esp’шкой всё получилось? Правильно я понимаю, что вы для неё добавляли перевод из glimpified tree в её собственный asm?
Всё получилось. Поддержка xtensa уже была в gcc, я расширил её на ABI call0. Это выразилось в основном в генерации специфических прологов и эпилогов для функций. Результат.nailxx
03.08.2015 17:13— всё описанное происходит с mainline gcc или с какой-то avr-специфичной веткой/репозиторием?
Рискую сейчас глупость сказать, но разве в mainline gcc нет таргета avr? avr-gcc, avr-g++ и прочие avr-* — это ж просто врапперы над каноническими gcc, g++ и т.д. Или я не прав? Если всё так, то да, стоит добавлять функционал в mainline.
— обязательно ли это должен быть плагин? Может быть добавить опцию и попробовать закоммитить в транк gcc (или avr-специфичной ветки)?
Совсем не обязательно. Даже лучше если у gcc появится какие-нибудь `-fflash-vtbl -fno-pure-vtable`. Я думал о плагине, т.к. он будет работать вне зависимости от решений людей-меинтейнеров. «Попробовать закоммитить в транк» звучит опасно. А если попытка не пройдёт? Т.е. всё работает, но просто флаг не хотят принимать по политическим причинам?
Я не знаком с настроениями среди разработчиков GCC. Быть может мои опасения напрасны?
Всё получилось.
Супер! Покопал ваши коммиты. Внушает доверие. А патч приняли в итоге в trunk?khim
03.08.2015 17:33+2Рискую сейчас глупость сказать, но разве в mainline gcc нет таргета avr? avr-gcc, avr-g++ и прочие avr-* — это ж просто врапперы над каноническими gcc, g++ и т.д. Или я не прав?
А вот про это, собственно, и спрашивают. Так бывает, что в upstream что-то такое живёт, но реально люди пользуются каким-то форком, про который upstream ничего не знает.
«Попробовать закоммитить в транк» звучит опасно. А если попытка не пройдёт? Т.е. всё работает, но просто флаг не хотят принимать по политическим причинам?
Я знаком с несколькими. Вполне адекватные люди. Ни про какие отказы что-то делать «по политическим причинам» я никогда не слышал (за исключением проблем с лицензиями, что, понятно, никак не затрагивает вновь написанный код специально для GCC).
Я не знаком с настроениями среди разработчиков GCC. Быть может мои опасения напрасны?
А вот технических требований у них бывает вагон и маленькая тележка. То есть, грубо говоря, то, что вы хотите делается «с помощью лома и какой-то матери» за несколько дней, а вот допиливание до варианта, который upstream примет — это скорее несколько недель. В основном несколько недель переписки, не кодинга.
jcmvbkbc
03.08.2015 17:53+3разве в mainline gcc нет таргета avr?
Таргет есть, вопрос — им ли вы пользуетесь.
«Попробовать закоммитить в транк» звучит опасно. А если попытка не пройдёт? Т.е. всё работает, но просто флаг не хотят принимать по политическим причинам?
Судя по тому, что запись в багзилле gcc по одной из ваших ссылок не закрыта как wontfix, надежда есть.
А патч приняли в итоге в trunk?
Да, он попал в релиз 5.1. Ссылочка — как раз на официальное git-зеркало gcc на gcc.gnu.org.nailxx
03.08.2015 19:18+2Пошерстил сейчас, что за toolset кладут в Arduino IDE под Windows, какие зависимости Arduino IDE от gcc в Linux. Не вижу причин, по которым нужно что-то отличное от меинстрима. Стало быть делаем на нём.
Судя по тому, что запись в багзилле gcc по одной из ваших ссылок не закрыта как wontfix, надежда есть.
Надежды, мечты… :) В общем да, вселяет оптимизм.
Да, он попал
Классно! Вселяет ещё больше.
ilynxy
03.08.2015 23:03+1Интересуюсь на всякий случай: шаманство с linker script (разместить все vtable в ROM, тем самым обязав конпелятор генерировть соответствующий код) не даёт результата? Или размещением vtable нельзя управлять в линкере?
ilynxy
03.08.2015 23:19+4Сам спросил сам отвечу. Не получится. Хотя можно (если постараться) сказать линкеру размещать vtables в ROM ничо это не меняет, инструкция ldd генерируется на этапе компиляции. Всё таки нужно в кишки gcc лезть и делать опцию.
khim
04.08.2015 00:54+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 для предка и для потомка… а если они должны «жить» в разных местах — как быть?).
jcmvbkbc
17.08.2015 11:00+4На прошедших выходных у меня нахардкодился вот такой прототип: github.com/jcmvbkbc/gcc-avr/commit/a83ac3ebaed7737cbdca19b513a55911a1ff8c35
Он не валится на тривиальных примерах и вроде делает то что нужно. Продолжаем?nailxx
17.08.2015 17:40Круть. Увы, умотал в отпуск, поэтому не смогу взглянуть на всё это на протяжении ближайших 2 недель. По возвращению обязательно вам напишу.
Gorthauer87
Что-то мне кажется, что быстрее будет clang+llvm допилить, там и api плагинов нормальное и процесс разработки более публичный.