Рентген Python

В главе 32 вы были процессором «Искры-8», а потом писали для неё программы на ассемблере: каждая переменная живёт в одном из четырёх регистров, и помнить, в каком, приходится вам; цикл — это прыжок на метку, а умножение двух чисел занимает дюжину строк. А до этого тридцать с лишним глав вы писали for x in a: и не думали, во что превращается эта строка. Между s += x и транзисторами из главы 29 должен стоять кто-то, кто переводит. Кто, и сколько стоит перевод?

Эта глава — рентгеновский кабинет. Пациент — функция из пяти строк, сумма списка. Мы просветим её слой за слоем: байт-код, в который её превращает Python, та же функция на C, машинный код процессора x86 и, наконец, «Искра-8». Каждый снимок показывает то, чего не видно на других: кто исполняет команды, где лежат переменные, во что обходится одно сложение. Последним будет замер. Он покажет, почему цикл на Python в десятки раз медленнее цикла на C и что вы получаете взамен.

Пять снимков одной функции

Прежде чем разбирать снимки по одному, разложим их рядом. Слева в виджете — исходный текст на Python, справа — выбранный слой. Цветом помечено, где какая работа: инициализация s = 0, обход списка, сложение, возврат ответа. Нажмите на строку или на цветную метку, и подсветится всё, что делает эту работу на соседнем снимке. Кнопка «Один элемент» прогоняет то, что выполняется ради одного элемента списка.

Пройдитесь по слоям и сравните строку «на элемент». Одна строка s += x стала тремя командами байт-кода, одной строкой C, одной машинной командой x86 и двумя командами «Искры-8». На первый взгляд байт-код не так уж длиннее машинного кода: шесть команд на элемент против четырёх. Подвох в том, кто их исполняет. Машинный код исполняет сам процессор, а байт-код процессору незнаком: его читает другая программа. С неё и начнём.

Снимок первый: байт-код

В главе 15 мы уже заглядывали в Python модулем dis и увидели, что выражение (a + b) * c он переводит в обратную польскую запись для стековой машины. Тогда это было выражение без переменных и циклов. Теперь просветим целую функцию.

Каждая строка вывода — одна команда. Первый столбец — номер строки исходного текста, к которой она относится, дальше метка (L1, L2 — места, куда прыгают), имя команды, её числовой аргумент и в скобках расшифровка аргумента. Такой список команд для виртуальной машины называют байт-кодом: каждая команда здесь занимает два байта, к этому мы скоро вернёмся.

Прочитаем снимок. LOAD_CONST 0 кладёт на стек ноль, STORE_FAST s снимает его и записывает в переменную s. Переменные функции лежат не в словаре, а в маленьком массиве внутри кадра вызова, и у каждой свой номер: a — 0, s — 1, x — 2. Числовой аргумент команды — этот номер, поэтому LOAD_FAST работает быстро: никакого поиска по имени, одно обращение к ячейке массива. Отсюда и FAST в названии.

Дальше цикл. GET_ITER заменяет список на вершине стека итератором — закладкой, которая помнит, до какого элемента мы дошли. FOR_ITER просит у закладки следующий элемент и кладёт его на стек; STORE_FAST x записывает его в x. Тело цикла — три команды: LOAD_FAST_LOAD_FAST кладёт на стек s и x (в Python 3.13 две загрузки подряд склеены в одну команду), BINARY_OP += снимает два числа и кладёт сумму, STORE_FAST s её запоминает. И наконец JUMP_BACKWARD — прыжок назад, на L1. Цикл, как и у «Искры-8», оказался прыжком на адрес раньше текущего.

Когда элементы кончаются, FOR_ITER снимает закладку и прыгает на L2, причём сразу через две команды — END_FOR и POP_TOP там для особых случаев, обычный цикл их перепрыгивает. Остаётся положить на стек s и вернуть его: RETURN_VALUE. Самая первая команда, RESUME, служебная: она отмечает начало функции.

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

Попробуйте gcd, алгоритм Евклида из задачи главы 5. Строка a, b = b, a % b превращается в маленький танец на стеке: кладём b и a, ещё раз b, считаем остаток, и STORE_FAST_STORE_FAST раскладывает два верхних значения по переменным крест-накрест. Временной переменной нет, её роль сыграл стек. А условие while b в байт-коде встречается дважды, перед циклом и в конце тела: так CPython переводит любой while.

Байты

То, что печатает dis, — расшифровка. Сам байт-код состоит из байтов, и лежат они в атрибуте __code__.co_code, рядом с таблицей констант и именами переменных. Разрежем их по два.

