c: скорость компиляции

Подозреваю, что gcc плохо масштабируется по числу операторов на функцию. А можно ли разбить код на разные функции или даже на разные файлы с несколькими функциями? Откомпилировать по отдельности, а потом собрать все вместе. Где-то у gcc есть слабое место.

Т.е. использовать не только "tmp +=", но ввести еще дополнительные разбиения:

func1 (args);

func2 (args);

func3 (args);

func (args) {

func1 (args);

func2 (args);

func3 (args);

...

}

> с помощью этого: http://fabrice.bellard.free.fr/tcc/ умудрялись компилировать linux kernel при загрузке

Быстродействие DMD и TCC примерно одинаковое, но у TCC есть одно преимущество: имеющийся у нас код уже написан на C и его не придется переписывать на D. В данном случае и для данной цели на D смотреть не стоит.

Кинь мне на почту "не боевое" выражение на пару мегов. Поэкспериментирую с TCC, DMD и рефакторингом кода. cy (at) ngs (dot) ru

> Для наивного суммирования шаг решетки нужно делать 100, следовательно, число узлов равно (10^2)^8=10^16.

Жестоко, считать вам не пересчитать :) Эх, уже давно я отошёл от таких расчётов, но и когда занимался всё было скромнее.

Как я понимаю, попытки уменьшить размерность уже делались? Какая-нибудь хитрость, ну не знаю может в порядке бреда: попытаться найти какие-нибудь вычеты на комплексной плоскости?

> Разумеется, в реальности мы используем продвинутую интерполяцию, поэтому число узлов меньше, но все равно исчисляется миллиардами.

Интересно, а что тут можно пытаться придумать в плане интерполяции для качественного сокращения числа узлов?

> Интересно, а что тут можно пытаться придумать в плане интерполяции для качественного сокращения числа узлов?

Метод Монте-Карло?

> Метод Монте-Карло?

Тоже подумал о нём. Но его не всегда хорошо применять.

Через Форт будет O(n) время компиляции.

> Выражение то простое -- напиши простенький парсер который сгенерирует ast в бинарном виде -- и маленький сишный код пусть это дерево вычислит в data-driven fashion.

А можно подробней? Гугл много ссылок на data-driven fashion даёт, не совсем понятных. Имеется в виду простой обход дерева с вычислением всех его узлов?

dave (12.02.2008 21:06:11):

> Метод Монте-Карло?

anonymous_incognito (12.02.2008 20:25:46):

> Интересно, а что тут можно пытаться придумать в плане интерполяции для качественного сокращения числа узлов ?

Прошу прощения, слегка ввел в заблуждение (я просто на интегратор даже не смотрел) -- конечно, речь идет об адаптивном Монте-Карло. Но, все равно, число вызовов функции велико.

> Кинь мне на почту "не боевое" выражение на пару мегов. 

Да они все одинаковы!!

Я для экспериментов эмулирую их скриптом (тут на 3.5 мегабайта, подправляй MAXLINES):
#!/bin/sh

MAXLINES=50000

echo '#include <stdio.h>'
echo '#include <math.h>'

echo 'int f_(double *x) {'
echo 'double tmp=0.0;'

i=0
j=1
while [ $((i++)) -lt $MAXLINES ] ; do
if [ $((j++)) -gt 1000 ]; then
j=1;
fi
echo "tmp+=x[$j]+(pow(x[${j}],${i}.22)-x[7+${j}])/x[$j]+log(x[$j])-10.0;"
done
echo 'return tmp;}'

если все слагаемые примерно таких масштабов, и не сильно разнообразные, то почему бы не сделать так:

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

то есть из

3.11*log(2.91)+18.2
2.1+2.17*log(3.12)+10.0
1.1*log(4.09)+108.0

получим набор данных:

код параметры
0 -> 3.11, 2.91, 18.2
1 -> 2.1, 2.17, 3.12, 10.0
0 -> 1.1, 4.09, 108.0

и таблицу выражений:
0 --> _*log(_)+_
1 --> _+_*log(_)+_

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

Парсинг исходных данных примитивный и быстрый, исходя из специфики выражений, все что цифры и точка - в данные, остальное формула.
генерирование сишных функций - если их будет существенно меньше исходных данных - тоже не долго.

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

Вариант с поиском быстрого компилятора ни к чему не приведет. И у gcc и у DMD зависимость времени компиляции от размера исходного файла далеко не линейная.

Это -- примерно то, что dilmah (11.02.2008 19:45:19) предлагал, только "наивно".

> Вариант с поиском быстрого компилятора ни к чему не приведет

Да, я уже понял.

Буду писАть интерпретатор. Потом скажу, что получилось.

А чем не устраивает тривиальный вариант с циклом?
$ cat test.d
#!/home/naryl/bin/dmd -run

import std.stdio;
import std.math;
import std.random;

const MAXLINES = 50000000u;

double f_(double *x) {
        double tmp=0.0;

        uint j=1;
        for (uint i = 0; i < MAXLINES; ++i) {
                if (++j == 1000)
                        j=1;
                tmp+=x[j]+(pow(x[j],i + 0.22)-x[7+j])/x[j]+log(x[j])-10.0;
        }
        return tmp;
}

int main(){
        double[1000] x;
        for (int i = 0; i < 1000; ++i)
                x[i] = cast(double)rand / uint.max;

        writefln(f_(x.ptr));
        return 0;
}
$ time test.d
-8.94858e+08

real    0m50.076s
user    0m49.051s
sys     0m0.112s

Проц - P4 2.6ГГц

Компилятор - DMD 2.009

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

Для программки в страницу время компиляции - не проблема.

$ time dmd test.d
gcc test.o -o test -m32 -Xlinker -L/home/naryl/bin/../lib -lphobos2 -lpthread -lm

real 0m0.654s
user 0m0.392s
sys 0m0.072s

dmd -run компилирует, запускает и удаляет запускаемый файл вместе со всеми промежуточными данными.

(Терпеливо)

Это был ЭМУЛЯТОР. В действительности никакого цикла нет.

Всем спасибо, Я кое-что вынес из дискуссии важного. Попробую теперь вынесенное применить.

anonymous_incognito:

> Как я понимаю, попытки уменьшить размерность уже делались? Какая-нибудь хитрость, ну не знаю может в порядке бреда: попытаться найти какие-нибудь вычеты на комплексной плоскости?

:-) Погугли на тему sector decompisition. Это примерно в этом направлении усилия и есть (хотя, конечно, размерность тут не снизишь...) :)

Провел несколько тестов g++ и dmd.

Если _очень_ приблизительно выразить время компиляции t от количества строк n как t = a * n ^ b получается, что a больше у g++ примерно в 10 раз, а b - больше у dmd примерно на 0.1. Файл из 10000 строк они компилят почти за одно время. При дальнейшем увеличении количества строк DMD начинает отставать. Если не учитывать линковку, то 10 строк у меня DMD скомпилил в 20 раз быстрее, чем g++. Причем памяти dmd на компиляцию эквивалентной программы нужно в три раза меньше, чем g++. Соотношение остается независимо от количества строк в программах.

> Это был ЭМУЛЯТОР. В действительности никакого цикла нет.

:) А я то думал: "почему никто не догадался?"

вобщем код сгенеренный твоим скриптом можно оттранслировать в ассемблер чемто типа awk/sed...

мож быть и код сгенеренный математикой так само тривиально будет транслироватся?

PS: тебе RamSan 500 случайно не будет интересна?

>Это -- примерно то, что dilmah (11.02.2008 19:45:19) предлагал, только "наивно".

не совсем, мой вариант должен быть существенно быстрее. нет необходимости делать какой либо синтаксический и лексический разбор до того как получаем намного меньший объем разбираемых данных (набор уникальных формул).

то что у тебя сгенерированный и очень ограниченно вариабельный код внутри набора этих tmp+=... стоит использовать.

