Максимально точное измерение кода

  • Tutorial

В моей статье полугодичной давности о длинной арифметике есть замеры скорости (throughput в тактах) очень коротких фрагментов кода — всего по несколько инструкций. Методика измерения была кривовата, но давала правдоподобные результаты. Потом выяснилось, что результаты таки неверные — поверхностный подход всегда сказывается.

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

Я использую только GCC — соответственно способ заточен под него. Но буду делать обобщения, чтобы владельцы других компиляторов могли разобраться.


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

Единственным недостатком RDTSC при микроизмерениях остается плавающая тактовая частота процессоров, потому что time stamp counter всегда считает такты в соответствии со стандартным множителем. Зафиксировать множитель — задача не всегда тривиальная, ищите "disable cpu scaling" в сочетании с названием своей ОС и типом процессора. Удачное решение в Gnome — апплет indicator-cpufreq.

Измерительная обвязка состоит из трех вложенных циклов.

Внутренний цикл управляет потоком данных как и в рабочей программе.
В таком духе:
type input1[n];
type input2[n];
type output[n];
...
    for (int i = 0; i < n; i++) {
        обработать input1[i] и input2[i]
        результат записать в output[i]
    } 

Важно, что в фразе «померить код» под «кодом» в этой статье подразумевается определенная последовательность инструкций процессора. Поэтому часть цикла между скобками либо должна быть написана на ассемблере, либо на Си, но вы должны четко понимать, чего добиваетесь от компилятора. Чтобы побороть кипучую активность GCC при -O3, сразу добавьте опции -fno-prefetch-loop-arrays, -fno-unroll-loops, -ftree-vectorizer-verbose=1. -fno-tree-vectorize либо -ftree-vectorize — уже в зависимости от того, что требуется на выходе — «как написано» или векторизованный вариант цикла.

Если вы хотите измерить обработку конкретного входа или код вообще без входа/выхода, все равно заверните его в цикл. Чтобы GCC не вынес код обратно, включите -fno-gcse (global common subexpression elimination), -fno-tree-pta (points-to analysis) и -fno-tree-pre (partial redundancy elimination). См. все опции оптимизации.

Начало цикла выровняйте на 32 байта. При -falign-loops (-O2) GCC делает это сам.

Средний цикл содержит 2 замера тактов и неизменный внутренний цикл посередине. Его роль — определить минимальное время, за которое может выполниться внутренний цикл. 20-30 итераций вполне хватает, чтобы все данные попали в кеш, начальная и конечная RDTSC заняли одинаковое время, а также сошлись все прочие звезды, если они существуют :-)

Внешний цикл управляет длиной внутреннего. Расположите в нем инициализацию входных данных перед средним циклом.

Внешний цикл необходим, потому что время, достигнутое в среднем цикле, всегда включает константу — время инициализации внутреннего цикла + затраты на 1 ошибку в предсказании перехода (самые умные интеловские ядра ошибаются реже). Поэтому время из среднего цикла нельзя просто разделить на кол-во итераций.

Но даже это еще не все! Разница времени выполнения внутренних циклов, отличающихся по длине на 1 итерацию, зачастую существенно варьируется. Причина — влияние разных этапов конвейера друг на друга. В то время, когда на каком-то этапе по идее должна вестись работа, на самом деле может происходить следующее:
  • обработка данных,
  • простой, т. к. следующий этап еще занят,
  • простой, т. к. не пришли данные с предыдущего этапа.
Кроме того, некоторые этапы имеют необычное поведение, например предсказатель переходов и планировщик микроопераций. Все это порождает затейливые эффекты.

В итоге на конвейере устанавливается «паттерн» работы длиной от 1 до 10-15(?) итераций:

Точный througput в тактах имеет смысл считать как минимум для 1 такого паттерна, а не 1 итерации.

Как легко убедиться из цифр в примерах ниже, даже при измерении паттернов разброс результатов остается. Предположительно, на самом деле RDTSC не так хороша, как расписано выше :-)

Итак, получив разницы времени выполнения внутренних циклов с длинами кратными шагу паттерна, остается посчитать статистики.

Примеры


