Оптимизатор SPF
By Azamadt Smaguloff. Sunday, 13. April 2008, 09:00:26
Поставим вопросы касающиеся оптимизации форта в список, от вопросов общего характера до более конкретных:
- Как вообще можно оптимизировать форт (или стековые языки вообще)? Какие подходы используются для этого? Каковы характерные особенности форт-программ с точки зрения оптимизации?
- Какие методы оптимизации используют существующие форт-системы? Каким образом они оцениваются (т.е.: "где бенчмарк?")?
- Как работает оптимизатор 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
:NONAME DUP 10 > IF 1 . THEN ; REST
Вывод:cmp eax, # A
jle @@1
...
@@1:
Похожим образом обрабатываются другие типичные комбинации 2DUP = IF ... THEN и им подобные:lib/ext/disasm.f
:NONAME 2DUP = IF 1 . THEN ; REST
Вывод:cmp eax, 0 [ebp]
jne @@1
...
@@1:
Оптимизируются последовательности логических операций (0= здесь аналогичен отрицанию, поэтому последовательность 0< 0= означает "больше или равно нулю" ):lib/ext/disasm.f
:NONAME DUP 0< 0= IF 1 . THEN ; REST
Вывод:or eax, eax
jl @@1
...
@@1:
- Компиляция слов порождаемых словами CREATE, VARIABLE, VALUE, USER. При компиляции переменных или констант, вместо записи простого вызова DOES-действия порождённого слова, запускается процедура специальной обработки которая разворачивает вызов в аналогичную последовательность машинного кода. Например:
lib/ext/disasm.f
10 CONSTANT c
:NONAME c ; REST
10 VALUE vl
:NONAME vl ; REST
VARIABLE vr
:NONAME vr @ ; REST
Вывод:mov -4 [ebp] , eax
mov eax , # A
lea ebp , -4 [ebp}
ret
mov -4 [ebp] , eax
mov eax , 572410 ( vl+5 )
lea ebp , -4 [ebp]
ret
mov -4 [ebp] , eax
mov eax , 57243C ( vr+5 )
lea ebp , -4 [ebp]
ret
Связанные ссылки:
- Статистика форт-слов собранная по большой базе рабочих исходников -- forth.org.ru/~day/stat.html.
- Тест-производительности форт-систем (целочисленные операции, пересылка памяти, сортировки и т.д.): www.mpeforth.com/arena/benchmrk.fth
- Заметка на Forth.Wiki автора оптимизатора SPF: Оптимизирующий компилятор.
-
MPE VFX Forth -- быстрая коммерческая форт-система.
-
SwiftForth -- быстрая коммерческая форт-система.
-
iForth -- быстрая коммерческая форт-система (к сожалению получить её копию можно только по почте).








Anonymous # 21. April 2008, 03:19
В ссылках можно указать ссылку
сравнения с Си ( правда тесты давнишние 2002г. )
http://www.forth.org.ru/~af/shootout.htm
profiT # 21. April 2008, 13:30
(вообще-то эта ссылка была в каком-то из черновиков)
Anonymous # 24. April 2008, 03:21
Мне интересно как быть с ситуацией применения Форта для МК где оптимизация не "проклятый вопрос"?
Производил, например, тесты в таком варианте Си -> Spf4
Макрооптимизатор Spf4 кода, в этом варианте, мало эффективен.
Anonymous # 31. July 2008, 23:32
забавно, я когда-то делал алгоритмы, которые "развернут" стековый код в нечто более обычное, с локальными переменными и ты пы, где уже можно делать data flow и ты пы. правда, для этого нужна VM, а не машинный код. зато в итоге можно применять любимые алгоритмы.
profiT # 1. August 2008, 12:26
Ех.
exs # 2. August 2008, 18:31
profiT # 2. August 2008, 18:47