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, чтобы передавать сведения о типе…