Книга: UNIX — универсальная среда программирования

8.7 Оценка времени выполнения

8.7 Оценка времени выполнения

Мы сравнивали hoc с другими программами-калькуляторами UNIX, чтобы приблизительно оценить, насколько хорошо он работает. К таблице, представленной ниже (табл. 8.1), можно, конечно, отнестись скептически, но она показывает "разумность" нашей реализации. Все приведенные в ней величины даны в секундах. Работа велась на PDP-11/70. Было выполнено два теста. Первый, вычисление функции Аккерманна ack(3,3), — хороший тест для отработки механизма вызова функций. Здесь происходят 2432 вызова, причем некоторые из них достаточно глубоко вложены.

func ack() {
 if ($1 == 0) return ($2+1)
 if($2 == 0) return (ack($1 - 1, 1))
 return (ack($1 - 1, ack($1, $2 - 1)))
}
ack(3,3)

Второй тест — стократное вычисление чисел Фибоначчи со значениями, меньшими 1000. В этом случае выполнялись в основном арифметические операции с периодическим вызовом функций:

proc fib() {
 a = 0
 b = 1
 while (b < $1) {
  с = b
  b = a+b
  a = c
 }
}
i = 1
while (i < 100) {
 fib(1000)
 i = i + 1
}

Тест выполнялся на четырех языках: hoc, bc(1), bas (древний диалект Бейсика, который существует только на PDP-11) и Си (использовался тип PDP-11 для всех переменных) .

Числа, приведенные в табл. 8.1, являются суммой пользовательского и системного времени процессора и вычислены с помощью функции time.

Таблица 8.1: Время работы на PDP-11/70 (в секундах)

Можно также приспособить Си программу для определения количества времени, используемого каждой функцией. Программу нужно перетранслировать в режиме профилирования, введя флаг -p в каждой единице трансляции Си и при режиме загрузки. Если изменить файл makefile для чтения:

hoc6: $(OBJS)
      сс $(CFLAGS) $(OBJS) -lm -о hoc6

чтобы команда сс задействовала переменную CFLAGS, а затем задать

$ make clean; make CFLAGS=-p

то результирующая программа будет выполняться с профилированием. После выполнения программы остается файл mon.out, который интерпретируется программой профилировщиком prof.

Для иллюстрации изложенного мы протестировали hoc6 на приведенной выше программе Фибоначчи:

$ hoc6 <fibtest       Запуск теста

$ prof hoc6 | sed 15q Анализ

name   %time cumsec #call ms/call
_pop    15.6 0.85   32182  0.03
_push   14.3 1.63   32182  0.02
mcount  11.3 2.25
csv     10.1 2.80
cret     8.8 3.28
_assign  8.2 3.73    5050  0.09
_eval    8.2 4.18    8218  0.05
_execute 6.0 4.51    3567  0.09
_varpush 5.9 4.83   13268  0.02
_lt      2.7 4.98    1783  0.08
_constpu 2.0 5.09     497  0.22
_add     1.7 5.18    1683  0.05
_getarg  1.5 5.26    1683  0.05
_yyparse 0.6 5.30       3 11.11
$

Результаты, полученные с помощью профилировщика, также подвержены случайным вариациям, как и те, что получены с помощью функции time, поэтому их следует считать лишь указанием настоящих значений, а не принимать за абсолютную истину. Тем не менее при необходимости приведенные значения могут помочь повысить быстродействие программы hoc. Приблизительно третья часть времени тратится на запись и чтение из стека. Накладные расходы еще более возрастут, если мы будем учитывать время выполнения функций связи csv и cret между программами Си (функция mcount представляет собой часть программы с профилированием, полученную с помощью команды ее -р.). Замена вызовов функций на макрообращения даст заметную разницу во времени выполнения.

Для проверки этого предположения мы изменили code.c, заменив вызовы push и pop на макрокоманды, управляющие стеком:

#define push(d) *stackp++ = (d)
#define popm() *--stackp = pop() /* функция все-таки нужна */

(Функция pop все-таки нужна в качестве кода операции нашей машины, поэтому нельзя заменить все обращения к ней.) Новая версия выполняется на 35% быстрее; время в табл. 8.1 сокращается от 5.5 до 3.7 с и от 5.0 до 3.1 с.

Оглавление книги