Срез в Go: окно над чужим массивом, два пути append и правило роста, которое все помнят неверно

Что здесь на самом деле спрашивают

Собеседование по срезам почти всегда идёт одной и той же лестницей, и полезно знать её заранее — тогда видно, куда ведёт разговор:

1. «Что такое срез?» — проверяют, знаете ли вы про заголовок. Ответ «динамический массив» закрывает вопрос и открывает следующий.
2. «Что делает append?» — проверяют, знаете ли вы, что случаев ДВА и что они различаются наличием запаса.
3. «Почему здесь изменился соседний срез?» (с кодом на бумажке) — проверяют первое и второе вместе. Это главный вопрос темы.
4. «Какая у append асимптотика?» — проверяют, отличаете ли вы амортизированную оценку от оценки одного вызова.

Все четыре — один и тот же вопрос под разными углами: знаете ли вы, что срез не владеет своими данными. Дальше урок идёт по этой лестнице.

База: срез — это окно над чужим массивом

Начнём с того, зачем срез вообще нужен. Массив в Go задаёт число элементов заранее и живёт с ним до конца: [6]int — это ровно шесть чисел, и других у него не будет. Работать так неудобно почти всегда: данных приходит столько, сколько приходит, и брать нужно то весь набор, то его кусок. Срез и есть ответ на это — способ смотреть на часть массива и говорить о ней как о целом.

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

Посмотрите, как это выглядит. Один массив и два среза над ним — и одна запись:

arr := [6]int{10, 20, 30, 40, 50, 60}
a := arr[1:4]     // [20 30 40]
b := arr[3:6]     // [40 50 60]
 
a[2] = 99

Прогон bench/goslice/internals.go печатает, что стало:

массив          [10 20 99 40 50 60]   ← было [10 20 30 40 50 60]
a               [20 30 99]
b               [99 50 60]

Одна запись — три изменившихся значения, и ни одно из них не копия. a[2] и b[0] — это одна и та же ячейка массива.

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

Держите эту фразу под рукой: она одна отвечает на три разных вопроса собеседования. Раз данные общие — добавление в один срез может записать в чужие ячейки. Раз массив может смениться — добавление обязано возвращать новое окно. Раз окно удерживает весь массив — короткий срез держит длинный в памяти.

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

Механизм 1: срез, массив и строка — три разные вещи

В Go есть три «последовательности», и их постоянно смешивают. Разница видна по одному числу — размеру самого значения:

[]int       24 байта   — три слова: указатель, длина, запас
string      16 байт    — два слова: указатель и длина
[5]int      40 байт    — МАССИВ это значение: пять чисел по восемь

Прочитайте эту табличку ещё раз: у [5]int размер зависит от количества элементов, у []int — нет. Это и есть вся разница. Массив в Go — значение, и func f(a [5]int) получает копию всех пяти чисел. Срез — описатель, и func f(s []int) получает копию трёх слов, за которыми лежит чужая память.

Отсюда сразу два практических вывода, которые стоит держать наготове:

• «Передавать срез по указателю ради скорости» бессмысленно: вы экономите восемь байт из двадцати четырёх. А вот *[1000]int вместо [1000]int — осмысленно, потому что там копируются восемь килобайт.
• Функция может изменить ваши данные, ничего не возвращая: s[0] = 1 внутри видно снаружи, потому что указатель в копии заголовка тот же.

Теперь посмотрите на сам заголовок и на то, как из выражения получаются его три поля. Переключайте выражения — фигура одна и та же, меняются числа:

Главное, что должно остаться от этой картинки: красная зона — не «свободное место». Это ячейки исходного массива, которые кто-то другой считает своими. s[1:3] не «отрезает кусок» — он открывает окно, за правым краем которого лежат чужие данные, и append пишет именно туда.

Правило из спецификации, которое стоит уметь произнести дословно: у s[low:high] запас равен cap(a) - low (cap(a) − low), а у трёхиндексной формы s[low:high:max] — max - low (max − low). Второе и есть единственный способ отрезать хвост.

Механизм 2: что делает append

append — не функция в обычном смысле, а встроенная операция, которую компилятор разворачивает в два пути.