Тридцать шесть байт. В каждой паре первый байт — номер операции, второй — аргумент: 149 0 — это RESUME, 83 1 — LOAD_CONST с константой номер 1 (под номером 0 Python хранит None). Устроено так же, как машинный код «Искры-8» из главы 32: код операции и операнд, только у «Искры» операнд бывает не у каждой команды. Странные пары 0 0 с именем CACHE интерпретатор не исполняет: в эти зарезервированные ячейки он записывает для себя заметки прямо внутри байт-кода. Зачем — увидим через раздел.

Цикл внутри цикла

Процессор этих байтов не понимает: у него свой набор команд, и 149 для него ничего не значит. Байт-код исполняет программа, которую вы запускаете словом python. Её зовут CPython, она написана на C, и сердце её — цикл: взять очередную команду, посмотреть на код операции, перейти к куску программы, который эту операцию выполняет, повторить. Это цикл «выборка — декодирование — исполнение» из главы 32, только сделанный программой, а не проводами. Получается процессор из программы, со своим набором команд и своей памятью, — виртуальная машина. А программу, которая исполняет чужие команды одну за другой, не переводя их заранее целиком, называют интерпретатором.

Виртуальную машину легко написать самому. Вот стековая машина на дюжину строк: у неё четыре команды, а программа для неё — список пар «операция, аргумент».

Нажмите «Шаги»: pc бежит по программе, а стек растёт и сжимается, как в проводнике. В самом CPython главный цикл живёт в файле Python/ceval.c, а тела команд с версии 3.12 описаны отдельно, в Python/bytecodes.c, и из них генерируется код на C. Обычных команд там больше сотни, да ещё семь десятков специальных версий, о которых чуть ниже, но устроены они так же. В задаче в конце главы вы дадите своей машине переменные и прыжки, и она научится считать циклы.

Теперь видно, куда уходит время. Процессор исполняет машинный код интерпретатора, а тот ради каждой команды байт-кода выбирает её, разбирает, прыгает к нужному обработчику и только потом делает собственно дело. Для LOAD_FAST дело — одно чтение из массива, а обвязка вокруг него обходится дороже самого чтения. Эта обвязка и есть цена интерпретации, и платят её на каждой команде.

Python присматривается

Есть у интерпретации и вторая цена, более скрытая. Команда BINARY_OP += не знает, что складывает. Байт-код для 1 + 2, "ab" + "cd", [1] + [2] и 0.5 + 1.5 один и тот же, а действия совершенно разные. Значит, при каждом сложении интерпретатор должен посмотреть на типы и выбрать, что делать. В C таких проверок нет: тип каждой переменной известен заранее, и компилятор сразу вставляет нужную машинную команду.

С версии 3.11 CPython научился с этим хитрить. Его называют специализирующим адаптивным интерпретатором (PEP 659, Марк Шеннон и проект Faster CPython). Когда команда выполнится пару раз, интерпретатор смотрит, с какими типами она работает, и подменяет её прямо в байт-коде на специальную версию — для целых, для дробных, для списков. Ячейки CACHE, которые мы видели среди байтов, служат ему блокнотом. Поймать подмену можно: dis с ключом adaptive=True показывает байт-код в его нынешнем, подстроенном виде.

BINARY_OP превратился в BINARY_OP_ADD_INT, а FOR_ITER — в FOR_ITER_LIST. Специальная версия всё равно проверяет типы, но одной быстрой проверкой: «оба ли целые?». Если да, сразу складывает, если нет — откатывается к общему пути и со временем подстраивается заново. Замените в разогреве [1, 2, 3] на [0.5, 1.5] и запустите ещё раз: увидите BINARY_OP_ADD_FLOAT. Python подстраивается под то, как программу действительно используют, — но проверку совсем убрать не может, ведь в следующий раз в функцию могут передать строки.

Снимок второй: C

Чтобы увидеть, как выглядит та же сумма без интерпретатора, надо переписать её на языке, который переводится прямо в машинный код. Самый известный такой язык родился вместе с операционной системой, на которой сегодня работает и сервер этого курса.

Вот наш пациент на C.

Код на C здесь — строка внутри Python: модуль cs.c в песочнице курса отдаёт её компилятору tcc, тот переводит её в машинный код прямо в памяти и запускает. Сравните с Python. Каждая переменная объявлена со своим типом: long — целое из 64 бит, ровно столько помещается в регистр процессора. Список стал массивом, и массив не знает своей длины, поэтому n приходится передавать отдельно. А параметр a — даже не массив, а адрес его первого элемента. Звёздочка в const long *a читается так: «a — адрес, по которому лежит long».

