6.3 Изучение частот появления слов языка FORTH



==130

Итак, выяснив разницу между стековыми машинами и компьютерами других архитектур, можно перейти к численным результатам, которые показывают, как стековые машины работают. Результаты измерений частот появления тех или иных инструкций и размеров кода для стековых и регистровых машин прилагается ( ссылки включают: Blake ( 1977 ), Cooke & Donde ( 1982 ), Cooke & Lee ( 1980 ), Cragon ( 1979 ), Haikala ( 1982 ), McDaniel ( 1982 ), Sweet & Sandman ( 1982 ), и Tanenbaum ( 1978 )). К сожалению, большая часть таких измерений проводилась для программ, написанных на обычных, а не стековых языках, подобных FORTH. Впервые статистика исполнения программ на FORTH была опубликована Hayes et al. ( 1987 ) и данная книга её слегка расширит.

Все сведения, приведённые в этой части, получены при тестировании программ на языке FORTH, так как только такие программы способны наилучшим образом выявить возможности стековых машин. Все предупреждения о тестировании по-прежнему актуальны и приведённые результаты должны использоваться только как некое приближение к «истине» ( что бы это слово ни обозначало ).



==131

Ниже даётся краткая аннотация шести тестов, которые использовались для получения количественных оценок. Все они, за исключением особо оговоренных случаев, писались для 16-разрядной FORTH-системы.

Frac : программа заполнения пространства фракталами, использующая генератор случайных чисел. Для единообразия условий рисования изображения программа запускается с одними и теми же начальными параметрами ( Koopman 1987e , Koopman 1987f ).

Life : простая реализация игры Джона Конвея «Жизнь» на экране размером 80x25 символов. За каждый запуск программа проигрывает десять поколений заполненного глайдерами экрана.

Math : библиотека 32-разрядных вычислений с плавающей запятой, целиком написанная на языке FORTH без использования машиннозависимой оптимизации. При каждом запуске программа вычисляет таблицу синусов, косинусов и тангенсов для десяти целочисленных значений угла в диапазоне от 1 до 10° ( Koopman 1985 ).

Compile : командный файл для компиляции нескольких программ на языке FORTH. Используется для измерения производительности самого компилятора.

Fib : вычисление 24-го числа Фибоначчи по рекурсивному алгоритму ( часто называемому «тупым» ).

Hanoi : задача о Ханойских башнях, написанная в виде рекурсивной процедуры. При каждом запуске программы вычисляет результат для 12 дисков.

Queens : задача о N ферзях ( ведущая своё происхождение от головоломки о 8 ферзях на шахматной доске ), написанная в виде рекурсивной процедуры. Программа находит первое удовлетворяющее условиям расположение N ферзей на доске размером NxN . При каждом вызове вычисляется положение при N равном 12 .

Три программы из перечисленных обеспечивают наилучшее сочетание различных аспектов программирования. Первая - «Math», которая интенсивно использует 16-разрядный стек при работе с 32-разрядными величинами ( и 48-разрядным промежуточным форматом с плавающей запятой ). Вторая - «Life», которая активно работает с массивами ячеек памяти и выполняет множество условных переходов. Третья - «Frac», которая рисует линию и элементарные графические проекции.

Замеры производительности при компиляции полезны тем, что отражают активность при разборе входного потока символов и поиска идентификаторов.

6.3.1 «Динамическая» частота появления инструкций

Табл. 6.1 показывает «динамическую» частоту появления для самых интенсивно исполняемых примитивов языка для программ «Frac», «Life», «Math» и «Compile». Динамической частотой инструкции называется число исполнений этой инструкции в ходе работы программы [* то есть частоту появления их в потоке команд при исполнении программы; есть ещё «статическая» - частота появления команды в исходном тексте ] . Полную версию таблицы можно посмотреть в Приложении _C  , табл. C.1 . Колонка «AVE» показывает средневзвешенное значение примитива для всех четырёх программ и является хорошим приближением к частоте появления в большинстве программ на языке FORTH. В таблицу включены слова, входящие в десятку наиболее употребительных из колонки «AVE» или в первый десяток для конкретной программы. Например, «EXECUTE» имеет средний ( «AVE» ) показатель всего 0.65%, но 2.45% для программы «Compile» и входит в десяток самых употребительных для неё.



==132

Первый и очевидный вывод: среди операций доминируют вызовы подпрограмм и выходы из них. Этот широко известный факт объясняет всё то внимание, которое FORTH-ориентированные стековые процессоры уделяют совмещению вызовов и выходов из подпрограмм с другими операциями. Число команд выхода «EXIT» несколько меньше, чем число вызовов «CALL», так как некоторые слова FORTH удаляют элементы из стека возврата, объединяя два уровня вызова подпрограмм. Это приводит к условному досрочному выходу из вызывающей подпрограммы.

