Глава 13 Том 3 · Контейнеры и структуры данных: введение

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

Том 3 содержит «как хранить данные». Одиннадцать контейнеров делятся на пять групп: последовательности (массив, буфер, семейство стеков, связный список) ведают раскладкой и ходом элементов; отображения и множества (map, intmap, set) ведают «поиск по ключу» и «принадлежность»; упорядоченные структуры (две формы AVL) ведают «порядок ключей и диапазоны»; очереди (SPSC/MPSC/MPMC) ведают «передачу между потоками»; пулы (фиксированный пул, пул переменного размера) ведают «массовым взятием-возвратом объектов». Главы 14–22 разбирают каждую вплотную, глава 23 закрывает том, собирая их в карту выбора.

Четыре семейных соглашения (сначала соглашения, потом контейнеры)

Все контейнеры тома 3 разделяют четыре соглашения, установленные в главе 14 и далее прямо цитируемые. Дескриптор на стеке, память в куче: Init открывается стековым дескриптором, контейнер сам ведает буферами, Unit возвращает точно; когда сам объект контейнера обязан жить в куче — пара Create/Destroy. Чтение полями, запись функциями: доступное только для чтения состояние (Count, Size, Data) — публичные поля, нулевые накладные расходы на горячих путях; операции, способные отказать, идут через возвращаемые значения функций в паре со слотом ошибки главы 4. Отказ без побочных эффектов: неудачное редактирование оставляет контейнер нетронутым — код очистки всегда безопасен. Трёхчастная итерация: Begin/Next/End — упорядоченный снапшот; указатели не переживают итерацию, вставки-удаления во время итерации запрещены — обход map, set, AVL и пулов полностью изоморфен. Четыре соглашения удешевляют «изучение одного контейнера» с ростом их числа: глава 14 — самая дорогая, каждая следующая переиспользует.

Одна сквозная линия: владение и порядок

Глубже четырёх соглашений идёт линия владения и порядка. Владение спрашивает «кем управляют эти данные» — семантика значения (слоты массивов/отображений) отдаёт управление контейнеру целиком, интрузивный стиль (узлы списков/AVL) оставляет объект вам, а контейнер ведает только связями, владеющий стиль (AVL-контейнер) вверяет жизнь и смерть дереву, пулы ведают взятием-возвратом, арены — совместным возвратом — язык владения главы 5 приземляется в томе 3 конкретным выбором контейнера. Порядок спрашивает «в какой последовательности я обращаюсь» — индекс, порядок вставки, порядок ключей, LIFO/FIFO, приоритет; каждый контейнер обещает ровно один порядок: индекс массива, порядок вставки отображения, порядок ключей AVL, «последним пришёл — первым ушёл» стека, «первым пришёл — первым ушёл» очереди. Ответьте при выборе контейнера на эти два вопроса — и ответ в основном готов: карта выбора главы 23 разворачивает именно эти два вопроса в пути решения.

Совет по чтению

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

Одно напоминание: этот том не решает конкурентность

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

Карта знаний тома

Самопроверка обучения (перед выходом из тома)

С закрытой книгой ответьте на шесть вопросов, каждый соответствует группе контейнеров: пачку однотипных записей с частым доступом по индексу и цельной сортировкой — что взять? Байтовый поток «копить по кускам, забирать целиком» — что взять? Жизненный цикл объектов ровный, хочется возвращать вместе — каков ответ главы 7 и каков ответ этого тома, почему они не конфликтуют? При поиске по ключу «экспорт в порядке вставки» и «экспорт в порядке ключей» — какое отображение каждое? Почему хеширование бессильно для «порядка ключей + диапазонных запросов» и как выбирать между двумя формами AVL? Почему взятие-возврат ста тысяч объектов соединений отдаётся пулу, а не куче? Шесть ответов текут свободно — том 3 действительно прочитан; где запинки — перечитайте контракты соответствующих глав; шесть вопросов указывают соответственно на: массив, буфер, разделение труда арены и пула, два семейства отображений, две формы AVL, пул объектов.

Взгляд на производительность: борьба констант

Споры о производительности контейнеров — по большей части борьба констант; три постоянных константных фактора этого тома заслуживают интуиции уже сейчас. Локальность: непрерывное хранение (массивы, буферы, слоты отображений) дружелюбно к предзагрузчику, цепные структуры (списки, деревья) каждым прыжком дают шанс промаху кэша — на миллионных обходах это часто звучит громче алгоритмической сложности. Число распределений: встраивание значений (массивы, отображения) и пулинг опускают распределение с «на объект» до «на контейнер/на страницу»; интрузивный стиль обнуляет вовсе — кривые backing статистики главы 6 суть наблюдаемая граница трёх стратегий. Цена синхронизации: безблокировочные очереди тарифицируют по топологии, SPSC дешевле всех — «топология известна — бери специализированное» — дисциплина, которую том преподносит в единственном касании конкурентности. Три фактора взаимно сдерживаются при выборе: O(1) вставок-удалений списка перед локальностью кэша часто не выигрывает пересылке массива — карта главы 23 закрепит такую «контринтуицию» правилами решения, а интуиция, которую следует забрать сейчас: сначала порядок величины, потом константы, ум — в последнюю очередь.

Связи с соседними томами

Назад: система памяти тома 1 (владеющий стиль главы 5, арена главы 7) — фундамент языка владения контейнеров, статистика главы 6 — инструмент проверки их производительности. Вперёд: парсеры тома 4 собираются из стеков (кадровые) и отображений (частоты слов); конкурентная система тома 6 берёт очереди и пулы как физические носители; таблица соединений сетевого движка тома 7 — полный цвет «массив + отображение + slot_map + пул». Можно сказать, каждый контейнер тома 3 сыграет главную роль в каком-то последующем томе — узнайте их сейчас, и при встрече останется одна новая переменная: бизнес.