CS Notes

array

6 min read

Array

← GC | Hash →

Динамический массив хранит элементы в непрерывном буфере и растёт при переполнении — эти принципы одинаковы в любом языке. Вопрос реализации: где именно лежит этот буфер? В Ruby ответ зависит от размера массива. Маленький массив помещает элементы прямо в слот объекта — без malloc, без указателя, с минимальным расстоянием до CPU-кеша. Когда элементов становится больше, чем вмещает слот, Ruby выделяет отдельный буфер. Эти два режима — embedded и heap — определяют внутреннюю жизнь RArray.

Два режима хранения

Структура RArray начинается с заголовка RBasic (16 байт: flags + klass). Дальше идёт union — одна и та же память интерпретируется по-разному в зависимости от флага RARRAY_EMBED_FLAG в поле flags:

Embedded (флаг RARRAY_EMBED_FLAG установлен):
┌─────────────────┬──────────────────────────────────┐
│  RBasic (16 B)  │  элементы: VALUE[] прямо в слоте │
│  flags + klass  │  длина закодирована во flags      │
└─────────────────┴──────────────────────────────────┘

Heap (флаг не установлен):
┌─────────────────┬─────┬──────┬─────┐     ┌──────────────────┐
│  RBasic (16 B)  │ len │ capa │ ptr │ --> │ VALUE[] в буфере │
│  flags + klass  │     │      │     │     └──────────────────┘
└─────────────────┴─────┴──────┴─────┘

В embedded-режиме длина массива кодируется прямо во flags заголовка, а элементы (VALUE, 8 байт каждый) лежат сразу после заголовка. Нет ни указателя, ни отдельной аллокации — один cache line захватывает и метаданные, и данные. Embedded режим держит данные рядом с метаданными по принципу пространственной локальности: одно обращение к памяти загружает и заголовок, и данные.

В heap-режиме объект хранит длину (len), ёмкость (capa) и указатель (ptr) на буфер, выделенный через malloc. Доступ к элементам требует разыменования указателя — второе обращение к памяти, потенциально на другой странице.

Сколько элементов помещается в слот

Embedded-ёмкость определяется простой формулой: всё пространство слота после заголовка RBasic делится на размер одного VALUE.

embedded_capacity = (slot_size - 16) / 8

С VWA (Ruby 3.2+) слоты бывают пяти размеров:

СлотEmbedded capacity
40 B3 элемента
80 B8 элементов
160 B18 элементов
320 B38 элементов
640 B78 элементов

До VWA все слоты были 40 байт — embedded вмещал максимум 3 элемента. Теперь массив из 8 элементов (типичный размер опций метода, координат, небольших коллекций) помещается в 80-байтный слот целиком — без malloc, без дополнительного указателя, с одним обращением к памяти вместо двух.

При создании массива GC выбирает слот подходящего размера. Если Ruby знает начальную ёмкость (литерал, Array.new(n)), он запрашивает слот, достаточный для embedded-хранения. Пустой [] получает слот 40 байт с ёмкостью 3.

Рост: когда embedded перестаёт хватать

Допустим, массив живёт в слоте 40 байт (embedded capacity = 3):

a = []        # embedded, capacity = 3
a << 1 << 2   # [1, 2] — ещё помещается
a << 3        # [1, 2, 3] — слот заполнен
a << 4        # нужен 4-й элемент → переход на heap

При добавлении четвёртого элемента Ruby проверяет: помещается ли новый размер в текущий слот? Нет — значит, пора переключаться на heap. Ruby выделяет буфер через malloc, копирует элементы из слота в буфер, сбрасывает флаг RARRAY_EMBED_FLAG и записывает указатель на буфер.

Размер слота зафиксирован при создании объекта — Ruby не перемещает объект в больший слот на лету. Это решение GC: перемещение между size pools происходит только при compaction.

Минимальный heap-буфер

Когда массив переходит на heap, Ruby выделяет буфер минимум на 16 элементов (ARY_DEFAULT_SIZE), даже если нужны всего 4. Без этого минимума массив, растущий с 4 до 10 элементов, переаллоцировался бы 3+ раза (на 4, 6, 9 элементов при коэффициенте 1.5). С минимумом 16 — ноль переаллокаций до 16-го элемента.

