фортеры - Оптимизатор SPF

Оптимизатор SPF

By Azamadt SmaguloffprofiT. Sunday, April 13, 2008 9:00:26 AM

Вопросы об оптимизаторе в SPF в частности, и об оптимизации Форта как языка вообще всегда вызывают живой интерес. Это один из тех "проклятых вопросов" которыми так любят заниматься и которые наиболее далеки от написания чего-то практически полезного "сегодня и сейчас" а не "завтра и никогда" (видимо, одно закономерно следует из другого).

Поставим вопросы касающиеся оптимизации форта в список, от вопросов общего характера до более конкретных:

Как вообще можно оптимизировать форт (или стековые языки вообще)? Какие подходы используются для этого? Каковы характерные особенности форт-программ с точки зрения оптимизации?
Какие методы оптимизации используют существующие форт-системы? Каким образом они оцениваются (т.е.: "где бенчмарк?")?
Как работает оптимизатор SPF?

Форту изначально была присуща рефлексивность (теоретически доступная в run-time) в виде шитого кода -- линейной последовательности ссылок в том или ином виде на низкоуровневые процедуры. Классическое исполнение форт-программы представляет собой проход по шитому коду простой виртуальной машиной (слово NEXT , "адресный интерпретатор"). Однако большинство сегодняшних быстрых форт-систем используют непосредственную компиляцию в машинный код, отказываясь от схемы с компиляцией шитого кода (то есть -- обходясь без посредника-промежуточного представления). В SPF (а также в других форт-системах использующих похожую схему) слова компиляции подобные POSTPONE и LITERAL вместо откладывания ссылки в шитый код или записи команды VFM (виртуальной форт-машины), напрямую компилируют машинные операции. Так как компиляция строго однопроходна то и возможности оптимизации ограничены последними n командами. Отсутствие промежуточного представления дополнительно сужает пространство для манёвра оптимизатору. Бытует мнение что главным препятствием по оптимизации программ на форте являются стековые перестановки (SWAP, DUP, DROP и т.д.) цель которых только в том чтобы расставить операнды на стеке в нужном порядке и которые не имеют полезного выхода. Оставим в стороне спорный анти-тезис о том что доля стековых операций в общем тексте и влиянии на окончательное время исполнения программы незначительна (что впрочем имеет под собой основания, см. статистику использования форт слов и обратите внимание на слабую представленность стековых слов вверху списка). Так или иначе, но одна из целей оптимизаторов быстрых форт-систем -- нивелировать влияние таких "бесполезных" операций на конечный код (машинный или шитый), по мере возможности и оправданности. Из-за ограниченности возможностей оптимизации строители форт-систем начали полагаться на оптимизацию на уровне архитектуры в виде выбора наиболее эффективной раскладки стековых элементов на регистры. Постепенно утвердились системы использующие один регистр как вершину стека данных со всевозможными вариациями как выбора конкретного регистра для TOS (EBX -- у SwiftForth, аккумулятор -- у SPF и VFX), так и использования аппаратного или "эмулируемого" стека. Особняком здесь стоит схема, применённая в JIT Tamarin (движок JS для продуктов на основе Gecko, форт-представление там используется как звено в цепочке преобразований). Это гораздо ближе к традиционной схеме взращённой на классической CS -- последовательность промежуточных представлений со структурными оптимизациями продуктов каждой из стадий. Код ActionScript/EcmaScript/Javascript "падает" на своё представление в форт-команды, которые распадаются в "тройки" со временными переменными одинарного присваивания, которые в свою очередь "падают" на конечный оптимизированный маш. код целевой платформы. У форта также есть обособленность чисел с плавающей точкой -- у них отдельный стек и свой набор слов и они оптимизируются (если оптимизируются) отдельно. Такие оптимизаторы есть у VFX и iForth. Наиболее обширный тест производительности охватывающий самые используемые форт-системы (включая SPF) -- бенчмарк от VFX. Оптимизатор SPF. Я не буду сильно углубляться в дебри и только в общих чертах обрисую его основные возможности:

Оптимизация основанная на шаблонах машинного кода ("если последние столько-то байт скомпилированного кода выглядят так-то и так-то -- делать то-то и то-то"). Именно эти шаблоны и реакции на них составляют подавляющую часть 100 с лишним килобайт оптимизатора (файл src/macroopt.f ). Пример типичного подобного правила см. у автора: Forth.Wiki: Оптимизирующий компилятор.

Оптимизация условных переходов, например типичная комбинация 10 > IF ... THEN падает не в последовательность действий: укладка на стек литерала 10, сравнение двух вехних значений и запись результата на стек и затем проверки флага с условным переходом а в две машинные команды:

lib/ext/disasm.f<br />
<span style='color:#000084; font-weight:bold; '>:NONAME </span><span style='color:#000084; font-weight:bold; '>DUP </span><span style='color:#008c00; '>10 </span><span style='color:#000084; font-weight:bold; '>> </span><span style='color:#800000; '>IF </span><span style='color:#008c00; '>1 </span><span style='color:#000084; font-weight:bold; '>. </span><span style='color:#800000; '>THEN</span><span style='color:#000084; font-weight:bold; '> ;</span> REST

Вывод:

<span style='color:#000084; font-weight:bold; '>cmp</span> eax, # A<br />
<span style='color:#000084; font-weight:bold; '>jle </span><span style='color:#800000; '>@@1</span><br />
...<br />
<span style='color:#800000; '>@@1:</span><br />

Похожим образом обрабатываются другие типичные комбинации 2DUP = IF ... THEN и им подобные:

lib/ext/disasm.f<br />
<span style='color:#000084; font-weight:bold; '>:NONAME </span><span style='color:#000084; font-weight:bold; '>2DUP </span><span style='color:#000084; font-weight:bold; '>= </span><span style='color:#800000; '>IF </span><span style='color:#008c00; '>1 </span><span style='color:#000084; font-weight:bold; '>. </span><span style='color:#800000; '>THEN</span><span style='color:#000084; font-weight:bold; '> ;</span> REST<br />

Вывод:

<span style='color:#000084; font-weight:bold; '>cmp</span> eax, <span style='color:#008c00; '>0</span> [ebp]
<span style='color:#000084; font-weight:bold; '>jne </span><span style='color:#800000; '>@@1</span><br />
...<br />
<span style='color:#800000; '>@@1:</span>

Оптимизируются последовательности логических операций (0= здесь аналогичен отрицанию, поэтому последовательность 0< 0= означает "больше или равно нулю" ):

lib/ext/disasm.f<br />
<span style='color:#000084; font-weight:bold; '>:NONAME </span><span style='color:#000084; font-weight:bold; '>DUP</span> 0&lt; <span style='color:#000084; font-weight:bold; '>0= </span><span style='color:#800000; '>IF </span><span style='color:#008c00; '>1 </span><span style='color:#000084; font-weight:bold; '>. </span><span style='color:#800000; '>THEN</span><span style='color:#000084; font-weight:bold; '> ;</span> REST

Вывод:

<span style='color:#000084; font-weight:bold; '>or</span> eax, eax<br />
<span style='color:#000084; font-weight:bold; '>jl </span><span style='color:#800000; '>@@1</span><br />
...<br />
<span style='color:#800000; '>@@1:</span>

Компиляция слов порождаемых словами CREATE, VARIABLE, VALUE, USER. При компиляции переменных или констант, вместо записи простого вызова DOES-действия порождённого слова, запускается процедура специальной обработки которая разворачивает вызов в аналогичную последовательность машинного кода. Например:

lib/ext/disasm.f<br />
<span style='color:#008c00; '>10 </span><span style='color:#000084; font-weight:bold; '>CONSTANT </span><span style='color:#000084; font-weight:bold; '>c</span><br />
<span style='color:#000084; font-weight:bold; '>:NONAME</span> c<span style='color:#000084; font-weight:bold; '> ;</span> REST<br />
<br />
<span style='color:#008c00; '>10 </span><span style='color:#000084; font-weight:bold; '>VALUE </span><span style='color:#000084; font-weight:bold; '>vl</span><br />
<span style='color:#000084; font-weight:bold; '>:NONAME</span> vl<span style='color:#000084; font-weight:bold; '> ;</span> REST<br />
<br />
<span style='color:#000084; font-weight:bold; '>VARIABLE </span><span style='color:#000084; font-weight:bold; '>vr</span><br />
<span style='color:#000084; font-weight:bold; '>:NONAME</span> vr <span style='color:#000084; font-weight:bold; '>@</span><span style='color:#000084; font-weight:bold; '> ;</span> REST

Вывод:

<span style='color:#000084; font-weight:bold; '>mov</span>     <span style='color:#008c00; '>-4</span> [ebp] , eax<br />
<span style='color:#000084; font-weight:bold; '>mov</span>     eax , # A<br />
<span style='color:#000084; font-weight:bold; '>lea</span>     ebp , <span style='color:#008c00; '>-4</span> [ebp}<br />
<span style='color:#000084; font-weight:bold; '>ret</span><br />
<br />
<span style='color:#000084; font-weight:bold; '>mov</span>     <span style='color:#008c00; '>-4</span> [ebp] , eax<br />
<span style='color:#000084; font-weight:bold; '>mov</span>     eax , <span style='color:#008c00; '>572410</span>  ( vl+<span style='color:#008c00; '>5</span>  )<br />
<span style='color:#000084; font-weight:bold; '>lea</span>     ebp , <span style='color:#008c00; '>-4</span> [ebp]<br />
<span style='color:#000084; font-weight:bold; '>ret</span><br />
<br />
<span style='color:#000084; font-weight:bold; '>mov</span>     <span style='color:#008c00; '>-4</span> [ebp] , eax<br />
<span style='color:#000084; font-weight:bold; '>mov</span>     eax , 57243C  ( vr+<span style='color:#008c00; '>5</span>  )<br />
<span style='color:#000084; font-weight:bold; '>lea</span>     ebp , <span style='color:#008c00; '>-4</span> [ebp]<br />
<span style='color:#000084; font-weight:bold; '>ret</span>

Связанные ссылки:

Статистика форт-слов собранная по большой базе рабочих исходников -- forth.org.ru/~day/stat.html.
Тест-производительности форт-систем (целочисленные операции, пересылка памяти, сортировки и т.д.): www.mpeforth.com/arena/benchmrk.fth
Заметка на Forth.Wiki автора оптимизатора SPF: Оптимизирующий компилятор.
MPE VFX Forth -- быстрая коммерческая форт-система.
SwiftForth -- быстрая коммерческая форт-система.
iForth -- быстрая коммерческая форт-система (к сожалению получить её копию можно только по почте).

Прекомпилированные константыРегулярные выражения

Comments

Anonymous # Monday, April 21, 2008 3:19:05 AM

Anonymous writes: В ссылках можно указать ссылку сравнения с Си ( правда тесты давнишние 2002г. ) http://www.forth.org.ru/~af/shootout.htm

Azamadt SmaguloffprofiT # Monday, April 21, 2008 1:30:39 PM

Да, спасибо.

(вообще-то эта ссылка была в каком-то из черновиков)

Anonymous # Thursday, April 24, 2008 3:21:55 AM

Anonymous writes: Мне интересно как быть с ситуацией применения Форта для МК где оптимизация не "проклятый вопрос"? Производил, например, тесты в таком варианте Си -> Spf4 Макрооптимизатор Spf4 кода, в этом варианте, мало эффективен.

Anonymous # Thursday, July 31, 2008 11:32:49 PM

Anonymous writes: забавно, я когда-то делал алгоритмы, которые "развернут" стековый код в нечто более обычное, с локальными переменными и ты пы, где уже можно делать data flow и ты пы. правда, для этого нужна VM, а не машинный код. зато в итоге можно применять любимые алгоритмы.

Azamadt SmaguloffprofiT # Friday, August 1, 2008 12:26:49 PM

И я делал (-ю). Лежит где-то "эскизик" на 12 кб.

Ех.