10 мин

12K

«Задача абстракции — не быть расплывчатой, а создать новый семантический уровень, на котором можно достичь абсолютной точности», — Эдсгер Дейкстра

Оглавление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Глава 15: Графы и их обход с эффективным использованием кэша

Взрывной рост количества промахов кэша

При определении топологии сети для обхода 500 коммутаторов нашей системе требовалось 37,5 миллисекунды. Вроде бы это не так медленно, если не учитывать количество промахов кэша: 8,5 миллиона. При 500 узлах это 17 тысяч промахов на узел.

Структура данных была фундаментально неподходящей для этой задачи.

Работа инструмента была простой: определение топологии сети при помощи обхода графа соединённых устройств. У каждого коммутатора было до 48 портов, а нам нужно было при помощи поиска в ширину найти все доступные устройства из начальной точки.

Реализация была как по учебнику — список смежности со стандартным BFS:

typedef struct node {
    int id;
    struct node **neighbors;  // Массив указателей
    int num_neighbors;
} node_t;

void bfs(node_t *start) {
    queue_t *q = queue_create();
    bool *visited = calloc(MAX_NODES, sizeof(bool));
    
    queue_push(q, start);
    visited[start->id] = true;
    
    while (!queue_empty(q)) {
        node_t *node = queue_pop(q);
        process(node);
        
        for (int i = 0; i < node->num_neighbors; i++) {
            node_t *neighbor = node->neighbors[i];
            if (!visited[neighbor->id]) {
                visited[neighbor->id] = true;
                queue_push(q, neighbor);
            }
        }
    }
}

В случае сети из 500 коммутаторов (в среднем по 12 соединений у каждого) статистика была такой:

$ perf stat -e cycles,cache-misses ./network_discovery_naive
  Performance counter stats:
    45,000,000 cycles
     8,500,000 cache-misses
     
Traversal time: 37.5 ms

8,5 миллиона промахов кэша на 500 узлов? Это 17 тысяч промахов кэша на узел!

Я переписал этот код, реализовав графовое представление, учитывающее кэш. Результаты:

$ perf stat -e cycles,cache-misses ./network_discovery_optimized
  Performance counter stats:
    12,000,000 cycles
     1,200,000 cache-misses
     
Traversal time: 10 ms

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

В этой главе мы поговорим об эффективном описании и обходе графов.

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

Обычно графы описываются двумя способами:

1. Матрица смежности

2D-массив, в котором matrix[i][j] = 1, если существует ребро от узла i к узлу j:

bool adj_matrix[MAX_NODES][MAX_NODES];

// Проверка существования ребра
if (adj_matrix[u][v]) {
    // Ребро от u к v существует
}

Плюсы: поиск ребёр за O(1)
Минусы: пространство O(n²) даже в случае разреженных графов

2. Список смежности

В каждом узле хранится список его соседей:

typedef struct {
    int *neighbors;
    int num_neighbors;
} node_t;

node_t nodes[MAX_NODES];

Плюсы: пространство O(n + m) (n узлов, m рёбер)
Минусы: поиск рёбер за O(степень)

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

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

1. Следование по указателям в списках смежности

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

typedef struct edge {
    int dest;
    struct edge *next;  // Связанный список рёбер
} edge_t;

typedef struct {
    edge_t *edges;  // Указатель на первое ребро
} node_t;

Проблема: все рёбра — это отдельные распределения, разбросанные по памяти.

Обход соседей:

Узел → Ребро1 (промах кэша) → Ребро2 (промах кэша) → Ребро3 (промах кэша) ...

Для узла с 12 соседями: 12 промахов кэша всего лишь при чтении списка соседей!

2. Плохая локальность в очереди BFS

В стандартном поиске в ширину (BFS) используется очередь указателей:

queue_push(q, neighbor);  // Запись указателя в узел

Проблема: узлы обрабатываются в порядке BFS, но они разбросаны в памяти.

Очередь: [Узел5, Узел12, Узел3, Узел45, ...]
       Каждый узел находится в отдельной линии кэша!

3. Произвольный доступ к посещённому массиву

Массив visited индексируется по ID узла:

visited[neighbor->id] = true;

Если ID узлов не последовательны и не сгруппированы, то это приводит к произвольному доступу к памяти.

Оптимизация 1: компактный список смежности

Вместо использования указателей будем хранить соседей в сплошном массиве:

typedef struct {
    int *neighbors;      // Сплошной массив ID соседей
    int num_neighbors;
} node_t;

typedef struct {
    node_t *nodes;
    int *edge_data;      // Все рёбра находятся в одном массиве
    int num_nodes;
} graph_t;

graph_t *graph_create(int num_nodes, int num_edges) {
    graph_t *g = malloc(sizeof(graph_t));
    g->nodes = malloc(num_nodes * sizeof(node_t));
    g->edge_data = malloc(num_edges * sizeof(int));
    g->num_nodes = num_nodes;
    
    // Узлы указывают на массив edge_data
    int offset = 0;
    for (int i = 0; i < num_nodes; i++) {
        g->nodes[i].neighbors = &g->edge_data[offset];
        g->nodes[i].num_neighbors = /* ... */;
        offset += g->nodes[i].num_neighbors;
    }
    
    return g;
}

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

• Все рёбра находятся в смежном массиве (улучшает предварительную выборку).

• Отсутствует следование по указателям (соседи расположены последовательно).

• Более оптимальное использование кэша.

Бенчмарк

Тест: BFS с графом из 500 узлов (средняя степень: 12)

Связанный список смежности:
  Промахи кэша: 8,5 миллиона
  Такты: 45 миллионов
  
Компактный список смежности:
  Промахи кэша: 2,8 миллиона (в 3 раза меньше)
  Такты: 18 миллионов
  Ускорение: 2,5×

Оптимизация 2: кэш-независимый BFS

Стандартный BFS обрабатывает узлы уровень за уровнем, но узлы на одном уровне в памяти могут находиться далеко друг от друга.

Блочный BFS

Обработка узлов блоками размером с кэш:

#define BLOCK_SIZE 64  // Обработка 64 узлов за раз

void bfs_blocked(graph_t *g, int start) {
    bool *visited = calloc(g->num_nodes, sizeof(bool));
    int *queue = malloc(g->num_nodes * sizeof(int));
    int head = 0, tail = 0;
    
    queue[tail++] = start;
    visited[start] = true;
    
    while (head < tail) {
        int block_end = (head + BLOCK_SIZE < tail) ? head + BLOCK_SIZE : tail;
        
        // Обработка блока узлов
        for (int i = head; i < block_end; i++) {
            int node_id = queue[i];
            node_t *node = &g->nodes[node_id];
            
            process(node);
            
            // Добавление соседей в очередь
            for (int j = 0; j < node->num_neighbors; j++) {
                int neighbor = node->neighbors[j];
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue[tail++] = neighbor;
                }
            }
        }
        
        head = block_end;
    }
}

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

• Обработка набора узлов перед переходом к следующему уровню.

• Улучшенная временная локальность (многократное использование посещённого массива в кэше).

• Амортизация оверхеда очереди.

Бенчмарк

Тест: BFS с графом из 500 узлов

Стандартный BFS:
  Промахи кэша: 2,8 миллиона
  Такты: 18 миллионов

Блочный BFS (блок размером 64):
  Промахи кэша: 1,5 миллиона
  Такты: 11 миллионов
  Ускорение: 1,6×

Оптимизация 3: формат Compressed Sparse Row (CSR)

В случае очень больших разреженных графов формат CSR бывает ещё более компактным:

typedef struct {
    int *row_ptr;     // row_ptr[i] = начало соседей узла i
    int *col_idx;     // col_idx[j] = ID соседа
    int num_nodes;
    int num_edges;
} csr_graph_t;

csr_graph_t *graph_to_csr(graph_t *g) {
    csr_graph_t *csr = malloc(sizeof(csr_graph_t));
    csr->num_nodes = g->num_nodes;
    csr->num_edges = /* общее количество рёбер */;

    csr->row_ptr = malloc((g->num_nodes + 1) * sizeof(int));
    csr->col_idx = malloc(csr->num_edges * sizeof(int));

    int offset = 0;
    for (int i = 0; i < g->num_nodes; i++) {
        csr->row_ptr[i] = offset;
        for (int j = 0; j < g->nodes[i].num_neighbors; j++) {
            csr->col_idx[offset++] = g->nodes[i].neighbors[j];
        }
    }
    csr->row_ptr[g->num_nodes] = offset;

    return csr;
}

// Доступ к соседям узла i
void visit_neighbors(csr_graph_t *g, int node_id) {
    int start = g->row_ptr[node_id];
    int end = g->row_ptr[node_id + 1];

    for (int i = start; i < end; i++) {
        int neighbor = g->col_idx[i];
        // Обработка соседа
    }
}

Структура памяти:

row_ptr: [0, 3, 7, 10, ...]  (узел 0 имеет соседей по индексам 0-2)
col_idx: [1, 2, 5, 0, 3, 4, 6, ...]  (сами ID соседей)

Преимущества:

• Минимальный оверхед памяти (всего два массива).

• Последовательный доступ к соседям (превосходная упреждающая выборка).

• Удобство для кэша (все данные сплошные).

Бенчмарк

Тест: граф из 10000 узлов, 120000 рёбер

Список смежности (указатели):
  Память: 2,4 МБ
  Промахи кэша: 85 миллионов
  Время BFS: 180 мс

Формат CSR:
  Память: 0,96 МБ (в 2,5 раза меньше)
  Промахи кэша: 18 миллионов (в 4,7 раза меньше)
  Время BFS: 42 мс
  Ускорение: 4,3×

Оптимизация 4: изменение порядка узлов для обеспечения локальности

Если можно изменить порядок ID узлов, располагайте соединённые узлы ближе друг к другу в памяти.

Упорядочивание в ширину

Присваиваем ID узлов в порядке BFS:

void reorder_bfs(graph_t *g, int start) {
    int *new_id = malloc(g->num_nodes * sizeof(int));
    int *old_id = malloc(g->num_nodes * sizeof(int));
    bool *visited = calloc(g->num_nodes, sizeof(bool));

    int next_id = 0;
    queue_t *q = queue_create();
    queue_push(q, start);
    visited[start] = true;

    while (!queue_empty(q)) {
        int node = queue_pop(q);
        new_id[node] = next_id;
        old_id[next_id] = node;
        next_id++;

        // Посещаем соседей
        for (int i = 0; i < g->nodes[node].num_neighbors; i++) {
            int neighbor = g->nodes[node].neighbors[i];
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue_push(q, neighbor);
            }
        }
    }

    // Перестройка графа с новыми ID
    // ...
}

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

• Посещённые совместно узлы нумеруются последовательно.

• Улучшенная локальность кэша при обходе.

• Операции доступа к массиву посещённых узлов более последовательные.

Бенчмарк

Тест: BFS с графом из 500 узлов

Произвольные ID узлов:
  Промахи кэша: 1,5 миллиона
  Такты: 11 миллионов

ID узлов, упорядоченные по BFS:
  Промахи кэша: 0,8 миллиона
  Такты: 7,5 миллиона
  Speedup: 1.5×

Оптимизация 5: параллельный обход графа

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

BFS с синхронными уровнями

Обрабатываем каждый уровень параллельно:

void bfs_parallel(csr_graph_t *g, int start, int num_threads) {
    bool *visited = calloc(g->num_nodes, sizeof(bool));
    int *current_level = malloc(g->num_nodes * sizeof(int));
    int *next_level = malloc(g->num_nodes * sizeof(int));

    int current_size = 1;
    current_level[0] = start;
    visited[start] = true;

    while (current_size > 0) {
        atomic_int next_size = 0;

        // Обрабатываем текущий уровень параллельно
        #pragma omp parallel for num_threads(num_threads)
        for (int i = 0; i < current_size; i++) {
            int node = current_level[i];
            int start = g->row_ptr[node];
            int end = g->row_ptr[node + 1];

            for (int j = start; j < end; j++) {
                int neighbor = g->col_idx[j];

                // Атомарное check-and-set
                bool expected = false;
                if (__atomic_compare_exchange_n(&visited[neighbor], &expected, true,
                                                0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
                    int pos = __atomic_fetch_add(&next_size, 1, __ATOMIC_SEQ_CST);
                    next_level[pos] = neighbor;
                }
            }
        }

        // Замена уровней местами
        int *temp = current_level;
        current_level = next_level;
        next_level = temp;
        current_size = next_size;
    }
}

Бенчмарк

Тест: BFS с графом из 10000 узлов (8-ядерный RISC-V, 1,2 ГГц)

Последовательный BFS:
  Такты: 120 миллионов
  Время: 100 мс

Параллельный BFS (2 ядра):
  Такты: 68 миллионов
  Время: 57 мс
  Ускорение: 1,75×

Параллельный BFS (4 ядра):
  Такты: 38 миллионов
  Время: 32 мс
  Ускорение: 3,1×

Параллельный BFS (8 ядер):
  Такты: 24 миллиона
  Время: 20 мс
  Ускорение: 5,0×

Неидеальность масштабирования (ускорение в 8 раз на 8 ядрах) вызвана:

• Оверхедом синхронизации (атомарные операции).

• Дисбалансом нагрузок (на некоторых уровнях мало узлов).

• Трафиком когерентности кэша.

Но в случае больших графов улучшение всё равно получается существенным.

Пример из реального мира: базисное дерево ядра Linux для кэша страниц

В ядре Linux для кэша страниц используется базисное дерево (специализированная графовая структура).

Проблема

Ядру нужно привязывать смещения файлов к физическим страницам:

• Миллионы страниц на один файл.

• Разреженные привязки (не у всех смещений есть страницы).

• Быстрый поиск (O(log n) или лучше).

Решение: базисное дерево

64-ичное дерево, где каждый уровень представляет 6 бит смещения:

#define RADIX_TREE_MAP_SHIFT 6
#define RADIX_TREE_MAP_SIZE (1 << RADIX_TREE_MAP_SHIFT)  // 64

struct radix_tree_node {
    void *slots[RADIX_TREE_MAP_SIZE];  // 64 указателя
    unsigned long tags[3][RADIX_TREE_MAP_SIZE / BITS_PER_LONG];
};

Почему 64-ичное:

• Один узел умещается в одну линию кэша (64 указателя × 8 байт = 512 байт ≈ 8 линий кэша).

• Низкое дерево (глубина ≤ 11 при 64-битных смещениях).

• Хороший баланс между занимаемой памятью и промахами кэша.

Производительность

Поиск по базисному дереву (глубина 3):
  Промахи кэша: 3 (по одному на уровень)
  Такты: ~50

Поиск по двоичному дереву (глубина 20):
  Промахи кэша: 20
  Такты: ~300

Ускорение: 6×

Соединяем всё вместе: оптимизированное обнаружение сети

Вот финальная оптимизированная версия, объединяющая в себе все эти методики:

typedef struct {
    int *row_ptr;
    int *col_idx;
    int num_nodes;
    int num_edges;
} network_graph_t;

void discover_network_optimized(network_graph_t *g, int start) {
    // Используем битовую карту для посещённых узлов (удобно для кэша)
    uint64_t *visited = calloc((g->num_nodes + 63) / 64, sizeof(uint64_t));

    // Используем очередь на основе массива (а не связанный список)
    int *queue = malloc(g->num_nodes * sizeof(int));
    int head = 0, tail = 0;

    queue[tail++] = start;
    visited[start / 64] |= (1UL << (start % 64));

    while (head < tail) {
        // Выполняем обработку по блокам, чтобы многократно использовать кэш
        int block_end = (head + 64 < tail) ? head + 64 : tail;

        for (int i = head; i < block_end; i++) {
            int node = queue[i];
            process_device(node);

            // Последовательный доступ к соседям (формат CSR)
            int start_idx = g->row_ptr[node];
            int end_idx = g->row_ptr[node + 1];

            for (int j = start_idx; j < end_idx; j++) {
                int neighbor = g->col_idx[j];
                uint64_t mask = 1UL << (neighbor % 64);
                int word = neighbor / 64;

                if (!(visited[word] & mask)) {
                    visited[word] |= mask;
                    queue[tail++] = neighbor;
                }
            }
        }

        head = block_end;
    }

    free(visited);
    free(queue);
}

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

Тест: обнаружение сети, 500 коммутаторов, в среднем 12 соединений

Изначальный код (список смежности, связанная очередь):
  Такты: 45 миллионов
  Промахи кэша: 8,5 миллиона
  Память: 128 КБ
  Время: 37,5 мс

Оптимизированный код (CSR, блочный BFS, битовая карта):
  Такты: 7,5 миллиона
  Промахи кэша: 0,8 миллиона
  Память: 24 КБ
  Время: 6,2 мс

Ускорение: 6,0×
Снижение количества промахов кэша: 10,6×
Снижение занимаемой памяти: 5,3×

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

Взрывной рост количества промахов кэша был ликвидирован. Время обнаружения сети упало с 37,5 мс до 6,2 мс, то есть в шесть раз. Количество промахов кэша снизилось с 8,5 миллиона до 0,8 миллиона, то есть в 10,6 раза. При обходе графа число промахов кэша упало с 17 тысяч до всего 1,6 тысячи.

Основные выводы:

1. Компактные списки смежности побеждают списки на основе указателей. Хранение всех рёбер в сплошном массиве позволяет избавиться от следования по указателям и улучшает упреждающую выборку, обеспечивая ускорение в 2,5 раза.

2. Формат CSR оптимален для разреженных графов. Два массива (row_ptr и col_idx) обеспечивают минимальный оверхед памяти и превосходную работу с кэшем. Ускорение по сравнению со списками на основе указателей составляет 4,3 раза.

3. Блочный BFS улучшает временную локальность. Обработка узлов блоками размером с кэш (64 узла) позволяет многократно использовать массив посещённых узлов в кэше, обеспечивая ускорение в 1,6 раза.

4. Помогает изменение порядка узлов. Присвоение ID в порядке BFS размещает соединённые узлы близко друг к другу в памяти. Ускорение в 1,5 раза.

5. Параллельный BFS достаточно хорошо масштабируется. BFS с синхронными уровнями и атомарными операциями достигает при 8 ядрах ускорения в 5 раз (эффективность 62%).

Наши показатели обнаружения сети:

• Компактный список смежности: в 2,5 раза быстрее, чем указатели.

• Формат CSR: в 4,3 раза быстрее, занимает в 2,5 раза меньше памяти.

• Блочный BFS: в 1,6 раза быстрее.

• Порядок BFS: в 1,5 раза быстрее.

• Всё вместе: в 6 раз быстрее, в 10,6 раз меньше промахов кэша.

Обход графов упирается в объём используемой памяти. Выбирайте удобные для кэша представления и паттерны доступа.

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