Быстрый путь: запаса хватает. Тогда не происходит ничего интересного: элемент кладётся в ячейку s[len], длина увеличивается на единицу, указатель и запас остаются прежними. Никакого выделения памяти, никакого копирования. Именно поэтому append в цикле по преаллоцированному срезу почти бесплатен.

Медленный путь: запаса не хватает. Вызывается growslice из рантайма, и он делает четыре шага:

1. считает новый запас — это nextslicecap, разбор в «Глубже»;
2. переводит его в байты и округляет вверх до класса размеров аллокатора;
3. выделяет новый массив;
4. копирует в него len уже уложенных элементов и кладёт новый.

Отсюда ответ на вопрос, который любят задавать следом: почему append возвращает срез? Потому что на медленном пути массив другой, и в старом заголовке указатель ведёт не туда. Изменить заголовок у вызывающей стороны append не может — тот передан по значению. Единственный способ сообщить новый указатель и новую длину — вернуть их.

И отсюда же главный вопрос всей темы: на быстром пути append пишет в уже существующий массив, который может быть общим. Посмотрите, как это выглядит по шагам — и как та же операция ведёт себя, когда запас исчерпан:

Второй сценарий на этой картинке важнее первого. Без него уносится правило «append опасен», а оно неверно: опасна ровно комбинация «длина меньше запаса» — то есть ровно та, которую создаёт s[1:3].

Механизм 3: удаление, вставка и цена сдвига

Каноническая идиома удаления выглядит одинаково для любого индекса:

s = append(s[:i], s[i+1:]...)

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

до:    [A B C D E F]        удаляем C (i = 2)
       s[:2] = [A B]        s[3:] = [D E F]

шаг:   append дописывает D, E, F в ячейки после B —
       то есть в ячейки, где лежали C, D, E того же массива

после: [A B D E F | F]      длина 5, шестая ячейка не стёрта

Три вещи видны сразу, и все три спрашивают. Во-первых, append здесь пишет в тот же массив — это тот самый быстрый путь из «Механизма 2», запаса заведомо хватает. Во-вторых, работы ровно столько, сколько элементов в хвосте. В-третьих, последняя ячейка остаётся заполненной — к этому урок вернётся ниже.

Отсюда и цена. Замер на срезе из 10 000 элементов:

Линейность видна прямо в числах: 1401 к 667 — это примерно 9999 к 4999. Цена зависит не от длины среза, а от длины хвоста, который надо сдвинуть. Удаление из начала — O(n), с конца — O(1), и это одна и та же запись при разных i.

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

Практический вывод, который стоит назвать: если порядок элементов не важен, удаление делается за O(1) заменой на последний:

s[i] = s[len(s)-1]
s = s[:len(s)-1]

И отдельная ловушка — та, из-за которой удаление течёт. Укоротив срез, вы уменьшили длину, но массив цел, и элемент за длиной по-прежнему в нём лежит. Если это указатель, объект за ним не соберётся:

live := []*Node{a, b, c}
live = live[:2]      // c больше не виден... но массив его держит

Проверено запуском: третий элемент остаётся в массиве и остаётся ненулевым. slices.Delete эту проблему решает сам — документация прямо говорит, что он zeroes the elements s[len(s)-(j-i):len(s)] (обнуляет элементы s[len(s)−(j−i):len(s)]). Через append обнулять хвост приходится руками.

Механизм 4: где срез держит память

Тот же механизм, но в масштабе, который стоит денег:

func firstThree(path string) []byte {
    data, _ := os.ReadFile(path)   // 50 МБ
    return data[:3]                // отдали три байта
}

Вернули три байта — в памяти остались пятьдесят мегабайт. Сборщик мусора работает с массивом целиком: жив указатель на его начало — жив весь массив. Более узкий срез ссылку не убирает, он только уменьшает длину.

Убирает копия:

return slices.Clone(data[:3])

slices.Clone returns a copy of the slice (возвращает копию среза), и после него исходный массив никем не удерживается. Оговорка из документации существенна: копия неглубокая, и если элементы сами на что-то ссылаются, это что-то останется общим.

Это, кстати, лучший ответ на вопрос «когда вы в последний раз ловили утечку в Go»: чаще всего утечка в Go — не забытая горутина, а вот такой удержанный массив.

Механизм 5: range копирует — гарантия и наблюдение

