Строки изнутри: три ширины, четыре случая раскладки и цена склейки

Ширину задаёт один символ

CPython по PEP 393 хранит строку в той из трёх ширин, которой хватает самому старшему символу. Ширина одна на всю строку: один эмодзи переводит в четыре байта каждый символ, включая все латинские буквы, которым хватило бы одного.

Длина во всех четырёх положениях переключателя одна и та же — двадцать. Меняется один символ из двадцати.

Ширин при этом три, а случаев, которые видно по размеру, четыре: ASCII вынесено в отдельную структуру с заголовком в 40 байт вместо 56 (числа — из этой 64-битной сборки). У ASCII-строки её представление в UTF-8 совпадает с ней самой, и кешировать нечего; у любой другой поля под этот кеш есть. Поэтому одна é увеличивает строку с 61 до 77 байт, не меняя числа байтов на символ.

На миллионе строк по шестнадцать символов это 54,4 мебибайта для латиницы и 118,3 для эмодзи — одна и та же информация, записанная разными ширинами.

Почему is иногда «работает»

CPython держит таблицу строк, в которой значение существует в одном экземпляре, и кладёт туда часть строк сам. Какую часть — нигде не обещано.

Одиночные символы заведены при старте не все, а только однобайтовые: chr(0x100), построенный дважды, даёт два разных объекта, а chr(0xFF) — один и тот же.

На 3.12.3, 3.13.7 и 3.14.7 наблюдается так: литерал, похожий на имя, интернируется; литерал с пробелом или знаком — нет; строка, собранная во время работы, — нет.

literal = "some_attribute_name"
built = "".join(["some_attribute", "_name"])
 
literal == built      # True
literal is built      # False

Опасность не в том, что is даёт неверный ответ, а в том, что он даёт верный, пока строки берутся из исходника. Код, сравнивающий строки через is, пройдёт все тесты, написанные на литералах, и сломается на первой строке из файла, из сети или из базы — молча, ответив False: «не тот же объект», хотя == дал бы True.

Отдельно стоит "ab" + "cd" is "abcd", который даёт True. Это не интернирование, а свёртка констант: сложение двух литералов выполняет компилятор, и в байт-коде остаётся одна константа. Замените литералы на переменные — и is даст False.

Почему склейка то быстрая, то нет

«Строки неизменяемы, поэтому склейка в цикле квадратична» — верное рассуждение с неверным следствием: обычный цикл со s += x работает линейно, потому что строка растёт на месте.

Условий у этого два. Первое — форма кода: накопитель обязан быть локальной переменной функции, и результат обязан присваиваться обратно в неё же. Второе проверяется во время работы: на строку не должно быть лишних ссылок.

Второе и есть то, чего не видно. Добавьте в цикл строку keep = s, которая ничего не вычисляет, — опкод останется тем же самым, а двадцать тысяч шагов вместо 0,8 миллисекунды займут 140,7.

Проверяется это не отношением времён — оно на такой машине гуляет, — а ценой одного шага. У быстрого пути она не меняется вовсе: 43, 42, 40, 39 наносекунд при росте N от 2500 до 20 000. У медленного растёт вместе с длиной: 201, 442, 962, 4644. Каждый шаг копирует всё, что уже накоплено.

Что из этого делать

Брать "".join(). В этом замере он не быстрее склейки по месту — 0,6 мс против 0,8, один порядок, — но надёжнее: его время не зависит ни от того, где лежит накопитель, ни от того, сохранил ли кто-то ссылку, ни от того, вынесут ли завтра этот код в метод класса.

Не сравнивать строки через is. Ни одна версия не обещает, какие строки интернируются сами, и границы этого поведения уже двигали между 3.12 и 3.13.

И помнить про ширину там, где строк много: один символ вне латиницы стоит не своих четырёх байт, а четырёх байт на каждый символ строки.

У строки размер объекта при одинаковой длине определяется тем, что в ней лежит, — и определяется СИСТЕМАТИЧЕСКИ: самым старшим кодом символа, а не историей объекта.

Это противоречит тому, чему учит любой другой контейнер, и потому проскакивает мимо. Строка из двадцати символов: двадцать латинских букв — это 61 байт, те же двадцать с одной кириллической — 98, с одним эмодзи — 140. Ни одна буква, кроме заменённой, не изменилась.