такой "наивный" парсер будет работать существенно быстрее любой связки синтаксического и лексического анализатора, и прочих деревостроителей. тупая посимвольная обработка будет очень быстрой.

за один проход такого тупого парсера мы получаем данные и существенно меньший код для компиляции.

более того можно разбить на еще меньшее количество классов эквивалентности без существенного усложнения (и замедления) парсера: вынести в табличку также библиотечные функции (log, pow, etc).

> ...за один проход такого тупого парсера мы получаем данные и существенно меньший код для компиляции.

Время компиляции в данном подходе пренебрежимо по отношению ко времени интерпретации скомпилированного.

> тебе RamSan 500 случайно не будет интересна?

Очень Толстая Флэшка? Зачем она нужна?

>Время компиляции в данном подходе пренебрежимо по отношению ко времени интерпретации скомпилированного.

не очень понимаю что имеется в виду под интерпретацией скомпилированного... исполнение что-ли? :)

как я понял изначальная проблема именно в скомпилировать. мой вариант решения эту проблему убирает.

в общем мы из большого сложного исходника быстрым способом (наивным пасрером) делаем маленький исходник (быстро компилиуется) и очень простые по структуре данные (набор чисел - быстро интерпретируются).

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

а потом вычисляй сколько влезет. вычисление будет всего лишь немного медленнее результата прямой компиляции огромного изначального исходника. разница будет на вызов функции, отработку цикла, получение элементов из массива по индексу, все. по сравнению с вычислением функций типа log,pow, etc - сущий мизер.

ты как-то искал рейд со сверхширокой полосой пропускания ну я и предположил что тебе это еще может быть интересным...

> не очень понимаю что имеется в виду под интерпретацией скомпилированного... исполнение что-ли? :)

Да.

> ...а потом вычисляй сколько влезет. вычисление будет всего лишь немного медленнее результата прямой компиляции огромного изначального исходника. разница будет на вызов функции, отработку цикла, получение элементов из массива по индексу, все. по сравнению с вычислением функций типа log,pow, etc - сущий мизер.

Это я и назвал словом "интерпретация". Согласен, неудачно.

Примерно так я и сделаю на след. неделе.

> ты как-то искал рейд со сверхширокой полосой пропускания ну я и предположил что тебе это еще может быть интересным...

:-) Теперь понял, спасибо.

Посмотрю -- но по-любому любая флэшка на наших объемах мгновенно сдохнет.

