Почему O(1) проигрывает O(n): структуры данных в Go на реальном железе

Объясню структуры данных через очередь в поликлинике, а потом покажу, где эта аналогия ломается: почему связный список с «вставкой за O(1)» в прикладном Go обычно проигрывает обычному массиву.

Спойлер: асимптотика здесь не ошибается. Ошибается вывод, который мы из неё делаем.

Статья для тех, кто асимптотику знает, но не проверял её замером.

Очередь

Сидишь в очереди к врачу. Номерка нет, ты знаешь одно: за кем занимать.

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

type patient struct {
    name string
    next *patient // «а я за вами»
}

Найти в такой очереди конкретного человека можно только пройдя её от соседа к соседу: двадцать человек — двадцать вопросов «вы последний?». Это O(n). Запомнил ещё и того, кто занял после тебя, — получился двусвязный список: ходить можно в обе стороны, и человека можно выдернуть, не обходя очередь заново, — но только если ты уже стоишь рядом с ним. Найти его всё равно придётся обходом.

Стулья

В коридоре стоят стулья, и они пронумерованы. «Третий стул» — идёшь и садишься, никого не спрашивая.

Это массив — в аналогии. В Go на практике здесь обычно будет слайс, элементы которого лежат в непрерывном backing array, и всё сказанное дальше про локальность относится именно к нему. Адрес элемента считается арифметикой: начало плюс номер, умноженный на размер. Один переход, что для третьего стула, что для три тысячи двести седьмого.

seats := make([]string, 40)
seats[3] = "Иванов"
who := seats[3] // сразу, без обхода

Цена — в том, что стулья прикручены к полу: посадить кого-то в середину ряда можно только сдвинув всех, кто правее.

Бабуля

А потом заходит бабуля.

Она помнит всех. Кто в синей куртке, кто с папкой, кто отошёл покурить, кто «я только спросить». Спрашиваешь «а Петрова кто?» — отвечает сразу, не пересчитывая очередь.

Бабуля — это hash map. Ключ (примета) превращается в число, число указывает, где искать, дальше остаётся проверить пару кандидатов.

byName := make(map[string]*patient, len(all))
for _, p := range all {
    byName[p.name] = p
}

p := byName["Петров"] // сразу, без прохода по очереди

Пока ты бежишь по очереди от соседа к соседу за O(n), бабуля уже всё знает.

Где Big O перестаёт помогать

В учебнике написано: вставка в связный список — O(1), в массив — O(n). Вывод как будто очевиден: вставляем часто — берём список.

Я такой вывод делал. Для прикладного Go он часто оказывается неверным.

Асимптотика отвечает на вопрос, как растёт время с размером данных. Она не говорит, сколько стоит одна операция. А разница в цене между «сдвинуть непрерывный кусок памяти» и «перейти по указателю в непредсказуемое место» — та часть, которой в формуле нет вообще.

Соседи

Процессор не читает память по одному байту. Он тянет её блоками — кеш-линиями. Размер линии зависит от микроархитектуры, а не от системы команд. На машине, где сделаны замеры (Apple M3 Pro), sysctl hw.cachelinesize отвечает 128 байт; на большинстве x86-64 будет 64. Стенд целиком — в конце статьи.

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

Для связного списка — наоборот. Узел такой формы на 64-битной платформе занимает 16 байт:

type node struct {
    val  int64  // 8
    next *node  // 8
}
// unsafe.Sizeof(node{}) == 16

В кеш-линию их влезает восемь. Но лежат ли рядом с нужным узлом те семь, которые понадобятся дальше по обходу, — зависит от того, как узлы распределились по куче. Если список собирали по одному узлу вперемешку с другими аллокациями, соседи по памяти и соседи по цепочке — разные узлы.

И главное: cur = cur.next — цепочка зависимых обращений. Адрес следующего узла становится известен только после того, как приехал предыдущий, и это резко ограничивает memory-level parallelism. Последовательный обход массива процессор хорошо предсказывает и подгружает линии вперёд; с разбросанным списком подгружать заранее ему значительно сложнее.