Строка при этом не единственный такой тип, и сказать это стоит сразу, чтобы дальше не путать разные причины. У целого размер зависит от величины числа: 0 занимает 28 байт, 2**1000 — 160. У списка при одинаковой длине он зависит от того, как список построили: list(range(100)) — 856 байт, а тот же по длине, собранный через append, — 920. Разница в том, что у строки это не история и не запас, а прямое следствие содержимого: те же двадцать символов при том же алфавите всегда дают то же число.

У статьи три части про устройство и четвёртая — задачи. Каждая из трёх отвечает на свой вопрос. Почему одинаковые по длине строки занимают разное место. Почему is для строк иногда срабатывает — и почему на это нельзя опираться. И почему s += x в цикле то линеен, то квадратичен: условий у быстрого пути два, и второе в коде не видно вовсе.

Часть I. Три ширины и четыре случая раскладки

Ширина выбирается по самому старшему символу

PEP 393 назвал и задачу, и решение одной фразой:

Ключевое здесь — «с наибольшим кодом». Ширина не выбирается для каждого символа отдельно: она одна на всю строку, и задаёт её самый старший из символов. Один эмодзи посреди латиницы переводит в четыре байта КАЖДЫЙ символ, включая все латинские буквы, которым хватило бы одного.

«Учетверяет» при этом относится к буферу символов, а не к размеру объекта целиком: в getsizeof входит ещё заголовок и завершающий ноль, поэтому у короткой строки итог вырастает не ровно вчетверо — 61 байт против 140 на двадцати символах.

Длина во всех четырёх положениях переключателя одна и та же — двадцать. Меняется один символ из двадцати, и вместе с ним меняется ширина всех.

Четвёртый случай — и он не ширина

Ширин в PEP 393 три: один, два и четыре байта на символ. А случаев, которые видно по размеру объекта, четыре, и четвёртый — не ширина: ASCII-строка лежит в отдельной структуре с более коротким заголовком. Дальше в статье «четыре» значит именно это — четыре случая раскладки компактной строки, а не четыре ширины:

2. ЧЕТЫРЕ ПРЕДСТАВЛЕНИЯ: БАЙТ НА СИМВОЛ И ЗАГОЛОВОК
---------------------------------------------------
  представление  байт/символ  заголовок   что помещается в эту ширину
  ASCII                    1         40   латиница, цифры, знаки — U+0000…U+007F
  Latin-1                  1         56   буквы с надстрочными знаками, U+0080…U+00FF
  UCS-2                    2         56   кириллица, греческий, иврит — до U+FFFF
  UCS-4                    4         56   эмодзи и всё остальное выше U+FFFF

  getsizeof('')        =   41 Б — один заголовок ASCII и ноль
  getsizeof('x' * 10)  =   51 Б — заголовок 40, десять байт, ноль
  getsizeof('é' * 10)  =   67 Б — байт на символ тот же, заголовок 56
  разница заголовков   =   16 Б — поля под кешированное
                              представление в UTF-8, которых у ASCII нет

  А вот одиночная 'é' даёт 61 Б, а не 58: это статическая
  строка, у которой представление в UTF-8 уже посчитано и лежит рядом.
  Мерить заголовок по строке в один символ поэтому нельзя.

ASCII и Latin-1 отличаются не шириной символа — она у обеих один байт, — а заголовком: 40 против 56. Шестнадцать байт разницы — это два поля под кешированное представление в UTF-8, которых у ASCII-строки нет, потому что её UTF-8 совпадает с ней самой байт в байт.

Здесь стоит развести две разные вещи, которые легко склеить. Каноническое представление — то, в котором строка хранится и по которому считается len, — это один, два или четыре байта на символ. Кеш UTF-8 — отдельное представление той же строки, которое может лежать рядом, если его кто-то запрашивал. Один байт на символ в первом смысле не означает «строка хранится в UTF-8»: у Latin-1 канонический байт и байт UTF-8 — разные вещи, и именно поэтому у неё есть поля под кеш.

Отсюда и то, что удивляет в первую очередь: одна é в строке из двадцати латинских букв увеличивает её с 61 до 77 байт, не меняя байтов на символ. Выросло не содержимое, а заголовок.