Адрес в руках

В главе 14 мы добывали адреса под микроскопом ctypes и вывели формулу: элемент номер $i$ лежит по адресу $\text{начало} + 8i$. Python прятал адреса за ярлыками, и чтобы их увидеть, пришлось вскрывать объекты. В C адрес — обычное значение, его можно хранить в переменной, складывать и печатать. Переменную, которая хранит адрес, называют указателем.

Адреса элементов a идут с шагом 8, элементов b — с шагом 4: int занимает четыре байта. Формула из главы 14 работает для любого типа, меняется только размер. Запустите ячейку ещё раз — числа будут другими. Система при каждом запуске кладёт стек программы по новому случайному адресу; это защита, и о ней пойдёт речь в главе 61.

В последней строке собрана вся арифметика указателей. &x даёт адрес x, *p — то, что лежит по адресу p. Прибавляя к указателю единицу, C прибавляет к адресу размер элемента, поэтому *(p + 2) — элемент номер 2. А запись a[i] по определению языка означает *(a + i). Сложение от порядка не зависит, поэтому 2[a] — то же самое, что a[2], и компилятор это принимает. Так никто не пишет, но курьёз хорошо показывает, что квадратные скобки в C — всего лишь сокращение для арифметики адресов. Массив в выражениях превращается в адрес первого элемента, поэтому функция total и получает указатель.

Снимок третий: машинный код x86-64

C ещё не машинный код, его переводит компилятор. Чтобы увидеть результат, нужен один компромисс. Песочница курса не привязана к одному процессору: она бывает запущена и на x86-64 (Intel, AMD), и на ARM, а машинный код у них разный. Поэтому листинги в этом разделе получены заранее: компилятором clang для x86-64, в записи ассемблера Intel. На этой архитектуре работает большинство серверов и персональных компьютеров, и вот как она видит нашу сумму.

Это перевод с ключом -O1 («оптимизировать, но без фанатизма»), комментарии после # наши. Цикл занял четыре команды. add rax, qword ptr [rdi + 8*rcx] читает восемь байт по адресу $\text{rdi} + 8 \cdot \text{rcx}$ и прибавляет их к rax: формула адреса из главы 14 записана прямо в команде, и процессор считает её сам, за один шаг. inc rcx — это i++. cmp rsi, rcx сравнивает n и i, а jne .L4 прыгает назад, если они не равны, — тот же JNZ loop, что у «Искры-8». Перед циклом две команды xor обнуляют i и s, а test rsi, rsi с jle отправляют пустой массив сразу к ответу 0.

Что a придёт в rdi, а n — в rsi, компилятор знает из договора. Функции на C пишут разные люди и компилируют разными компиляторами, а вызывать друг друга они должны без ошибок. Поэтому для каждой системы записано соглашение о вызовах. В Linux на x86-64 оно такое: первые шесть целых аргументов приходят в регистрах rdi, rsi, rdx, rcx, r8, r9, остальные — через стек, а ответ функция оставляет в rax. Поэтому в конце total нет команды «вернуть s»: сумма копилась в rax с самого начала, и ret остаётся только вернуть управление.

Теперь переключите оптимизацию. На -O0 компилятор переводит каждую строку дословно: каждая переменная получает место в памяти, и даже ради i++ её читают из памяти, прибавляют единицу и пишут обратно. На -O1 переменные переезжают в регистры, и цикл сжимается в три раза. На -O2 цикл снова становится длиннее: компилятор складывает числа парами в 128-битных регистрах xmm и проходит четыре элемента за круг. Как одна команда работает с несколькими числами сразу, расскажет глава 35.

В остальных функциях есть сюрпризы. В fact на -O1 исчезла рекурсия: компилятор понял, что умножения можно делать по дороге вниз, и превратил функцию в цикл. В max и dist нет прыжка для if: команды cmovg («переложить, если больше») и cmovge («…если больше или равно») выбирают значение без всякого ветвления. В swap временная переменная t растворилась в регистре. Компилятор вправе переписать программу как угодно, лишь бы результат остался прежним.

Кадр стека

ret «возвращает управление» — но куда? Функцию total могут позвать из сотни мест. В главе 5 мы видели, как эту задачу решил Дэвид Уилер на EDSAC: перед прыжком в подпрограмму вызывающий сообщал ей свой адрес. Там же мы заметили беду его способа: адрес возврата хранился в одном экземпляре, и подпрограмма не могла вызвать саму себя.