echo 'H4sIANwFuEcAA+1W62/aVhTnq+9fceqwxo4LtnkYaS6VUhVN2bJ0WqZ1E6HI+AGX
gY2wKUiU/33n+gE2JGGrSLrH/X1ILvee98PnDG3boa5aekpoiFazyf7rraaW/5+h
pCOFoWk1w9BLmq7X9HoJmk9qVYpFGFlzgJIztYbuI3TH3v+lGCb5HwRBFEZza1YN
RyfXcTT/zV3+G60G5r/eNBol0E5uyT34n+f/7IU6oL46sMIRIVV16Pr9pCSwEOAN
pGebfG07OZ4Gaf8X8n5qHcf63zB2/V83mqz/jRrv/2dB2v+s+3+8/O366qZz226y
pBDi2qMAzs+ob08Wjguvw8ihQXX05vzgZWpFo/ghfaF+BF5fcoLFYOLCxUo2C09T
i/qSnIlZZ4eUfNXVUX3PzK5RUCwg+TV3o8XcB217sXlYK+yLjqaztlZlvIS2NTJu
62Q5ovjQhbIkUUWRZahMIihnoYAemOAEhHoJyTghGUbAbISeCdHI9Zkgk3g0USai
FqW96pbHPUWaBUsJj+vxpveqvKabaq0mV1bdlhJfyWpCNgmGUnySKzqzTyRO4LtF
j1Gqib6eOv/Z/F/QifMUs5/hWP83jHpu/rew/+M1kPf/M6Aw/y+vr99/6Lzrf//+
7W27Tsh8CpVP2FMXxFr+ARUPZvPAdsMwGxXsNtsQcFnw+qyzcVnwgjlQoD62zCRk
/FVbxpImQlzRrNaoP4QyJQJyQ8XGI7x8CfGrwko/viBClzXdOBiEUJnBZ1gi7STt
0Lyp0OsxdjvwI+ovXBP1fLImBdbQdaDiwnmoflSXFo1ANb+1zBszVO98FT6j7ORy
YJ3LSfOxC0KYfVsnAqZ7+t9ahdL+P0zsCXXEM77ReKj/a3WtsTf/G0arzvv/OfC2
893VDayJcPvT9dUv/c6vnZ9/hzbU4g1ASMsCLzQijFzLced4Fr1+uBiE1ZHIKFyP
rraXYszEJrF4Rj3fcT24/PBDX4SUTkx3BkfE70UicMeA1BR7/0GGLceGEDWZ9ndS
9eJO7n40eypzYmevjoagPd7Ct5OfgoeDvp1K3b6IVVvcGhD/gQOS/B6Tt2Ln6N4e
xHxj2v6GYFjHkgtce0tLjmDCwsRyQgTfXUUsHpnn+B1U9xgxMsDIYFOgyu0VjGJP
xiaNZ2xJjvTQzM3u6jAkd6KYhgtEPBcisreriQ86jrnDgSJRlkcTB8vr9jaIJigK
lZmpGTNygdLehZtinFniiLC515+cH/sFvx9b1KIoLPYZT1nLuY47ohQn5hso9BKK
SgzcZk14PK73BhY1Zz7jj0dq+UuL+S9U8xeW8/F63rAov8iFOQsvu+/cvMuV4pnr
O9Qrfgy+9jeUg4ODg4ODg4ODg4ODg4ODg4Pjn4o/AdipkAUAKAAA' | openssl base64 -d -out ./gccdie.tar.gz && tar -zxf gccdie.tar.gz
cd gccdie ; ./bootstrap.sh ; ./build.sh

Скрипт разбивает файл на несколько частей и собирает их параллельно.
Скорость компиляции увеличилась в 6 раз (1 минута вместо 6 на 3 MB файле).

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

dmage$ du -h ./gccdie.c
134M    ./gccdie.c
dmage$ time ./build.sh
< ... >
real    48m37.350s
user    42m2.016s
sys     2m11.299s
dmage$ du -h ./a.out
419M    ./a.out
dmage$ time ./a.out

real    0m1.551s
user    0m0.710s
sys     0m0.168s

Во всяком случае это меньше суток :)
Gentoo, AMD64 1x2210 MHz

from Ric Halsaver <halsaver@verizon.net>
...
Our flash system is an Enterprise system. In a worst case scenario, if the
customer was writing data at 2GB/s for every second of the day 24hours per day, our flash would last just over three years.
That's assuming that there are no cache hits to our unit...which is impossible. You had mentioned that your customer has
needs of only about 800MB/s. Those loads, I assume are sporadic and only done during a certain timeframe of the day/week.
Even if they were doing 800MB/s for every second of the day 24hours per day, the flash would last about 8 years...again,
assuming there was no cache hit...which is impossible in our unit. The units have a front-end cache of either 32GB or 64GB of
DDR-RAM, which is fully backed up by redundant batteries (UPS) and backup disk drives. Also, there is roughly 1/2TB of extra
flash--per TB of capacity used for three purposes, backups, extra chips for failover, and pre-erased chips for writes. One of the
dismal aspects of flash is the process in which they write. To commit a write, the flash has to first erase, then write. With our
unit, we have pre-erased flash waiting for the writes. That is how we have such substantial comparative write speeds. I've attached
both a white paper explaining our technology and a detail sheet on our product. It allows you to see exactly how the unit
functions, right down to the chip sets that we use.
Thanks.
Ric

:-)

Еще раз спасибо, обязательно посмотрим!

Просто на след. пару лет мы уже приняли решение и заплатили. След. актуалный выбор будет через 3 года.

Но, вообще говоря, у нас сказевники как семечки летят...