Заодно прогон предупреждает о ловушке, в которую легко попасть при самостоятельной проверке: мерить заголовок по строке в один символ нельзя. Одиночная é даёт не 58 байт, а 61, потому что это статическая строка, у которой представление в UTF-8 уже посчитано и лежит рядом.

Как ширина определена в замере

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

Первый способ — измерение, никакого знания о внутренностях не требует:

per_char = sys.getsizeof(ch * 11) - sys.getsizeof(ch * 10)

Второй — чтение поля kind в заголовке объекта через ctypes. Прогон печатает оба и отдельной строкой говорит, совпали они или нет. На 3.12.3, 3.13.7 и 3.14.7 совпали.

Во что это обходится

Миллион коротких строк — обычный масштаб для журнала, кеша или разобранного файла. Вот что там значит выбор ширины:

5. ЧТО ИЗ ЭТОГО СЛЕДУЕТ ДЛЯ МИЛЛИОНА КОРОТКИХ СТРОК
---------------------------------------------------
  1000000 строк по 16 символов, только сами строки, без контейнера:
  ASCII            57 Б на строку →     54.4 МиБ
  Latin-1          73 Б на строку →     69.6 МиБ
  UCS-2            90 Б на строку →     85.8 МиБ
  UCS-4           124 Б на строку →    118.3 МиБ

Первая и последняя строки — это одна и та же информация, записанная четырьмя разными ширинами, и между ними больше чем вдвое. И уменьшить эту разницу оптимизацией кода нельзя — её задают сами данные: строка с единственным эмодзи в конце стоит как строка из одних эмодзи.

Часть II. Интернирование

Четыре состояния, а не два

«Интернирована или нет» — упрощение, из-за которого наблюдения не складываются. Состояний четыре, и они перечислены в InternalDocs/string_interning.md — единственном документе InternalDocs, который есть и в 3.13, и в 3.14:

Проверить состояние можно двумя способами: вызовом приватной sys._is_interned (появилась в 3.13) и чтением двух младших битов поля state в заголовке объекта. Прогон печатает оба.

Три состояния из четырёх называют одним словом «интернирована», и от этого теряется главное: интернирование и бессмертие — разные вещи. Документация sys.intern предупреждает об этом прямо:

То есть состояние 1 — «интернирована и смертна»: строка лежит в таблице, но исчезнет вместе с последней ссылкой. Состояние 2 — «интернирована и бессмертна». Состояние 3 — «статическая», заведена при старте интерпретатора и не принадлежит никакому коду. Начиная с 3.14 первые два различает и отдельная функция sys._is_immortal; до неё различить их можно было только по полю.

Что интернируется само

Прогон bench/strings/interning.py на 3.13.7; на 3.12.3 три из этих строк дают другое состояние — почему, разобрано ниже:

2. ЧТО ИНТЕРНИРУЕТСЯ САМО
-------------------------
  строка                          состояние поля   sys._is_interned
  литерал, похожий на имя        1 интернирована        да
  литерал с пробелами и знаком   0 не интернирована    нет
  литерал из цифр                1 интернирована        да
  пустая строка                  3 статическая          да
  один символ из Latin-1         3 статическая          да
  литерал в 4096 символов        1 интернирована        да
  собрана join во время работы   0 не интернирована    нет

Что отсюда видно — не правило языка, а поведение этой сборки: интернируется литерал, похожий на имя. Пробел или восклицательный знак — и строка остаётся обычной. Пустая строка в одном экземпляре заведена при старте интерпретатора.

А вот «любой одиночный символ существует в одном экземпляре» — неверно, и граница лежит не там, где её ожидают. Статические одиночные строки заведены только на однобайтовые символы. Прогон строит символы во время работы, чтобы литерал и свёртка константы не подменили ответ. Таблица снята на 3.13.7; на 3.12.3 обе колонки с is те же, а поле state читается нулём у всех семи символов — состояние «статическая» у одиночных строк появилось в 3.13:

6. «ОДИН СИМВОЛ» — ЭТО НЕ ЛЮБОЙ СИМВОЛ
--------------------------------------
  Статические одиночные строки заведены не на все символы, а только
  на однобайтовые: U+0000…U+00FF. Проверяется это построением во время
  работы — chr(n) и join, — чтобы ни литерал, ни свёртка константы не
  подменили ответ.
  символ          chr is chr  join is chr  состояние  _is_interned  _is_immortal
  U+0061     'a'        True         True          3            да             —
  U+00E9     'é'        True         True          3            да             —
  U+00FF     'ÿ'        True         True          3            да             —
  U+0100     'Ā'       False        False          0           нет             —
  U+03B1     'α'       False        False          0           нет             —
  U+0416     'Ж'       False        False          0           нет             —
  U+1F600     '😀'       False        False          0           нет             —