У этого раздела два утверждения разного сорта, и урок специально их разводит: одно верно всегда, второе верно на конкретной машине под конкретной нагрузкой. Смешивать их — значит производить суеверия.

v — это копия элемента, и запись в неё срез не меняет.

for _, v := range items {
    v.done = true        // потеряно: v — копия
}
for i := range items {
    items[i].done = true // так
}

Это не про скорость и не про версию Go. Это про то, что range по значению присваивает элемент переменной цикла, а присваивание в Go копирует. Ошибка из-за этого не компилируется в предупреждение и не падает в тестах: код честно меняет копию.

А вот вывод «значит, range по значению медленнее» замер не подтверждает.

for _, v := range xs   21 782 нс   — структура в 64 байта копируется
for j := range xs      22 577 нс   — копии нет

По значению вышло быстрее, кратность 0,96. Причина в том, что у индексной формы своя цена: на каждом обращении xs[j] компилятор проверяет границы, а range по значению идёт по памяти подряд без проверок. Две цены оказались одного порядка, и какая перевесит — зависит от размера элемента, от того, что делается внутри цикла, и от того, сумел ли компилятор убрать проверку границ.

Обобщать это число нельзя ни в одну сторону: на структуре в килобайт копия наверняка перевесит. Содержательно здесь другое — что разница не на порядок, а значит, выбирать форму цикла надо по семантике, а не по скорости.

На собеседовании это хороший ход: назвать копирование как гарантию, а производительность — как измеряемое, и не путать их. Ровно так и обстоит дело.

Механизм 6: nil и пустой срез

var a []int      // nil
b := []int{}     // не nil

Длина у обоих ноль, append работает с обоими, for range не сделает ни шага. Отличия ровно два, и оба всплывают далеко от места создания:

Второе — источник настоящих багов: клиент, ожидающий массив, получает null и падает. В коде это выглядит как «мы же вернули пустой список».

Правило: внутри кода разницы не делайте — проверяйте len(s) == 0, а не s == nil; а на границе с JSON инициализируйте явно.

Глубже: рост запаса и цена «амортизированно O(1)»

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

Здесь живёт самое частое заученное правило — и оно неверно. Вот последовательность запасов, через которые реально проходит []int при append по одному:

1 2 4 8 16 32 64 128 256 512 848 1280 1792 2560 3408 5120 7168 9216 12288 16384 21504

Удвоение кончается не на 1024, а на 512: следующее число — 848. Вот соответствующий кусок рантайма, целиком:

const threshold = 256
if oldCap < threshold {
    return doublecap
}
for {
    // Transition from growing 2x for small slices
    // to growing 1.25x for large slices.
    newcap += (newcap + 3*threshold) >> 2
    if uint(newcap) >= uint(newLen) {
        break
    }
}

Разберём по частям, потому что оба «известных» числа ломаются именно здесь.

Порог — 256, а не 1024. Пока старый запас меньше 256, возвращается ровно удвоение. При oldCap == 256 включается формула, но она сама даёт 256 + (256 + 768)/4 = 512 — то есть удвоение «случайно» продолжается ещё один шаг. Первое число, где расхождение видно, — это 848 после 512.

Множитель — не 1,25. Формула прибавляет четверть запаса плюс 192 (это 3*256/4). При запасе 512 получается 512 + (512 + 768)/4 = 832, и множитель равен 1,63. Доля от 192 падает с ростом запаса, поэтому к 1,25 ряд сходится — но идёт к нему сверху и долго:

2,00 … 2,00  1,66  1,51  1,40  1,43  1,33  1,50  1,40  1,29  1,33  1,33  1,31

Обратите внимание: ряд не монотонный. Это уже третий эффект — округление до классов размеров. Формула просила 832 элемента, то есть 6656 байт; аллокатор выдал ближайший класс, 6784 байта, — а это 848 элементов. Рантайм считает в байтах, и обратно в элементы делится с остатком.

Проще всего это увидеть на типе, размер которого не степень двойки. Вот тот же append для структуры в 15 байт:

1 2 4 8 16 32 68 136 273 546 904 1365 1911 2730

Шестьдесят восемь. Двести семьдесят три. Эти числа никто не задумывал — они получились делением байтов на пятнадцать.

