Хабрахабр

[Перевод] С — не низкоуровневый язык

Ваш компьютер не является быстрой версией 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) достигают высокой производительности другим путём: они требуют написания параллельных программ. Это значительно усложняет процессоры и приводит к увеличению потребления энергии, но позволяет программистам писать по большей части последовательный код.

Современный процессор Intel выполняет до 180 инструкций одновременно (в отличие от последовательной абстрактной машины C, которая ожидает, что предыдущая инструкция выполнится перед тем, как начнётся выполнение следующей). Высокий параллелизм на уровне команд является прямой причиной появления Spectre и Meltdown. Если вы хотите держать конвейер инструкций полным, то вам нужно угадать следующие 25 ветвей. Типичная эвристика кода на С показывает, что есть одно ветвление в среднем на каждые семь инструкций. Эти выброшенные данные имеют видимые косвенные результаты, что и было использовано в атаках Spectre и Meltdown. Это, в свою очередь, добавляет сложности — неправильно угаданную ветвь процессор сначала просчитает, а потом результаты расчётов выбросит, что негативно влияет на энергопотребление.

Его нельзя отключить или уменьшить его потребление энергии, что делает его неудобным в эпоху «тёмного кремния», когда транзисторы стоят мало, но задействованные транзисторы являются ценным ресурсом. Переименование регистров потребляет много энергии и площади кристалла в современных процессорах. Если инструкции не имеют зависимостей, которые нужно перестраивать, то и в переименовании регистров нет необходимости. Это устройство отсутствует в GPU, где параллелизм достигается путём использования потоков вместо попыток параллельного выполнения изначально последовательного кода.

Её не существует уже пару десятилетий. Рассмотрим ещё одну фундаментальную часть дизайна С: плоскую память. Современный процессор зачастую имеет три уровня кеширования между регистрами и основной памятью, чтобы таким образом уменьшить время на обращение к последней.

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

Оптимизация С

Одна из общих характеристик, приписываемых языкам низкого уровня, — скорость. В частности, их должно быть легко транслировать в быстрый код без сложного компилятора. Тот аргумент, что достаточно умный компилятор может сделать язык быстрым, зачастую игнорируется сторонниками С, когда они говорят о других языках.

Но уровни быстродействия, которые ожидают увидеть программисты, достигаются только с помощью невероятно сложных оптимизаций, выполняемых компилятором.
Компилятор Clang (включая соответствующие части LLVM) — это около 2 млн строк кода. К сожалению, с помощью простой трансляции нельзя получить быстрый код из С.
Архитекторы процессоров прикладывают героические усилия для создания чипов, которые могут выполнять код на С быстро. Для анализа и трансформации кода, которые необходимы для ускорения С, нужны около 200 000 строк кода (без учёта комментариев и пустых строк).

Для оптимального выполнения этого цикла на современном процессоре компилятор должен определить, что итерации цикла не зависят друг от друга. Например, для обработки большого количества данных в C нужно написать цикл, который обрабатывает каждый элемент последовательно. Эта информация в C гораздо более ограниченна, чем в таком языке, как Fortran, что является основной причиной того, что C не сумел вытеснить его из сферы высокопроизводительных вычислений. Ключевое слово restrict может помочь в этом случае — оно гарантирует, что записи в один указатель не будут мешать чтению из другого указателя.

Язык низкого уровня для таких процессоров имел бы собственные векторные типы произвольной длины. После того как компилятор определил, что итерации независимы друг от друга, следующий шаг — попытка векторизировать результат, потому что пропускная способность современных процессоров в четыре—восемь раз выше для векторизированного кода, чем для скалярного. В промежуточном представлении 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.

В 2015 году результаты опроса среди программистов на C, авторов компиляторов и членов комитета по стандартизации показали, что существуют проблемы с пониманием C. С тех пор реализации C стали гораздо сложнее — для поддержания иллюзии того, что C легко переносится на аппаратную платформу и работает быстро. Если вы заполните эту структуру нулями и потом укажете значение некоторым полям, будут ли в битах выравнивания нули? Например, этот язык позволяет реализации добавлять выравнивание в структуры (но не в массивы), чтобы гарантировать, что все поля правильно выровнены для целевой платформы. В зависимости от компилятора и уровня оптимизации это может быть правдой (или нет). Согласно результатам опроса, 36% были уверены, что будут, а 29% опрошенных не знали ответа.

Это довольно тривиальный пример, однако многие программисты или дают неправильный ответ, или не могут ответить вовсе.

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

