Проблема измерений
Узнав из Главы 2 об иерархии памяти, вы, возможно, захотите оптимизировать свой код. Но есть одна проблема: как понять, что оптимизация на самом деле сработала?
Этот урок дорого мне обошёлся.
Я оптимизировал реализацию хэш-таблицы в загрузчике. Исходя из своего понимания поведения кэша, я переписал хэш-функцию так, чтобы она была «более дружественной к кэшу», и был уверен, что она станет быстрее.
Я запустил код. Мне показалось, что он быстрее. Я закоммитил изменения.
Неделю спустя коллега провёл бенчмарки и выяснил, что моя «оптимизация» замедлила код на 15%. Я оптимизировал не то, но у меня не было данных, чтобы подтвердить мои предположения.
Вывод: никогда не доверяйте своей интуиции, всегда проводите замеры.
В этой главе я расскажу, как измерять правильно. Мы создадим комплексный фреймворк бенчмаркинга и научимся эффективно использовать инструменты профилирования.
Высокоточные тайминги
Первая сложность: как измерять время наиболее точно?
Плохое решение: использовать time()
time_t start = time(NULL);
run_test();
time_t end = time(NULL);
printf("Time: %ld seconds\n", end - start);Проблема: разрешение в 1 секунду. Бесполезно для быстрых операций.
Более подходящее решение: использовать clock_gettime()
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
run_test();
clock_gettime(CLOCK_MONOTONIC, &end);
long ns = (end.tv_sec - start.tv_sec) * 1000000000L +
(end.tv_nsec - start.tv_nsec);
printf("Time: %ld ns\n", ns);Преимущества:
Наносекундное разрешение
CLOCK_MONOTONIC: изменения системного времени никак не влияютПортируемость (POSIX)
Наилучшее решение: использовать счётчики тактов CPU
На RISC-V:
static inline uint64_t rdcycle(void) {
uint64_t cycles;
asm volatile ("rdcycle %0" : "=r" (cycles));
return cycles;
}
uint64_t start = rdcycle();
run_test();
uint64_t end = rdcycle();
printf("Cycles: %lu\n", end - start);На x86_64:
static inline uint64_t rdtsc(void) {
uint32_t lo, hi;
asm volatile ("rdtsc" : "=a" (lo), "=d" (hi));
return ((uint64_t)hi << 32) | lo;
}На ARM64:
static inline uint64_t rdcycle(void) {
uint64_t val;
asm volatile("mrs %0, pmccntr_el0" : "=r"(val));
return val;
}Преимущества:
Наилучшая точность (1 такт)
Непосредственные измерения оборудования
Отсутствие оверхеда системных вызовов
Недостатки:
Уникально для каждой архитектуры
Может влиять на масштабирование частоты
Может потребовать конфигурирования ядра (ARM)
Статистический анализ
Единственный замер не имеет никакого смысла. Необходимо множество прогонов и статистический анализ.
Почему?
Состояние кэшей меняется между прогонами
На тайминги влияют прерывания ОС
Варьируется прогнозирование ветвлений
Варьируется поведение распределителя памяти
Минимальное решение: выполнить несколько прогонов и вывести минимум/максимум/среднее
#define ITERATIONS 1000
uint64_t times[ITERATIONS];
for (int i = 0; i < ITERATIONS; i++) {
uint64_t start = rdcycle();
run_test();
uint64_t end = rdcycle();
times[i] = end - start;
}
// Вычисление статистики
uint64_t min = times[0], max = times[0], sum = 0;
for (int i = 0; i < ITERATIONS; i++) {
if (times[i] < min) min = times[i];
if (times[i] > max) max = times[i];
sum += times[i];
}
uint64_t mean = sum / ITERATIONS;
printf("Min: %lu cycles\n", min);
printf("Max: %lu cycles\n", max);
printf("Mean: %lu cycles\n", mean);Более хорошее решение: добавить медиану и квадратическое отклонение
// Сортировка по медиане
qsort(times, ITERATIONS, sizeof(uint64_t), compare_uint64);
uint64_t median = times[ITERATIONS / 2];
// Вычисление квадратичного отклонения
double variance = 0;
for (int i = 0; i < ITERATIONS; i++) {
double diff = (double)times[i] - (double)mean;
variance += diff * diff;
}
double stddev = sqrt(variance / ITERATIONS);
printf("Median: %lu cycles\n", median);
printf("Std dev: %.2f cycles\n", stddev);Какую информацию возвращать?
Минимум: производительность в наилучшем случае («тёплый» кэш)
Медиана: типичная производительность (более надёжный показатель, чем среднее)
Квадратичное отклонение: изменчивость (чем меньше, тем лучше)
Максимум: наихудший случай (важно для систем реального времени)
Архитектура фреймворка бенчмаркинга
Давайте создадим фреймворк для постоянного использования. Вот его интерфейс:
typedef struct {
const char *name;
void (*setup)(void);
void (*run)(void);
void (*teardown)(void);
} benchmark_t;
void benchmark_run(benchmark_t *bench, int iterations);Реализация:
void benchmark_run(benchmark_t *bench, int iterations) {
uint64_t *times = malloc(iterations * sizeof(uint64_t));
printf("Running benchmark: %s\n", bench->name);
// Разогревающий прогон
if (bench->setup) bench->setup();
bench->run();
if (bench->teardown) bench->teardown();
// Сами измерения
for (int i = 0; i < iterations; i++) {
if (bench->setup) bench->setup();
uint64_t start = rdcycle();
bench->run();
uint64_t end = rdcycle();
if (bench->teardown) bench->teardown();
times[i] = end - start;
}
// Вычисления и статистический отчёт
report_statistics(bench->name, times, iterations);
free(times);
}Пример использования:
// Тестовые данные
int array[1000];
void setup_array(void) {
for (int i = 0; i < 1000; i++) {
array[i] = i;
}
}
void test_sequential_access(void) {
volatile int sum = 0;
for (int i = 0; i < 1000; i++) {
sum += array[i];
}
}
benchmark_t bench = {
.name = "Sequential Array Access",
.setup = setup_array,
.run = test_sequential_access,
.teardown = NULL
};
benchmark_run(&bench, 1000);Анализ кэша при помощи perf
Тайминги сообщают нам время, но не причину. Для этого нам понадобится анализ кэша.
Linux perf — стандартный инструмент для анализа производительности:
# Базовая статистика кэша
$ perf stat -e cache-references,cache-misses ./program
Performance counter stats:
1,234,567 cache-references
12,345 cache-misses # 1,00% от всех ссылок на кэшПолезные события:
cache-references: общее количество операций доступа к кэшуcache-misses: промахи кэша (на всех уровнях)L1-dcache-loads: загрузки данных кэша L1L1-dcache-load-misses: промахи загрузок данных кэша L1LLC-loads: загрузки кэша последнего уровняLLC-load-misses: промахи загрузок кэша последнего уровня
Подробный анализ:
# Анализ кэша L1
$ perf stat -e L1-dcache-loads,L1-dcache-load-misses ./program
Performance counter stats:
10,000,000 L1-dcache-loads
100,000 L1-dcache-load-misses # 1.00% miss rate
# Все уровни кэша
$ perf stat -e cache-references,cache-misses,\
L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses ./programСравнение реализаций:
# Версия с массивом
$ perf stat -e cache-misses ./array_test
1,234 cache-misses
# Версия со связанным списком
$ perf stat -e cache-misses ./list_test
45,678 cache-misses # В 37 раз больше промахов!Интеграция perf с бенчмарками
Мы можем интегрировать измерения perf с нашим фреймворком бенчмаркинга:
typedef struct {
uint64_t cycles;
uint64_t cache_references;
uint64_t cache_misses;
uint64_t l1_loads;
uint64_t l1_misses;
} perf_counters_t;
void benchmark_run_with_perf(benchmark_t *bench, int iterations) {
// Подготовка счётчиков perf
int fd_cache_ref = perf_event_open(PERF_COUNT_HW_CACHE_REFERENCES);
int fd_cache_miss = perf_event_open(PERF_COUNT_HW_CACHE_MISSES);
// Выполняем бенчмарк
perf_counters_t counters = {0};
for (int i = 0; i < iterations; i++) {
if (bench->setup) bench->setup();
// Считываем счётчики начала
uint64_t start_ref = read_counter(fd_cache_ref);
uint64_t start_miss = read_counter(fd_cache_miss);
uint64_t start_cycles = rdcycle();
bench->run();
// Считываем счётчики завершения
uint64_t end_cycles = rdcycle();
uint64_t end_miss = read_counter(fd_cache_miss);
uint64_t end_ref = read_counter(fd_cache_ref);
if (bench->teardown) bench->teardown();
counters.cycles += end_cycles - start_cycles;
counters.cache_references += end_ref - start_ref;
counters.cache_misses += end_miss - start_miss;
}
// Выводим результаты
printf("Benchmark: %s\n", bench->name);
printf(" Cycles: %lu\n", counters.cycles / iterations);
printf(" Cache refs: %lu\n", counters.cache_references / iterations);
printf(" Cache misses: %lu (%.2f%%)\n",
counters.cache_misses / iterations,
100.0 * counters.cache_misses / counters.cache_references);
}Сложности
1. Компиляторные оптимизации
Компилятор может удалить наш бенчмарк оптимизацией:
// ПЛОХО: компилятор это оптимизирует
void test(void) {
int sum = 0;
for (int i = 0; i < 1000; i++) {
sum += array[i];
}
// sum никогда не используется, весь цикл удаляется!
}
// ХОРОШО: использовать volatile или возвращаемое значение
void test(void) {
volatile int sum = 0; // Предотвращает оптимизацию
for (int i = 0; i < 1000; i++) {
sum += array[i];
}
}2. Разница между «холодным» и «тёплым» кэшем
Первый прогон всегда выполняется медленнее («холодный» кэш):
// Первый прогон: "холодный" кэщ
run_test(); // 10000 тактов
// Второй прогон: "тёплый" кэш
run_test(); // 1000 тактовРешение: всегда выполняйте разогревающий прогон или возвращайте производительность и «холодного», и «тёплого».
3. Оверхед измерений
Код замера таймингов сам отнимает время:
uint64_t start = rdcycle(); // ~10 тактов
uint64_t end = rdcycle(); // ~10 тактов
printf("Overhead: %lu\n", end - start); // ~20 тактовРешение: измерять оверхед и вычитать его, или выполнять тестовые прогоны достаточно долго, чтобы влияние оверхеда было ничтожным.
4. Шум системы
Прерывания ОС, другие процессы, масштабирование частот — всё это добавляет шум.
Решение:
Выполнять много итераций
Показывать медиану (снижает влияние выбросов)
Отключить масштабирование частоты:
cpupower frequency-set -g performanceПривязаться к ядру CPU:
taskset -c 0 ./programПовысить приоритет:
nice -n -20 ./program
Особенности встраиваемых систем
При бенчмаркинге во встраиваемых системах возникают уникальные сложности:
1. Ограниченный набор инструментов профилирования
Во многих встраиваемых системах нет perf и похожих на него инструментов.
Решение: напрямую использовать счётчики производительности оборудования через регистры с отображением в память.
Пример (RISC-V):
// Включаем счётчики производительности (машинный режим)
#define CSR_MCOUNTEREN 0x306
#define CSR_MCOUNTINHIBIT 0x320
void enable_perf_counters(void) {
// Разрешаем пользовательскому режиму считывать счётчики
asm volatile ("csrw %0, %1" :: "i"(CSR_MCOUNTEREN), "r"(0x7));
// Включаем все счётчики
asm volatile ("csrw %0, %1" :: "i"(CSR_MCOUNTINHIBIT), "r"(0x0));
}2. Отсутствие операционной системы
В системах bare-metal нет clock_gettime().
Решение: использовать аппаратные таймеры или счётчики тактов.
// Используем таймер SoC (пример)
#define TIMER_BASE 0x10000000
#define TIMER_MTIME (*(volatile uint64_t*)(TIMER_BASE + 0x00))
uint64_t get_time_us(void) {
return TIMER_MTIME; // Предполагаем, что таймер работает на 1 МГц
}3. Ограничения реального времени
В системах реального времени наихудший сценарий важнее, чем средний.
Решение: выводить максимальное время и 99-й перцентиль.
// Сортировка по времени
qsort(times, iterations, sizeof(uint64_t), compare);
uint64_t min = times[0];
uint64_t max = times[iterations - 1];
uint64_t p50 = times[iterations / 2];
uint64_t p99 = times[(iterations * 99) / 100];
printf("Min: %lu cycles\n", min);
printf("P50: %lu cycles\n", p50);
printf("P99: %lu cycles\n", p99);
printf("Max: %lu cycles\n", max);4. Ограниченность памяти
Невозможно хранить тысячи измерений.
Решение: использовать онлайн-алгоритмы (скользящую статистику).
typedef struct {
uint64_t count;
uint64_t min;
uint64_t max;
double mean;
double m2; // Для вычисления дисперсии
} running_stats_t;
void update_stats(running_stats_t *stats, uint64_t value) {
stats->count++;
if (value < stats->min) stats->min = value;
if (value > stats->max) stats->max = value;
// Онлайн-алгоритм Уэлфорда вычисления среднего и дисперсии
double delta = value - stats->mean;
stats->mean += delta / stats->count;
double delta2 = value - stats->mean;
stats->m2 += delta * delta2;
}
double get_stddev(running_stats_t *stats) {
return sqrt(stats->m2 / stats->count);
}Практический пример: массив и связанный список
Давайте разберём бенчмарк, сравнивающий массивы и связанные списки:
#define SIZE 1000
#define ITERATIONS 1000
// Реализация на основе массива
int array[SIZE];
void setup_array(void) {
for (int i = 0; i < SIZE; i++) {
array[i] = i;
}
}
void test_array_sequential(void) {
volatile int sum = 0;
for (int i = 0; i < SIZE; i++) {
sum += array[i];
}
}
// Реализация на основе связанного списка
typedef struct node {
int value;
struct node *next;
} node_t;
node_t *list_head = NULL;
void setup_list(void) {
list_head = NULL;
for (int i = SIZE - 1; i >= 0; i--) {
node_t *node = malloc(sizeof(node_t));
node->value = i;
node->next = list_head;
list_head = node;
}
}
void test_list_sequential(void) {
volatile int sum = 0;
node_t *curr = list_head;
while (curr) {
sum += curr->value;
curr = curr->next;
}
}
void teardown_list(void) {
node_t *curr = list_head;
while (curr) {
node_t *next = curr->next;
free(curr);
curr = next;
}
}
// Выполняем бенчмарки
int main(void) {
benchmark_t benchmarks[] = {
{
.name = "Array Sequential",
.setup = setup_array,
.run = test_array_sequential,
.teardown = NULL
},
{
.name = "List Sequential",
.setup = setup_list,
.run = test_list_sequential,
.teardown = teardown_list
}
};
for (int i = 0; i < 2; i++) {
benchmark_run_with_perf(&benchmarks[i], ITERATIONS);
}
return 0;
}Ожидаемый вывод:
Benchmark: Array Sequential
Cycles: 1,234
Cache refs: 250
Cache misses: 16 (6.40%)
Benchmark: List Sequential
Cycles: 4,567
Cache refs: 1,000
Cache misses: 950 (95.00%)Анализ:
Массив: в 3,7 раза быстрее
Массив: в 15,8 меньше промахов кэша
Список: промахи кэша в 95% случаев (почти каждая операция доступа промахивается)
Подведём итог
Мы решили проблемы измерений, создав комплексный фреймворк бенчмаркинга. «Оптимизация», которая казалась быстрее, оказалась на 15% медленнее — нас подвела интуиция, но не данные. Фреймворк показал истину благодаря высокоточным таймингам, статистическому анализу и профилированию кэша.
Методики измерений:
Высокоточные тайминги (
clock_gettime(), счётчики тактов)Статистический анализ (минимум, медиана, stddev)
Анализ кэша (
perf, аппаратные счётчики)
Архитектура фреймворка:
Структура, подходящая для многократного применения
Этапы подготовки/прогонов/освобождения
Разогревающие прогоны
Множественные итерации
Распространённые сложности:
Компиляторные оптимизации (используйте
volatile)Разница между «холодным» и «тёплым» кэшем (разогревающие прогоны)
Оверхед измерений (нужно вычитать или минимизировать)
Шум системы (множественные итерации, вывод медианы)
Особенности встраиваемых систем:
Прямой доступ к аппаратным счётчикам
Анализ наихудших сценариев (максимум, P99)
Онлайн-статистика (ограниченная память)
Тайминг голой системы
В следующей главе: вооружённые нашим фреймворком бенчмаркинга, мы глубже погрузимся в массивы и узнаем, как максимизировать локальность и производительность кэша.