Современные процессоры хранят адрес возврата на стеке. Команда call f кладёт на вершину стека адрес следующей за ней команды и прыгает в f. Команда ret снимает этот адрес со стека и прыгает по нему. Каждый вызов кладёт свой адрес возврата, поэтому вызовы могут вкладываться друг в друга сколько угодно глубоко, пока хватает стека. Рядом с адресом возврата функция держит свои переменные и сохранённые значения регистров. Весь этот участок стека, принадлежащий одному вызову, называют кадром стека. Мы рисовали такие кадры в главе 5, а теперь у каждого появился адрес в памяти.

Пройдите программу «вызов» по строкам C. main зовёт sum_sq, та дважды зовёт square. Каждый call кладёт адрес возврата, каждая функция начинает с одной и той же пары: push rbp сохраняет указатель кадра того, кто её вызвал, mov rbp, rsp делает началом нового кадра текущую вершину. Дальше sub rsp, … отводит место под переменные, то есть сдвигает вершину стека вниз. При возврате всё идёт в обратном порядке. Кадр второго вызова square ложится на то же место, где был первый, и затирает оставшийся от него мусор. Освободить кадр — значит сдвинуть вершину стека, ничего не стирая.

В программе «рекурсия» fact(3) зовёт fact(2), та — fact(1), и на стеке одновременно три кадра одной функции, у каждого своё n и свой адрес возврата. Так выглядит в памяти стек вызовов из главы 9. Если рекурсия не остановится, Python это заметит: он следит за глубиной и после тысячи кадров бросает RecursionError. C не следит ни за чем.

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

За краем массива

Кадр — плотно упакованная полоса памяти: переменные, сохранённый rbp и адрес возврата лежат вплотную. Что будет, если программа запишет в массив больше элементов, чем в нём есть? Python ответит IndexError: перед каждой записью по индексу он проверяет границу. C не проверяет — это стоило бы лишней команды на каждое обращение, а язык делали для скорости.

В программе «за край массива» функция work заводит массив buf из четырёх чисел и просит fill записать в него k семёрок. Двигайте ползунок и проходите программу. При k = 5 пятая семёрка попадает в пустую прокладку, которую компилятор оставил между переменными, и ничего не происходит. При k = 6 затирается переменная k самой work, при k = 7 — сохранённый указатель кадра main. Программа по-прежнему завершается как ни в чём не бывало: испорченные значения ей больше не понадобились. Но при k = 8 семёрка ложится на адрес возврата, и ret прыгает по адресу 7, где нет никакого кода.

Самое неприятное здесь — тишина. Ошибка в одном месте портит память в другом, и программа падает (или не падает) гораздо позже, совсем не там, где ошибка. Стандарт C прямо говорит, что запись за край массива — неопределённое поведение: может случиться что угодно, и компилятор ничего не обязан. Вот то же самое без стека — массив в структуре и соседняя переменная.

Одна лишняя итерация, и secret стал нулём. А если записываемые данные пришли извне — из сети, из файла — и подобраны так, чтобы адрес возврата указал на нужное атакующему место? Так в 1988 году червь Морриса, среди прочего, проникал в компьютеры через переполнение буфера в сетевой службе finger. Подробнее об этом классе ошибок и о защитах от него — в главе 61. Нам пока хватит одного вывода: проверка границ в Python — часть цены, которую он платит, чтобы такие ошибки были громкими.

Снимок четвёртый: «Искра-8»

Последний снимок — самый глубокий, на нём видны провода. Та же функция для «Искры-8» из главы 32, написанная вручную так, как её написал бы компилятор. Указатель на массив приходит в R0, длина — в R1, ответ возвращается в R2: соглашение о вызовах мы придумали сами, но оно ничем не хуже Linux.

Положите рядом листинг x86 с ключом -O1. Одна команда add rax, qword ptr [rdi + 8*rcx] на «Искре» распалась на две: LDR читает байт по адресу из регистра, ADD складывает. Формулы адреса у «Искры» нет, поэтому вместо индекса i мы двигаем сам указатель: INC R0 — это a++. Шаг 1, а не 8, потому что элемент занимает один байт. Счётчик идёт вниз, к нулю, и DEC сам ставит флаг Z, так что отдельное сравнение не нужно. CALL и RET работают как у большого процессора: адрес возврата ложится на стек по SP — это прыжок Уилера в железе из главы 32.