Что из этого нужно на собеседовании. Не последовательность наизусть, а три утверждения: рост геометрический с убывающим множителем; порог 256; конкретные значения cap не гарантированы, потому что считается в байтах. Последнее — самое полезное: код, который полагается на равенство cap какому-то числу, сломается при смене версии Go или типа элемента.

Асимптотика, и что за ней прячется

«Амортизированно O(1)» — правильный ответ, который обычно произносят как пароль. За ним стоят два разных утверждения, и на собеседовании ценно разделить их вслух.

Первое: сумма работы линейна. Переезды случаются всё реже, и объёмы копирования складываются в геометрическую прогрессию. Поэтому построение среза из n элементов стоит O(n), а не O(n²), как было бы при росте на единицу.

Второе: отдельный вызов может стоить O(n). Тот append, на котором случился переезд, копирует весь массив. Для среднего времени это неважно; для хвостовых задержек — потенциально важно.

Слово «потенциально» здесь не осторожность, а точность. Скачок виден в p99 только там, где переезд большой и попадает в горячий путь запроса: срез растёт до десятков тысяч элементов внутри обработчика. Если срез строится один раз на старте, или его длина — сотни элементов, или переезды случаются вне запроса, в хвосте это не проявится вовсе. Проверять надо профилем, а не арифметикой: утверждение «append портит p99» верно про нагрузку, а не про append.

Посмотрите на обе половины сразу. Линия — суммарное копирование, отвесные засечки — переезды:

А теперь то, что обычно не рассказывают. Множитель при n — не единица. Вот замер: сколько элементов всего скопировал рантайм, пока срез рос до n:

Множитель растёт с размером — и это не дефект, а прямое следствие предыдущего раздела. Сумма геометрической прогрессии со знаменателем r равна n/(r−1): при удвоении это ≈1·n, при множителе 1,25 — уже ≈4·n. На тысяче элементов рантайм ещё удваивает, поэтому выходит 1,87; на миллионе давно работает медленная формула, поэтому 4,15.

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

И отсюда же ответ на «как это убрать»: make([]T, 0, n), если конечный размер известен. Не «чтобы append был быстрее», а чтобы переездов не было вовсе — в задаче в конце урока это оказалось семикратной разницей.

Как отвечать на собеседовании

Короткий ответ: срез не владеет данными — это окно над чужим массивом, и два окна могут смотреть в одни и те же ячейки. Поэтому запись через один срез видна во втором, а append в одних случаях дописывает в тот же массив, в других переезжает в новый — и именно поэтому он возвращает срез, а результат присваивают обратно.

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

Этого достаточно, чтобы ответить верно. Дальше — то, что добавляют, если собеседник копает.

Если интервьюер копает глубже

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

Про рост говорите честно, а не уверенно. «Удваивается на малых размерах, дальше медленнее; порог 256; множитель сразу после порога заметно больше 1,25, к нему он только сходится; конкретные значения cap не гарантированы, потому что считается в байтах» — это ответ человека, который смотрел в nextslicecap. «×2 до 1024, потом ×1,25» — ответ по чужому пересказу, и один уточняющий вопрос это вскроет.

Асимптотику разделяйте на две. «Амортизированно O(1) — это про сумму. Один вызов в момент переезда стоит O(n), и для p99 это важно». Такое разделение почти никто не проговаривает, а оно показывает, что за формулой стоит понимание.

На «как этого избежать» отвечайте формами, а не намерениями. Три штуки: make([]T, 0, n) — убрать переезды; s[a:b:b] — отрезать запас перед выдачей наружу; slices.Clone — не удерживать большой массив.

Дальше спросят

Частые заблуждения

Практика

Две задачи. Сначала ответьте, потом сверьтесь с настоящим выводом: в обеих правильный ответ взят из прогона скрипта, а не назначен.

s := []int{1, 2, 3, 4, 5}
t := s[1:3]
fmt.Println(len(t), cap(t))
t = append(t, 99)
fmt.Println(s)
fmt.Println(t)

2 4
[1 2 3 99 5]
[2 3 99]

2 2
[1 2 3 4 5]
[2 3 99]

2 4
[1 2 3 4 5]
[2 3 99]

2 5
[1 2 3 99 5]
[1 2 3 99]

Проверка знаний