Динамический массив изнутри: память, capacity и подводные камни
Динамический массив изнутри: память, capacity и подводные камни
В уроке по слайсам мы научились использовать слайсы. Теперь разберём, как они работают под капотом.
ℹ️ Если ты выбрал не Go
Разбор идёт на слайсах, потому что в Go внутренности видны почти напрямую. Но речь о динамическом массиве, а он есть в любом языке, и главные выводы переносятся один к одному.
Python:
listустроен так же - непрерывный блок памяти плюс запас, рост с перевыделением.list.appendамортизированно O(1), вставка в начало черезinsert(0, x)- O(n), ровно как в Go. Разница в том, что запас Python выбирает по своей формуле, и «предаллокацию» вручную не задать: ближайший аналогmake([]T, 0, n)это создать список нужного размера сразу.PHP:
arrayэто не массив, а упорядоченная хеш-таблица. Вставка в начало (array_unshift) у него тоже O(n): таблица перестраивается и числовые ключи переиндексируются, так что серия вставок в начало квадратична, как и в Go. Выводы про непрерывность памяти и локальность к PHP-массиву применимы лишь частично: ближайший аналог по поведению -SplFixedArray.Что переносится в любой язык: рост с перевыделением, амортизированная стоимость
append, разница между «длиной» и «выделенной ёмкостью», и то, что срез большого массива может удержать в памяти весь массив.
Структура слайса
Слайс - это структура из трёх полей:
// Примерно так выглядит внутри runtime
type slice struct {
array unsafe.Pointer // указатель на массив
len int // длина
cap int // ёмкость
}
s := make([]int, 3, 5)
// array → [0, 0, 0, _, _]
// len = 3
// cap = 5
<?php
declare(strict_types=1);
// PHP-массив - это упорядоченная hash-table (HashTable struct в Zend)
// Нет cap(), нет ptr - всё под капотом
$s = [0, 0, 0];
// count($s) === 3 - это всё, что доступно наружу
В PHP массив - это упорядоченная хеш-таблица «из коробки», а не linear memory. Реальных
slice header(ptr/len/cap) или ручных «buckets» в PHP нет - Zend engine прячет это внутри. PHP-пример показывает API-эквивалент, а не точное воспроизведение Go-памяти.
import sys
# list в CPython - та же тройка, что и slice header, только скрытая:
# ob_item - указатель на массив (но не значений, а указателей на объекты)
# ob_size - длина, её возвращает len()
# allocated - ёмкость, наружу не выставлена
s = [0, 0, 0]
# ob_item -> [ptr, ptr, ptr, _, ...]
# len(s) == 3
# «cap» можно только оценить по размеру самого объекта списка:
# (getsizeof - размер пустого списка) / 8 байт на указатель
capacity = (sys.getsizeof(s) - sys.getsizeof([])) // 8 # 4: CPython округляет до кратного 4
# Отличие от Go: элементы лежат не в самом массиве, а где-то в куче,
# массив хранит только указатели. Локальность памяти хуже; за «массивом
# значений» в стиле Go иди в array.array или memoryview.
Как работает append
s := make([]int, 0, 4)
// cap=4, массив выделен
s = append(s, 1, 2, 3) // len=3, cap=4 - влезает
s = append(s, 4) // len=4, cap=4 - последний слот
s = append(s, 5) // len=5, cap=8 - новый массив!
Когда len == cap, Go выделяет новый массив (обычно x2) и копирует данные.
<?php
declare(strict_types=1);
// PHP-эквивалент append: оператор []= или array_push()
$s = [];
$s[] = 1;
$s[] = 2;
$s[] = 3;
array_push($s, 4, 5); // эквивалентно нескольким []=
// PHP-массив - value type. По умолчанию передаётся копией:
function modifyByValue(array $s): array
{
$s[] = 999;
return $s;
}
// Если нужно изменить in-place - явный reference:
function modifyByRef(array &$s): void
{
$s[] = 999;
}
# Аналог append: list.append для одного элемента, list.extend для нескольких.
# Предаллокации «cap=4, len=0» у list нет - он сразу выделяет под первые элементы.
s: list[int] = []
s.extend([1, 2, 3]) # len=3, allocated=4 - влезает
s.append(4) # len=4, allocated=4 - последний слот
s.append(5) # len=5, allocated=8 - новый массив указателей!
# Когда len == allocated, CPython перевыделяет массив. Формула роста не x2,
# а примерно new_len + new_len // 8 + 6 (округлённо до 4): рост плавнее,
# перевыделений больше, но append всё равно амортизированно O(1).
# В отличие от PHP, list - ссылочный тип. Функция меняет тот самый список,
# никакого & не нужно (и никакой копии по умолчанию нет):
def modify_in_place(s: list[int]) -> None:
s.append(999)
# Если нужна независимая копия - делай её явно:
def modify_copy(s: list[int]) -> list[int]:
s = s.copy()
s.append(999)
return s
Когда buffer переполняется - Zend перевыделяет память внутри HashTable, но capacity не выставляется наружу. На бенчмарках это всё ещё amortized O(1).
⚠️ Ловушка с подслайсами
Подслайс ссылается на тот же массив. Изменения в одном видны в другом - пока не произойдёт расширение.
original := []int{1, 2, 3, 4, 5}
sub := original[1:3] // [2, 3], но cap=4!
sub = append(sub, 99)
// sub = [2, 3, 99]
// original = [1, 2, 3, 99, 5] - СЮРПРИЗ!
// Защита - третий индекс (full slice expression): s[low:high:max]
safe := original[1:3:3] // len=2, cap=2 (cap = max - low)
safe = append(safe, 99) // места нет: append выделит новый массив
// safe = [2, 3, 99], original не изменился
Третий индекс ограничивает cap подслайса. Когда cap равен len, любой append не помещается в общий массив и копирует данные в новый, поэтому исходный слайс остаётся нетронутым. Так стоит отдавать подслайс наружу, если не хочешь, чтобы чужой append переписал твои данные.
<?php
declare(strict_types=1);
$original = [1, 2, 3, 4, 5];
$sub = array_slice($original, 1, 2); // [2, 3] - независимая копия
$sub[] = 99;
// $sub === [2, 3, 99]
// $original === [1, 2, 3, 4, 5] - никаких сюрпризов
В PHP такой ловушки нет:
array_slice($original, 1, 2)всегда возвращает новый массив. Backing array не разделяется - Zend сразу копирует. Минус: чуть больше памяти и аллокаций; плюс: не выстрелишь в ногу.
original = [1, 2, 3, 4, 5]
sub = original[1:3] # [2, 3] - срез list всегда новый список, свой массив указателей
sub.append(99)
# sub == [2, 3, 99]
# original == [1, 2, 3, 4, 5] - сюрприза нет
# Но копия поверхностная: указатели скопированы, объекты - общие.
# Для вложенных списков ловушка возвращается:
matrix = [[1, 2], [3, 4]]
row = matrix[0:1] # новый внешний список...
row[0].append(99) # ...но matrix[0] - тот же объект
# matrix == [[1, 2, 99], [3, 4]] - СЮРПРИЗ!
# Честный аналог Go-подслайса, разделяющего память, - memoryview над буфером:
buf = bytearray(b"\x01\x02\x03\x04\x05")
view = memoryview(buf)[1:3] # не копия, окно в тот же буфер
view[0] = 99
# buf == bytearray(b"\x01\x63\x03\x04\x05") - изменение видно в исходнике,
# как и в Go. Правда, append у memoryview нет: окно нельзя расширить.
nil-слайс и пустой слайс
var s []int (nil-слайс) и s := []int{} (пустой) ведут себя одинаково для len, range и append. Разница - в указателе внутри заголовка: у nil-слайса он nil, у пустого ненулевой. Прикладной код замечает это в двух местах: сравнение s == nil и encoding/json, который кодирует nil как null, а пустой слайс как [].
var a []int
b := []int{}
x, _ := json.Marshal(a) // null
y, _ := json.Marshal(b) // []
<?php
declare(strict_types=1);
// В PHP нет nil-слайса, но та же развилка возникает между null и []:
echo json_encode(null); // null
echo json_encode([]); // []
import json
# В Python та же развилка - None против пустого списка:
json.dumps(None) # 'null'
json.dumps([]) # '[]'
В API это разные контракты: если клиент ждёт массив, инициализируй слайс через make([]T, 0) или []T{}.
Безопасное копирование
// Полная копия - безопасно
src := []int{1, 2, 3}
dst := make([]int, len(src))
copy(dst, src)
// Или через append
dst2 := append([]int(nil), src...)
<?php
declare(strict_types=1);
// Простое присваивание уже копирует (copy-on-write до первой модификации)
$src = [1, 2, 3];
$dst = $src;
$dst[] = 99;
// $src === [1, 2, 3]
// Spread в литерал
$dst2 = [...$src];
// Или array_merge
$dst3 = array_merge([], $src);
import copy
# Присваивание НЕ копирует - это вторая ссылка на тот же список
src = [1, 2, 3]
alias = src
alias.append(99)
# src == [1, 2, 3, 99]
# Полная копия - любой из трёх способов, все O(n)
src = [1, 2, 3]
dst = src.copy()
dst2 = src[:]
dst3 = list(src)
# Все три - поверхностные (как copy() в Go копирует значения, а не то,
# на что указывают указатели). Для вложенных структур - deepcopy:
nested = [[1, 2], [3]]
dst4 = copy.deepcopy(nested)
dst4[0].append(99)
# nested == [[1, 2], [3]]
Предаллокация
// ПЛОХО: постоянные реаллокации
var result []int
for i := 0; i < 10000; i++ {
result = append(result, i)
}
// ХОРОШО: одна аллокация
result := make([]int, 0, 10000)
for i := 0; i < 10000; i++ {
result = append(result, i)
}
<?php
declare(strict_types=1);
// В PHP «явной» предаллокации нет: $arr = []; $arr[] = ... работает,
// но Zend сам ресайзит HashTable пошагово (степени двойки).
// Если очень нужна гарантия - SplFixedArray с known size:
$result = new SplFixedArray(10000);
for ($i = 0; $i < 10000; $i++) {
$result[$i] = $i;
}
// SplFixedArray - C-array, без hash overhead. Быстрее на больших размерах
// но не поддерживает строковые ключи и динамический рост.
# Аналога make([]int, 0, 10000) нет: нельзя задать ёмкость, не задав длину.
# ПЛОХО (но терпимо): рост по формуле CPython, десятки перевыделений
result: list[int] = []
for i in range(10000):
result.append(i)
# ХОРОШО: одна аллокация - сразу создать список нужной длины и заполнять по индексу
result = [0] * 10000
for i in range(10000):
result[i] = i
# ИДИОМАТИЧНО: list(iterable). Если источник знает свою длину
# (range, другой list), CPython спросит её через __length_hint__
# и выделит массив одним куском.
result = list(range(10000))
# А вот list comprehension - это append в цикле: длину он не спрашивает
# и растёт по той же формуле, что и первый вариант. Читается лучше,
# но предаллокацией не является.
\SplFixedArray- редкий случай, когда PHP даёт честную «фиксированную ёмкость». Внутри это C-массив указателей, без HashTable.
Стратегия роста
До Go 1.18: удваивание до 1024, затем рост на 25%. С Go 1.18: удвоение только до 256, дальше рост плавно замедляется к ~25% (512 → 848 → 1280 → 1792 → ...). Для 10 000 элементов, добавленных по одному с нуля, это 19 перевыделений. Суть та же - amortized O(1).
func main() {
var s []int
prevCap := 0
for i := 0; i < 20; i++ {
s = append(s, i)
if cap(s) != prevCap {
fmt.Printf("len=%2d cap=%2d\n", len(s), cap(s))
prevCap = cap(s)
}
}
}
// len= 1 cap= 1
// len= 2 cap= 2
// len= 3 cap= 4
// len= 5 cap= 8
// len= 9 cap=16
// len=17 cap=32
<?php
declare(strict_types=1);
// В PHP capacity не видна снаружи - Zend сам ресайзит HashTable степенями двойки.
// Косвенно можно наблюдать через memory_get_usage():
$s = [];
$prevMem = 0;
for ($i = 0; $i < 20; $i++) {
$s[] = $i;
$mem = memory_get_usage();
if ($mem !== $prevMem) {
echo 'len=' . count($s) . ' mem_delta=' . ($mem - $prevMem) . "\n";
$prevMem = $mem;
}
}
// Скачки memory_get_usage показывают реаллокации - та же амортизированная O(1)
import sys
def main() -> None:
# cap() нет, но sys.getsizeof(list) = заголовок + allocated * 8 байт,
# поэтому ёмкость восстанавливается из размера объекта
s: list[int] = []
prev_cap = 0
for i in range(20):
s.append(i)
capacity = (sys.getsizeof(s) - sys.getsizeof([])) // 8
if capacity != prev_cap:
print(f"len={len(s):2d} cap={capacity:2d}")
prev_cap = capacity
main()
# len= 1 cap= 4
# len= 5 cap= 8
# len= 9 cap=16
# len=17 cap=24
# Не удвоение, а формула ~ n + n // 8 + 6 с округлением до 4:
# ёмкость растёт медленнее, перевыделений больше, но итог тот же amortized O(1)
Утечки памяти через слайсы
// Оба варианта паникуют, если len(data) < 16: проверяй длину заранее.
// ПЛОХО: держим весь массив в памяти
func getHeaderLeaky(data []byte) []byte {
return data[:16] // весь data не соберётся GC!
}
// ХОРОШО: копируем нужное (bytes.Clone - с Go 1.20)
func getHeaderCopy(data []byte) []byte {
return bytes.Clone(data[:16])
}
<?php
declare(strict_types=1);
function getHeader(string $data): string
{
// substr возвращает новую строку, исходная $data может быть собрана GC
return substr($data, 0, 16);
}
Этой ловушки в PHP нет:
substr($data, 0, 16)илиarray_slice()всегда копируют, не удерживая ссылку на исходник. PHP не разделяет backing arrays между объектами на уровне языка.
# Срез bytes - всегда копия, исходный data освободится: утечки нет
def get_header(data: bytes) -> bytes:
return data[:16]
# Ловушка возвращается с memoryview - это и есть «окно в чужой буфер»,
# как подслайс в Go. Такой срез делают, чтобы избежать копирования
# больших данных, и ровно поэтому он держит весь буфер живым.
# ПЛОХО: держим весь буфер в памяти
def get_header_view(data: bytes) -> memoryview:
return memoryview(data)[:16] # пока жив view, жив весь data
# ХОРОШО: копируем нужное, окно закрываем
def get_header_copy(data: bytes) -> bytes:
with memoryview(data) as view:
return bytes(view[:16])
Удаление дубликатов in-place
Частая задача: убрать повторы из отсортированного слайса, не выделяя новый массив. Решение - два указателя: read идёт по всем элементам, write показывает, куда положить следующий уникальный. В конце слайс обрезается до write: длина меняется, а массив под ним тот же. Время O(n), дополнительная память O(1).
// removeDuplicates убирает повторы из отсортированного слайса
// и возвращает слайс на тот же массив, но короче.
func removeDuplicates(s []int) []int {
if len(s) == 0 {
return s
}
write := 1
for read := 1; read < len(s); read++ {
if s[read] != s[write-1] {
s[write] = s[read]
write++
}
}
return s[:write]
}
// removeDuplicates([]int{1, 1, 2, 3, 3}) == [1 2 3]
<?php
declare(strict_types=1);
// PHP-array - хеш-таблица, но тот же приём с двумя позициями работает.
function removeDuplicates(array &$s): int
{
$n = count($s);
if ($n === 0) {
return 0;
}
$write = 1;
for ($read = 1; $read < $n; $read++) {
if ($s[$read] !== $s[$write - 1]) {
$s[$write] = $s[$read];
$write++;
}
}
// Обрезаем хвост (array_slice создаёт новый массив):
$s = array_slice($s, 0, $write);
return $write;
}
def remove_duplicates(s: list[int]) -> int:
"""Убирает повторы из отсортированного списка на месте, возвращает новую длину."""
if not s:
return 0
write = 1
for read in range(1, len(s)):
if s[read] != s[write - 1]:
s[write] = s[read]
write += 1
del s[write:] # обрезаем хвост на месте
return write