Несколько подробностей о шаблонах или форк-бомба этапа компиляции

Недавно заинтересовался инстанцированием плюсовых шаблонов. В интернетах втречается термин code bloat ^[1]. Для с++ это может означать неконтроллируемое увеличение кода генерируемого компилятором. Код увеличивается за счет того что инстанцирование новой функции имеет более высокий приоритет чем преобразование аргументов к более удобному типу. Т.е. template T foo(T a); для int и char — это две разные функции. Получить одну функцию можно либо отказом от шаблонов, либо использованием явного преобразования типов.
Но давайте вывернем проблему наизнанку и попробуем получить из минимума строк кода исполняемый файл максимально возможного размера.
Результат не очень впечатил — у меня получилось всего 53Mb из 60 строк кода. И то лишь для одного из трех опробованных компиляторов и ценой нескольких часов компиляции. Максимальное отношение объем/строки — 2.3МБ/строку для объема 14МБ.
Как и почему так получилось — под катом.

Ресурсы

Один ноутбук c 4Гб памяти,
процессором «Intel® Core(TM) i3-2330M CPU @ 2.20GHz»,
ОС Linux 3.7.3-101.fc17.x86_64
и отключеным swap разделом.
Отключить своп пришлось по тойже причине, по которой в названии поста появилась форк-бомба. При достаточно большом объеме задачи компилятор выедал всю память и начинал активно обмениваться с диском, что намертво и надолго вешало машину.

Версии компиляторов:

• g++ (GCC) 4.7.2 20120921 (Red Hat 4.7.2-2)
• Intel® C++ Intel® 64 Compiler XE for applications running on Intel® 64, Version 13.1.1.163 Build 20130313
• clang version 3.3 (trunk 179304)

Длинные массивы

Самый простой способ — организовать массив этапа комиляции и нанизать на него функций. Вот так:

template<long n> inline void nop(){nop<n-1>();asm("nop"); }
template<> inline void nop<0>() {asm("nop");}
 int main(int argc, char ** argv) {
        nop<LVL>();
        return 0;
} 

В итоге должена получиться функция main() заполненная пустыми бесполезными операциям nop.

Размер последовательности nop теоретически определяется глубиной рекурсии. В мане g++ утверждается, что максимальная глубина 17 и 1024 для с++11.

В стандартах конкретных чисел я не нашел. Обнаружился лишь пункт, что максимальная глубина рекурсии определяется реализацией:
4.7.1.14 для с++03
4.7.1.15 для c++11
Что и подтвердилось на опыте. Для достаточно большого LVL компиляторы вылетали. Удивил clang++ который вылетал на 2¹³, в отличие от g++ и icpc достигающих 2¹⁷.

Сборка осуществлялась командами:

 clang++  -DLVL=$(( 2**$n)) -o list$n ./list.cc -ftemplate-depth=3000000 -O$x
     g++  -DLVL=$(( 2**$n)) -o list$n ./list.cc -ftemplate-depth=3000000 -O$x
    icpc  -DLVL=$(( 2**$n)) -o list$n ./list.cc -O$x

в рамках

#/bin/bash
MIN=0
MAX=19
for i in 2;
do
        mkdir -p attempt$i
        cd attempt$i
        for CXX in clang++ g++ icpc
        do
                mkdir -p $CXX
                cd $CXX
                for O in O0 O1 O2 O3 Os 
                do
                        mkdir -p $O
                        cd $O
                        (while :;do free -m |grep Mem|awk '{print $3}' >> ./memory;sleep 1;done)&
                        TIME=$!
                        for i in $(seq $MIN $MAX)
                        do
 #                             CMD="$CXX -$O ../../../fbomb.cc -DLVL=$i -o fbomb$i" #-save-temps=obj "
                                CMD="$CXX -$O ../../../list.cc -DLVL=$(( 2 ** $i)) -o list$i  -ftemplate-depth=3000000" #-save-temps=obj "
                                echo $CMD
                                $CMD    
                                sleep 5
                                sleep 5
                        done
                        kill -9 $TIME
                        cd ..
                done
                cd ..
        done
        cd ..
done

Собирались бинарники последовательно и долго. Для каждого компилятора, для каждого уровня оптимизации. Результаты сборки показаны в виде графиков. Четыре столбца изображений:

1. Зависимость используемой памяти от времени. Эти графики даны скорее для справки, т.к. во время компиляции работали ещё Х-сервер и браузер, однако основные тенденции видны.
2. Размер бинарного файла. Максимальный получился — 14МБ
3. Количество символов. Ключевое слово inline — лишь рекомедация компилятору, поэтому при больших N. Nop-ы группируются в обычные функции. Подсчитаны они так:

   nm --demangle ./list$i|grep nop|wc -l

4. Количество честных nop-ов. Подсчитанно из дизассеблера:

   objdump -d ./list$i|grep 'nop$'|wc -l

Картинки

Сравнение разных уровней оптимизации для одинаковых компиляторов

Потребление памяти во время компиляции	Размер исполняемого файла	Количество символов в исполняемом файле	Количество операций nop

Сравнение разных компиляторов при различных уровнях оптимизации

Потребление памяти во время компиляции	Размер исполняемого файла	Количество символов в исполняемом файле	Количество операций nop

