Проблема измерений

Узнав из Главы 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: загрузки данных кэша L1

  • L1-dcache-load-misses: промахи загрузок данных кэша L1

  • LLC-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)

  • Онлайн-статистика (ограниченная память)

  • Тайминг голой системы

В следующей главе: вооружённые нашим фреймворком бенчмаркинга, мы глубже погрузимся в массивы и узнаем, как максимизировать локальность и производительность кэша.