Интерес представляет и время, затрачиваемое словами, которые тасуют элементы в стеке. Суммарная цифра по всем таким командам составляет около 25%. На первый взгляд довольно много. С другой стороны, все стековые процессоры могут совмещать реорганизацию содержимого стека с другой полезной работой ( подобной комбинации «OVER -» ), а значит, полученная цифра гораздо больше, чем встречающиеся на практике значения. Кроме того, в полученных 25% пятую часть занимает очень активное использование слов «>R» и «R>» в библиотеке математики с плавающей запятой при работе с 32-битными величинами. Эти издержки отсутствуют в 32-разрядных процессорах или в 16-разрядных машинах, имеющих память с быстрым доступом для хранения промежуточных результатов ( таких как NC4016 и RTX 2000 ).



==133

Любопытна и очень важная задача размещения для последующего использования данных в стеке ( в число примитивов входят «VARIABLE», «@», «LIT», «CONSTANT» и «USER» ). К счастью, в стековых машинах и эти действия можно совмещать с другими операциями.

И, наконец, заглянув в Приложение _C  , можно обнаружить, что множество инструкций имеют динамическую частоту появления менее 1%. Тем не менее, немедленно исключать их как ненужные не стоит, потому что при отсутствии аппаратной поддержки исполнение многих из них потребует много времени. Для выяснения степени важности инструкции одной частоты появления недостаточно.

6.3.2 «Статическая» частота появления инструкций



==134

В табл. 6.2 приведены «статические» частоты появления инструкций , встречающихся при компиляции программ «Frac», «Life» и «Math» и при работе программы «Compile» ( через неё прогонялись «Frac», «Queens», «Hanoi» и «Fib» ). Статической частотой инструкции называется число появлений этой инструкции в исходном тексте программы. Колонка «AVE» показывает средневзвешенное значение для четырёх остальных значений, являющихся хорошим приближением к частоте компиляции для большинства программ на языке FORTH. В таблицу включены слова, входящие в десятку наиболее употребительных для колонки «AVE» или в первый десяток для конкретной программы.

При статических измерениях очень частыми становятся вызовы подпрограмм - каждая четвёртая компилируемая инструкция. Отметим, что «Frac» посчитана дважды, так как включается ещё и в «Compile», и, на самом деле число вызовов чуть меньше.

6.3.3 Сжатие инструкций в RTX 32P

Если команды выхода из подпрограмм используются столь активно, то не стоит удивляться, что в большинстве стековых машин есть механизмы совмещения выхода из процедуры с другими операциями. Есть ещё одно важное дополнительное наблюдение - в исходных текстах вызовы подпрограмм встречаются чаще, чем выходы из них [* одна из причин отмечалась выше ] , и привлекательнее для комбинирования с другими операциями.

RTX 32P , обсуждавшийся в §5.3 , уникален тем, что только у него есть единый формат, совмещающий код операции и адрес перехода или вызова подпрограммы. На первый взгляд это кажется зряшной тратой памяти, но её цена относительно невелика, а возможный прирост производительности очень заметен. К сожалению, единый формат инструкций подходит только для 32-разрядных процессоров, так как 16 бит недостаточно для хранения кода операции и большого поля адреса.

В таблицах ниже показаны результаты вычислительной и компиляционной статистики, набранной на переписанных с учётом преимуществ RTX 32P версиях «Frac», «Life» и «Math».

6.3.3.1 Увеличение скорости исполнения

В табл. 6.3a , 6.3b , 6.3c и 6.3d представлены результаты измерения частоты выполнения различных инструкций на RTX 32P для программы, собранной с четырьмя различными уровнями оптимизации. Часть (a) таблицы показывает результаты исполнения без сжатия инструкций и подпрограмм и без локальной оптимизации кода ( комбинирования соседних инструкций ).

Часть (b) показывает эффект от упаковки часто встречающихся кодовых последовательностей ( подобных «SWAP DROP», «OVER +», «Variable @» и «Variable @ +» ) в одну инструкцию. Ряд, помеченный «OP-OP», показывает число парных сочетаний, которые рассматриваются как один опкод в графах «OP», «OP-CALL», «OP-EXIT» и «OP-CALL-EXIT». Все специальные случаи появления пар «LITERAL +» , «LITERAL AND» и т.д. упомянуты в виде «LITERAL-OP». «VARIABLE-OP» включает комбинации «Variable @» и «Variable !», а «VARIABLE-OP-OP» объединяет «Variable @ +» и «Variable @ -». Все особые случаи констант и переменных требуют использования отдельной инструкции для хранения кода операции и адреса и не могут комбинироваться с другими директивами. Для тестовых программ сокращение числа исполняемых команд при локальной оптимизации может достигать 10%.



==135



==136

