«В Computer Science есть только две сложные вещи: инвалидация кэша и придумывание названий», — Фил Карлтон

Оглавление

Глава 1: Разрыв в производительности

Глава 2: Иерархия памяти

Глава 3: Бенчмаркинг и профилирование

Глава 4: Массивы и локальность кэша

Глава 5: Связанные списки — убийцы кэша

Глава 6: Стеки и очереди

Глава 7: Хэш-таблицы и конфликты кэша

Глава 8: Динамические массивы и управление памятью

Глава 9: Двоичные деревья поиска

Глава 10: B-деревья и деревья, эффективно использующие кэш

Глава 11: Префиксные деревья и базисные деревья

Глава 12: Кучи и очереди с приоритетом

Глава 13: Структуры данных без блокировок

Глава 14: Обработка строк и эффективность использования кэша

Разрыв в производительности

Наш парсер логов обрабатывал 800 тысяч строк в секунду. Нам требовалось 3 миллиона строк в секунду. От нужного нам показателя мы отставали в 3,75 раза.

Задача инструмента заключалась в парсинге строк логов в реальном времени, извлечении временных меток, уровней логов и сообщений из миллионов строк в секунду. Обработка миллиона строк логов в текущей реализации требовала 1,25 секунды — слишком долго для анализа в реальном времени.

Профилировщик показывал 85 миллионов промахов кэша. Для обработки строк это казалось слишком большим показателем.

В реализации использовались стандартные строковые функции C — простые, читаемые, но, очевидно, слишком медленные:

typedef struct {
    char timestamp[32];
    char level[16];
    char message[256];
} log_entry_t;

void parse_log_line(const char *line, log_entry_t *entry) {
    // Format: "2024-12-05 10:30:45 [INFO] System started"
    char *p = strchr(line, '[');
    if (!p) return;
    
    // Извлечение временной метки
    int ts_len = p - line - 1;
    strncpy(entry->timestamp, line, ts_len);
    entry->timestamp[ts_len] = '\0';
    
    // Извлечение уровня
    char *end = strchr(p, ']');
    int level_len = end - p - 1;
    strncpy(entry->level, p + 1, level_len);
    entry->level[level_len] = '\0';
    
    // Извлечение сообщения
    strcpy(entry->message, end + 2);
}

Просто и понятно. Но медленно:

$ perf stat -e cycles,cache-misses ./log_parser_naive
  Performance counter stats:
    12,500,000,000 cycles
        85,000,000 cache-misses
        
Throughput: 800,000 lines/second

Я переписал этот код, добавив обработку строк с учётом кэша. Результаты были такими:

$ perf stat -e cycles,cache-misses ./log_parser_optimized
  Performance counter stats:
     2,800,000,000 cycles
        12,000,000 cache-misses
        
Throughput: 3,600,000 lines/second

В 4,5 раза быстрее и в 7 раз меньше промахов кэша.

В этой главе мы поговорим о том, как эффективно использовать кэш при обработке строк.

Что нам рассказывают в учебниках

Обработка строк на C проста:

• strlen(): подсчёт символов до '\0'

• strcpy(): копирование символов до '\0'

• strcmp(): сравнение, пока не будет найдено различие или '\0'

• strstr(): поиск подстроки

Алгоритмы из учебников просты и правильны. Но они не используют кэш эффективно.

Проверка реальностью: почему строковые функции медленные

1. Множественные обходы данных

Давайте рассмотрим этот распространённый паттерн:

char *trim_whitespace(char *str) {
    // Проход 1: поиск начала
    while (isspace(*str)) str++;
    
    // Проход 2: поиск конца
    char *end = str + strlen(str) - 1;
    while (end > str && isspace(*end)) end--;
    
    // Проход 3: Null-terminate
    *(end + 1) = '\0';
    
    return str;
}

Три обхода одной строки! Каждый обход — это потенциальный промах кэша.

2. Непредсказуемая длина

