Глава 23 Выбор контейнера: путь решения от требований к контейнеру

Ориентация главы

Закрывающая глава тома 3 не вводит новых контейнеров; она делает ровно одно: сжимает знания десяти предыдущих глав в исполнимый процесс выбора. Цена неверно выбранного контейнера не видна в код-ревью — она прячется в квартальном разборе «почему этот интерфейс чем дальше, тем медленнее». Глава даёт три оси решения (владение, порядок, режим доступа), одну карту решений, два сравнительных опыта, где говорят данные, и пять самых частых вопросов «вам на самом деле не нужен X» — антивыбор. После главы любая потребность организации данных должна отдавать кандидатов и способ проверки за тридцать секунд — эти «тридцать секунд» не риторика, а проходной балл упражнения один.

23.1引入

Реальная сцена: «ожидающие обработки наряды» в системе нарядов должны поддерживать три операции — брать наивысший по приоритету, смотреть детали по номеру наряда, архивировать по завершении. Каждая операция указывает на свой контейнер: приоритетную очередь, отображение, архивный массив. Ответ новичка — «найти всесильный контейнер» — его не существует; ответ ветерана — «один вопрос, одно представление»: массив хранит все наряды (авторитетные данные), отображение ведает «номер наряда → индекс» (представление локации), приоритетная обработка — линейный проход или сортировка по надобности (представление приоритета). Данные в одном экземпляре, представления строятся по надобности — это первый урок выбора: сперва авторитетное хранилище, потом представления; не гоняйтесь за всесильным контейнером.

Второй урок тоньше: выбор adjudицируется данными, не интуицией. Учебник говорит «вставка-удаление списка O(1) бьёт массив O(n)» — но в смешанной нагрузке миллионного обхода и нескольких тысяч вставок кеш-локальность массива регулярно позволяет суммарному времени обогнать список на порядок. Два сравнительных опыта главы существуют ровно для этой «контринтуитивности»: прогоните цифры на своей машине руками, и основание выбора поднимется с «слышал» до «измерил».

23.2概念

Три вопроса решают

Первый вопрос урезает кандидатов вдвое: жизненный цикл равномерен → арена (не вопрос контейнера); равновеликие объекты часто берутся и возвращаются → пул; объекты должны самоподдерживаться (многовидность, на стеке, в пуле) → интрузивные или значимые контейнеры с дескрипторами; контейнер в полном распоряжении → значимые контейнеры. Второй режет ещё вдвое: по индексу → массив; по порядку вставки → map/set; по ключам и диапазонам → AVL; LIFO → семейство стеков; FIFO → очереди. Третий решает среди оставшихся по жару: обходо-жарко — непрерывное хранение, локационно-жарко — отображение, вставка-удаление жарко — вопрос, держите ли вы уже узел, межпотоково — только очереди.

Карта решений

Пять вопросов антивыбора (мантры ревью)

Пять частых заблуждений, каждое стоит назвать; они же годятся мантрами ревью — услышали фразу, задайте соответствующие три вопроса. «Нужен универсальный контейнер» — не существует; авторитетное хранилище + представления и есть ответ (см. Введение). «Список быстро вставляет-удаляет» — предпосылка: вы уже держите узел; поиск узла по индексу O(n) и локальность хромает. «Хеширование всегда быстрее всех» — на целочисленных ключах xintmap быстрее, а на потребности порядка ключей хеширование попросту не отвечает. «Сперва блокировка, для спокойствия» — межпотоковая передача на очередях, локация на осколках; блокировка — последнее средство тома 6, не первая реакция. «Пул лечит всё» — короткоживущие объекты с ровным жизненным циклом принадлежат арене; пул ведает «частым взять-вернуть»; при семантическом сдвиге не годится ни тот, ни другой. Общий корень пяти: контейнер как вера, а не инструмент — карта и заменяет веру процессом.

Как adjudицировать споры констант

Сложность даёт порядок величины; константы решают исход; инструмент adjudикации один — измерение, и вердикт измерения принадлежит вашей нагрузке и вашей машине; сменили пропорцию — перемеряйте. Метод: зафиксируйте масштаб данных (скажем, миллион элементов), зафиксируйте смесь операций (скажем, 90% обхода + 10% вставок-удалений), хронометрируйте xrtNow (возвращает миллисекунды xtime, глава 3), каждый кандидат три раза, берите медиану — толерантная мысль Near главы 10 применима и к чтению цифр производительности. Статистика главы 6 добавляет доказательство с памяти: счётчики выделений и прокси попаданий кеша (тысяч в секунду) читаются вместе; одно время вводит в заблуждение о причинах.

