Hacker News Digest

Моя предыдущая статья о обобщённых структурах данных в C готовила почву к теме: структура, которая заменяет динамические массивы, даёт стабильные указатели и хорошо работает с аренными аллокаторами. Её переоткрывали много раз под разными именами: “levelwise-allocated pile” (2001), в Zig — Segmented List, частично похожая на C++ std::deque. Мне нравится название Per Vognsen — Segment Array.

Скачать мой однофайловый заголовок segment_array.h можно, подписавшись на рассылку.

Идея проста: фиксированный массив указателей на сегменты; каждый следующий сегмент вдвое больше предыдущего; новые сегменты выделяются по мере необходимости. Поскольку элементы не двигаются, указатели на них стабильны, не остаются “дыры” в арене, а доступ по индексу — за O(1).

Реализация

Структура на C:

typedef struct { u32 count; int used_segments; u8 *segments[26]; } SegmentArrayInternal;

Почему всего 26 сегментов? Из 64 бит указателя обычно реально используются 48, так что 49 сегментов уже перекрывают адресное пространство (~256 ТиБ). Я предпочитаю индекс u32 (до ~4 млрд элементов) — это даёт 32 сегмента. Ещё убираем 6 маленьких (1..32), начинаем с 64, остаётся 26 сегментов — хватает для 4 294 967 232 элементов (чуть меньше UINT32_MAX). Фиксированный массив рядом со структурой снижает риск промаха кэша.

Размеры сегментов — степени двойки: проще математика и быстрые сдвиги для индексов.

#define SMALL_SEGMENTS_TO_SKIP 6

#define log2i(X) ((u32) (8*sizeof(unsigned long long)
- __builtin_clzll((X)) - 1))

u32 capacity_for_segment_count(int segment_count) { return ((1 << SMALL_SEGMENTS_TO_SKIP) << segment_count) - (1 << SMALL_SEGMENTS_TO_SKIP); }

void *_sa_get(SegmentArrayInternal sa, u32 index, size_t item_size) { int segment = log2i((index >> SMALL_SEGMENTS_TO_SKIP) + 1); u32 slot = index - capacity_for_segment_count(segment); return sa->segments[segment] + item_sizeslot; }

log2i использует __builtin_clzll (подсчёт ведущих нулей) для быстрого вычисления номера сегмента.

Clang оптимизирует _sa_get до ~10 инструкций x86-64 (-O3), так что узким местом будет память, а не вычисления индекса. При последовательной итерации можно обходить сегменты напрямую; в segment_array.h есть макрос.

Выделение нового элемента:

u32 slots_in_segment(int segment_index) { return (1 << SMALL_SEGMENTS_TO_SKIP) << segment_index; }

void *_sa_alloc(SegmentArrayInternal *sa, size_t item_size) { if (sa->count >= capacity_for_segment_count(sa->used_segments)) { size_t segment_size = item_size * slots_in_segment(sa->used_segments); sa->segments[sa->used_segments++] = malloc(segment_size); } sa->count++; return _sa_get(sa, sa->count-1, item_size); }

Замечание: можно сделать ёмкость строго степенью двойки, если первые два сегмента одинакового размера. Код станет менее изящным, но это спасает от ~50% потерь памяти при использовании как массива бакетов в хеш-таблице со степенью двойки.

Дженерики

Я применяю технику из прошлой статьи для типобезопасного хранения любого типа. Макрос связывает тип с общей структурой:

#define SegmentArray(type)
union {
SegmentArrayInternal internal;
type *payload;
}

Дальше макросы используют payload, чтобы передавать сведения о типе…

• Обсуждается структура «сегментированный массив» (экспоненциальные сегменты), её плюсы и минусы, и сравнение с существующими решениями: std::deque, ropes, Zig std.SegmentedList, rust-array-stump, plf::colony.
• Критика терминологии: это не «массив» в классическом смысле из‑за неконтигуозной памяти; многие API ожидают сплошной/страйдовый буфер и не подойдут.
• Производительность: при локальных L1-итерациях вычислительная часть индексации может быть ощутима; для больших объёмов память становится бутылочным горлышком. Предлагаются оптимизации итерации по сегментам и замечания про clz/bsr/lzcnt и опции компилятора.
• Виртуальная память как альтернатива: резервирование большого диапазона и по мере роста коммит страниц/guard pages; отмечены плюсы на Linux (MAP_POPULATE, mremap), но плохо для embedded/WASM.
• Сравнение с deque: фиксированные блоки vs экспоненциальные, поддержка prepend, рандом-доступ есть; реализация MSVC критикуется за малый размер блока, GNU/libc++ лучше.
• Недостатки сегментов: ухудшение предвыборки/кэш-локальности при линейной итерации, отсутствие стабильной непрерывности для API, сложность с хеш-таблицами при росте (rehash), потенциальный перерасход памяти при экспоненциальных размерах.
• Предложения: настраиваемый минимальный размер сегмента, функции «склейки» мелких сегментов, разбор условий, когда экспоненциальные сегменты оправданы, и замечания о чрезмерной макротрюковости в C/C23.

I remember that when I was first learning Spanish in high school, I found a piece of (Windows) software that pelted you with a series of pairs of an infinitive and a tense, and you had to conjugate the infinitive accordingly. (Spanish conjugation typically changes the end of the