Такой анализ был выполнен следующим образом. В исследовании Паттерсона (Patterson) [РАТТ82-а], о котором мы уже упоминали в главе 4, тестовые программы на языках С и Pascal были скомпилированы в машинные программы компьютеров VAX, PDP-11 и Motorola 68000. Затем в процессе выполнения программ оценивалось среднее количество машинных команд и обращений к памяти при реализации операторов - разных типов. Соответствующие данные представлены во второй ж третьей колонках табл. 12.2. Они были получены при регистрации частоты появления определенных групп команд в процессе выполнения программы и, следовательно, отражают динамику выполнения программы. Данные в четвертой и пятой колонках табл. 12.2 представляют взвешенные статистические оценки и были получены следующим образом: каждое значение из второй и третьей колонок умножалось на количество машинных команд, которое сформировал компилятор при трансляции оператора соответствующего типа в исходной программе. Затем результаты были нормализованы. Таким образом, каждый элемент в четвертой и пятой колонках представляет собой относительную частоту появления, оператора определенного типа в типовой программе, взятую с весом, пропорциональным количеству машинных команд, необходимых для его реализации в выполняемой программе. По этому же принципу сформированы и данные в шестой и седьмой колонках табл. 12, 2, но в качестве весовых коэффициентов взято количество обращений к памяти при реализации в машинной программе оператора каждого типа.
Данные в колонках с четвертой по седьмую можно рассматривать как косвенную оценку времени выполнения в машинной программе операторов того или иного типа из программы на языке высокого уровня. Из приведенных данных следует, что больше всего времени в типовой программе уходит на процедуры вызова подпрограмм и возврата из подпрограмм.
Обращаю внимание читателей на то, что данные в табл. 12.2 справедливы для наборов команд, типичных для компьютеров 80-х годов.. Вполне возможно, что выполненный по этой же методике анализ для компьютеров с другим набором машинных команд даст несколько отличающиеся результаты, но, тем не менее, эти данные .вполне репрезентативны для всех компьютеров с расширенным набором команд (компьютеров с CISC-архитектурой). Следовательно» основываясь на них, можно искать наиболее эффективные пути поддержки языков высокого уровня в наборе машинных команд.
Таблица 12.2. Взвешенная относительная динамическая частота появления в программах операторов языков высшего уровня
| Динамическая частота появления | Взвешенная оценка количества машинных команд | Взвешенная оценка количества обращений к памяти | ||||
| Pascal | С | Pascal | С | Pascal | С | |
| Присваивание | 45 | 38 | 13 | 14 | 15 | |
| (ASSIGN) | ||||||
| Возврат на | 5 | 3 | 42 | 32 | 83 | 26 |
| начало цикла | ||||||
| (LOOP) | ||||||
| Вызов | 15 | 12 | 31 | 33 | 44 | 45 |
| подпрограмм | ||||||
| (CALL) | ||||||
| Условный | 29 | 43 | 11 | 21 | 7 | 13 |
| переход (IF) | ||||||
| Безусловный | ||||||
| переход | - | 3 | - | - | - | - |
| (GOTO) | ||||||
| Другие | 6 | 1 | 3 | 1 | 2 | 1 |
Хотя статистические характеристики типов операндов, используемых в программах, не менее важны, чем характеристики . операторов, их исследованию уделялось значительно меньше внимания. Особый интерес представляют несколько аспектов применения операндов в программах.
В уже упоминавшейся работе Паттерсона [РАТТ82-а] рассматривалась динамическая частота появления в программах переменных разных классов (табл. 12.3). Статистические параметры для программ, написанных на языках С и Pascal, достаточно хорошо согласуются, и оказывается, что большинство ссылок в программе относится к скалярным переменным. Более того, свыше 80% этих скалярных переменных являются локальными. Ссылки на массивы или составные структурные переменные требуют предварительного обращения к соответствующему индексу или указателю, который, в свою очередь, чаще всего также является локальной переменной. Следовательно, в типичной программе превалируют ссылки на скалярные переменные, причем значительная часть ез. являются локальными.
В исследовании Паттерсона анализировались динамические статистические параметры программ на языках высокого уровня, не зависящие от того, какова архитектура компьютера, на котором эта программа будет выполняться. Как уже отмечалось в предыдущем разделе, при более глубоком статистическом анализе программ архитектуру компьютера следует обязательно учитывать. В работе [LUND77] рассматривались динамические характеристики программ компьютера PDP-10 и было показано, что в среднем на одну машинную команду приходится 0.5 ссылок на операнд, находящийся в памяти, и 1.4 ссылок на операнды в регистрах. Аналогичные результаты приводятся и в работе [HUCK83J, где анализировались программы компьютеров IBM S/370, PDP-11 и VAX, написанные на языках С, Pascal и FORTRAN. Конечно, эти характеристи-ки очень зависят от особенностей архитектуры компьютеров и качества компиляторов, но, тем не менее, они несут объективную информацию о соотношении разных способов обращения к переменным в программах.
Последние из упомянутых работ, с одной стороны, свидетельствуют о важности учета характеристик компьютера при анализе, а с другой — указывают, на какие способы обращения к операндам нужно обратить особое внимание конструкторам процессоров, поскольку они встречаются в программах чаще других. Из исследований Паттерсона следует, что в первую очередь нужно оптимизировать механизм обращения к локальным скалярным переменным.
Таблица 12.3. Динамическое распределение типов операндов в программах
| Pascal | C | В среднем | |
| Целые константы | 16 | 23 | 20 |
| Скалярные переменные | 58 | 53 | 55 |
| Массивы/структуры | 26 | 24 | 25 |
Вызовы подпрограмм
Выше неоднократно подчеркивалось, что обращение к подпрограммам является одним из наиболее важных аспектов программирования на языках высокого уровня. Данные, , представленные в табл. 12.2, свидетельствуют о том, что больше всего времени при выполнении типичных программ тратится именно на операции вызова подпрограмм и возврата из подпрограмм. Следовательно, разработка методов оптимальной реализации таких операторов на уровне машинных команд принесет наибольший эффект. При выборе методов реализации нужно принимать во внимание два аспекта: количество параметров (аргументов), передаваемых при вызове подпрограммы, и переменных, с которыми работает подпрограмма; глубина вложенности вызовов подпрограмм.
В своей работе [TANE78] Таненбаум (Tanenbaum) показал, что при вызове 98% подпрограмм передается менее 6 параметров и что в 92% вызванных подпрограмм' используется менее 6 скалярных локальных переменных. Аналогичные результаты получила и группа исследователей из Беркли [КАТЕ83] (табл. 12.4). Они свидетельствуют, что для активизации подпрограмм нужно передавать весьма ограниченное количество слов данных. Работы, на которые мы ссылались выше, также указывают на то, что большая часть операций внутри подпрограмм выполняется с локальными скалярными переменными, причем количество таких переменных в типичном случае весьма невелико.
Группа исследователей RISC-архитектуры из Беркли также проанализировала типичную последовательность вызовов подпрограмм и возврата из них в главной программе, написанной на языке высокого уровня. Было обнаружено, что в программах довольно редко встречается непрерывная последовательность вызовов вложенных подпрограмм и, соответственно, непрерывная последовательность операторов возврата из подпрограмм. Значительно чаще программа имеет дело со сравнительно узким окном вложенности. Ранее, в главе 4, мы уже иллюстрировали это свойство типичных программ диаграммой, представленной на рис. 4.29. Результаты упомянутых исследований еще раз подтверждают уже неоднократно описанное свойство локализации ссылок, присущее подавляющему большинству компьютерных программ.
Таблица 12.4. Аргументы ж локальные переменные подпрограмм
| Характеристика выполняемой подпрограммы | Компиляторы, интерпретаторы | Небольшие программы, не включающие численных расчетов |
| Более 3 аргументов | 0-7% | 0-5% |
| Более 6 аргументов | 0-3% | 0% |
| Более 8 слов аргументов и локальных скалярных переменных | 1-20% | 0-6% |
| Более 12 слов аргументов и локальных скалярных переменных | 1-6% | 0-3% |
Реализация