Промах кеша с походом в оперативную память стоит десятки наносекунд, то есть сотни тактов; точное число зависит от уровня кеша, памяти и процессора. Формула O(n) этой цены не содержит.

Проверяем. Одинаковые данные, одинаковая работа — сложить все значения:

// массив
sum := 0
for _, v := range s {
    sum += v
}

// список
sum := 0
for cur := head; cur != nil; cur = cur.next {
    sum += cur.val
}

Медианы пяти прогонов, -count=5. Все варианты содержат одни и те же значения, тест сверяет их сумму:

Цена одного элемента на миллионе:

массив:               491 мкс / 1e6 ≈ 0.49 нс на элемент
список подряд:       1.77 мс  / 1e6 ≈ 1.8  нс на узел
список вразброс:    158.2 мс  / 1e6 ≈ 158  нс на узел

158 нс на один зависимый переход по указателю — ровно тот порядок, которого стоит обращение к памяти мимо кеша. Асимптотика у обоих обходов O(n).

Этой цифре я сначала не поверил. Разброшенный список отличался от плотного двумя вещами сразу: узлы выделены по одному через &node{}, и связи перемешаны. Значит ×322 могли объясняться вовсе не локальностью, а поведением аллокатора. Так появился четвёртый вариант: узлы в том же одном блоке make([]node, n), что и у плотного, но связаны в случайном порядке. Отличие от плотного ровно одно — порядок связей.

Он дал 158.2 мс против 146.7 мс у отдельных аллокаций. Разница 7% при отставании от массива в три сотни раз: случайные связи внутри одного блока уже дают те же ~150 мс. Похоже, почти вся разница здесь именно в порядке обхода. Пять прогонов не позволяют сказать, что способ аллокации не влияет вообще, но рядом с ×300 его вклад небольшой.

У этой машины L1d — 64 КБ, L2 — 4 МБ. Теперь посмотрим на размер рабочего набора:

Даже плотный список стоит примерно ×3.6, и эта надбавка почти одинакова на всех размерах: ×3.3, ×3.8, ×3.6, ×3.6. Из чего она складывается, один этот бенчмарк не разделяет — у узла 16 байт против 8 у элемента массива, то есть вдвое больший рабочий набор, плюс чтение next и зависимость шага от предыдущего. Важно, что от размера данных она не зависит.

А цена перестановки связей от размера зависит резко. Если считать не от массива, а от плотного списка: ×1.0, ×2.8, ×6.6, ×89. На тысяче элементов разницы почти нет — всё помещается в L1. Когда рабочий набор перестаёт помещаться в L2, та же перестановка стоит в девяносто раз.

list_dense — это список сразу после того, как его аккуратно собрали в цикле. Замерь только его, и вывод получится «медленнее, но терпимо». Бывают нагрузки, где список таким и остаётся, но после череды вставок и удалений рассчитывать на это уже нельзя.

Вставка

Хорошо, обход у списка медленнее. Но вставка-то O(1)?

O(1) — это только момент перецепления указателей. До нужного места ещё надо дойти:

// список: сначала дойти, потом вставить
prev := head
for k := 0; k < i-1; k++ { // вот где появляется O(n), если известен индекс, а не узел
    prev = prev.next
}
prev.next = &node{val: 42, next: prev.next}

// массив: сдвинуть хвост
s = append(s, 0)
copy(s[i+1:], s[i:])
s[i] = 42

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

Список с обходом проигрывает массиву в 2.7 раза на обоих размерах — при том что «по учебнику» у него вставка O(1), а у массива O(n).

Вот в третьей колонке у списка действительно O(1): 3.4 нс на тысяче элементов и 3.6 нс на ста тысячах. Именно такую картину и ожидаешь от O(1) — пропал обход, и стоимость почти не изменилась. Нужный узел для этого должен уже лежать в руках.

Список имеет смысл там, где указатель на нужный узел уже есть и добывать его обходом не надо. Классический пример — LRU-кеш: map даёт указатель на узел за один шаг, список переставляет его в начало за одну операцию. Ни одного обхода.

type lru struct {
    order *list.List                    // порядок использования
    index map[string]*list.Element      // ключ → узел в списке
}

