Ваш компьютер не является быстрой версией PDP-11
Привет!
Меня зовут Антон Довгаль, я С (и не только) разработчик в Badoo.
Мне попалась на глаза статья Дэвида Чизнэлла, исследователя Кембриджского университета, в которой он оспаривает общепринятое суждение о том, что С — язык низкого уровня, и его аргументы мне показались достаточно интересными.
В свете недавно обнаруженных уязвимостей Meltdown и Spectre стоит потратить время на выяснение причин их появления. Обе эти уязвимости эксплуатировали спекулятивное выполнение инструкций процессорами и позволяли атакующему получать результаты по сторонним каналам. Вызвавшие уязвимости особенности процессоров наряду с некоторыми другими были добавлены для того, чтобы программисты на C продолжали верить, что они программируют на языке низкого уровня, хотя это не так уже десятки лет.
Производители процессоров не одиноки в этом. Разработчики компиляторов C/C++ тоже внесли свою лепту.
Что такое язык низкого уровня?
Американский учёный в области компьютерных технологий и первый лауреат премии Тьюринга Алан Перлис дал такое определение:
«Язык программирования является низкоуровневым, если написанные на нём программы требуют внимания к несущественному».
Хотя это определение относится к С, оно не даёт понимания того, что люди желают видеть в языке низкого уровня. Различные свойства заставляют людей считать язык низкоуровневым. Представьте некую шкалу языков программирования с ассемблером на одном конце и интерфейсом к компьютеру Enterprise — на другом. Низкоуровневые языки «ближе к железу», тогда как высокоуровневые ближе к тому, как думают люди.
Чтобы быть «ближе к железу», язык должен предоставлять абстракции, которые соответствуют абстракциям целевой платформы. Легко доказать, что С был низкоуровневым языком в PDP-11. Последовательное выполнение программ, плоское адресное пространство, даже операторы пре- и постинкремента отлично ложились на режимы адресации PDP-11.
Быстрые эмуляторы PDP-11
Ключевая причина появления уязвимостей Spectre и Meltdown в том, что создатели процессоров не просто делали быстрые процессоры, а делали быстрые процессоры с интерфейсом PDP-11. Это важно, потому что позволяет программистам на С и дальше верить в то, что их язык близок к аппаратной части.
Код С предоставляет в основном последовательный абстрактный автомат (до C11 — полностью последовательный, если исключить нестандартные расширения). Создание нового потока — это вызов функции библиотеки, операция, которая довольно дорога. Поэтому процессоры, желая продолжать выполнять код C, полагаются на параллелизм на уровне команд (instruction-level parallelism, ILP). Они анализируют соседние операции и выполняют независимые параллельно. Это значительно усложняет процессоры и приводит к увеличению потребления энергии, но позволяет программистам писать по большей части последовательный код. В противоположность этому графические процессоры (GPU) достигают высокой производительности другим путём: они требуют написания параллельных программ.
Высокий параллелизм на уровне команд является прямой причиной появления Spectre и Meltdown. Современный процессор Intel выполняет до 180 инструкций одновременно (в отличие от последовательной абстрактной машины C, которая ожидает, что предыдущая инструкция выполнится перед тем, как начнётся выполнение следующей). Типичная эвристика кода на С показывает, что есть одно ветвление в среднем на каждые семь инструкций. Если вы хотите держать конвейер инструкций полным, то вам нужно угадать следующие 25 ветвей. Это, в свою очередь, добавляет сложности — неправильно угаданную ветвь процессор сначала просчитает, а потом результаты расчётов выбросит, что негативно влияет на энергопотребление. Эти выброшенные данные имеют видимые косвенные результаты, что и было использовано в атаках Spectre и Meltdown.
Переименование регистров потребляет много энергии и площади кристалла в современных процессорах. Его нельзя отключить или уменьшить его потребление энергии, что делает его неудобным в эпоху «тёмного кремния», когда транзисторы стоят мало, но задействованные транзисторы являются ценным ресурсом. Это устройство отсутствует в GPU, где параллелизм достигается путём использования потоков вместо попыток параллельного выполнения изначально последовательного кода. Если инструкции не имеют зависимостей, которые нужно перестраивать, то и в переименовании регистров нет необходимости.
Рассмотрим ещё одну фундаментальную часть дизайна С: плоскую память. Её не существует уже пару десятилетий. Современный процессор зачастую имеет три уровня кеширования между регистрами и основной памятью, чтобы таким образом уменьшить время на обращение к последней.
Кеш скрыт от программиста и потому недоступен из C. Эффективное использование кеша — это один из способов ускорить выполнение кода на современном процессоре, однако он полностью скрыт от абстрактной машины и программисты вынуждены полагаться на знание деталей имплементации кеша (например, что два выровненных 64-битных значения могут оказаться в одной строке кеша) для написания эффективного кода.
Оптимизация С
Одна из общих характеристик, приписываемых языкам низкого уровня, — скорость. В частности, их должно быть легко транслировать в быстрый код без сложного компилятора. Тот аргумент, что достаточно умный компилятор может сделать язык быстрым, зачастую игнорируется сторонниками С, когда они говорят о других языках.
К сожалению, с помощью простой трансляции нельзя получить быстрый код из С.
Архитекторы процессоров прикладывают героические усилия для создания чипов, которые могут выполнять код на С быстро. Но уровни быстродействия, которые ожидают увидеть программисты, достигаются только с помощью невероятно сложных оптимизаций, выполняемых компилятором.
Компилятор Clang (включая соответствующие части LLVM) — это около 2 млн строк кода. Для анализа и трансформации кода, которые необходимы для ускорения С, нужны около 200 000 строк кода (без учёта комментариев и пустых строк).
Например, для обработки большого количества данных в C нужно написать цикл, который обрабатывает каждый элемент последовательно. Для оптимального выполнения этого цикла на современном процессоре компилятор должен определить, что итерации цикла не зависят друг от друга. Ключевое слово restrict может помочь в этом случае — оно гарантирует, что записи в один указатель не будут мешать чтению из другого указателя. Эта информация в C гораздо более ограниченна, чем в таком языке, как Fortran, что является основной причиной того, что C не сумел вытеснить его из сферы высокопроизводительных вычислений.
После того как компилятор определил, что итерации независимы друг от друга, следующий шаг — попытка векторизировать результат, потому что пропускная способность современных процессоров в четыре—восемь раз выше для векторизированного кода, чем для скалярного. Язык низкого уровня для таких процессоров имел бы собственные векторные типы произвольной длины. В промежуточном представлении LLVM присутствуют как раз такие типы, потому что всегда проще разбить большие операции с векторами на несколько маленьких, чем конструировать бОльшие векторные операции.
На этом этапе оптимизаторам приходится бороться с правилами работы памяти C. С гарантирует, что структуры с одинаковым префиксом могут использоваться взаимозаменяемо, и предоставляет доступ к смещению полей структур в языке. Это означает, что компилятор не может изменить очерёдность полей в структуре или добавить выравнивание для улучшения векторизации (например, трансформировав структуру из массивов в массив структур или наоборот). Это обычно не является проблемой в языках низкого уровня, где есть возможность контроля над расположением полей в структуре, но это делает сложнее задачу ускорения C.
C также требует выравнивания в конце структуры, поскольку он гарантирует отсутствие выравнивания в массивах. Выравнивание — довольно сложная часть спецификации C, которая плохо взаимодействует с другими частями языка. Например, у вас должна быть возможность сравнить две структуры, используя метод сравнения без учёта типов (то есть функцию memcmp()), поэтому копия структуры тоже должна быть выровнена. В некоторых случаях копирование выравнивания занимает значительное время.
Рассмотрим две базовые оптимизации, которые производит компилятор C: SROA (scalar replacement of aggregates, скалярная замена агрегатов) и размыкание цикла.
SROA пытается заменить структуры и массивы фиксированного размера на отдельные переменные. Это позволяет компилятору обрабатывать доступ к ним независимо друг от друга и игнорировать операцию, если очевидно, что её результат не используется. В некоторых случаях косвенным эффектом этой оптимизации является удаление выравнивания.
Вторая оптимизация, размыкание цикла, преобразует цикл с условием в условие с разными циклами в обеих ветвях. Это меняет порядок выполнения в противовес утверждению о том, что программист знает, что будет выполняться на языке низкого уровня. И ещё это создаёт серьёзные проблемы с тем, как в C обрабатываются неопределённые переменные и неопределённое поведение.
В С неинициализированная переменная имеет неопределённое значение, которое может быть разным при каждом обращении. Это важно, поскольку позволяет реализовать ленивую переработку (lazy recycling) страниц памяти. Например, во FreeBSD реализация malloc() сообщает системе, что страницы более не задействованы, а система использует первую запись в страницу как доказательство того, что это не так. Обращение к только что выделенной памяти может получить старое значение, тогда операционная система может повторно использовать страницу памяти, после чего заменить её на заполненную нулями страницу при следующей записи в другое место страницы. Второе обращение к тому же месту страницы получит нулевое значение.
Если в условии используется неопределённое значение, то результат тоже не определён — может произойти что угодно. Представьте оптимизацию по размыканию цикла, где цикл выполняется ноль раз. В оригинале весь цикл является мёртвым кодом. В разомкнутой версии теперь есть условие с переменной, которая может быть не инициализирована.
В результате мёртвый код может быть преобразован в неопределённое поведение. Это только одна из многих оптимизаций, которые при более тщательном исследовании семантики C оказываются ненадёжными.
В итоге можно заставить код на C работать быстро, но только затратив тысячи человеко-лет на создание достаточно умного компилятора. Но и это возможно только при условии нарушения некоторых правил языка. Создатели компиляторов позволяют программистам на C представлять, что они пишут код, который «близок к железу», но им приходится генерировать машинный код, который ведёт себя по-другому, чтобы программисты продолжали верить в то, что они пишут на быстром языке.
Понимая C
Одним из базовых атрибутов языка низкого уровня является то, что программисты могут легко понять, как абстрактная машина языка переносится на физическую машину. Это определённо было так на PDP-11, где выражения на C транслировались в одну или две инструкции. Аналогично компилятор клал переменные в слоты стека и преобразовывал простые типы в понятные для PDP-11.
С тех пор реализации C стали гораздо сложнее — для поддержания иллюзии того, что C легко переносится на аппаратную платформу и работает быстро. В 2015 году результаты опроса среди программистов на C, авторов компиляторов и членов комитета по стандартизации показали, что существуют проблемы с пониманием C. Например, этот язык позволяет реализации добавлять выравнивание в структуры (но не в массивы), чтобы гарантировать, что все поля правильно выровнены для целевой платформы. Если вы заполните эту структуру нулями и потом укажете значение некоторым полям, будут ли в битах выравнивания нули? Согласно результатам опроса, 36% были уверены, что будут, а 29% опрошенных не знали ответа. В зависимости от компилятора и уровня оптимизации это может быть правдой (или нет).
Это довольно тривиальный пример, однако многие программисты или дают неправильный ответ, или не могут ответить вовсе.
Если добавить указатели, семантика C становится ещё более запутанной. Модель BCPL была довольно проста: все значения являются словами. Каждое слово — это или данные, или адрес в памяти. Память — это плоский массив ячеек с индексацией по адресу.
Модель С позволяет реализацию для разных платформ, включая сегментированные архитектуры, где указатель может состоять из ID сегмента и смещения, а также виртуальные машины со сборщиком мусора. Спецификация C ограничивает разрешённые операции с указателями, чтобы избежать проблем с такими системами. Ответ на Defect Report 260 содержит упоминание происхождения указателя:
«Реализации могут следить за происхождением набора битов и обращаться с содержащими неопределённое значение иначе, чем с теми, которые содержат определённое. Они могут обращаться с указателями по-разному в зависимости от их происхождения, даже если они одинаковы с точки зрения их битового значения».
К сожалению, слово «происхождение» отсутствует в спецификации C11, поэтому компиляторы сами решают, что оно означает. GCC и Clang, например, отличаются в том, сохраняет ли своё происхождение указатель, который конвертировали в целое и назад. Компиляторы могут решить, что два указателя на результаты malloc() при сравнении всегда дают отрицательный результат, даже если они указывают на один и тот же адрес.
Эти недопонимания не являются сугубо академическими. Например, уже наблюдались уязвимости, которые стали результатом переполнения знакового целого (неопределённое поведение в C) или разыменования указателя до его проверки на NULL, притом что компилятору было указано, что указатель не может быть NULL.
При наличии подобных проблем сложно ожидать от программиста полного понимания того, как программа на C транслируется на соответствующую архитектуру.
Представляя процессор не для C
Предлагаемые исправления для защиты от Spectre и Meltdown вызывают серьёзное ухудшение производительности, сводя на нет все достижения микроархитектуры за последнее десятилетие. Возможно, пора перестать думать о том, как сделать код на C быстрее, и вместо этого задуматься о новых моделях программирования на процессорах, которые созданы для скорости.
Есть множество примеров архитектур, которые не были сфокусированы на традиционном коде C и из которых можно черпать вдохновение. Например, такие ориентированные на многопоточность процессоры, как Sun/Oracle UltraSPARC Tx, не требуют столько кеша, чтобы держать занятыми свои исполнительные устройства. Исследовательские процессоры расширили этот концепт до очень большого количества аппаратно-планируемых потоков. Ключевая идея состоит в том, что с достаточным количеством потоков процессор может приостановить те потоки, которые ожидают данных, и наполнить исполнительные устройства инструкциями из других потоков. Проблема же состоит в том, что программы на C обычно имеют очень мало потоков.
ARM’s SVE (Scalar Vector Extensions, скалярные векторные расширения) — ещё одна аналогичная работа из Беркли, которая предлагает взглянуть на улучшенный интерфейс между программой и аппаратным обеспечением. Обычные блоки векторизации реализуют операции с векторами фиксированного размера и ожидают, что компилятор адаптирует алгоритм к указанному размеру. В противоположность этому интерфейс SVE предлагает программисту самостоятельно описать уровень параллелизма и ожидает, что аппаратная часть самостоятельно адаптирует его к имеющимся в наличии исполнительным устройствам. Использовать это в C сложно, потому что автовекторизатор должен рассчитать параллелизм на основании циклов в коде.
Кеши имеют большой размер, но это не единственная причина их сложности. Протокол поддержки когерентности кеша — одна из сложнейших составляющих современного процессора. Большая часть сложности появляется из-за того, что нужно поддерживать язык, в котором данные могут быть одновременно разделяемыми и изменяемыми. В качестве обратного примера можно привести абстрактную машину в стиле Erlang, где каждый объект или локальный, или неизменяемый. Протокол когерентности кеша для такой системы имел бы только два случая: изменяемые данные и разделяемые данные. Кеш программного потока, который перенесли на другой процессор, нужно явно инвалидировать, но это относительно редкая операция.
Неизменяемые объекты могут упростить кеши ещё больше, а также сделать некоторые операции дешевле. В проекте Maxwell от Sun Labs было отмечено, что объекты в кеше и недавно созданные объекты — почти всегда одни и те же. Если объекты умирают до того, как их исключают из кеша, то можно не записывать их в основную память и таким образом сэкономить потребление энергии. Проект Maxwell предложил сборщик мусора, который работал в кеше и позволял быстро перерабатывать память. С неизменяемыми объектами в куче и изменяемым стеком сборщик мусора становится очень простым конечным автоматом, который легко реализуется в аппаратной части и позволяет эффективно использовать относительно небольшой кеш.
Процессор, который создан исключительно для скорости, а не для компромисса между скоростью и поддержкой C, вероятно, должен поддерживать большое количество потоков, иметь большие блоки векторизации и более простую модель памяти. Выполнять код на C на таком процессоре будет сложно, поэтому, учитывая объём старого кода на C в мире, он вряд ли будет иметь коммерческий успех.
В сфере разработки программного обеспечения есть миф о том, что параллельное программирование — это сложно. Алан Кэй был бы очень удивлён, услышав это: он научил детей использовать модель акторов, с помощью которой они писали программы на более чем 200 потоков. Это неизвестно и программистам на Erlang, которые часто пишут программы с тысячами параллельных компонентов. Более правильно говорить, что параллельно программирование сложно на языке с абстрактной машиной, подобной C. И если обратить внимание на преобладание параллельного аппаратного обеспечения (от многоядерных процессоров до многоядерных GPU), то это просто ещё один способ сказать, что C не подходит для современного аппаратного обеспечения.
Автор: Antony Dovgal