strlen() должна выполнять сканирование до '\0':

size_t strlen(const char *s) {
    const char *p = s;
    while (*p) p++;
    return p - s;
}

В случае 1000-символьной строки:

• Нужно сканировать 1000 байт

• ~16 линий кэша (по 64 байта каждая)

• Если строка не в кэше: 16 промахов кэша

3. Посимвольная обработка

strcmp() сравнивает по одному байту за раз:

int strcmp(const char *s1, const char *s2) {
    while (*s1 && *s1 == *s2) {
        s1++;
        s2++;
    }
    return *(unsigned char *)s1 - *(unsigned char *)s2;
}

Современные CPU могут сравнивать по 8 байт (64 бита) за раз, но strcmp() этим не пользуется.

Оптимизация 1: парсинг за один проход

Вместо множества проходов можно обрабатывать строку один раз:

void parse_log_line_optimized(const char *line, log_entry_t *entry) {
    const char *p = line;
    char *out;
    
    // Один проход: извлечение всех полей
    
    // Временная метка (до пробела перед '[')
    out = entry->timestamp;
    while (*p && *p != '[') {
        if (*p != ' ' || *(p+1) != '[') {
            *out++ = *p;
        }
        p++;
    }
    *out = '\0';
    
    // Уровень (между '[' и ']')
    if (*p == '[') p++;
    out = entry->level;
    while (*p && *p != ']') {
        *out++ = *p++;
    }
    *out = '\0';
    
    // Сообщение (после '] ')
    if (*p == ']') p++;
    if (*p == ' ') p++;
    strcpy(entry->message, p);
}

Результат:

• Старый код: 3 прохода (strchr, strchr, strcpy)

• Новый: 1 проход

• Ускорение: 2,1×

Оптимизация 2: SIMD-операции со строками

У современных CPU есть команды SIMD (Single Instruction, Multiple Data), способные одновременно обрабатывать несколько байт.

strlen() с SIMD

Оптимизированная strlen() компилятора GCC использует на x86 команды SIMD:

// Упрощённая версия strlen из glibc
size_t strlen_simd(const char *s) {
    const char *p = s;
    
    // Обработка 16 байт за раз при помощи SSE2
    while ((uintptr_t)p & 15) {  // Выравнивание до 16 байт
        if (*p == 0) return p - s;
        p++;
    }
    
    __m128i zero = _mm_setzero_si128();
    while (1) {
        __m128i data = _mm_load_si128((__m128i *)p);
        __m128i cmp = _mm_cmpeq_epi8(data, zero);
        int mask = _mm_movemask_epi8(cmp);
        
        if (mask != 0) {
            return p - s + __builtin_ctz(mask);
        }
        p += 16;
    }
}

Ускорение: для длинных строк в 4-8 раз быстрее, чем побайтовая обработка.

Векторное расширение RISC-V

У RISC-V есть векторное расширение (RVV) SIMD-операций:

# strlen с RVV
strlen_rvv:
    li      t0, 0           # length = 0
    vsetvli t1, zero, e8    # Задание длины вектора для 8-битных элементов
    
loop:
    vle8.v  v0, (a0)        # Загрузка вектора байт
    vmseq.vi v1, v0, 0      # Сравнение с нулём
    vfirst.m t2, v1         # Поиск первого совпадения
    bgez    t2, found       # Если найдено, выполняется выход
    
    add     t0, t0, t1      # length += vector_length
    add     a0, a0, t1      # ptr += vector_length
    j       loop
    
found:
    add     a0, t0, t2      # длина + позиция
    ret

Я провёл бенчмаркинг разных реализаций strlen() на RISC-V:

Тест: strlen() для 10000 строк (средняя длина: 100 байт)

Наивная побайтовая:
  Такты: 12,5 миллиона
  Промахи кэша: 850 тысяч

Оптимизированная (по слову за раз):
  Такты: 4,2 миллиона
  Промахи кэша: 320 тысяч
  Ускорение : 3,0×

RVV (векторное расширение):
  Такты: 1,8 миллиона
  Промахи кэша: 180 тысяч
  Ускорение: 6,9×

Вывод: по возможности для массовых операций со строками следует использовать SIMD/векторные команды.

Оптимизация 3: оптимизация для малых строк (Small String Optimization, SSO)

Многие строки короткие. Вместо распределения памяти кучи можно хранить короткие строки встраиваемым образом.

Проблема с распределением кучи

Стандартная std::string C++  выполняет распределение в куче:

std::string s = "hello";  // Распределяется 6 байт в куче

Затраты:

• malloc(): ~100 тактов

• Промах кэша при доступе к строковым данным

• Фрагментация

Small String Optimization

Можно хранить короткие строки (≤15 байт) внутри объекта строки:

typedef struct {
    union {
        struct {
            char *ptr;      // Указатель кучи (для длинных строк)
            size_t len;
            size_t cap;
        } heap;
        struct {
            char data[16];  // Встроенное хранение (для коротких строк)
            uint8_t len;    // Длина в младшем байте
        } sso;
    } u;
} string_t;

#define SSO_MAX 15

void string_init(string_t *s, const char *str) {
    size_t len = strlen(str);
    if (len <= SSO_MAX) {
        // Используем SSO
        memcpy(s->u.sso.data, str, len);
        s->u.sso.data[len] = '\0';
        s->u.sso.len = len | 0x80;  // Задаём старший бит, чтобы обозначить SSO
    } else {
        // Используем кучу
        s->u.heap.ptr = malloc(len + 1);
        memcpy(s->u.heap.ptr, str, len + 1);
        s->u.heap.len = len;
        s->u.heap.cap = len + 1;
    }
}

Бенчмарк

Я измерил влияние этой оптимизации на нашем парсере логов:

Тест: парсинг 1 миллиона строк логов (средняя длина сообщения: 45 байт)

Без SSO (вся куча):
  Такты: 8,5 миллиарда
  Промахи кэша: 45 миллионов
  Вызовы malloc: 3 миллиона
  Производительность: 1,2 миллиона строк/с

С SSO (сообщения ≤15 байт встраиваются):
  Такты: 5,8 миллиарда
  Промахи кэша: 28 миллионов
  Вызовы malloc: 1,8 миллиона (снижение на 40%)
  Производительность: 1,7 миллиона строк/с
  Ускорение: 1,4×

Почему это помогает:

• Для коротких строк не нужны malloc (экономия ~100 тактов на каждой)

• Повышенная локальность кэша (данные встроены)

• Меньше фрагментация памяти

Оптимизация 4: интернирование строк

Если есть много дублирующихся строк, можно сохранять каждую уникальную строку один раз и использовать указатели.

Проблема

В нашем парсере логов встречалось множество повторяющихся строк:

[INFO] System started
[INFO] System started
[INFO] System started
[ERROR] Connection failed
[ERROR] Connection failed
[INFO] System started
...

При отдельном хранении каждой строки впустую тратится память и пространство кэша.

Интернирование строк

Будем хранить уникальные строки в хэш-таблице и возвращать указатели на уже имеющиеся строки:

typedef struct {
    hash_table_t *table;  // Сопоставляем строку с интернированным указателем
} string_intern_t;

const char *string_intern(string_intern_t *intern, const char *str) {
    // Проверяем, интернирована ли уже строка
    const char *existing = hash_table_get(intern->table, str);
    if (existing) {
        return existing;  // Возвращаем имеющийся указатель
    }

    // Не найдена, добавляем в таблицу
    char *copy = strdup(str);
    hash_table_put(intern->table, copy, copy);
    return copy;
}

Теперь вместо хранения полных строк:

// До: каждый элемент хранит полную строку
typedef struct {
    char level[16];     // "INFO", "ERROR" и так далее
    char message[256];
} log_entry_t;

мы используем указатели на интернированные строки:

// После: каждый элемент хранит указатель
typedef struct {
    const char *level;    // Указывает на интернированную строку
    const char *message;
} log_entry_t;

Бенчмарк

Тест: парсинг 1 миллиона строк логов (10 уникальных уровней логов,
1000 уникальных сообщений)

Без интернирования:
  Память: 256 МБ (1 миллион × 256 байт)
  Промахи кэша: 45 миллионов

С интернированием:
  Память: 8 МБ (1 миллион × 8-байтные указатели + 50 КБ уникальных строк)
  Промахи кэша: 12 миллионов (в 3,8 раза меньше)
  Ускорение: 2,8×

Почему это помогает:

• В 32 раз меньше памяти (256 МБ → 8 МБ)

• Более оптимальное использование кэша (нужно кэшировать меньше уникальных строк)

• Сравнение строк превращается в сравнение указателей (O(1) вместо O(n))

Оптимизация 5: удобный для кэша поиск строк

Наивная strstr() слишком медленная для длинных строк, её можно оптимизировать.

Алгоритм Бойера — Мура — Хорспула

Вместо проверки каждой позиции перескакиваем вперёд на основании несовпадений:

const char *strstr_bmh(const char *text, const char *pattern) {
    size_t n = strlen(text);
    size_t m = strlen(pattern);

    if (m > n) return NULL;

    // Создаём таблицу переходов
    size_t skip[256];
    for (int i = 0; i < 256; i++) {
        skip[i] = m;
    }
    for (size_t i = 0; i < m - 1; i++) {
        skip[(unsigned char)pattern[i]] = m - 1 - i;
    }

    // Поиск
    size_t pos = 0;
    while (pos <= n - m) {
        size_t i = m - 1;
        while (i < m && text[pos + i] == pattern[i]) {
            if (i == 0) return &text[pos];
            i--;
        }
        pos += skip[(unsigned char)text[pos + m - 1]];
    }

    return NULL;
}

Бенчмарк

Тест: поиск подстроки "ERROR" в 1 миллионе строк логов (средняя длина логов: 100 байт)

Наивная strstr():
  Такты: 18,5 миллиарда
  Промахи кэша: 85 миллионов
  Производительность: 540 тысяч операций поиска/с

Бойер-Мур-Хорспул:
  Такты: 4,2 миллиарда
  Промахи кэша: 22 миллиона
  Производительность: 2,4 миллиона операций поиска/с
  Ускорение: 4,4×

Почему это помогает:

• Пропуск символов вместо проверки каждой позиции

• Улучшенное поведение кэша (меньше операций доступа к памяти)

• Алгоритм особенно быстр, если паттерн совпадает нечасто

Пример из реального мира: строковые функции ядра Linux

В ядре Linux есть высокооптимизированные строковые функции, учитывающие поведение кэша.

strcmp() со сравнением по слову за раз

Вместо побайтового сравнения за раз сравниваются 8 байт:

// Упрощённая версия strcmp ядра
int strcmp_fast(const char *s1, const char *s2) {
    unsigned long *l1 = (unsigned long *)s1;
    unsigned long *l2 = (unsigned long *)s2;

    // Сравниваем по 8 байт за раз
    while (1) {
        unsigned long w1 = *l1;
        unsigned long w2 = *l2;

        if (w1 != w2) {
            // Разница найдена, находим конкретный байт
            for (int i = 0; i < 8; i++) {
                if (((char *)&w1)[i] != ((char *)&w2)[i]) {
                    return ((unsigned char *)&w1)[i] - ((unsigned char *)&w2)[i];
                }
                if (((char *)&w1)[i] == 0) {
                    return 0;
                }
            }
        }

        // Проверяем наличие нулевого символа
        if (has_zero(w1)) return 0;

        l1++;
        l2++;
    }
}

Макрос has_zero() для обнаружения нулевых байтов использует битовые трюки:

#define ONES ((unsigned long)-1/0xFF)
#define HIGHS (ONES * 0x80)

#define has_zero(x) (((x) - ONES) & ~(x) & HIGHS)

Ускорение: в случае длинных строк в 3-5 раз быстрее, чем побайтовое сравнение.

Соединяем всё вместе: оптимизированный парсер логов

Ниже показан окончательный оптимизированный парсер логов, в котором применены все эти техники:

typedef struct {
    string_intern_t *intern;  // Для уровней логов
    char buffer[4096];        // Многоразовый буфер
} log_parser_t;

void parse_log_optimized(log_parser_t *parser, const char *line, log_entry_t *entry) {
    const char *p = line;
    char *out = parser->buffer;

    // Однопроходной парсинг

    // Извлечение временной метки (встроенной, без распределения)
    while (*p && *p != '[') {
        if (*p != ' ' || *(p+1) != '[') {
            *out++ = *p;
        }
        p++;
    }
    *out++ = '\0';
    entry->timestamp = parser->buffer;

    // Извлечение уровня (интернированного)
    if (*p == '[') p++;
    char *level_start = out;
    while (*p && *p != ']') {
        *out++ = *p++;
    }
    *out++ = '\0';
    entry->level = string_intern(parser->intern, level_start);

    // Извлечение сообщения (SSO или куча)
    if (*p == ']') p++;
    if (*p == ' ') p++;
    entry->message = p;
}

Окончательный бенчмарк

Тест: парсинг 1 миллиона строк логов

Исходный (наивный):
  Такты: 12,5 миллиарда
  Промахи кэша: 85 миллионов
  Память: 256 МБ
  Производительность: 800 тысяч строк/с

Оптимизированный (все техники):
  Такты: 2,8 миллиарда
  Промахи кэша: 12 миллионов
  Память: 32 МБ
  Производительность: 3,6 миллиона строк/с

Ускорение: 4,5×
Снижение количества промахов кэша: 7,1×
Снижение объёма используемой памяти: 8×

Подведём итог

Разрыв в производительности был ликвидирован. Теперь парсер логов обрабатывает 3,6 миллиона строк в секунду по сравнению с исходными 800 тысячами: улучшение в 4,5 раза, превысившее целевое значение в 3 миллиона строк. Количество промахов кэша упало с 85 миллионов до 12 миллионов, и парсер теперь способен выполнять анализ в реальном времени.

Основные наблюдения:

1. Однопроходность парсинга критически важна. Множественные проходы по строкам впустую тратят пропускную способность кэша. Каждый символ нужно обрабатывать только один раз.

2. SIMD/векторные команды полезны. В случае групповых операций наподобие strlen() и strcmp() SIMD способен обеспечить ускорение в 4-8 раз.

3. Small String Optimization (SSO) позволяет избавиться от распределений. В случае строк размером ≤15 байт встроенное хранение экономит ~100 тактов на строку и повышает локальность кэша.

4. Интернирование строк снижает объём используемой памяти и давление на кэш. В случае повторяющихся строк хранение каждой уникальной строки только один раз уменьшает объём занимаемой памяти в 10-100 и повышает частоту попадания кэша.

5. Сравнение по одному слову за раз происходит быстрее. Сравнение 8 байт за раз вместо 1 байта обеспечивает strcmp() ускорение в 3-5 раз.

Показатели нашего парсера логов:

• Однопроходный парсинг: ускорение в 2,1 раза

• strlen с SIMD: ускорение в 6,9 раза

• SSO: ускорение в 1,4 раза, на 40% меньше malloc

• Интернирование строк: ускорение в 2,8 раза, снижение памяти в 32 раз

• Поиск алгоритмом Бойера — Мура — Хорспула: ускорение в 4,4 раза

Обработка строк часто упирается в ограничения ввода-вывода или кэша, а не в CPU. Нужно сосредоточиться на снижении промахов кэша и распределений памяти.

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