Сравните результаты замеров (здесь и далее все значения в тактах) из статьи про длинную арифметику:
Поверхностный метод 7.5 5.5 5.5 7 5 2 2.5 3.25(?)–3.5
Умный метод 7 6 6 7 5 2 2 3

Все дальнейшие тесты проводились на 2 ядрах: AMD K10 и Intel Core 2 Wolfdale.

Важно оценить сами инструменты.

Пустой цикл
Внутренний цикл выглядит так:
for (int i = 0; i < inner_len; i++) {
    asm volatile ( "" );
} 

K10		1.8 ± 0.7
Core 2	10.0 ± 2.4 на 10 итераций.
Далее (10, 1.0) — (длина паттерна, итого в среднем на 1 итерацию)

RDTSC
Без среднего и внутреннего цикла:
typedef unsigned long long ull;

inline ull rdtsc() {
	unsigned int lo, hi;
	asm volatile ( "rdtsc\n" : "=a" (lo), "=d" (hi) );
	return ((ull)hi << 32) | lo;
}

...
    for (int i = 0; i < TOTAL_VALUES; i++) {
        ull t1 = rdtsc();
        ull t2 = rdtsc();
        printf("%lld\n", t2 - t1);
    }

K10		69.7 ± 1.5
Core 2	31.0 ± 0.3


Приближенное вычисление синуса


Интересно посмотреть, сколько можно сэкономить, вычисляя синус рядом Тейлора 3-го порядка. При углах от −π/2 до π/2 получается точность в 2 знака после запятой. Можно представить приложения, где ее будет достаточно.

Каркас:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <limits>

typedef unsigned long long ull;

#define MIDDLE_LEN (20)
#define TOTAL_VALUES (10000)

#define VEC_LEN (1)

// len in _numbers_
#define DATA_LEN (TOTAL_VALUES * VEC_LEN)

inline ull rdtsc() {
	unsigned int lo, hi;
	asm volatile ( "rdtsc\n" : "=a" (lo), "=d" (hi) );
	return ((ull)hi << 32) | lo;
}

typedef double my_float;
#define BYTE_LEN (DATA_LEN * sizeof(my_float))

int main() {
	my_float *angles = (my_float *) malloc(BYTE_LEN);
	my_float *sines = (my_float *) malloc(BYTE_LEN);
	еще приготовления

	for (int inner_len = 0; inner_len < DATA_LEN; inner_len += VEC_LEN) {
		for (int i = 0; i < inner_len; i++)
			инициализация angles[i]
		
		ull inner_min = std::numeric_limits<ull>::max();
		
		for (int mi = 0; mi < MIDDLE_LEN; mi++) {
			ull t1 = rdtsc();

			for (int i = 0; i < inner_len; i += VEC_LEN) {
				записать синус angles[i] в sines[i]
			}
			ull t = rdtsc() - t1;
			inner_min = t < inner_min ? t : inner_min;
		}
		// статистики считаются отдельным скриптом
		printf("%lld\n", inner_min);
	}
}


Инструкция FSIN — точный синус
Именно ее вызывает sin из math.h. Генерируемые микрооперации, наверное, напоминают эту реализацию синуса, так как скорость выполнения тоже зависит от угла. Поэтому точный througput имеет смысл, если в цикле вычисляется синус одного и того же угла. Среднее по случайному углу нужно для сравнения с независимым от угла грубым расчетом.

// приготовления
my_float randoms[DATA_LEN];
for (int i = 0; i < DATA_LEN; i++)
	randoms[i] = rand() / 2.0 / RAND_MAX * M_PI;

// инициализация углов
angles[i] = 0.0 или 0.0001 или M_PI * 0.5 или randoms[i];

// вычисление синуса
asm volatile (
	"fldl (%0)\n\t"
	"fsin\n\t"
	"fstpl (%1)\n\t"
	:: "r" (angles + i), "r" (sines + i)					
);
угол 0.0 0.0001 π/2 случайный
K10 30.2 ± 10.3 89.8 ± 2.9 143.1 ± 8.5 (2, 71.6) 75.6
Core 2 40.0 ± 11.0 68.0 ± 5.6 88.0 ± 13.0 89.4


