Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

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

Помня, что «доказательства важнее размышлений», напишем код, который проверяет, насколько замедляют программу два типичных приёма программирования. Один из них типичен для всего функционального программирования, а второй нашёл место в 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
};
Тест даёт возможность посчитать разницу между t2 и t1. Эта разница покажет «стоимость» вызова подпрограммы с предсказуемым адресом. А раз адрес предсказуем, то процессор будет пытаться заранее сделать вычисления, чтобы ускорить их ход. Но когда адрес вызываемой функции становится известным лишь в последний момент, то спекулятивное исполнение становится невозможным. Что сказывается на времени исполнения подпрограмм — оно увеличивается. С помощью третьего теста попробуем получить количественную оценку этого увеличения.
x = i = 0;
очередной байт = буфер;
НАЧАЛО ТЕСТА("t3 = t2 + дополнительное время \
	на выполнение подпрограммы с непредсказуемым адресом");
for (; i < длина; ++i, ++очередной байт)
	x = (* адр [x]) (x, *очередной байт);
КОНЕЦ ТЕСТА();

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

  A B C
t1 1237 1810 609
t2 2574 2683 1031
t3 5519 5959 4109

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

  A B C
t2-t1 1337 873 422
t3-t2 2945 3276 3078
%% 220 375,3 729

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



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


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

Во второй части тестов попробуем измерить, как скорость исполнения влияет каррирование функций. Для этого сперва измерим время вычислений с вызовом функции 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]);
КОНЕЦ ТЕСТА();

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

  A B C
T1 617 453 172
T2 955 951 328
T3 2016 1576 656

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

  A B C
T2-T1 338 498 156
T3-T2 1399 1123 484
%% 414 225,5 310

И здесь мы видим, что каррирование так же заметно замедляет программу. Между тем, в 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

ОценитеОценки посетителей
   ██████████████████████████████████████████ 1 (100%)
   ▌ 0
   ▌ 0
   ▌ 0

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

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

Авторизация

Регистрация

Выслать пароль

Карта сайта


Содержание

Каким должен быть язык программирования?

Анализ и критика

●  Устарел ли текст как форма представления программы

●  Русский язык и программирование

●  Многоязыковое программирование

Синтаксис языков программирования

Синтаксический сахар

●  Некоторые «вкусности» Алгол-68

●  «Двухмерный» синтаксис Python

●  Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

●  Должна ли программа быть удобочитаемой?

●  Стиль языка программирования

●  Тексто-графическое представление программы

●●  Разделители

●●  Строки программы

●●  Слева направо или справа налево?

●  Комментарии

●●  Длинные комментарии

●●  Короткие комментарии

●●  Комментарии автоматической генерации документации

●●  Нерабочий код

●●  Помеченные комментарии

●  Нужны ли беззнаковые целые?

●  Шестнадцатиричные и двоичные константы

●  Условные операторы

●  Переключатель

●  Циклы

●●  Продолжение цикла и выход из него

●  Некошерный «goto»

●  Изменение приоритетов операций

●  Операции присвоения и проверки на равенство. Возможно ли одинаковое обозначение?

●  Так ли нужны операции «&&», «||» и «^^»?

●  Постфиксные инкремент и декремент

●  Почему в PHP для конкатенации строк используется «.»?

●  Указатели и ссылки в C++

●●  О неправомерном доступе к памяти через указатели

●  Обработка ошибок

●  Функциональное программирование

●●  Нечистые действия в чистых функциях

●●  О чистоте и нечистоте функций и языков

●●  Макросы — это чистые функции, исполняемые во время компиляции

●●  Хаскелл, детище британских учёных

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

●●  C vs Haskell: сравнение скорости на простом примере

●●  Уникальность имён функций: за и против

●●  Каррирование: для чего и как

●●  О тестах, доказывающих отсутствие ошибок

●  Надёжные программы из ненадёжных компонентов

●●  О многократном резервировании функций

●  Использование памяти

●  Почему динамическое распределение памяти — это плохо

●  Как обеспечить возврат функциями объектов переменной длины?

●●  Типы переменного размера (dynamically sized types, DST) в языке Rust

●●  Массивы переменной длины в C/C++

●●  Размещение объектов в стеке, традиционный подход

●●  Размещение объектов переменной длины с использованием множества стеков

●●  Размещение объектов переменной длины с использованием двух стеков

●●  Реализация двухстековой модели размещения данных

●●  Двухстековая модель: тесты на скорость

●●  Изменение длины объекта в стеке во время исполнения

●●  Размещение объектов переменной длины с использованием одного стека

●  Можно ли забыть о «куче», если объекты переменной длины хранить в стеке

●  Безопасность и размещение объектов переменной длины в стеке

●  Массивы, структуры, типы, классы переменной длины

●  О хранении данных в стеке, вместо заключения

●  Реализация параметрического полиморфизма

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Новости и прочее




Последние отзывы

2024/05/12 22:14 ••• Сисадмин со стажем
О превращении кибернетики в шаманство

2024/05/11 16:33 ••• Автор сайта
Энтузиасты-разработчики компиляторов и их проекты

2024/04/28 15:58 ••• Автор сайта
Обработка ошибок

2024/04/23 00:00 ••• alextretyak
Признаки устаревшего языка

2024/04/21 00:00 ••• alextretyak
Постфиксные инкремент и декремент

2024/04/20 21:28 ••• Бурановский дедушка
Русский язык и программирование

2024/04/07 15:33 ••• MihalNik
Все языки эквивалентны. Но некоторые из них эквивалентнее других

2024/04/01 23:39 ••• Бурановский дедушка
Новости и прочее

2024/04/01 23:32 ••• Бурановский дедушка
Русской операционной системой должна стать ReactOS

2024/03/22 20:41 ••• void
Раскрутка компилятора

2024/03/20 19:54 ••• kt
О многократном резервировании функций

2024/03/20 13:13 ••• Неслучайный читатель
Надёжные программы из ненадёжных компонентов

2024/03/07 14:16 ••• Неслучайный читатель
«Двухмерный» синтаксис Python