Кому интересно, чем дело кончилось -- 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 подход проблему решит. Надо, конечно, нечто поумнее стековой машины, но путь, в общем-то, ясен.