CS Notes

string

7 min read

String

← Hash | JIT →

Array ввёл паттерн embedded/heap: данные либо в слоте объекта, либо в отдельном буфере через malloc. Строки используют тот же паттерн — RString содержит union, переключающийся между inline-хранением и указателем. Но у строк есть два дополнительных измерения. Байты нужно интерпретировать: одна и та же последовательность [0xC3, 0xA9] — это “e” в UTF-8, но два символа “Ã©” в ISO-8859-1. А неизменяемые строки можно дедуплицировать — хранить в единственном экземпляре на весь процесс.

Поведение строки определяется тремя независимыми осями:

Режим хранения (embedded/heap/shared) — где физически лежат байты. Определяет стоимость доступа к данным: один cache miss или два, malloc или нет.

Кодировка + coderange — как интерпретировать байты и какие оптимизации доступны. Определяет стоимость посимвольных операций: str.length за O(1) или O(n).

Мутабельность (mutable/frozen/fstring) — можно ли модифицировать строку. Определяет возможность дедупликации и безопасность использования как ключа хеша.

Эти оси ортогональны: embedded frozen UTF-8 строка с coderange 7BIT — самый быстрый случай (данные в кеше, без копирования, побайтовые операции). Heap shared строка с невалидной кодировкой — самый медленный (два cache miss, потенциальное копирование при записи, посимвольная обработка невозможна).

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

Рассмотрим веб-приложение, обрабатывающее HTTP-запрос. Путь запроса — строка из ~30 символов:

path = request.path  # "/api/v1/users/42" — 17 байт

Как и массив, строка использует union в RString для переключения между embedded и heap:

Embedded (данные в слоте):
┌─────────────────┬─────┬────────────────────────────────────┐
│  RBasic (16 B)  │ len │ символы + null-терминатор           │
│  flags + klass  │ 8 B │ прямо в слоте                       │
└─────────────────┴─────┴────────────────────────────────────┘

Heap (данные в отдельном буфере):
┌─────────────────┬─────┬─────┬─────┐     ┌──────────────────────┐
│  RBasic (16 B)  │ len │ ptr │capa │ --> │ символы + терминатор  │
│  flags + klass  │     │     │     │     └──────────────────────┘
└─────────────────┴─────┴─────┴─────┘

Поле len хранит длину в байтах, не в символах — потому что один символ в UTF-8 может занимать от 1 до 4 байтов. Количество символов вычисляется при вызове str.length исходя из кодировки — об этом позже.

Строка "/api/v1/users/42" — 17 байт. В 40-байтном слоте после заголовка RBasic (16 байт) и поля len остаётся ~23 байта — строка помещается целиком, embedded-режим. В отличие от массива, строки требуют дополнительное место для null-терминатора (1 байт для UTF-8). Формула embedded-ёмкости: slot_size - offsetof(RString, as.embed.ary) - termlen.

С VWA (Ruby 3.2+):

СлотEmbedded capacity
40 B~23 байт
80 B~55 байт
160 B~135 байт

Большинство строк в типичном приложении — пути, ключи хешей, имена методов, короткие значения — укладываются в 55 байт. С VWA (слот 80 B) они хранятся без malloc.

Null-терминатор

Ruby хранит и длину (len), и null-терминатор. Длина нужна для O(1) доступа к размеру. А терминатор? Строки в Ruby постоянно передаются в C-расширения и системные вызовы — fopen, connect, сетевые библиотеки. Все они ожидают null-terminated строки. Без терминатора каждый такой вызов требовал бы копирования строки с добавлением \0 — лишняя аллокация на каждом системном вызове.

Размер терминатора зависит от кодировки: 1 байт (0x00) для UTF-8, 2 байта (0x0000) для UTF-16, 4 байта для UTF-32. Это учитывается при расчёте embedded-ёмкости.

Стратегия роста

Допустим, приложение собирает тело ответа инкрементально:

body = ""
users.each { |u| body << u.to_json << "\n" }

Пустая строка начинает в embedded-режиме. По мере конкатенации она перерастает слот и переключается на heap — Ruby выделяет буфер через malloc. При дальнейшем росте heap-буфер удваивается (коэффициент 2.0), в отличие от массивов с их 1.5. Причина — строки чаще растут инкрементально (<< в цикле), и более агрессивный рост сокращает число переаллокаций.

Shared-строки: Copy-on-Write

Тело ответа собрано — 10 КБ текста. Приложению нужен превью первых 100 символов для логирования:

preview = body[0..99]

Копировать 100 байт ради превью расточительно, особенно если превью только читается. Ruby не копирует буфер: дочерняя строка получает указатель на буфер родителя (возможно, со смещением) и флаг STR_SHARED. Родитель помечается как STR_SHARED_ROOT.

