Три шага resize

Когда динамический массив переполняется, происходит resize. На уровне реализации это три шага:

Главная стоимость — шаг 2, memcpy. На современных CPU memcpy очень быстрый: десятки GB/sec. Но в момент resize вся работа сосредоточена в одной операции, и она блокирует append на это время. Это и есть spike, который мы видели на p99/p999.

Стоимость каждого шага

• malloc(N) — O(1) в большинстве реализаций. Glibc malloc, jemalloc, tcmalloc держат пулы блоков разных размеров и быстро отдают нужный. Но если фрагментация большая, может потребоваться запрос у ОС (sbrk на Linux, VirtualAlloc на Windows) — это ~1-10 микросекунд.

• memcpy(dst, src, N * 8) — O(N) по байтам. На SSD-RAM современный memcpy идёт со скоростью ~20-50 GB/sec на одном ядре. Миллион указателей (8 MB) копируется за ~200-400 микросекунд.

• free(old) — O(1). Возвращает блок в pool аллокатора. Часто блок не отдаётся ОС, а ждёт реюз.

Суммарно: один resize большого list (1M элементов) стоит ~200-500 микросекунд. Это и есть тот «spike» в нашем замере (max = 8500 ns на p99.9 — но это на маленьких размерах, при больших spike дотягивает до миллисекунд).

Как замерить spike

Используем sys.getsizeof как индикатор resize:

import sys
import time

xs = []
prev_size = sys.getsizeof(xs)
spikes = []

for i in range(1_000_000):
    t0 = time.perf_counter_ns()
    xs.append(i)
    t1 = time.perf_counter_ns()
    new_size = sys.getsizeof(xs)
    if new_size != prev_size:
        # это resize: размер буфера изменился
        spikes.append((len(xs), t1 - t0, new_size - prev_size))
        prev_size = new_size

# покажем первые и последние ресайзы
print("первые 5 resize:")
for length, ns, delta in spikes[:5]:
    print(f"  len={length:>7,}  duration={ns:>7,} ns  buffer +{delta} bytes")

print(f"\nвсего resize: {len(spikes)}")
print(f"последний:    len={spikes[-1][0]:,}  duration={spikes[-1][1]:,} ns")

Типовой результат:

первые 5 resize:
  len=      1  duration=   1,800 ns  buffer +32 bytes
  len=      5  duration=     400 ns  buffer +32 bytes
  len=      9  duration=     650 ns  buffer +64 bytes
  len=     17  duration=     720 ns  buffer +64 bytes
  len=     25  duration=     900 ns  buffer +64 bytes

всего resize: 53
последний:    len=798,193  duration=2,250,000 ns

Последний resize стоил 2.25 миллисекунды! Это копирование ~800 тысяч указателей в новый буфер. На обычных append спайки в десятки наносекунд — этот в 30 000 раз дороже. Вот это и значит «O(n) worst-case».

Почему resize виден в latency

Допустим, ваш сервис принимает поток событий и складывает их в буфер. На 99% событий latency 0.05 мс. На 0.001% (resize) — 2.5 мс. Если у вас p99.9 SLA = 1 мс — вы его пробьёте.

Решений два:

1. Pre-allocate. Если знаете финальный размер: xs = [None] * N. Никаких resize.
2. Incremental resize. Размазать копирование: вместо «целого resize за один append» — на каждом append копировать 1-2 элемента в новый буфер «параллельно». Так делают real-time hash tables в Redis (rehash incremental).

В обычном DE-флоу — пакетная обработка, throughput — spike не страшен. Но junior должен понимать, что происходит и как замерить.

Освобождает ли память shrinking?

Динамический массив легко растёт. А что насчёт уменьшения? Если вы из списка на 1M элементов удалили 999 999 — буфер остался 1M-большой?

В CPython — нет, есть shrinking. Когда после удаления ob_size < allocated / 2, происходит resize вниз. Но это не agressive: shrink происходит только при pop или del. Если вы массово заменяете xs = old[:1], новый list получает свежий маленький буфер.

В Java ArrayList и C++ std::vector shrinking не происходит автоматически. Нужно явно вызвать trimToSize() или shrink_to_fit(). Это сознательное решение: shrinking — это тоже copy, и его лучше делать руками.

Что делает аллокатор при больших realloc

На очень больших размерах (десятки MB) malloc обращается напрямую к ОС через mmap. Эта память возвращается в ОС при free, и физически освобождается. На маленьких блоках (меньше 128 KB) аллокатор держит память «у себя» в free-list — даже после free ОС эту память не получит обратно, пока процесс не упадёт.

Это объясняет, почему python-процесс с большим list не отпускает память даже после del: аллокатор хранит освобождённые блоки в pool на случай новых выделений. Если ваше приложение генерирует и удаляет много больших списков, это нормально — будет «плато» по RSS, но не растущий leak.

Полный пример: scope resize и память

import sys
import gc

def show_rss():
    import resource
    rss = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
    # на macOS rss в байтах, на Linux в KB
    return rss

# создаём большой list
xs = list(range(10_000_000))
print(f"after build:   getsizeof={sys.getsizeof(xs):,}  rss={show_rss():,}")

# удаляем 99% элементов
xs = xs[:100_000]
gc.collect()
print(f"after slice:   getsizeof={sys.getsizeof(xs):,}  rss={show_rss():,}")

# rss остаётся высоким, потому что free возвращает блоки в pool, не в ОС

getsizeof маленький (только под новый список), rss остаётся высоким — память застряла в аллокаторе. Это норма.

Попробуй сам

Постройте таблицу resize и оцените, сколько ваш CPU копирует элементов в секунду:

import sys
import time

def benchmark_resize_speed(N):
    xs = []
    prev_size = sys.getsizeof(xs)
    biggest_resize = (0, 0, 0)  # (length, ns, copied_bytes)
    for i in range(N):
        t0 = time.perf_counter_ns()
        xs.append(i)
        t1 = time.perf_counter_ns()
        new_size = sys.getsizeof(xs)
        if new_size != prev_size:
            duration = t1 - t0
            if duration > biggest_resize[1]:
                biggest_resize = (len(xs), duration, prev_size)
            prev_size = new_size
    return biggest_resize

length, ns, copied = benchmark_resize_speed(10_000_000)
mb_per_sec = copied / ns * 1000
print(f"largest resize: at len={length:,}, took {ns:,} ns")
print(f"copied {copied:,} bytes => bandwidth ~{mb_per_sec:.1f} MB/sec")

На современном железе должно быть 10-30 GB/sec для memcpy. Это и есть «нативный» memcpy с использованием SIMD-инструкций. Никакой Python в нём нет — это чистый C.