Массив или указатели: как выбрать представление дерева по памяти и скорости в 2026 году

Короткий ответ: что выбрать для дерева в 2026 году

Берите массив, когда дерево статично или меняется редко, а нагрузка сводится к обходу, поиску и сканированию диапазона. Указатели берите, когда структура живая: узлы появляются, исчезают и переподвешиваются тысячи раз в секунду, а позиция вершины в памяти заранее неизвестна.

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

Арифметика для 64-битной системы. Указатель занимает 8 байт. По правилам System V ABI структура принимает выравнивание своего наибольшего поля, а её размер кратен этому выравниванию: узел с двумя указателями и ключом int получает выравнивание 8 и размер 24 байта, причём часть байт уходит на отступы. Узел, записанный тремя int32-полями, даёт 12 байт без отступов. На 10 млн узлов это порядка 240 МБ против 120 МБ, а с накладными расходами аллокатора разрыв растёт.

Об источнике цифр. Мы даём расчётные модели, а не результаты сторонних исследований: подтверждённых публичных замеров именно под эту задачу в переданных нам материалах нет. Числа по памяти выводятся из sizeof и правил выравнивания, их проверяют одной строкой на своей платформе. Числа по времени зависят от процессора, памяти и компилятора, поэтому их нужно снимать своим бенчмарком, а не переносить из статьи.

Почему представление дерева вообще влияет на память и скорость

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

Локальность данных и кэш процессора

Процессор читает память кэш-линиями по 64 байта. Если узлы лежат рядом, одна линия отдаёт сразу 5 узлов по 12 байт, и следующий шаг обхода почти всегда попадает в уже загруженные данные. Если узлы разбросаны, каждая линия отдаёт один узел, остальные 40 с лишним байт уходят впустую.

Порядок задержек по опубликованным бенчмаркам: попадание в L1 около 1 нс (порядка 1,0–1,3 нс в замерах на Kaby Lake и Haswell), попадание в DRAM примерно 60–100 нс. Это разрыв в десятки раз, а не в два порядка, но и его достаточно: бюджет времени обхода определяется не арифметикой, а числом промахов. Для ориентира промежуточные уровни: попадание в L2 около 4–5 нс, в L3 около 13–17 нс. Аппаратный префетчер тянет данные вперёд, когда видит последовательный поток адресов, и не помогает при переходах по указателям, потому что следующий адрес известен только после чтения текущего узла.

Посчитаем трафик для обхода 1 млн узлов. Массив из 12-байтовых узлов занимает 12 МБ, это около 187 500 кэш-линий, прочитанных по порядку. Указатели при разбросе по куче дают до 1 млн обращений к разным линиям, то есть до 64 МБ трафика. Схема хранения влияет на кэш и в других задачах: порядок обхода многомерных массивов меняет скорость циклов по той же причине, и там этот эффект разобран с формулами адресации.

Накладные расходы указателей

Первый источник расходов - сами адреса. Два указателя на детей это 16 байт из 24 у типового узла, то есть две трети структуры заняты навигацией. Индексы int32 на те же роли занимают 8 байт и позволяют адресовать 2 млрд вершин, чего хватает почти для любой практической задачи.

Второй источник - аллокатор. Каждый вызов malloc добавляет служебный заголовок чанка и округляет размер до собственного выравнивания, поэтому реально занятая память на узел выше, чем sizeof. Точный размер накладных расходов зависит от реализации аллокатора и версии glibc: проверяйте его на своей платформе через massif или mallinfo, а не переносите из статьи. На 10 млн вершин даже несколько лишних байт на узел превращаются в десятки мегабайт против 120 МБ у массива с int32-индексами.

Третий источник - фрагментация. Дерево, которое долго живёт и перестраивается, оставляет в куче дыры разного размера; вставка новой вершины может упереться в отсутствие подходящего свободного блока, хотя суммарно память есть. Пул памяти или арена решают эту проблему: узлы выдаются блоками по тысячи штук, и накладные расходы на вершину падают до долей байта. Как считать фактический объём вместе с заголовками и оверхедом аллокатора, разобрано в материале про измерение памяти под массивы и профилирование.

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

Ниже методика, по которой вы воспроизведёте сравнение у себя, и расчётные ориентиры. Готовых чужих цифр под эту задачу мы не приводим по причине, указанной выше: разброс между платформами слишком велик, чтобы переносить результаты.

Методика замеров и инструменты

Компиляторы: gcc 13 и clang 18, флаги -O2 -march=native, для чистоты ещё раз с -O0 и -O3. Время снимайте через clock_gettime с CLOCK_MONOTONIC и делайте не меньше пяти прогонов, отбрасывая первый как прогрев.

Размер узла проверяется до запуска бенчмарка:

printf("%zu\n", sizeof(struct Node));
printf("%zu\n", sizeof(int) * 3);

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

struct Node { struct Node *left; struct Node *right; int key; };
int left[N]; int right[N]; int key[N];

Обход в массиве выражается циклом по индексам, отсутствие ребра кодируется значением -1. Пиковую память процесса смотрите так:

/usr/bin/time -v ./tree_bench --nodes=10000000 --layout=array
valgrind --tool=massif --pages-as-heap=yes ./tree_bench --nodes=10000000 --layout=ptr
ms_print massif.out.12345

Счётчики кэша снимайте через perf:

perf stat -e cache-references,cache-misses,LLC-load-misses,dTLB-load-misses ./tree_bench --nodes=10000000 --layout=ptr

Для точной картины промахов на узел подойдёт valgrind --tool=cachegrind --branch-sim=yes. Учтите, что симулятор замедляет программу в десятки раз, поэтому размер дерева для него берите на два порядка меньше. Дополнительно измерьте миграцию: на NUMA-системе привяжите процесс к сокету через numactl --cpunodebind=0 --membind=0, иначе часть промахов окажется обращением к памяти соседнего сокета с задержкой примерно в полтора-два раза выше.

Результаты: память

Таблица считается из sizeof и правил выравнивания для 64-битной платформы, N = 10 000 000 вершин. Столбец с учётом malloc даёт нижнюю оценку: точные накладные расходы зависят от аллокатора.

Отдельный пункт про TLB. Массив на 10 млн 12-байтовых узлов занимает 120 МБ, это около 30 000 страниц по 4 КБ. Кэш трансляций второго уровня у современных ядер имеет ограниченную ёмкость: например, у Sandy Bridge это 1024 записи, а у актуальных ядер структура TLB описана в разделах «Cache and Memory Subsystem» документации Intel SDM, и точное число записей зависит от поколения. Поэтому обход по всей структуре упирается в промахи TLB. Страницы по 2 МБ сокращают число записей на порядки, и промахи TLB практически исчезают. Для массива это включается через mmap с флагом MAP_HUGETLB или madvise(MADV_HUGEPAGE), для узлов в куче такой трюк не работает.

Результаты: скорость

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

Ключевая асимметрия: на обходе и поиске массив почти всегда впереди, потому что выигрывает на промахах кэша и на TLB. На вставке в середину массива вы платите копированием, и с ростом дерева этот счёт уходит в линейный. Если дерево перестраивается постоянно, выигрыш указателей будет заметен на больших N, а на десятках тысяч узлов разница утонет в шуме.

Когда массив выигрывает, а когда проигрывает

Граница проходит по частоте модификаций и по тому, нужно ли хранить адрес вершины между операциями. Всё остальное вторично.

Сценарии, где массив даёт выигрыш

• Префиксное дерево для автодополнения: дети лежат в непрерывном словаре переходов, обход идёт по маленькому блоку, который целиком умещается в L1 или L2.
• Двоичная куча в планировщике задач: родитель и дети связаны арифметикой индексов, вставка идёт в конец, просеивание читает две соседние линии.
• Сегментное дерево над массивом значений: 2N узлов в одном блоке, запросы читают логарифмическое число линий вместо случайных переходов.
• Индекс, который строится один раз при старте и живёт до рестарта: обновления редки, а запросов миллионы.
• Дерево, которое нужно передать в другой процесс, записать на диск или отправить по сети куском памяти. Сериализация массивов и выравнивание структур требуют меньше работы, когда нет россыпи указателей, которые нельзя сохранить напрямую.

Сценарии, где указатели незаменимы

• Абстрактное синтаксическое дерево компилятора: узлы создаются по мере разбора, типы различаются, обход идёт один раз после парсинга.
• Красно-чёрное дерево или дерево с балансировкой: ротации переставляют связи десятки раз на тысячу вставок, и копировать массив на каждую ротацию слишком дорого.
• Структуры с указателями на родителя, на внешние объекты и на разделяемые поддеревья: индексов не хватит, нужны адреса.
• Дерево, живущее в куче рядом с другими объектами и изменяющее размер непредсказуемо.

Как выбрать представление дерева под вашу задачу: чек-лист

Пройдите пункты по порядку, каждый ответ сужает выбор.

1. Оцените долю вставок и удалений. Больше десяти процентов от операций и в середину структуры - берите указатели или гибрид.
2. Оцените долю обходов и поиска. Если обход занимает больше 90 процентов времени работы, массив выигрывает почти всегда.
3. Посчитайте бюджет памяти. Умножьте sizeof узла на ожидаемое число вершин и добавьте запас на накладные расходы аллокатора, если узлы живут в куче.
4. Проверьте, есть ли верхняя граница размера. Если да, массив можно зарезервировать целиком или выдавать блоками из пула.
5. Соберите прототип на 10 млн вершин и прогоните perf stat с cache-misses. Выводы по вашей нагрузке важнее любой таблицы.
6. Учтите особенности языка и рантайма, они описаны ниже.