body (shared root): ptr --> "{"id":1,"name":"Alice"...}\n{"id":2...}\0"
preview (shared):   ptr --------^  len=100

Буфер копируется только при модификации дочерней строки — Copy-on-Write. Механизм идентичен shared-массивам: shared-корень pinned для GC compaction, копирование происходит только при записи.

Строки в Ruby изменяемые по умолчанию — это принципиальное отличие от Java или Python. Изменяемость даёт удобство (str << "...", str.gsub!(...)), но создаёт проблему: если две переменные ссылаются на одну строку, изменение через одну отразится на другой. CoW решает это: пока строки только читаются, они разделяют память, а копирование откладывается до первой записи.

Кодировка

Запрос содержит параметр с именем пользователя из Японии:

name = params[:name]  # "田中太郎" — 4 символа, 12 байт в UTF-8
name.length           # => 4
name.bytesize         # => 12

length и bytesize возвращают разные числа: один символ кандзи занимает 3 байта в UTF-8. Чтобы вычислить количество символов, Ruby должен пройти все байты и декодировать мультибайтовые последовательности — O(n) от длины в байтах. Для ASCII-строк, где один символ = один байт, length == bytesize и ответ — за O(1). Ruby кеширует информацию о содержимом, чтобы не проверять это каждый раз.

Хранение кодировки

Каждая строка несёт информацию о своей кодировке. Индекс кодировки закодирован в 7 битах поля flags заголовка RBasic (биты 10–16). Это позволяет адресовать до 127 кодировок без дополнительного поля — кодировка не увеличивает размер объекта. Одна и та же последовательность байтов [0xC3, 0xA9] — это “e” в UTF-8, но два отдельных символа “Ã©” в ISO-8859-1. Кодировка определяет интерпретацию.

Coderange: кеш свойств содержимого

Помимо индекса кодировки, Ruby хранит coderange (биты 8–9 в flags) — кеш информации о содержимом строки:

7BIT — все байты в диапазоне 0x00–0x7F (чистый ASCII). str.length == str.bytesize, str[i] работает за O(1), строковые операции сводятся к побайтовым.

VALID — содержимое валидно в текущей кодировке (проверено). Для UTF-8 это означает корректные мультибайтовые последовательности. Доступ по индексу символа — O(n) в общем случае: нужно пройти байты с начала.

BROKEN — обнаружены невалидные байты.

UNKNOWN — содержимое ещё не проверено.

Coderange вычисляется при первой необходимости и сбрасывается в UNKNOWN при модификации строки. Для строки "/api/v1/users/42" coderange = 7BIT: все байты — ASCII, и length возвращает результат за O(1). Для "田中太郎" coderange = VALID: length требует прохода по 12 байтам, чтобы найти 4 символа.

Frozen strings и интернирование

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

Frozen strings

str.freeze делает строку неизменяемой: любая попытка модификации вызовет FrozenError. Frozen-строки безопасны как ключи хешей — гарантировано, что ключ не изменится после вставки. Ruby автоматически замораживает строковые ключи при вставке в хеш.

С Ruby 2.3 доступен магический комментарий # frozen_string_literal: true — все строковые литералы в файле автоматически frozen. Это не только защита от случайных мутаций, но и возможность для следующей оптимизации.

fstring: интернированные frozen строки

Если строка frozen и неизменна, одинаковые строки можно хранить в единственном экземпляре на весь процесс. Ruby поддерживает глобальную таблицу fstrings (frozen interned strings). Путь от обычной строки к fstring:

  1. Строка становится frozen (через freeze, # frozen_string_literal: true или -"str").
  2. При использовании как ключа хеша или через явный dedup/-"str" Ruby ищет строку в глобальной таблице fstrings.
  3. Если строка с таким содержимым уже есть — возвращает существующий объект. Если нет — регистрирует текущую строку в таблице.
a = "hello".freeze
b = "hello".freeze
a.object_id == b.object_id  # => true — один объект в памяти

Для embedded fstrings Ruby хранит предвычисленный хеш после содержимого строки в том же слоте (флаг STR_PRECOMPUTED_HASH). Это ускоряет использование строки как ключа хеша: при поиске не нужно повторно вычислять хеш.

fstrings применяются автоматически для символов (:foo хранит строковое представление как fstring), frozen-литералов и ключей хешей. В типичном Rails-приложении сотни одинаковых строк ("id", "name", "created_at") превращаются в единичные fstring-объекты — экономия памяти пропорциональна числу повторений.

Sources

← Hash | JIT →

Graph View