Как может язык, чей компилятор написан на C, быть быстрее C?

Взглянув на веб-страницу Джулии , вы можете увидеть некоторые тесты нескольких языков по нескольким алгоритмам (время показано ниже). Как может язык с компилятором, изначально написанным на C, превзойти C-код?

Рисунок: время тестов относительно C (чем меньше, тем лучше, производительность C = 1,0).

Не существует необходимой связи между реализацией компилятора и выходными данными компилятора. Вы могли бы написать компилятор на языке, таком как Python или Ruby, чьи самые распространенные реализации очень медленные, и этот компилятор мог бы выводить высокооптимизированный машинный код, способный опередить C. Сам компилятору потребовалось бы много времени для запуска, потому что егокод написан на медленном языке. (Точнее говоря, написано на языке с медленной реализацией. Языки не являются по сути быстрыми или медленными, как отмечает Рафаэль в комментарии. Я расширяю эту идею ниже.) Скомпилированная программа будет работать так же быстро, как и ее. собственная реализация позволила - мы могли бы написать компилятор на Python, который генерирует тот же машинный код, что и компилятор Фортрана, и наши скомпилированные программы будут работать так же быстро, как и Фортран, даже если для их компиляции потребуется много времени.

Это другая история, если мы говорим о переводчике. Интерпретаторы должны быть запущены во время работы интерпретируемой программы, поэтому существует связь между языком, на котором реализован интерпретатор, и производительностью интерпретируемого кода. Требуется некоторая умная оптимизация времени выполнения, чтобы создать интерпретируемый язык, который работает быстрее, чем язык, на котором реализован интерпретатор, и конечная производительность может зависеть от того, насколько часть кода подходит для такого рода оптимизации. Многие языки, такие как Java и C #, используют среды выполнения с гибридной моделью, которая сочетает в себе некоторые преимущества интерпретаторов и некоторые преимущества компиляторов.

В качестве конкретного примера давайте более подробно рассмотрим Python. Python имеет несколько реализаций. Наиболее распространенным является CPython, интерпретатор байт-кода, написанный на C. Есть также PyPy, который написан на специализированном диалекте Python, называемом RPython, и использует гибридную модель компиляции, похожую на JVM. PyPy намного быстрее чем CPython в большинстве тестов; он использует все виды удивительных трюков для оптимизации кода во время выполнения. Тем не менее, язык Python, на котором работает PyPy, является точно таким же языком Python, на котором работает CPython, за исключением нескольких различий, которые не влияют на производительность.

Предположим, мы написали компилятор на языке Python для Fortran. Наш компилятор производит тот же машинный код, что и GFortran. Теперь мы скомпилируем программу на Фортране. Мы можем запустить наш компилятор поверх CPython или запустить его на PyPy, поскольку он написан на Python, и обе эти реализации работают на одном и том же языке Python. Мы обнаружим, что если мы запустим наш компилятор на CPython, затем запустим его на PyPy, а затем скомпилируем один и тот же исходный код Fortran с помощью GFortran, мы получим один и тот же машинный код все три раза, поэтому скомпилированная программа всегда будет работать примерно на той же скорости. Однако время, необходимое для создания этой скомпилированной программы, будет другим. CPython, скорее всего, займет больше времени, чем PyPy, а PyPy, скорее всего, займет больше времени, чем GFortran, хотя все они в конце будут выводить один и тот же машинный код.

При сканировании таблицы тестов на сайте Julia видно, что ни один из языков, работающих на интерпретаторах (Python, R, Matlab / Octave, Javascript), не имеет каких-либо критериев, где они превосходят C. Это в целом соответствует тому, что я ожидал увидеть, хотя я мог представить себе код, написанный с помощью высокооптимизированной библиотеки Numpy (написанной на C и Fortran) Python, превосходящей некоторые возможные реализации C подобного кода. Языки, которые равны или лучше чем C, компилируются (Fortran, Julia ) или используют гибридную модель с частичной компиляцией (Java и, возможно, LuaJIT). PyPy также использует гибридную модель, поэтому вполне возможно, что если бы мы запустили один и тот же код Python на PyPy вместо CPython, мы бы фактически увидели, что он побеждает C в некоторых тестах.

Как машина, созданная человеком, может быть сильнее человека? Это точно такой же вопрос.

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

Я хочу сделать одно замечание против общего предположения, которое, на мой взгляд, ошибочно до степени вредности при выборе инструментов для работы.

Нет такого понятия, как медленный или быстрый язык. ¹

На нашем пути к ЦП, который на самом деле что-то делает, есть много шагов².