Последняя колонка пуста не случайно: sys._is_immortal появилась только в 3.14, а прогон снят на 3.13.7.

Граница ровно между U+00FF и U+0100. Кириллическая Ж, построенная дважды, — два разных объекта, и is на ней даёт False. То есть «одиночный символ» — это про Latin-1, а не про Unicode.

И главное: строка, собранная во время работы, не интернировалась ни в одном из проверенных случаев. Отсюда разница, на которой ломается код:

literal = "some_attribute_name"
built = "".join(["some_attribute", "_name"])
 
literal == built      # True
literal is built      # False

Где is ломается незаметно

Опасность не в том, что is даёт неверный ответ. Опасность в том, что он даёт ВЕРНЫЙ ответ всё время, пока строки берутся из исходника, и перестаёт — как только они приходят откуда-то ещё:

4. ГДЕ ЭТО ЛОМАЕТСЯ НЕЗАМЕТНО
-----------------------------
  Одна и та же по смыслу строка, полученная двумя путями:
    из исходника:      состояние 1
    из декодирования:  состояние 0
    равны:       True
    тождественны: False

Код, который сравнивает строки через is, пройдёт все тесты, написанные на литералах, и сломается на первой строке, пришедшей из файла, из сети или из базы. Ошибка при этом не выглядит ошибкой: сравнение просто отвечает «не равны».

Язык на эту тему не обещает ничего. Он говорит только, что is сравнивает тождественность:

Ни слова о том, что равные литералы дают один объект. Всё, что об этом наблюдается, — поведение реализации, и оно менялось.

Одно и то же, а состояния разные

Вот прямое доказательство того, что границы «интернировано» двигают между версиями. Литерал "some_attribute_name", тот же самый:

Для кода из этого не следует ничего: строка интернирована в обоих случаях, и is для двух таких литералов отвечает одинаково. Следует другое: «интернировано» — не одно состояние, а семейство, и его устройство — не то, на чём стоит строить сравнение.

Часть III. Склейка

Два условия, а не одно

«Строки неизменяемы, поэтому склейка в цикле квадратична» — верное рассуждение с неверным следствием: обычный цикл со s += x работает линейно. Причина — специализация BINARY_OP_INPLACE_ADD_UNICODE, и условий у неё два.

Сразу о границах этого раздела. Всё, что здесь описано, — оптимизация CPython, а не свойство строк: неизменяемость никуда не делась, менять строку на месте позволено ровно потому, что на неё больше никто не смотрит. Ни одна версия такого поведения не обещает, а условия у него узкие: конкретная форма кода, конкретное число ссылок и конкретное имя специализации, которое между выпусками меняется. Числа ниже сняты на 3.13.7, опкоды прочитаны на ней же.

Первое условие — форма кода. Специализация выбирается по тому, что стоит СЛЕДУЮЩЕЙ инструкцией, и записано это в Python/bytecodes.c прямо:

tier1 op(_BINARY_OP_INPLACE_ADD_UNICODE, (left, right --)) {
    assert(next_instr->op.code == STORE_FAST);
    PyObject **target_local = &GETLOCAL(next_instr->op.arg);
    DEOPT_IF(*target_local != left);

То есть накопитель обязан быть локальной переменной функции, и результат обязан присваиваться обратно в неё же. Накопитель в элементе списка или в атрибуте объекта этому не удовлетворяет, и там выбирается обычное сложение.

Второе условие проверяется уже во время работы, и цель его названа в том же файле:

Одна строка кода, которая ничего не делает

Второе условие — то, что показывает второе положение переключателя на схеме выше. Две функции:

def local_var():
    s = ""
    for _ in range(N):
        s += X
    return s
 
 
def extra_reference():
    s = ""
    for _ in range(N):
        keep = s
        s += X
    return s

Разница — строка keep = s, которая ничего не вычисляет и никуда не передаётся. Прогон печатает опкоды всех четырёх функций после прогрева, и у этих двух он ОДИН И ТОТ ЖЕ:

3. ПОЧЕМУ ТАК: ДВА УСЛОВИЯ, А НЕ ОДНО
-------------------------------------
  Первое условие — форма кода. Специализация выбирается по тому, что
  стоит СЛЕДУЮЩЕЙ инструкцией, и видна в разобранном байт-коде:
  функция                        опкод сложения после прогрева
  local_var                      BINARY_OP_INPLACE_ADD_UNICODE
  extra_reference                BINARY_OP_INPLACE_ADD_UNICODE
  list_slot                      BINARY_OP_ADD_UNICODE
  attribute                      BINARY_OP_ADD_UNICODE

А время — нет. В том же прогоне первая функция проходит двадцать тысяч шагов за 0,8 миллисекунды, вторая — за 140,7.

Зависит ли цена одного шага от уже накопленного

Проверять квадратичность отношением времени на этой машине нельзя: отношение между соседними размерами гуляет от 4,4 до 9,7, и на длинах в сотни килобайт в него, скорее всего, входит ещё и смена стратегии выделения памяти — замер её не отделяет. Зато прекрасно проверяется другое — цена ОДНОГО шага:

2. ЦЕНА ОДНОГО ШАГА: ЗАВИСИТ ЛИ ОНА ОТ УЖЕ НАКОПЛЕННОГО
-------------------------------------------------------
  Вот в чём разница на самом деле. У линейного накопления цена одного
  шага постоянна; у квадратичного каждый шаг копирует всё накопленное,
  и потому дорожает вместе с длиной.
  N        локальная: мс   нс на шаг    элемент списка: мс   нс на шаг
  2500              0.11          43                  0.50         201
  5000              0.21          42                  2.21         442
  10000             0.40          40                  9.62         962
  20000             0.79          39                 92.88        4644

Левая колонка «нс на шаг» не меняется: длина накопителя на цену шага не влияет вовсе. Правая растёт вместе с N — каждый шаг копирует всё, что уже накоплено. Это и есть разница между «строка выросла на месте» и «строка скопирована целиком», предъявленная, а не названная.

Что из этого делать

Комментарий в исходнике сам называет, ради чего оптимизация сделана: This attempts to avoid quadratic behavior when one neglects to use str.join() (Это попытка избежать квадратичного поведения, когда str.join() забыли применить) То есть быстрый путь — подстраховка на случай, когда написано не лучшим способом, а не разрешение писать так всегда.

Числа из того же прогона:

В ЭТОМ замере join выигрывает мало, и дело не в выигрыше: 0,6 мс против 0,8 — один порядок. Другого порядка отношение получится на других данных: куски другой длины, другое их число, другой алфавит — и разрыв может уйти в любую сторону, поэтому «join быстрее» и «join медленнее» одинаково не следуют отсюда.

Что следует — join НАДЁЖНЕЕ. Его время не зависит ни от того, где лежит накопитель, ни от того, сохранил ли кто-то ссылку на строку, ни от того, вынесут ли завтра этот код в метод класса. Склейка по месту зависит от всего перечисленного, и ломается молча.

Часть IV. Практика

import sys

left = "ab"
right = "cd"

one = "abcd"
two = left + right
three = "ab" + "cd"

print(one == two, one is two)
print(one == three, one is three)
print(sys.getsizeof("ab"), sys.getsizeof("αβ"))

True False
True True
43 62

True True
True True
43 62

True False
True False
43 43

True False
True True
43 44

История версий

Чем измерено

Числа этой статьи получены этими скриптами. Каждый открывается прямо отсюда — вместе с записью прогона.

Байты и состояния — сравнимы между версиями, записи на всех трёх:

• bench/strings/layout.py
• bench/strings/interning.py

Время — одна запись, одна сборка:

• bench/strings/concat.py

Опора под задачи раздела «Практика»:

• bench/strings/practice.py

Python 3.12.3 (GCC 13.3.0), 3.13.7 (Clang 20.1.4), 3.14.7 (Clang 22.1.3); Intel Xeon 2,80 ГГц, 2 vCPU. Байты между версиями сравнимы — это раскладка объекта. Время нет: у сборок разные компиляторы и разные флаги.

Фрагменты Python/bytecodes.c приводятся по тегу v3.13.7 дословно.