проФорт

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

1. Как вообще можно оптимизировать форт (или стековые языки вообще)? Какие подходы используются для этого? Каковы характерные особенности форт-программ с точки зрения оптимизации?
   
2. Какие методы оптимизации используют существующие форт-системы? Каким образом они оцениваются (т.е.: "где бенчмарк?")?
   
3. Как работает оптимизатор 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 -- быстрая коммерческая форт-система (к сожалению получить её копию можно только по почте).