Ряд Тейлора 3-го порядка
// приготовления
my_float d6 = 1.0 / 6.0;
my_float d120 = 1.0 / 120.0;

my_float randoms[DATA_LEN];
for (int i = 0; i < DATA_LEN; i++)
	randoms[i] = rand() / 2.0 / RAND_MAX * M_PI;

// инициализация углов
angles[i] = randoms[i];

// вычисление синуса
my_float x = angles[i];
sines[i] = x - x*x*x*d6 + x*x*x*x*x*d120;
K10 61.2 ± 15.6 (8, 7.7)
Core 2 35.2 ± 16.8 (4, 8.8)

Векторизованный ряд Тейлора
Если просто добавить опцию GCC -ftree-vectorize, по сути будет тот же результат (cм. выше). А тут используются Vector Extensions.
#define VEC_LEN (2)
typedef my_float float_vector __attribute__ ((vector_size (16)));
...
// приготовления
float_vector d6_v = {1.0 / 6.0, 1.0 / 6.0};
float_vector d120_v = {1.0 / 120.0, 1.0 / 120.0};

my_float randoms[DATA_LEN];
for (int i = 0; i < DATA_LEN; i++)
	randoms[i] = rand() / 2.0 / RAND_MAX * M_PI;

// инициализация углов
angles[i] = randoms[i];

// вычисление синуса
float_vector x = *((float_vector *)(angles + i));
*((float_vector *)(sines + i)) = x - x*x*x*d6_v + x*x*x*x*x*d120_v;
K10 41.8 ± 14.2 (5, 8.4, 4.2 на 1 синус)
Core 2 44.3 ± 16.6 (5, 8.9, 4.5)
Скорость выполнения 1 итерации чуть ниже, чем в скалярном варианте, а вычисления синуса 1 угла — почти в 2 раза выше.

Получается, что вычисление синуса с точностью до 2 знаков можно организовать как минимум в 10 раз быстрее, чем обычно.


Источники


Еще ссылки


П. С.

