LINUX.ORG.RU
Форум — Development  

Было: «c: скорость компиляции»


0

0

Кому интересно, чем дело кончилось -- http://www.linux.org.ru/view-message.jsp?msgid=2492593

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

На коротких выражениях оно сливает тому же, скомпилированному gcc без оптимизации, в несколько раз, с оптимизацией -- в 30-40 раз. На "средних" выражениях, когда gcc еще справляется, но только без оптимизации, они примерно равны. "Длинные" выражения (многомегабайтные) тоже считаются с приемлемой скоростью.

Например, выражение порядка 300 килобайт gcc транслирует (без оптимизации) за 10 секунд (с оптимизацией за 2 часа не справился, я его вырубил), и считает 10 000 раз за 27 секунд. Мой трансляор его транслирует в пределах погрешности (0.000000 секунд) и машина вычисляет его (те же 10000 раз) за 33 секунды.

С простейшим "боевым" выражением (с трансляцией которого gcc не справился за неделю раборы на 1.3 мегагерцовом Итанике) мой транслятор поладил за полсекунды, и вычислялка справилась 10 000 раз за 140 секунд.

Думаю, data-driven подход проблему решит. Надо, конечно, нечто поумнее стековой машины, но путь, в общем-то, ясен.

★★★★★

Ответ на: комментарий от cvv

> освети свой транслятор хоть чуть-чуть?

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

Никаких особых трюков, разве что небольшие целочисленные степени заменяю на умножения.

Про польскую запись см. например в Википедии http://ru.wikipedia.org/wiki/обратная_польская_запись

Die-Hard ★★★★★
() автор топика
Ответ на: комментарий от Die-Hard 

по ссылке приведен пример Глагола... ээээх, нравится мне этот язык :))) просто улыбает! :)

ЗАДАЧА Перевести(вход-, выход+: РЯД ИЗ ЗНАК);
 ПЕР
   сч1, сч2: УЗКЦЕЛ;
   зн: ЗНАК;
 УКАЗ
   зн := 0X; сч2 := 0;
   ОТ сч1 := 0 ДО ДЛИНА(вход)-1 ВЫП
     ЕСЛИ вход[сч1] = ")" ТО
       ПОКА Стек[ДЛИНА(Стек)-1] # "(" ВЫП
         выход[сч2] := Удалить();
         УВЕЛИЧИТЬ(сч2)
       КОН;
       зн := Удалить()
     АЕСЛИ вход[сч1] = "(" ТО
       Добавить(вход[сч1])
     АЕСЛИ (вход[сч1] = "+") ИЛИ (вход[сч1] = "-") ИЛИ (вход[сч1] = "/") ИЛИ (вход[сч1] = "*") ТО
       ЕСЛИ ДЛИНА(Стек) = 0 ТО Добавить(вход[сч1]) ИНАЧЕ
         ЕСЛИ Преимущество(вход[сч1]) > Преимущество(Стек[ДЛИНА(Стек)-1]) ТО
           Добавить(вход[сч1])
         ИНАЧЕ
           ПОКА (ДЛИНА(Стек) # 0) И (Преимущество(вход[сч1]) <= Преимущество(Стек[ДЛИНА(Стек)-1])) ВЫП
             выход[сч2] := Удалить(); УВЕЛИЧИТЬ(сч2)
           КОН;
           Добавить(вход[сч1])
         КОН
       КОН
     АЕСЛИ Знак.Буква(вход[сч1]) ТО
       выход[сч2] := вход[сч1];
       УВЕЛИЧИТЬ(сч2)
     КОН
   КОН;
   ПОКА ДЛИНА(Стек) # 0 ВЫП
     выход[сч2] := Удалить();
     УВЕЛИЧИТЬ(сч2)
   КОН
 КОН Перевести;

Deleted
()

интересно как вы контролируете машинную погрешность при вычислении таких гигантских выражений

anonymous
()
Ответ на: комментарий от anonymous

> как вы контролируете машинную погрешность при вычислении таких гигантских выражений

Никак! Надеемся, что они друг друга скомпенсируют.

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

Die-Hard ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development