Файл максимального размера получился 14МБ для 2¹⁷ компилятора icpc. Для g++ — 12 МБ. Оба при O0. Уровен оптимизации O0 не выполняет inline подстановку, поэтому количество nop<long> символов совпадает с количеством nop операций.

Высокие деревья

Для линейной структуры данных размер генерируемого файла ограничивается, как минимум максимальной глубиной рекурсии принятой по умолчанию(256 для clang++, 900 для g++). Чтобы обойти его можно попробовать создать дерево. Максимальная теоритическая глубина дерева этапа компиляции — (sizeof(long)-1) == 63. А 2⁶⁴ байт переполнит любой диск. Практический предел много меньше.
Используя дерево, мы не выходим за пределы максимальной глубины рекурсии.
Исходный код занимает 19 строк и выглядит так:

#ifndef LVL
#       define LVL 3
#endif
long x = 0;
template<int N=LVL, long I=0> 
struct foo{
        inline static double bar(double m)
                {x++;return foo<N-1,I>::bar(m) + foo<N-1,((1<<(LVL-N))|I)>::bar(m) + I;};
};
template<long I>
struct foo<0,I>{
        inline static double bar(double m) {x++; return m;} 
};
#include <iostream>
int main(int argc, char **argv){
        double ret = foo<>::bar(argc);
        std::cout << x << " " << ret << std::endl;
        return int(ret);
}

В итоге получается дерево, каждый узел которого имеет собственный тип. Каждый тип характеризуется парой чисел:

• N — номер уровня;
• I — номер узла на уровне.

Каждый узел внутри одного уровня пронумерован от 0 до N.

Баловаться с nop-ами тут я не стал, использовал сложение. Глобальная long x — использвалась для контроля правильности сборки. В результате возвращается 2^LVL+1.

Сборка осуществлялась командами:

 clang++  -DLVL=$n -o fbomb$n ./fbomb.cc  -O$x
     g++  -DLVL=$n -o fbomb$n ./fbomb.cc  -O$x
    icpc  -DLVL=$n -o fbomb$n ./fbomb.cc -O$x

в том же сценарии что приведен выше.
Максимальный LVL получился равным 18 для clang++. Для g++ и icpc — 16, причем не зависимо от того была ли указана опция --std=c++11 или нет. Компиляторам не хватало памяти.

Картинки для дерева

Потребление памяти во время компиляции	Размер исполняемого файла	Количество символов в исполняемом файле

Потребление памяти во время компиляции	Размер исполняемого файла	Количество символов в исполняемом файле

Максимальный размер файла:

• 43МБ для icpc -O0 -DLVL=17;
• 42МБ для clang++ -O0 -DLVL=17;
• 22MB для g++ -O0 -DLVL=16.

Явное инстанцирование

43МБ — не так уж и мало, но можно ли сделать файл ещё больше при заданном объеме оперативной памяти? Оказалось можно, но только одним компилятором из трех — icpc. Для этого нужно использовать внешние шаблоны и явное инстанцирование.
Модифицируем немного исходный код, чтобы все параметры шаблона указывались при его описании. Разделим исходный код на три файла — описание шаблона, main функция и частичное инстанцирование поддеревьев:

extern long x;

template<int L=LVL, int N=L, long I=0>
struct foo{
        inline static double bar(double m)
                {x++;return foo<L,N-1,I>::bar(m) + foo<L,N-1,((1<<(L-N))|I)>::bar(m) + I;};
};
template<int L, long I>
struct foo<L,0,I>{
        inline static double bar(double m) {x++; return m;} 
};

#include "fbomb.hh"
//for i in $(seq 0 13);do echo "extern template struct foo<LVL,L,$i>;";done
#define L   (LVL-5)
extern template struct foo<LVL,L,0>;
extern template struct foo<LVL,L,1>;
extern template struct foo<LVL,L,2>;
extern template struct foo<LVL,L,3>;
...
extern template struct foo<LVL,L,30>;
extern template struct foo<LVL,L,31>;

#include <iostream>
long x = 0;
int main(int argc, char **argv){
        double ret = foo<LVL>::bar(argc);
        std::cout << x << " " << ret << std::endl;
        return int(ret);
}

template class foo<LVL, _L, _I>;

Оказалось, что g++ -c main.cc -DLVL=21 требует вылетает по недостатку памяти также как при полном инстанцировании независимо от версии стандарта. Такая же ситуация для clang++. Icpc компилирует main.cc менее чем за секунду. Однако компиляция поддеревьев заняла более 4 часов времени:

for i in $(seq 0 31);do
    echo -n "$i:";date;
    icpc -O2 -c ./part.cc -o part21_16_$i.o -DLVL=21 -D_L=16 -D_I=$i;sleep 10;
done

Потребление памяти во время компиляции поддеревьев

Линковка заняла меньше минуты. В результате получился файл размером 53МБ. Это файл собирался с -O2. -O0 дало бы больший размер, но пересобирать это несколько раз я не стал из-за времени и бессмысленности результата.

Самое большое отношение объем/количество строк = 2.3Мб/cтроку получилось для массива из первой части (icpc -O0 list.cc)
Метрика конечно шутошная, но забавная. 2.3 — максимум что получилось. Буду рад узнать если кто-нибудь получит большее отношение.

Удачи нам всем.

Автор: korisk

Источник ^[2]