Описанный метод не профилирует код. Вероятность того, что он поможет при оптимизации, также крайне мала, потому что даже если производительность упирается в вычислительный конвейер, сравнивать решения всегда можно обычным clock()-ом по циклу на миллион итераций.
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 36

  • UFO just landed and posted this here
      0
      На K10 rdtsc выполняется за 67-71, на Core 2 — 30-32. Вообще у Агнера некоторые цифры из этого поста есть и гораздо больше. По Агнеру, на K10 rdtsc занимает 67, на Core 2 — 32 такта.
        +4
        Я сам занимался данной проблемой некоторое время назад и хотелось бы поделиться своими замечаниями.

        Процессор очень хитрое устройство, поэтому если писать что то такое:
        ull t1 = rdtsc();
        for (int i = 0; i < inner_len; i += VEC_LEN) {
        записать синус angles[i] в sines[i]
        }
        ull t = rdtsc() - t1;
        

        то может получиться так, что процессор поменяет инструкции местами(так как они не зависят), поэтому rdtcs() может вызваться не там где нужно и результат будет не верным.

        Мое решение следующие(GCC only). Я не стал приводить весь код, только основное:
        
        inline void start()
        {
        	asm volatile (  "cpuid\n\t"
        					"rdtsc\n\t"
        					"mov %%edx, %0\n\t"
        					"mov %%eax, %1\n\t" : "=r"(time_edx), "=r"(time_eax) ::
        					"%rax", "%rbx", "%rcx", "%rdx");
        }
        
        inline void stop ()
        {
        	asm volatile (  "rdtscp\n\t"
        					"mov %%edx, %0\n\t"
        					"mov %%eax, %1\n\t"
        					"cpuid\n\t" : "=r"(time_edx1), "=r"(time_eax1) ::
        					"%rax", "%rbx", "%rcx", "%rdx");
        
        	time_last =
        				(static_cast<unsigned long long>(time_edx1) << 32 | static_cast<unsigned long long>(time_eax1)) -
        				(static_cast<unsigned long long>(time_edx)  << 32 | static_cast<unsigned long long>(time_eax));
        }
        
        

        Рассмотрим подробнее, как устроен данный код.

        Вначале необходимо вызвать инструкцию cpuid для того, чтобы процессор не менял порядок исполнения инструкций. Затем, вызывая инструкцию rdtsc, происходит запись количества тактов процессора в регистры edx и eax.
        Инструкция rdtscp читает значение количества тактов процессора и сохраняет их в регистры edx и eax, гарантируя при этом, что весь код, который находится до этой инструкции, будет выполнен. После данной инструкции, также стоит вызвать инструкцию cpuid, что бы предотвратить внеочередное исполнение инструкций.

        Следует заметить, что на «замеряемое» время это ни как не повлияет, т.к. инструкция cpuid следует за инструкцией rdtscp(которая появилась только в процессорах начиная с Intel Core i7)

        Подробности можно посмотреть тут: Gabriele Paoloni. How to Benchmark Code Execution Times on Intel IA-32 and IA-64 Instruction Set Architectures, September 2010
          0
          > то может получиться так, что процессор поменяет инструкции местами(так как они не зависят), поэтому rdtcs() может вызваться не там где нужно и результат будет не верным.

          А можно ли для этого применять volatile переменные и memorybarier (читал здесь: ru.wikipedia.org/wiki/GCC_Inline_Assembly)? И если нет, то почему?
            +3
            asm volatile — это просьба к компилятору, чтобы он ничего не трогал, но к процессору это никакого отношения не имеет.
              0
              Спасибо!
        –1
        Синтетика такая синтетика. Какой смысл в замере времени выполнения нескольких инструкций в идеальных условиях?
        • UFO just landed and posted this here
            +6
            По идее профайлер должен позволить лучше понять микроархитектурные феномены, у него есть доступ к апаратным счетчикам.

            И да, я отлично понимаю какой смысл оптимизировать процедуры шифрования из OpenSSL или видео кодек. Это вычислительные задачи, упирающиеся в процессор, и микроархитектурные особенности здесь проявляются в полный рост.

            Но здесь идет речь о профилировании кусков кода в сотни и сотни инструкций. Того же самого кода, который выполняется в реальном приложении. И с оптимизатором бороться не надо.

            А вот какой смысл гонять бенчмарк на 2-3 инструкции, которые в реальности будут исполняться в потоке других инструкций совершенно по-другому, я решительно не понимаю.
            • UFO just landed and posted this here
                0
                А что делать, если наш код может запускаться на десятках разных процессорах, отличающихся в разы размером кеша, длиной ковеера, числом ALU, наличием или отсутствием внеочередного исполнения инструкций и так далее и так далее?
                • UFO just landed and posted this here
                    0
                    И шипить отдельный вариант кода для каждого процессора? Не ожидал что все настолько серьезно.
                    • UFO just landed and posted this here
                    –1
                    Десятки разных процессоров — где ж вы их возьмете?
                    Для мейнстрима (х86) оптимизация для Intel даст прирост на AMD с вероятностью 95%.
                      0
                      Core i7 и Intel Atom отличаются достаточно сильно.

                      Утверждается, что для мейнстрима (x86) есть куча вариантов, отличающихся в разы размером кеша, длиной ковеера, числом ALU, наличием или отсутствием внеочередного исполнения инструкций и так далее и так далее.

                      Я конечно не специалист в этом вопросе, но кажется мне, что оптимизировав код на пределе возможностей конкретного камня, мы получим нечто, работающее далеко не так хорошо на других камнях. В лучшем случае, скорость будет как у любого другого кода, который специально не оптимизировался под микроархитектурные особенности. В худшем — сильно просядем к примеру из-за того что данные перестали хорошо укладываться в кеш.
                        +1
                        Ну так десяток где то?
                        Для атома, если очень приспичит — напишете свою версию.
                        Хотя даже не так — делается «общая версия» — по возможности тупая, с минимальной базой х86 (например П3). Дальше детектор спецификации процессора и переключение ветки кода на оптимизированную если архитектурные ограничения позволяют ее выполнить.

                        Насчет размеров кешей и прочего — архитектурно-оптимизированные библиотеки частенько поставляются сорцами (см. Atlas, FFTW) и когда вы ее компилируете на целевом процессоре все автоматически подгоняется. А те библиотеки как MKL работают по описанному выше алгоритму — ветки кода и детектор процессора.

                    0
                    Если разницу в скорости двух различных реализаций нельзя увидеть таймерами, то точно также её нельзя будет увидеть в production системе.
                      0
                      А разве нужна интуиция при проведении оптимизации производительности кода?
                      Как по мне, то нужно полагаться на показания профайлера, а не на интуицию.
                      • UFO just landed and posted this here
                          0
                          Звучит красиво, а конкретные примеры есть?

                          По мне, если уж очень хочется оптимизировать на таком низком уровне, проще использовать генетические алгоритмы для определения оптимального порядка инструкций, чем вручную возиться.
                          • UFO just landed and posted this here
                              0
                              Процессорное время всяко дешевле времени людей, как минимум нужно комбинировать оба подхода.

                              Такие вещи есть смысл делать только, когда все алгоритмические оптимизации исчерпаны. Значит у нас есть более-менее конечный вариант кода сгенерированный оптимизирующим компилятором. Простая перестановка инструкций это конечно слегка примитивно, имеет смысл добавить «эквивалентные преобразования кода» (например haddp <-> shufp + addp и т.д.).

                              Понятно что сразу сесть и написать их все будет трудновато. Но если список расширять каждый раз когда «человек оказался умнее машины», то очень скоро можно будет в 99% случаев просто закинуть программу на кластер и идти пить чай)))
                              • UFO just landed and posted this here
                                  0
                                  Если тонкая оптимизация выявила потребность в изменении семантики, значит кто-то сильно накосячил раньше на этапе алгоритмических оптимизаций и профилирования))

                                  Я не предлагал писать оптимизирующий компилятор, а скорее «дооптимизатор» который можно постепенно научить известным ручным трюкам, тупо говоря «этот и этот код эквивалентны». А с комбинаторным «взрывом» как раз должны помочь генетические алгоритмы.

                                  Но это дело вкуса, по мне так выигрыш не стоит затраченных усилий. Даже программы которые пускают на Tier 1 кластеры (а это слоты на миллионы CPU часов) никто так не вылизывает.
                  0
                  Я понимаю, что немного :)
                  Применимость: сравнение однопоточного потенциала процессоров, просто интерес.
                    0
                    Зачем городить огород с RDTSC когда есть perf/oprofile и наносекундные таймеры?
                      0
                      В первом примере «поверхностный подход» — это именно использование наносекундных таймеров.

                      Повторюсь, мой метод к профилированию отношения не имеет.

                      Вообще, в посте rdtsc и такты можно заменить на какой-нибудь performance counter, например «uops scheduled», без особой потери смысла. Многие советы лежат в другой плоскости.
                      0
                      Про синус можно почитать тут:
                      software.intel.com/sites/products/documentation/hpc/mkl/vml/functions/sin.html
                      Там же найдете и другие матфункции. Понятно что реализация будет другая, отличная от GCC.
                        0
                        > Поэтому часть цикла между скобками либо должна быть написана на ассемблере, либо на Си, но вы должны четко понимать, чего добиваетесь от компилятора.

                        Раскройте пожалуйста смысл.
                          0
                          Если пишете на Си, проверьте с помощью ключа -S генерируемый ассемблерный код. Чтобы понимать, что вообще измеряется. Иногда компилятор может наломать дров с разворачиванием циклов и т. д.
                            0
                            О, теперь дошло!

                            > Если пишете на Си, проверьте с помощью ключа -S генерируемый ассемблерный код.
                            Вот это было не понятно.
                          0
                          > начальная и конечная RDTSC заняли одинаковое время

                          Возможно ошибаюсь, но наверное имелось в виду не начальное и конечное RDTSC, а разница между начальным и конечным RDTSC?
                            0
                            Время выполнения rdtsc не всегда зафиксировано четко. Если 1-я rdtsc займет 29 тактов, а 2-я 31, то время непосредственно измеряемого кода будет выведено на 2(?) такта больше, чем если 1-я rdtsc займет 31, 2-я — 29 тактов.
                              0
                              > Время выполнения rdtsc не всегда зафиксировано четко.

                              Мда… Сколько же тут подводных камней…

                          Only users with full accounts can post comments. Log in, please.