Измеряем замедление при вызове функций высших порядков

Помня, что «доказательства важнее размышлений», напишем код, который проверяет, насколько замедляют программу два типичных приёма программирования. Один из них типичен для всего функционального программирования, а второй нашёл место в ML, Haskell, F#.

Во-первых, это использование функций как объектов первого класса (функции высших порядков — higher-order functions). Оно уравнивает в правах адреса функций с остальными объектами программы, их использование становится столь же равноправным, частым и удобным, как и обычных переменных. Функции высших порядков есть не во всех императивных языках. В Си такие функции вроде бы уравняли в правах с обычными переменными, но реализация вышла синтаксически неудобной. Она не стимулирует лишний раз пользоваться этой возможностью. Но нас интересует насколько замедляет программу вызов функции, адрес которой возвратили из другой функции и который (а) прогнозируем и (б) не прогнозируем.

Во-вторых, это каррирование. Нас интересует, насколько оно влияет на скорость программы.

Для написания тестов выберем компилятор TinyCC, который известен своей компактностью и скоростью компиляции, которая в 9 раз выше, чем у GCC. TinyCC почти не делает оптимизаций, генерирует ровно такой код, какой ему предписали, что и требуется для тестов.

Вызов подпрограмм как предсказуемому адресу, так и непредсказуемому

В качестве подопытного кролика выберем операцию «исключающее или». Во-первых, она простейшая, во-вторых, она, в отличие от «и» и «или», в принципе не обладает свойством ленивости. Поскольку процессор выполняет операции очень быстро, то для замеров времени будем повторять операции в цикле. Чтобы цикл был долгим, прочитаем файл большого размера (256 Мб), а после чтения и будем побайтно выполнять в цикле «исключающее или».

Для начала сделаем замер, как сколько времени выполняется цикл с «исключающим или»:

// к этому моменту файл размером 256 Мб уже прочитан
x = i = 0;
очередной байт = буфер;
НАЧАЛО ТЕСТА("t1 = время выполнения цикла вычислений без вызова подпрограмм");
for (; i < длина; ++i, ++очередной байт)
	x ^= *очередной байт;
КОНЕЦ ТЕСТА();

Во втором тесте измеряем время, которое тратится на выполнение цикла, в котором выполняется вызов подпрограммы, внутри которой — «исключающее или»:

x = i = 0;
очередной байт = буфер;
НАЧАЛО ТЕСТА("t2 = t1 + время выполнения \
	вызовов подпрограммы из массива \
	с известным индексом");
for (; i < длина; ++i, ++очередной байт)
	x = (* адр [0]) (x, *очередной байт);
КОНЕЦ ТЕСТА();

_31	F00 (_31  a, _31  b) { return  a ^ b; };
_31	F01 (_31  a, _31  b) { return  a ^ b; };
. . .
_31	FFF (_31  a, _31  b) { return  a ^ b; };

typedef  _31 (*адрес бинарной функции)(_31, _31);
// массив одинаковых функций, различающихся только именем
адрес бинарной функции  адр[] = {
	F00, F01, . . . FFF
};

x = i = 0;
очередной байт = буфер;
НАЧАЛО ТЕСТА("t3 = t2 + дополнительное время \
	на выполнение подпрограммы с непредсказуемым адресом");
for (; i < длина; ++i, ++очередной байт)
	x = (* адр [x]) (x, *очередной байт);
КОНЕЦ ТЕСТА();

Результаты тестов на трёх разных компьютерах (под буквами A, B, C) будут таковы:

Эти результаты дают возможность найти t2-t1 (время выполнения косвенных вызовов подпрограммы из массива с известным индексом), t3-t2 (дополнительное время на выполнение подпрограммы с непредсказуемым адресом) и соотношение (t3-t2)/(t2-t1) в процентах:

Как видим, если адрес перехода (то есть вызываемой подпрограммы) непредсказуем, то это серьёзно замедляет программу. Полученные результаты говорят за себя. Ниже — итоги в графическом виде.

Вызов функций обычных и каррированных

Во второй части тестов попробуем измерить, как скорость исполнения влияет каррирование функций. Для этого сперва измерим время вычислений с вызовом функции 8 аргументов, а затем каррируем эту функцию, то есть разобьём на 8 функций по одному аргументу. Измерим «расходы» на выполнения цикла с 8 вычислениями:

x = i = 0;
очередной байт = буфер;
НАЧАЛО ТЕСТА("T1 = время выполнения 8 вычислений");
for (; i < длина; i += 8, очередной байт += 8)
	x ^= очередной байт[0] ^ очередной байт[1] ^ очередной байт[2] ^
	очередной байт[3] ^ очередной байт[4] ^ очередной байт[5] ^ 
	очередной байт[6] ^ очередной байт[7];
КОНЕЦ ТЕСТА();

Затем измерим время работы в цикле функции 8 аргументов:

x = i = 0;
очередной байт = буфер;
НАЧАЛО ТЕСТА("T2 = T1 + время вызова функции 8 аргументов");
for (; i < длина; i += 8, очередной байт += 8)
	x ^= функция 8 аргументов (очередной байт[0], очередной байт[1], 
		очередной байт[2], очередной байт[3], очередной байт[4],
		очередной байт[5], очередной байт[6], очередной байт[7]);
КОНЕЦ ТЕСТА();

В завершение — время работы в цикле 8 вызовов каррированных функций.

x = i = 0;
очередной байт = буфер;
НАЧАЛО ТЕСТА("T3 = T1 + время вызова 8 функций одного аргумента");
for (; i < длина; i += 8, очередной байт += 8)
	x ^= ф7 (очередной байт[0]) (очередной байт[1]) (очередной байт[2])
		(очередной байт[3]) (очередной байт[4]) (очередной байт[5])
		(очередной байт[6]) (очередной байт[7]);
КОНЕЦ ТЕСТА();

В итоге получаем следующие результаты:

Эти результаты дают возможность найти T2-T1 (время вызова функции 8 аргументов), T3-T2 (время вызова 8 функций одного аргумента) и соотношение (T3-T2)/(T2-T1) в процентах:

И здесь мы видим, что каррирование так же заметно замедляет программу. Между тем, в Haskell все функции — каррированные. Это значит, что программы на Haskell заведомо проигрывают в этом аспекте...

P. S. Для тестирования использовались компьютеры A, B и C следующих конфигураций:

• A — процессор Intel Pentium N3710 1.6 GHz, 4 Гб ОЗУ,
• B — процессор Intel Xeon X3430 2.4 GHz, 16 Гб ОЗУ,
• C — процессор Intel Pentium G3250 3.2 GHz, 8 Гб ОЗУ.

Опубликовано: 2022.01.01, последняя правка: 2023.04.21    20:20

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su