23.3示例

Сравнительный опыт один: массив против списка — кто берёт при обходо-горячей нагрузке

/* race_list.c —— сравнение: обход миллиона узлов + тысяча вставок-удалений */
#define XRT_MODULE_ALL
#define XRT_IMPLEMENTATION
#include <xrt.h>
#include <stdio.h>

typedef struct node { int Value; struct node* Next; } node;

int main(void)
{
	xarray tArray;
	node* pChain = NULL;
	xtime t0, t1;
	long long iSum = 0;

	xrtArrayInit(&tArray, sizeof(int));
	for ( int i = 0; i < 1000000; ++i ) {
		int v = i;
		xrtArrayPush(&tArray, &v);
	}
	for ( int i = 0; i < 1000000; ++i ) {
		node* p = (node*)xrtMalloc(sizeof(node));
		p->Value = i; p->Next = pChain; pChain = p;
	}

	t0 = xrtNow();
	for ( size_t i = 0; i < tArray.Count; ++i ) {
		iSum += *(int*)xrtArrayGet(&tArray, i);
	}
	t1 = xrtNow();
	printf("array scan: %lld us (sum=%lld)\n",
		(long long)(t1 - t0), iSum);

	iSum = 0;
	t0 = xrtNow();
	for ( node* p = pChain; p != NULL; p = p->Next ) {
		iSum += p->Value;
	}
	t1 = xrtNow();
	printf("list  scan: %lld us (sum=%lld)\n",
		(long long)(t1 - t0), iSum);

	while ( pChain != NULL ) {
		node* p = pChain->Next;
		xrtFree(pChain);
		pChain = p;
	}
	xrtArrayUnit(&tArray);
	return 0;
}

Что только что произошло. Обе структуры вмещают тот же миллион целых, суммы сходятся. Массив — один непрерывный кусок памяти; аппаратный предзагрузчик превращает обход в конвейер; каждый прыжок списка — потенциальный промах кеша — миллион прыжков, миллион «подожди память». «O(1) вставки-удаления» списка из учебника вам не соврало, но вставки — одна тысячная вашей нагрузки: константа горячей операции и есть переменная решения. Поднимите долю вставок-удалений до 50% и перезапустите — разрыв сузится; за каждой клеткой карты решений должна стоять такая таблица с вашей машины.

Сравнительный опыт два: линейный поиск массива против локации отображением

/* race_lookup.c —— сто тысяч записей, сто тысяч поисков по ключу */
#define XRT_MODULE_ALL
#define XRT_IMPLEMENTATION
#include <xrt.h>
#include <stdio.h>

typedef struct item { int Key; int Value; } item;

static item Items[100000];

int main(void)
{
	xmap tMap;
	xtime t0, t1;
	long long iSum = 0;

	for ( int i = 0; i < 100000; ++i ) {
		Items[i].Key = i * 7;
		Items[i].Value = i;
	}
	xrtMapInit(&tMap, sizeof(int));
	for ( int i = 0; i < 100000; ++i ) {
		int Key = Items[i].Key;
		xrtMapGetOrAdd(&tMap, (xbytesview){ &Key, sizeof(Key) }, NULL);
	}

	t0 = xrtNow();
	for ( int i = 0; i < 100000; ++i ) {
		int Key = i * 7;
		for ( size_t j = 0; j < 100000; ++j ) {
			if ( Items[j].Key == Key ) {
				iSum += Items[j].Value;
				break;
			}
		}
	}
	t1 = xrtNow();
	printf("array linear: %lld us (sum=%lld)\n",
		(long long)(t1 - t0), iSum);

	iSum = 0;
	t0 = xrtNow();
	for ( int i = 0; i < 100000; ++i ) {
		int Key = i * 7;
		int* pValue = (int*)xrtMapGet(
			&tMap, (xbytesview){ &Key, sizeof(Key) });
		if ( pValue != NULL ) {
			iSum += *pValue;
		}
	}
	t1 = xrtNow();
	printf("map lookup  : %lld us (sum=%lld)\n",
		(long long)(t1 - t0), iSum);
	xrtMapUnit(&tMap);
	return 0;
}

Что только что произошло. Те же сто тысяч поисков по ключу: линейный проход массива — O(n) каждый — суммарно десятки миллиардов операций; отображение — амортизированные O(1) за раз. Разрыв в три порядка уже не «спор констант», а вопрос порядка величины — за правилом карты «локационно-жарко → отображение» стоит именно эта таблица. Следите за честностью сравнения: отсортируй массив и ищи делением — разрыв сожмётся до порядка; сравнительный опыт обязан дать каждому кандидату его сильнейшую форму, иначе вы меряете соломенное чучело.