Замените данные на .byte 200, 100, а длину в R1 — на 2. «Искра» напечатает 44: регистры у неё восьмибитные, и сумма считается по модулю 256. Это переполнение из главы 11, только в восьми битах вместо шестнадцати. В Python о нём думать не приходится, его целые растут сколько потребуется. Это ещё одна проверка, которую он делает за вас при каждом сложении.

Пять снимков сложились в цепочку. Python компилирует текст в байт-код. Байт-код исполняет интерпретатор, который сам — программа на C, скомпилированная в машинный код. Машинный код исполняет процессор, собранный из вентилей. Перевод с языка на язык делает компилятор. В главе 52 вы напишете свой, для «Искры-8»: строки на маленьком языке будут сами превращаться в такие же листинги, как этот.

Переводчик и толмач

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

Компилировать Python сразу в машинный код мешает, в частности, то, что из текста неизвестно, что будет складывать s += x: целые, дроби или строки. Это выясняется только во время работы. Поэтому есть третий путь — JIT-компиляция, компиляция «на лету». Исполнитель сначала интерпретирует программу, присматривается, какие куски выполняются чаще всего и с какими типами, и переводит именно их в машинный код. Так работают Java, JavaScript в вашем браузере и PyPy — другая реализация Python. В CPython 3.13 появился экспериментальный JIT-компилятор (PEP 744), по умолчанию он выключен. Специализация, которую мы поймали в разделе о байт-коде, — первый шаг на этом пути.

У интерпретации есть и достоинство, и в этой главе оно уже сработало. Байт-код одинаков на любом процессоре: модуль dis показал бы те же команды и на ноутбуке с ARM, и на сервере с x86-64, а машинный код для них приходится компилировать отдельно. Потому листинги x86 мы и готовили заранее, а байт-код получали прямо в песочнице. Это та же переносимость, ради которой Ритчи делал C, только поднятая ещё на этаж выше.

Замер: Python против C

Пора назвать цену числом. Возьмём цикл, в котором почти нет ничего, кроме арифметики, и прогоним его тремя способами: на чистом Python, через numpy (там цикл написан на C внутри библиотеки) и на C. Время для C измеряет сама программа на C функцией clock(), для Python — timeit.

У нас на сервере курса вышло несколько десятков наносекунд на шаг у Python, около двух у numpy и одна-две у C. Ваши числа будут другими — они зависят от процессора и от того, чем он занят, — но порядок сохранится: Python в десятки раз медленнее. И это при том, что tcc, который компилирует C в песочнице, почти ничего не оптимизирует. Оптимизирующий компилятор сделал бы цикл ещё быстрее.

Теперь мы можем объяснить каждую наносекунду. Пропустите work через dis: на шаг цикла приходится десять команд байт-кода. Каждая — проход по циклу интерпретатора: выбрать, разобрать, прыгнуть к обработчику. Каждый BINARY_OP проверяет типы. Числа i * i доходят до девяти триллионов и не помещаются в маленькие объекты, которые Python держит наготове, поэтому почти каждое промежуточное значение — новый объект в куче, который надо создать, а потом освободить, когда число ссылок на него (то самое поле из главы 14) упадёт до нуля. В C на шаг уходит пара десятков машинных команд, и i * i среди них — одна команда умножения. Это у tcc, который даже i и s держит в памяти, а не в регистрах.

Практическое правило на завтра такое. Если программа тормозит, сначала найдите место, где она проводит время, профилировщиком из главы 13. Почти всегда это один внутренний цикл. Его стоит отдать коду, написанному на C: встроенным функциям (sum, sorted, str.join, collections.Counter), numpy для чисел, а если ничего готового нет — модулю на C или другому способу компиляции. Остальные девяносто процентов программы пусть остаются на удобном Python.

Задачи

Куда дальше

Цена каждого слоя теперь видна в наносекундах, и кажется, что о скорости мы знаем всё: меньше команд — быстрее. Проверим на матрице $4096 \times 4096$, которая лежит в памяти строка за строкой. Сложим её элементы дважды, сначала по строкам, потом по столбцам. Работа одна и та же: те же шестнадцать миллионов сложений, те же числа, одинаковый код, только два цикла поменялись местами.

Суммы совпали, а время — нет: у нас обход по столбцам оказался медленнее примерно в шесть раз. Число машинных команд одинаковое, значит, дело не в них. Видимо, память отвечает на разные вопросы с разной скоростью: что-то в ней лежит близко, а что-то далеко. Насколько далеко и почему — в главе 34.