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

Ресурсы

Один ноутбук 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 — максимум что получилось. Буду рад узнать если кто-нибудь получит большее отношение.

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