1. По крайней мере, один программист с определенными навыками.
2. (Формальный) язык, на котором они программируют («исходный код»).
3. Библиотеки, которые они используют.
4. То, что переводит исходный код в машинный код (компиляторы, интерпретаторы).
5. Общая аппаратная архитектура, например, количество процессоров и схема иерархии памяти.
6. Операционная система, которая управляет оборудованием.
7. Оптимизация на процессоре.

Каждый отдельный элемент влияет на фактическое время выполнения, которое вы можете измерить, иногда в значительной степени. Различные «языки» фокусируются на разных вещах³.

Просто чтобы привести несколько примеров.

• 1 против 2-4 : среднестатистический программист на Си, скорее всего, будет производить код намного хуже, чем среднестатистический программист на Java, как с точки зрения корректности, так и эффективности. Это потому, что у программиста больше обязанностей в C.

• 1/4 против 7 : на низкоуровневом языке, таком как C, вы можете использовать некоторые функции процессора как программист . В языках более высокого уровня это может делать только компилятор / интерпретатор, и только если они знают целевой процессор.

• 1/4 против 5 : вы хотите или должны управлять макетом памяти, чтобы наилучшим образом использовать архитектуру памяти под рукой? Некоторые языки дают вам контроль над этим, некоторые нет.

• 2/4 против 3 : Интерпретируемый Python сам по себе ужасно медленный, но есть популярные привязки к высоко оптимизированным, скомпилированным в нативе библиотекам для научных вычислений. Таким образом, выполнение определенных действий в Python в конце концов происходит быстро , если большая часть работы выполняется этими библиотеками.

• 2 против 4 : Стандартный интерпретатор Ruby довольно медленный. JRuby, с другой стороны, может быть очень быстрым. То есть тот же язык быстро использует другой компилятор / интерпретатор.

• 1/2 против 4. Используя оптимизацию компилятора, простой код можно перевести в очень эффективный машинный код.

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

Чтобы было ясно, это отвечает на вопрос, потому что показывает, что язык, на котором написан компилятор (шаг 4), является всего лишь одним из кусочков головоломки и, вероятно, вообще не имеет значения (см. Другие ответы).

1. Конечно, есть языковые функции, которые дороже, чем другие. Но наличие функций не означает, что вы должны их использовать, а дорогая функция может сэкономить использование многих более дешевых и, следовательно, окупиться в итоге. (Из других преимуществ, которые нельзя измерить во время работы.)
2. Я пропускаю алгоритмический уровень, потому что он не всегда применим и в основном не зависит от используемого языка программирования. Имейте в виду, что, например, разные алгоритмы лучше подходят для разных аппаратных средств.

3. Я намеренно не рассматриваю здесь другие показатели успеха: эффективность времени выполнения, эффективность использования памяти, время разработки, безопасность, безопасность, (доказуемость?) Правильность, поддержка инструментов, независимость от платформы, ...

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

Здесь есть одна забытая вещь об оптимизации.

Были долгие споры о том, что Fortran превзошел C. Разъединенные уродливые дебаты: один и тот же код был написан на C и Fortran (как думали тестировщики), и производительность тестировалась на основе тех же данных. Проблема в том, что эти языки различаются, C позволяет использовать псевдонимы для указателей, а Fortran - нет.

Таким образом, коды не были одинаковыми, в тестируемых файлах C не было __restrict, что дало различия, после того как файлы были переписаны, чтобы сообщить компилятору о том, что он может оптимизировать указатели, среды выполнения становятся похожими.

Дело в том, что некоторые методы оптимизации проще (или начинают быть законными) во вновь созданном языке.

Также это возможно в долгосрочной перспективе для виртуальной машины с JIT, превосходящей C. Есть две возможности:
JIT-код может использовать преимущества машины, на которой он его размещает (например, некоторые SSE или другие эксклюзивные для некоторых векторизованных команд ЦП), которые не были реализованы в сравниваемая программа.$X$

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

В этом тесте также есть JS, и есть более быстрые виртуальные машины, чем V8, и он также работает быстрее, чем C в некоторых тестах.

Я проверил это, и были уникальные методы оптимизации, еще не доступные в C-компиляторах.

Компилятор C должен был бы выполнить статический анализ всего кода сразу, пройтись по данной платформе и обойти проблемы с выравниванием памяти.

ВМ просто транслитерирует часть кода в оптимизированную сборку и запускает ее.

О Джулии - когда я проверял, что он работает с AST кода, например, GCC пропустил этот шаг, и недавно начал получать оттуда некоторую информацию. Это плюс другие ограничения и методы VM могут объяснить немного.

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

Компилятор C генерирует переменные загрузки из регистров.
Но во время выполнения эти переменные известны и рассматриваются как константы при выполнении.
Таким образом, вместо загрузки переменных из регистров (и не выполнения кэширования, потому что оно может измениться, а из статического анализа это не ясно), они обрабатываются полностью как константы и складываются и распространяются.

Предыдущие ответы дают в значительной степени объяснение, хотя в основном с прагматической точки зрения, поскольку вопрос имеет смысл , что превосходно объясняется ответом Рафаэля .

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

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

Что такое компилятор?

Компилятор , сокращенно до если нет двусмысленности, является реализацией вычислимой функции которая будет переводить программный текст вычисляющий функцию , написанный на языке источника в текст программы , написанной на целевом языке , который должен вычислить ту же функцию .$C_{S\to T}$$C$$\mathcal C_{S\to T}$$P_{:S}$$\mathcal P$ $S$$P_{:T}$ $T$$\mathcal P$

С семантической точки зрения, т.е. denotationally , это не имеет значения , как эта функция компиляции вычисляется, т.е. то, что реализация выбрана. Это может быть даже сделано волшебным оракулом. Математически, функция - это просто набор пар .$\mathcal C_{S\to T}$$C_{S\to T}$$\{(P_{:S},P_{:T})\mid P_S\in S \wedge P_T\in T\}$

Семантическая функция компилирование является правильным , если оба и вычислить ту же самую функцию . Но эта формализация применима и к некорректному компилятору. Единственный момент заключается в том, что независимо от того, что реализовано, достигается тот же результат независимо от средств реализации. Семантически важно то, что делается компилятором, а не то, как (и как быстро) это делается.$\mathcal C_{S\to T}$$P_S$$P_T$$\mathcal P$

На самом деле получение из является оперативной проблемой, которая должна быть решена. Вот почему функция компиляции должна быть вычислимой функцией. Тогда любой язык, обладающий мощью Тьюринга, независимо от того, насколько он медленный, обязательно сможет создавать код, столь же эффективный, как и любой другой язык, даже если он может делать это менее эффективно.$P_{:T}$$P_{:S}$$\mathcal C_{S\to T}$

Уточняя аргумент, мы, вероятно, хотим, чтобы компилятор имел хорошую эффективность, чтобы перевод мог быть выполнен в разумные сроки. Таким образом, производительность программы компилятора важна для пользователей, но не влияет на семантику. Я говорю о производительности, потому что теоретическая сложность некоторых компиляторов может быть намного выше, чем можно было бы ожидать.

О начальной загрузке

Это проиллюстрирует различие и покажет практическое применение.

В настоящее время общее место , чтобы сначала осуществить язык с переводчиком , а затем написать компилятор в языке самой. Этот компилятор может быть запущен с интерпретатором для преобразования любой программы в программу . Таким образом, у нас есть работающий компилятор с языка на (машинный?) Язык , но он очень медленный, хотя бы потому, что работает поверх интерпретатора.I S C S → $S$$I_S$ S C S → $C_{S\to T\,:S}$$S$ I S P : S P : T S$C_{S\to T\,:S}$$I_S$$P_{:S}$$P_{:T}$$S$$T$

Но вы можете использовать это средство компиляции для компиляции компилятора , поскольку он написан на языке , и, таким образом, вы получите компилятор написанный на целевой язык . Если предположить, как это часто бывает, что является язык , который более эффективно интерпретировать (машинный родной, например), то вы получите более быструю версию компилятора работает непосредственно на языке . Он выполняет точно такую ​​же работу (т. Е. Производит те же целевые программы), но делает это более эффективно. S C S → $C_{S\to T\,:S}$$S$ TT$C_{S\to T\,:T}$$T$$T$$T$

По теореме Blum об ускорении существуют программы, которые написаны и работают на самой быстрой комбинации компьютер / компилятор, и будут работать медленнее, чем программа на том же самом компьютере на вашем первом компьютере, на котором работает интерпретированный BASIC. Там просто не самый быстрый язык. Все, что вы можете сказать, это то, что если вы пишете один и тот же алгоритм на нескольких языках (реализации; как уже было отмечено, существует множество различных компиляторов C, и я даже сталкивался с довольно способным интерпретатором C), он будет работать быстрее или медленнее в каждом из них. ,

Не может быть "всегда более медленной" иерархии. Это явление, которое знают все люди, владеющие несколькими языками: каждый язык программирования был разработан для конкретного типа приложений, а наиболее используемые реализации были любовно оптимизированы для программ такого типа. Я почти уверен, что, например, программа для дурачения со строками, написанными на Perl, вероятно, победит тот же алгоритм, написанный на C, в то время как программа, работающая с большими массивами целых чисел в C, будет быстрее, чем Perl.