func (c *lru) Get(key string) (any, bool) {
    el, ok := c.index[key]
    if !ok {
        return nil, false
    }
    c.order.MoveToFront(el) // указатель уже есть — O(1) без обхода
    return el.Value, true
}

Ещё один настоящий случай — когда нужны стабильные адреса. append может выделить новый backing array и скопировать туда данные. Взятый раньше указатель остаётся валидной памятью, но ссылается на старый массив: через слайс вы уже видите новый, и запись по старому указателю в него не попадёт. Узлы списка с места не двигаются.

Переезд

У бабули тоже есть цена, и первая — рост.

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

А теперь что делает Go. Начиная с версии 1.24 встроенный map реализован по схеме Swiss Tables, и команда Go в блоге называет причину прямо: Go часто используют для серверов, чувствительных к задержкам, поэтому операции над встроенными типами не должны произвольно влиять на tail latency.

Как это сделано, по описанию из того же блога:

• хранилище разбито на группы по 8 слотов, к каждой группе прицеплено 64-битное control word — по байту на слот;

• байт говорит, пуст слот, удалён или занят, и если занят — содержит младшие 7 бит хеша ключа (h2);

• поиск сравнивает искомый h2 со всеми восемью байтами control word одной операцией вместо восьми последовательных сравнений ключей (по описанию в том же блоге, на amd64 для этого используются SIMD-инструкции). Сравниваются не ключи, а метаданные, поэтому совпадение — это ещё не ответ, а кандидат: 7 бит совпадают у разных ключей примерно в одном случае из 128, и полный ключ всё равно проверяется;

• большая карта разбита на независимые таблицы, каждая до 1024 записей; старшие биты хеша выбирают таблицу. Переполнилась одна — делится она, остальных это не касается.

Проверяем, замеряя каждую из миллиона вставок по отдельности:

d := make([]time.Duration, n) // место под отсчёты — заранее

m := make(map[int]int)
for i := 0; i < n; i++ {
    start := time.Now()
    m[i] = i
    d[i] = time.Since(start)
}

Это демонстрационный эксперимент, а не бенчмарк цены mapassign. Одна вставка быстрее вызова time.Now, поэтому прибор — заметная часть измеряемого: пустой замер (только time.Now и time.Since) даёт p50 = 41 нс. Читать медиану как чистую стоимость вставки нельзя. Что этой методикой видно хорошо — выбросы: вставка, которая стоит многократно дороже соседних, из-под накладных расходов таймера торчит.

Миллион вставок, GC отключён на время замера:

пустой замер (только таймер):  p50 = 41 нс
p50   = 167 нс
p99   = 875 нс
p99.9 = 32.7 мкс
max   = 2.01 мс        ← ≈12 000× от измеренной медианы
дороже 100 × p99 (87.5 мкс): 98 вставок из 1 000 000

Здесь рассказ пришлось править по факту. Худшая вставка заняла 2 мс. Выбросы кучкуются примерно между #838 000 и #926 000 и на степени двойки не похожи. GC я на время теста отключил, так что это не он.

Почему именно они возникают, из этого теста я не знаю. Можно подозревать выделение новых таблиц или первые обращения к свежим страницам памяти, но таймер вокруг m[k] = v этого не доказывает. Тут уже нужен профиль.

Локализация роста избавляет от копирования всей карты, но выбросы в хвосте остаются. Если у вас в SLA стоят миллисекунды на хвосте, «в Go теперь хорошая карта» — не аргумент.

Работу при росте можно частично или полностью не делать, если размер известен заранее:

m := make(map[string]int)            // размер неизвестен — карта растёт по ходу дела
m := make(map[string]int, len(rows)) // размер известен

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

На десяти тысячах записей подсказка даёт втрое по времени, а на миллионе — всего 15%. Зато память ровно вдвое на обоих размерах, и вдвое меньше аллокаций. На этом стенде подсказка оказалась в первую очередь про память и аллокатор; с другими типами ключей и значений картина может отличаться.

Ещё несколько свойств map

Второе, за что бабуля берёт плату: на маленьких наборах её работа заметна.