Матрица выбора: сценарий → рекомендация

Влияние стека и языка

В C и C++ доступны оба варианта: массив int-индексов и узлы через malloc. Если дерево небольшое и живёт внутри одной функции, узел-массив можно положить на стек, но при десятках миллионов вершин стек переполнится, и единственный путь - куча. Когда массив размещать на стеке, а когда в куче, разбирается отдельно в материале про размещение массивов на стеке и в куче.

Rust: Vec<Node> с индексами и новым типом для идентификатора вершины заменяет сырые указатели и снимает вопросы с временем жизни. Вариант Box<Node> удобнее для рекурсивных обходов, но каждое дерево превращается в россыпь аллокаций; Rc<RefCell> добавляет счётчик ссылок и проверку заимствования в рантайме.

Go: срез структур работает как массив, но интерфейсы и указатели на структуры означают отдельные объекты в куче и работу сборщика мусора. Дерево на индексах в []Node даёт сборщику один живой объект вместо миллионов.

Java и Python: скрытые заголовки объектов и упаковка примитивов делают разрыв по памяти ещё больше, чем в C. В 64-битной HotSpot JVM заголовок обычного объекта это mark word (8 байт) плюс klass word (4 байта) и выравнивающий padding, то есть минимум 16 байт; у массива в заголовок добавляется ещё 4 байта длины. Поэтому массив int на 10 млн элементов занимает около 40 МБ, а 10 млн объектов Node с двумя ссылками - заметно больше сотен мегабайт. Для Python на таких объёмах дерево из объектов почти всегда требует перехода на numpy-массивы или бинарный формат.

Актуальность в 2026 году: что изменилось

Фундамент не изменился: время доступа к DRAM по-прежнему в десятки раз больше времени доступа к L1, и этот разрыв не сокращается так быстро, как растёт число ядер. Изменились детали, которые стоит учесть.

Кэши выросли. У серверных процессоров третьего уровня десятки и сотни мегабайт: например, у флагманского Intel Xeon 6900P заявлен L3 объёмом 504 МБ. Этого хватает, чтобы удержать в кэше дерево на несколько миллионов узлов целиком. Это уменьшает разрыв на средних размерах, но не отменяет его на больших: как только структура перестаёт помещаться в L3, преимущество последовательного доступа возвращается.

Память стала быстрее и шире: современные серверные платформы, такие как Xeon 6700P, поддерживают DDR5, PCIe 5.0, CXL и AMX. Пропускная способность выручает последовательный поток и почти не помогает при переходах по указателям, потому что задержка доступа к DRAM остаётся высокой.

NUMA остаётся фактором. На двухсокетной машине обращение к памяти соседнего узла добавляет заметную задержку, и обход по разбросанным узлам получает её на каждом промахе. Массив, привязанный к сокету через membind, ведёт себя предсказуемее.

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

Итоги и рекомендации

Массив - для статики, обходов, поиска и жёстких требований к памяти. Указатели - для живых деревьев с частыми перестройками и сложными связями. Гибрид, массив структур с int32-индексами вместо адресов, закрывает большую часть случаев, где нужны и быстрый обход, и вставки.

Практический порядок действий: начните с массива индексов, замерьте свой сценарий через perf stat с cache-misses, и только если вставки и удаления в середину съедают больше десятой части времени, переходите на узлы в куче с пулом памяти. Пул обязателен, иначе вы обменяете скорость обхода на фрагментацию и рост RSS.

Перед сменой представления в проде соберите контрольные точки: пиковый RSS по massif, число промахов кэша на операцию, время обхода на 1, 10 и 100 млн узлов, задержку вставки под нагрузкой. С этими четырьмя числами решение перестаёт быть вопросом вкуса.

Источники

• Язык программирования Си: размещение структур и их полей — правила выравнивания и размеры структур (System V ABI).
• Как Rust обрабатывает repr и ABI на границе с C — выравнивание полей структур на x86-64.
• Smarter CPU Testing: Kaby Lake и Haswell, задержки памяти — задержки L1, L2, L3 и DRAM.
• Sandy Bridge: Setting Intel's Modern Foundation — структура TLB и задержки промахов.
• Taking a page from the kernel's book: a TLB issue — устройство TLB у современных ядер и Intel SDM.
• Intel Xeon: поколения, сравнение и выбор процессора — L3 504 МБ у Xeon 6900P, поддержка DDR5, PCIe 5.0, CXL и AMX у Xeon 6700P.
• Memory Layout of Objects in Java — заголовки объектов и массивов в HotSpot JVM.