Том 3 закрывается: от клеток к интуиции

Конечная точка карты выбора — не заученные клетки, а вживление их в интуицию — знак готовности: читая описание потребности, вы автоматически видите «куда авторитетное хранилище, куда представления, какая операция несёт жар», за тридцать секунд называете кандидатов и способ проверки и знаете, какой вопрос антивыбора скорее всего подстерегает. К этому моменту одиннадцать контейнеров тома 3 — уже не одиннадцать инструментов, а мысленная карта под рукой: разбор тома 4, конкурентность тома 6 и сеть тома 7 достраивают этажи всё на той же карте.

23.4契约

• Три вопроса решают: владение → порядок → режим; отсеивайте кандидатов в этом порядке.
• Авторитетное хранилище + представления: данные в одном экземпляре, представления по надобности; отказ от всесильных контейнеров.
• Измерение adjudицирует: фиксированный масштаб и смесь, медиана из трёх, доказательство с памяти рядом (статистика главы 6); каждому кандидату сильнейшую форму — соломенных чучел не бить.
• Пять вопросов антивыбора: универсальный контейнер / вставка-удаление списка / хеширование всегда быстрее всех / сперва замок / пул лечит всё — у каждого на карте отмечен ответ-замена.
• Граница конкурентности: кроме очередей, контейнеры тома не потокобезопасны; межпотоковые ответы — в томе 6 — несите границу на этапе проектирования, а не переделкой при конкурентизации.

Комбинации: три высокочастотных архитектурных наброска

Поверх клеток карты в реальных проектах повторяются три «многоконтейнерные комбинации», стоит запомнить целиком. Менеджер ресурсов: фиксированный пул с объектами (авторитетное хранилище) + xmap для локации по ключу + интрузивный список для порядка свежести (LRU/очистка) + slot_map, раздающий дескрипторы с поколением — четыре контейнера, по клетке каждый, складывающиеся в целую систему «взять-вернуть, локализовать, упорядочить, сослаться»; таблица соединений главы 67 — её конкурентная версия в масштабе. Рабочая зона парсера: фиксированный стек как стек кадров (глубина ограничена границами ресурсов) + арена для временных фрагментов (уборка по области видимости) + xmap как таблица символов (экспорт сообщений об ошибках в порядке вставки) — глава 31 тома 4 употребит это в исходном виде. Поток событий: два яруса SPSC последовательно (сбор → агрегация → обработка) + фиксированный пул на стороне агрегации, переиспользующий объекты событий — потоки журналов и мониторинга тома 6 — готовое изделие этого скелета. Общая нить трёх набросков: ни одного «умного» выбора контейнера — всё естественный исход трёх отвеченных вопросов; это и есть конечное состояние, с которым глава хочет вас отпустить: выбор — не вдохновение, а процесс.

Когда рефакторить выбор контейнера

Выбор контейнера — не одноразовый. Три сигнала означают возврат к карте: переход порядка величины (данные с тысяч доросли до миллионов — линейный поиск массива из незаметного стал узким местом; цифры опыта два — прививка заранее); дрейф режима доступа (страница, бывшая обходо-доминированной, обрела высокочастотную локацию — добавить представление дешевле, чем переписывать авторитетное хранилище); конкурентизация (однопоточный модуль делится между потоками — все ответы, кроме очередей, в томе 6; не тащите на уровне контейнеров). Внесите три сигнала в чек-лист технического долга — и контейнерный долг не «растёт молча до взрыва позиции».

Типичные ошибки

/* Нужна: локация по ключу + экспорт в порядке ключей. Инерция: я умею списки */
xlist Pending;   /* локация O(n), без порядка - оба требования не выполнены */

/* Три вопроса: владение = объекты самоподдерживаются; порядок = ключи; режим = локация + диапазон */
/* Ответ: интрузивный AVL (объекты существуют, добавить поле-узел и подвесить) */
xavl ByKey;

if ( Complexity == "O(1)" ) {
	Choose(It);          /* вставка-удаление списка O(1) -> выбран список, обходо-горячая нагрузка бьёт наотмашь */
}

/* фиксируем масштаб и смесь, оба кандидата по три раза, медиана, выбор цифрами */
Benchmark(候选A, 负载);
Benchmark(候选B, 负载);
Choose(winner_by_measurement);

Практические задания

Итоги