Часть (c) показывает результаты замены локальной оптимизации на сжатие инструкций. Это означает, что везде, где это возможно, операции комбинируются с последующими директивами вызова подпрограмм и выхода из них. Пара инструкций вызов-выход преобразуются в безусловный переход для исключения концевой рекурсии. В итоге комбинации операций и вызовов/выходов из подпрограмм составляют до 24% всех инструкций. Иначе говоря, «бесплатно» будут выполнены около 40% исходных вызовов процедур. Почти все выходы из них выполняются в дополнение к другим операциям. Исключение составляют лишь специальные инструкции, вроде работы с константами или указателем стека возврата, которые нельзя объединить с выходом из подпрограммы.



==137

Часть (d) показывает эффект от использования локальной оптимизации одновременно со сжатием инструкций. Число инструкций в получившемся коде уменьшается на четверть по сравнению с исходным. Такое увеличение производительности становится возможным без каких-либо аппаратных или программных затрат - только за счёт выполнения вызовов подпрограмм параллельно с другими операциями.

Результаты измерений показывают, что число инструкций для библиотеки «Math» уменьшилось с 6.1 миллиона для 16-разрядной системы до 940 тысяч для RTX 32P, указывая на необходимость 32-разрядного процессора для вычислений с плавающей запятой. Цифры для «Life» ( состоящей по большей части из работы с 8-разрядными данными ) почти одинаковы для обеих систем. Данные для «Frac» демонстрируют четырёхкратное увеличение числа инструкций, вызванное более высоким графическим разрешением 32-разрядной версии, которое требует вычисления в четыре раза большего числа точек и, соответственно, приблизительно в четыре раза большего числа инструкций.

6.3.3.2 Цена вопроса в терминах расхода памяти

Увеличение производительности от комбинирования операций с вызовами подпрограмм выгодно, так как фактически не использует дополнительные ресурсы внутри процессора. На самом деле из-за использования единственного формата инструкций конструкция процессора упрощается. Остаётся вопрос о влиянии таких технических решений на использование памяти.

К счастью, программы на языке FORTH имеют частоту статического появления вызовов подпрограмм [* присутствия в коде ]   даже большую, чем частота динамического появления [* исполнения ] . Это обеспечивает широкие возможности для их комбинирования с другими операциями. Табл. 6.4a и 6.4b показывает разницу статического объёма исходной программы по сравнению с объёмом после компрессии и локальной оптимизации.

RTX 32P использует 9-разрядные коды операций, 21-разрядные адреса и 2-битное поле управления. Если предположить, что мы можем использовать оптимально упакованные инструкции, то можно создать формат операций, имеющий 11 бит, включая бит-признак выхода из подпрограммы, и 23-битный формат вызовов/переходов. Кроме того, без стеснения заявим, что все выходы из подпрограмм всегда комбинируются с другими операциями или вызовы заменяются переходами. Всё перечисленное предполагает создание машины с переменной шириной слова ( 11-битными кодами операций и 23-битными вызовами подпрограмм, что есть задача нетривиальная ), мы же просто хотим узнать теоретический минимум.

Три оптимизированных программы состоят из 1953 11-битных кодов, 1389 23-битных вызовов подпрограмм и 565 34-битных комбинаций. Всё вместе занимает 72640 бит.

Теперь рассмотрим реальные программы, транслированные для RTX 32P с применением оптимизации. Учитывая фиксированный 32-битный формат, имеющий не всегда используемые поля, получаем общий объём 3300 инструкций равным 105600 бит. Таким образом, увеличение расхода памяти - стоимость в единицах её объёма - равно 32900 бит или на 31% больше теоретического минимума.



==138



==139

При более внимательном взгляде можно обнаружить, что 766 неиспользуемых 9-разрядных полей кода операции и 917 неиспользуемых 23-разрядных полей адреса дают в сумме 27985 бит или 27% превышения расхода памяти [* с учётом того, что единый формат занимает 9+21+2=32 бита, а раздельный «теоретический» 11+23=34 бита ]   при 25% уменьшении числа исполняемых инструкций [* «OP-OP»: 952 + 383 + 1965 = 3300 ( со сжатием ) против 1250 + 515 + 2422 = 4187 ( без сжатия )] . Таким образом, существенный прирост скорости получен при относительно скромных затратах даже по сравнению с форматом инструкций переменной ширины.

У представленных здесь расчётов есть небольшой недостаток: они проводились на нескольких относительно небольших примерах. В них выполняются некоторые довольно сложные действия и проведённые измерения могут создать впечатление, что программы для стековых машин много места не занимают, но трудность заключается в том, что большую программу на языке FORTH найти сложно [* !!! Больших проектов на FORTH не существует ] . Так или иначе, выбранные примеры имеют разумное покрытие словаря FORTH и по ответственному мнению автора результаты близки к тому, что можно получить, используя программы большего размера.

Одним из возможных путей получения заметно больших программ было бы использование результатов компиляции текстов на традиционных языках, но такой код имел бы существенно иные характеристики, потому что методы решения проблем с использованием Си и FORTRAN существенно отличаются от таковых при использовании FORTH. Этот тезис будет дополнительно рассмотрен в Части _7  .



==139