Стратегия роста heap-буфера

Когда heap-буфер заполняется, Ruby увеличивает его на 50% от текущего размера (коэффициент 1.5). Для сравнения, динамический массив в теории обычно удваивается — Ruby выбрал более экономный по памяти вариант. При 1.5 массив после расширения использует минимум 67% буфера (при 2.0 — 50%).

heap capacity = 16  → добавляем элементы → заполнился
               +8  = 24  → заполнился
               +12 = 36  → заполнился
               +18 = 54  → ...

Рост на 50% даёт амортизированную O(1) вставку — как и при удвоении, — но с меньшим потолком неиспользуемой памяти.

Shared-массивы: Copy-on-Write

Массив из 1000 элементов занимает 8 КБ данных (1000 × 8 байт VALUE). Если каждый вызов ary[100..200] копирует 100 элементов — это 800 байт и memcpy на каждый срез. В коде, активно работающем со срезами (парсинг, обработка данных), эти копии складываются в заметный расход CPU и памяти.

Ruby избегает копирования: создание подмассива (ary[1..3]) или копии (ary.dup) не копирует элементы. Дочерний массив получает указатель на буфер родителя и флаг RARRAY_SHARED_FLAG. Родитель помечается как RARRAY_SHARED_ROOT_FLAG, и его счётчик ссылок увеличивается.

a = [1, 2, 3, 4, 5]

         a (shared root)
         ptr --> [1][2][3][4][5]
                      ^
b = a[1..3]           |
         b (shared) --+
         ptr --> [2][3][4]  (смещённый указатель в тот же буфер)

Буфер копируется только при модификации дочернего массива — это Copy-on-Write. Пока массивы только читаются, они разделяют память. Для приложений, активно использующих срезы (парсинг, обработка данных), это экономит и время, и память.

Shared-корень не может быть перемещён GC compaction, пока на него есть ссылки: он помечается как pinned.

Уменьшение массива

Динамический массив в теории описывает проблему shrink: после удаления большинства элементов capacity остаётся на пиковом уровне, и память тратится впустую. Некоторые реализации (Java ArrayList) предлагают явный trimToSize(), другие уменьшают буфер автоматически при падении заполненности ниже порога.

Ruby не делает ни того, ни другого для heap-буфера. Массив, выросший до capacity 10 000 и затем pop’нувшийся до 100 элементов, сохраняет буфер на 10 000 — capacity не уменьшается. Явного метода для сжатия capacity нет.

Единственный механизм возврата памяти — переход heap → embedded. Когда длина массива после pop, shift, clear или slice! снова помещается в слот, Ruby копирует элементы из heap-буфера обратно в слот, освобождает буфер через free и выставляет RARRAY_EMBED_FLAG. Условия: массив не shared и не frozen. Для массива в слоте 80 байт это означает ≤8 элементов — типичный порог для небольших коллекций. Но массив из 100 элементов в heap-буфере на 10 000 не получит ни уменьшения буфера, ни перехода в embedded.

Compaction и embedded-режим

GC compaction перемещает объекты, чтобы освободить целые страницы для возврата ОС. При перемещении GC может выбрать слот другого размера. Если массив в heap-режиме перемещается в больший слот, где его элементы помещаются в embedded — Ruby переключает массив обратно в embedded и освобождает heap-буфер.

До compaction:  [слот 40 B] + [malloc-буфер на 6 элементов] → heap mode
После:          [слот 80 B, 8 embedded capacity]             → embedded mode

Это единственный способ увеличить слот объекта — Ruby не делает этого при обычном росте, только при GC compaction. Результат: меньше malloc-буферов, лучше локальность, меньше фрагментация.

Жизненный цикл массива

Создание:    [] → embedded (слот 40 B, capacity 3)
Рост:        << << << << → heap (malloc, min capacity 16, рост ×1.5)
Срез:        a[1..3] → shared (указатель в буфер родителя, CoW)
Модификация: shared << x → копирование буфера (break CoW)
Уменьшение:  pop/clear → heap capacity не уменьшается; если помещается в слот → обратно embedded
Compaction:  GC перемещает в больший слот → может вернуться в embedded

Sources

← GC | Hash →

Graph View

Backlinks