Давайте вернемся к исходной строке: «Как язык, чей компилятор написан на C, может быть быстрее, чем C?» Я думаю, что это действительно означало сказать: как программа, написанная на Юлии, ядро ​​которой написано на C, может быть быстрее, чем программа, написанная на C? В частности, как могла бы программа «Мандель», написанная на Джулии, выполняться за 87% времени выполнения эквивалентной программы «Мандель», написанной на С?

Трактат Бабу до сих пор является единственным правильным ответом на этот вопрос. Все остальные ответы пока более или менее отвечают на другие вопросы. Проблема с текстом Бабу состоит в том, что теоретическое описание «Что такое компилятор», состоящее из многих абзацев, написано в терминах, которые, вероятно, трудно понять оригинальному постеру. Любой, кто схватывает понятия, на которые ссылаются слова «семантический», «денотационный», «реализация», «вычислимый» и т. Д., Уже знает ответ на этот вопрос.

Более простой ответ заключается в том, что ни код C, ни код Julia не могут напрямую выполняться машиной. Оба должны быть переведены, и этот процесс перевода предлагает множество способов, с помощью которых исполняемый машинный код может работать медленнее или быстрее, но при этом все же давать один и тот же конечный результат. И С, и Джулия делают компиляцию, что означает серию переводов в другую форму. Обычно текстовый файл, читаемый человеком, преобразуется во некоторое внутреннее представление, а затем записывается в виде последовательности инструкций, которые компьютер может понять непосредственно. С некоторыми языками есть нечто большее, чем это, и Джулия - одна из них - у нее есть компилятор "JIT", что означает, что весь процесс перевода не должен происходить сразу для всей программы. Но конечным результатом для любого языка является машинный код, который не нуждается в дальнейшем переводе, код, который можно отправить непосредственно в процессор, чтобы он что-то сделал. В конце концов, это «вычисление», и существует более одного способа сообщить процессору, как получить желаемый ответ.

Можно представить себе язык программирования, который имеет операторы «плюс» и «умножение», и другой язык, который имеет только «плюс». Если ваши вычисления требуют умножения, один язык будет «медленнее», потому что, конечно, процессор может делать оба сразу, но если у вас нет никакого способа выразить необходимость умножения 5 * 5, вам остается написать «5 + 5 + 5 + 5 + 5 ". Последний займет больше времени, чтобы прийти к тому же ответу. Предположительно, это происходит с Джулией; возможно, язык позволяет программисту сформулировать желаемую цель вычисления множества Мандельброта таким образом, который невозможно напрямую выразить в C.

Процессор, использованный для тестирования, был указан как процессор Xeon E7-8850 2,00 ГГц. В тесте C использовался компилятор gcc 4.8.2 для создания инструкций для этого процессора, в то время как Julia использует среду компилятора LLVM. Возможно, что серверная часть gcc (часть, которая производит машинный код для конкретной архитектуры ЦП) не так продвинута, как серверная часть LLVM. Это может иметь значение в производительности. Также происходит много других вещей - компилятор может «оптимизировать», возможно, выполняя инструкции в ином порядке, чем это указано программистом, или даже вообще ничего не делать, если он может анализировать код и определять, что это не так. Требуется получить правильный ответ. И программист мог бы написать часть программы на C так, чтобы она была медленной, но не

Все это способы сказать: существует множество способов написания машинного кода для вычисления множества Мандельброта, и язык, который вы используете, оказывает большое влияние на то, как пишется этот машинный код. Чем больше вы понимаете, что такое компиляция, наборы инструкций, кэши и т. Д., Тем лучше вы будете получать желаемые результаты. Основным выводом из результатов тестов, приведенных для Юлии, является то, что ни один язык или инструмент не может быть лучшим во всем. Фактически, лучший фактор скорости на всем графике был для Java!

Скорость скомпилированной программы зависит от двух вещей:

1. Рабочие характеристики машины, выполняющей ее
2. Содержимое исполняемого файла

Язык, на котором написан компилятор, не имеет отношения к (1). Например, компилятор Java может быть написан на C, Java или Python, но во всех случаях «машиной», выполняющим программу, является JVM.

Язык, на котором написан компилятор, не имеет отношения к (2). Например, нет причины, по которой компилятор C, написанный на Python, не может вывести точно такой же исполняемый файл, как компилятор C, написанный на C или Java.

Я постараюсь предложить более короткий ответ.

Суть вопроса заключается в определении «скорости» языка .

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

* Предположения иногда ошибочны.

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

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