Посчитать хеш, выбрать группу, сравнить control word, проверить ключ целиком — это работа. Перебрать несколько элементов подряд в массиве — тоже работа, но она вся в кеше и без хеширования.

С восьми ключей map уже впереди, и дальше отрыв растёт линейно, потому что у него время почти не меняется — 18-19 нс от шестнадцати ключей и до ста двадцати восьми.

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

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

Три грабли

Ещё три свойства map, на которые натыкаются в проде.

Конкурентная запись убивает процесс. Не паникой, которую можно поймать:

fatal error: concurrent map writes

recover не поможет — это fatal error, а не panic: процесс умирает целиком, вместе со всеми остальными запросами. Лечится обычным sync.RWMutex рядом с картой; sync.Map — не универсальная замена: её документация прямо называет два сценария, под которые она оптимизирована, — ключ записывается один раз и читается много (write-once, read-many) и наборы ключей у горутин не пересекаются. В остальных случаях map под мьютексом обычно проще и понятнее. Но первый вопрос — зачем карта вообще разделяется между горутинами.

Порядок обхода не определён. Спецификация языка говорит прямо: порядок итерации по карте не задан и не гарантируется одинаковым от одной итерации к другой.

for k, v := range m { // порядок не определён; полагаться на него нельзя
    fmt.Println(k, v)
}

Ловится обычно тестом, который зелёный локально и красный в CI — или наоборот. Нужен порядок — собирайте ключи в слайс и сортируйте.

Память после удаления. Что происходит с занятой картой памятью, когда из неё удалили все ключи, — вопрос к реализации, а не к спецификации, и по одной версии Go отвечать за другую нельзя. Поэтому замер:

heap до карты:        0.2 МБ
миллион записей:     36.3 МБ   (+36.1 МБ)
после delete всех:   36.3 МБ   (len = 0)
после clear:         36.3 МБ
удержано: 100%

В этом эксперименте на Go 1.24.7 результат однозначный: ни delete всех ключей, ни clear не вернули ни одного мегабайта. Карта на миллион записей заняла 36 МБ и держит их, пока сама достижима.

Если после пика важно избавиться от удержанной ёмкости, карту придётся заменить новой: clear очищает содержимое, но не ёмкость.

Как замерялось

go version   : go1.24.7
GOOS/GOARCH  : darwin/arm64
CPU          : Apple M3 Pro, GOMAXPROCS=12
cache line   : 128 байт   (sysctl hw.cachelinesize)
L1d / L2     : 64 КБ / 4 МБ
прогонов     : 5 (-count=5), в таблицах медианы

Числа с ARM-машины, и на x86-64 с 64-байтной линией абсолютные значения будут другими. Механизм — нет: он про то, что происходит, когда рабочий набор перестаёт помещаться в кеш.

Обход я гонял дважды. В первом прогоне разброс был такой, что на тысяче элементов разброшенный список местами выходил быстрее плотного — похоже, машина была занята чем-то ещё. В статье числа из второго прогона.

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

Что выбрать

Ни одна из этих структур не «лучше» другой. Они отвечают на разные вопросы:

Универсальных порогов в таблице намеренно нет. Число, на котором map начинает выигрывать у перебора, зависит от типа ключа, размера значения, доли промахов и процессора — у меня оно одно, у вас будет другое. Надёжный способ его узнать — замерить свой случай.

Код и замеры из статьи лежат на backendstart.ru — там же есть другие разборы backend-задач в таком формате. Всё можно прогнать у себя.

Что забрать с собой

1. Список берут за то, что указатель на узел уже есть или нужны стабильные адреса. Не за «O(1) на вставке».

2. Замеряете список — гоняйте оба состояния, узлы подряд и узлы вразброс. Первое польстит.

3. Знаете размер карты — скажите его в make. На моём тесте это вдвое меньше памяти и аллокаций.

4. Худшая из миллиона вставок в карту заняла у меня 2 мс. Критична tail latency — смотрите свой request path.

5. Карта между горутинами без синхронизации убивает процесс целиком, и recover не спасёт.

В таблице сложности у массива и списка по-прежнему написано O(n). На моём M3 Pro между ними получилось ×322.

Big O не соврал. Просто про разницу в ×322 он ничего не обещал.