Спецификация C ограничивает разрешённые операции с указателями, чтобы избежать проблем с такими системами. Модель С позволяет реализацию для разных платформ, включая сегментированные архитектуры, где указатель может состоять из ID сегмента и смещения, а также виртуальные машины со сборщиком мусора. Ответ на Defect Report 260 содержит упоминание происхождения указателя:

Они могут обращаться с указателями по-разному в зависимости от их происхождения, даже если они одинаковы с точки зрения их битового значения». «Реализации могут следить за происхождением набора битов и обращаться с содержащими неопределённое значение иначе, чем с теми, которые содержат определённое.

К сожалению, слово «происхождение» отсутствует в спецификации C11, поэтому компиляторы сами решают, что оно означает. GCC и Clang, например, отличаются в том, сохраняет ли своё происхождение указатель, который конвертировали в целое и назад. Компиляторы могут решить, что два указателя на результаты malloc() при сравнении всегда дают отрицательный результат, даже если они указывают на один и тот же адрес.

Например, уже наблюдались уязвимости, которые стали результатом переполнения знакового целого (неопределённое поведение в C) или разыменования указателя до его проверки на NULL, притом что компилятору было указано, что указатель не может быть NULL. Эти недопонимания не являются сугубо академическими.

При наличии подобных проблем сложно ожидать от программиста полного понимания того, как программа на C транслируется на соответствующую архитектуру.

Представляя процессор не для C

Предлагаемые исправления для защиты от Spectre и Meltdown вызывают серьёзное ухудшение производительности, сводя на нет все достижения микроархитектуры за последнее десятилетие. Возможно, пора перестать думать о том, как сделать код на C быстрее, и вместо этого задуматься о новых моделях программирования на процессорах, которые созданы для скорости.

Например, такие ориентированные на многопоточность процессоры, как Sun/Oracle UltraSPARC Tx, не требуют столько кеша, чтобы держать занятыми свои исполнительные устройства. Есть множество примеров архитектур, которые не были сфокусированы на традиционном коде C и из которых можно черпать вдохновение. Ключевая идея состоит в том, что с достаточным количеством потоков процессор может приостановить те потоки, которые ожидают данных, и наполнить исполнительные устройства инструкциями из других потоков. Исследовательские процессоры расширили этот концепт до очень большого количества аппаратно-планируемых потоков. Проблема же состоит в том, что программы на C обычно имеют очень мало потоков.

Обычные блоки векторизации реализуют операции с векторами фиксированного размера и ожидают, что компилятор адаптирует алгоритм к указанному размеру. ARM’s SVE (Scalar Vector Extensions, скалярные векторные расширения) — ещё одна аналогичная работа из Беркли, которая предлагает взглянуть на улучшенный интерфейс между программой и аппаратным обеспечением. Использовать это в C сложно, потому что автовекторизатор должен рассчитать параллелизм на основании циклов в коде. В противоположность этому интерфейс SVE предлагает программисту самостоятельно описать уровень параллелизма и ожидает, что аппаратная часть самостоятельно адаптирует его к имеющимся в наличии исполнительным устройствам.

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

В проекте Maxwell от Sun Labs было отмечено, что объекты в кеше и недавно созданные объекты  — почти всегда одни и те же. Неизменяемые объекты могут упростить кеши ещё больше, а также сделать некоторые операции дешевле. Проект Maxwell предложил сборщик мусора, который работал в кеше и позволял быстро перерабатывать память. Если объекты умирают до того, как их исключают из кеша, то можно не записывать их в основную память и таким образом сэкономить потребление энергии. С неизменяемыми объектами в куче и изменяемым стеком сборщик мусора становится очень простым конечным автоматом, который легко реализуется в аппаратной части и позволяет эффективно использовать относительно небольшой кеш.

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

Алан Кэй был бы очень удивлён, услышав это: он научил детей использовать модель акторов, с помощью которой они писали программы на более чем 200 потоков. В сфере разработки программного обеспечения есть миф о том, что параллельное программирование — это сложно. Более правильно говорить, что параллельно программирование сложно на языке с абстрактной машиной, подобной C. Это неизвестно и программистам на Erlang, которые часто пишут программы с тысячами параллельных компонентов. И если обратить внимание на преобладание параллельного аппаратного обеспечения (от многоядерных процессоров до многоядерных GPU), то это просто ещё один способ сказать, что C не подходит для современного аппаратного обеспечения.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть