Динамический массив изнутри: память, 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.

Slice header в Go: указатель, len, cap и backing array

Как работает 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)

Рост capacity слайса при append: realloc на каждом удвоении

Утечки памяти через слайсы

// Оба варианта паникуют, если 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

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой, вести прогресс.