Может ли динамический язык, такой как Ruby / Python, достичь производительности, подобной C / C ++?

64

Интересно, можно ли создавать компиляторы для динамических языков, таких как Ruby, чтобы они были похожи и сопоставимы по производительности с C / C ++? Из того, что я понимаю о компиляторах, возьмем, к примеру, Ruby, компиляция кода Ruby никогда не может быть эффективной, потому что способ, которым Ruby обрабатывает отражение, такие функции, как автоматическое преобразование типов из целых в большие целые и отсутствие статической типизации, делают создание эффективного компилятора для Ruby крайне сложно.

Можно ли построить компилятор, который может компилировать Ruby или любые другие динамические языки в двоичный файл, который работает очень близко к C / C ++? Есть ли фундаментальная причина, по которой JIT-компиляторы, такие как PyPy / Rubinius, будут в конечном итоге или никогда не будут соответствовать C / C ++ по производительности?

Примечание: я понимаю, что «производительность» может быть неопределенной, поэтому, чтобы это прояснить, я имел в виду, если вы можете сделать X в C / C ++ с производительностью Y, можете ли вы сделать X в Ruby / Python с производительностью, близкой к Y? Где X - это все: от драйверов устройств и кода ОС до веб-приложений.

Ичиро
источник
1
Можете ли вы перефразировать вопрос, чтобы он поощрял ответы, подкрепленные соответствующими доказательствами над другими?
Рафаэль
@ Рафаэль, я пошел дальше и отредактировал. Я думаю, что моя редакция не меняет принципиально смысл вопроса, но делает его менее привлекательным для мнений.
«SO- перестать быть злым» Жиля
1
В частности, я думаю, что вам нужно исправить один (или несколько) конкретных показателей производительности. Продолжительность? Использование пространства? Использование энергии? Время разработчика? Возврат инвестиций? Обратите внимание также на этот вопрос в нашей мета, который касается этого вопроса (или, скорее, его ответов).
Рафаэль
Этот вопрос является типичным инициатором религиозных войн. И как мы видим из ответов, у нас есть один, хотя и очень цивилизованный.
Андрей Бауэр
Существуют динамические языки, допускающие необязательные аннотации типов (например, Clojure). Из того, что я знаю, производительность, связанная с аннотированными функциями, эквивалентна тому, когда язык будет статически типизирован.
Педро Морте Роло

Ответы:

68

Всем тем, кто сказал «да», я предложу контрапункт, что ответ «нет» по замыслу . Эти языки никогда не смогут соответствовать производительности статически скомпилированных языков.

Кос предложил (очень правильное) замечание, что динамические языки имеют больше информации о системе во время выполнения, которую можно использовать для оптимизации кода.

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

Уильям Эдвардс предлагает хороший обзор аргумента .

В частности, оптимизация, упомянутая Косом, не может быть применена за очень ограниченным диапазоном, если вы не ограничите выразительную мощь ваших языков довольно резко, как упомянул Девин. Это, конечно, жизнеспособный компромисс, но ради обсуждения вы получите статический язык, а не динамический. Эти языки принципиально отличаются от Python или Ruby, так как большинство людей их понимают.

Уильям приводит несколько интересных слайдов IBM :

  • Каждая переменная может быть динамически набрана: нужны проверки типов
  • Каждый оператор может потенциально генерировать исключения из-за несоответствия типов и т. Д. Нужны проверки исключений
  • Каждое поле и символ могут быть добавлены, удалены и изменены во время выполнения: нужны проверки доступа
  • Тип каждого объекта и его иерархию классов можно изменить во время выполнения: нужны проверки иерархии классов

Некоторые из этих проверок могут быть исключены после анализа (примечание: этот анализ также требует времени - во время выполнения).

Кроме того, Кос утверждает, что динамические языки могут даже превосходить производительность C ++. JIT действительно может анализировать поведение программы и применять подходящие оптимизации.

Но компиляторы C ++ могут делать то же самое! Современные компиляторы предлагают так называемую оптимизацию на основе профилей, которая, если им дать соответствующий ввод, может моделировать поведение во время выполнения программы и применять те же оптимизации, которые применимы к JIT.

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

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

Конрад Рудольф
источник
2
@Raphael Это «недостаток» компилятора. В частности, была ли javacкогда-нибудь профильная оптимизация? Не настолько, насколько я знаю. В общем случае не имеет смысла делать компилятор языка JITted хорошо оптимизирующим, поскольку JIT может справиться с этим (и, по крайней мере, таким образом, больше языков извлекают выгоду из усилий). Так что (понятно) javac, насколько я знаю, в оптимизатор никогда не вкладывали много усилий (для языков .NET это определенно верно).
Конрад Рудольф
1
@ Рафаэль Ключевое слово: возможно. Это не показывает это в любом случае. Это все, что я хотел сказать. Я привел причины (но не доказательства) для своего предположения в предыдущих пунктах.
Конрад Рудольф
1
@ Я не отрицаю, что это сложно. Это просто интуиция. В конце концов, отслеживание всей этой информации во время выполнения обходится дорого. Я не убежден вашей точки зрения о IO. Если это предсказуемо (= типичный вариант использования), то PGO может предсказать это. Если это не так, я не уверен, что JIT также может оптимизировать его. Может быть, время от времени из чистой удачи. Но достоверно? …
Конрад Рудольф
2
@ Конрад: Ваша интуиция ложна. Дело не в изменении во время выполнения, а в непредсказуемости во время компиляции . Лучшее место для JIT против статической оптимизации не в том случае, когда поведение программы изменяется во время выполнения «слишком быстро» для профилирования, а в том случае, когда поведение программы легко оптимизировать при каждом отдельном запуске программы, но сильно варьируется между пробеги. Статический оптимизатор обычно должен оптимизировать только для одного набора условий, тогда как JIT оптимизирует каждый прогон отдельно, для условий, которые происходят в этом прогоне.
Бен
3
Примечание: эта ветка комментариев превращается в мини-чат. Если вы хотите продолжить это обсуждение, принесите его в чат. Комментарии должны быть использованы для улучшения исходного поста. Пожалуйста, прекратите этот разговор здесь. Благодарю.
Роберт Картейно
20

если вы можете сделать X в C / C ++ с производительностью Y, можете ли вы сделать X в Ruby / Python с производительностью, близкой к Y?

Да. Взять, к примеру, PyPy. Это набор кода Python, который выполняет интерпретацию близко к C (не слишком близко, но и не так далеко). Это достигается путем выполнения полного анализа программы исходного кода для присвоения каждой переменной статического типа (подробности см. В документации Annotator и Rtyper ), а затем, когда она вооружена той же информацией о типе, которую вы предоставляете C, она может выполнить то же самое виды оптимизации. По крайней мере, в теории.

Конечно, компромиссом является то, что RPython принимает только подмножество кода Python, и в целом, даже если это ограничение снято, только подмножество кода Python может преуспеть: подмножество, которое можно проанализировать и получить статические типы.

Если вы достаточно ограничите Python, можно создать оптимизаторы, которые смогут воспользоваться ограниченным подмножеством и скомпилировать его в эффективный код. Это не очень интересная выгода, на самом деле, это хорошо известно. Но весь смысл использования Python (или Ruby) в первую очередь заключался в том, что мы хотели использовать интересные функции, которые, возможно, плохо анализируют и приводят к хорошей производительности! Итак, интересный вопрос на самом деле ...

Кроме того, будут ли JIT-компиляторы, такие как PyPy / Rubinius, когда-либо соответствовать производительности C / C ++?

Неа.

Под этим я подразумеваю: конечно, возможно, по мере накопления кода вы можете получить достаточно информации о наборе и достаточно горячих точек для компиляции всего кода вплоть до машинного кода. И, возможно, мы можем заставить это работать лучше, чем C для некоторого кода. Я не думаю, что это очень спорно. Но он все еще должен «прогреваться», а производительность все еще немного менее предсказуема, и она не будет так же хороша, как C или C ++ для определенных задач, которые требуют стабильно и предсказуемо высокой производительности.

Существующие данные о производительности для Java, которые содержат больше информации о типах, чем Python или Ruby, и более разработанный JIT-компилятор, чем Python или Ruby, до сих пор не соответствуют C / C ++. Это, однако, в том же поле.

Девин Жанпьер
источник
1
«Конечно, компромисс заключается в том, что принимается только подмножество кода Python, или, вернее, только подмножество кода Python может преуспеть: подмножество, которое можно проанализировать и получить статические типы». Это не совсем точно. Только подмножество может быть принято компилятором RPython. Компиляция в RPython для достаточно эффективного C работает только потому, что трудно компилируемые части Python никогда не будут встречаться в программах RPython; дело не только в том, что если они произойдут, они не будут оптимизированы. Это скомпилированный интерпретатор, который обрабатывает весь Python.
Бен
1
О JIT: я видел несколько тестов, где Java превосходила несколько разновидностей C (++). Похоже, что только C ++ с надстройкой надежно держится впереди. В этом случае мне интересно узнать производительность на время разработчика, но это уже другая тема.
Рафаэль
@Ben: если у вас есть RPython, тривиально создать компилятор / интерпретатор, который прибегает к использованию интерпретатора CPython в случае сбоя компилятора RPython, поэтому «только подмножество кода Python может работать хорошо: ...» совершенно точно.
Ли Райан
9
@ Рафаэль Много раз было показано, что хорошо написанный код C ++ превосходит Java. Это «хорошо написанная» часть, которую довольно сложно получить в C ++, поэтому во многих тестах вы видите результаты, которые Java превосходит в C ++. C ++, следовательно, дороже, но когда требуется жесткий контроль памяти и металлический песок, C / C ++ - это то, к чему вы обращаетесь. C, в частности, просто AC / P ассемблер.
TC1
7
Сравнение максимальной производительности других языков с такими языками, как C / C ++, является своего рода бесполезным упражнением, поскольку вы можете встроить сборку непосредственно как часть языковой спецификации. Все, что машина может выполнить, запустив программу, написанную на любом языке, в худшем случае можно скопировать, написав сборку из трассы выполненных инструкций. Гораздо более интересным показателем, как предполагает @Raphael в предыдущем комментарии, является производительность на усилия по разработке (человеко-часы, строки кода и т. Д.).
Patrick87
18

Короткий ответ: мы не знаем , спросите еще раз через 100 лет. (Возможно, мы еще не знаем тогда; возможно, мы никогда не узнаем.)

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

Опять же, теоретически языки высокого уровня могут достичь производительности машинного кода, но они не превзойдут ее. Это все еще очень теоретически, потому что в практическом плане мы очень редко прибегаем к написанию машинного кода. Этот аргумент не применим к сравнению языков более высокого уровня: это не означает, что C должен быть более эффективным, чем Python, только тот машинный код не может работать хуже, чем Python.

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

Тем не менее, есть неоспоримые случаи, когда языки высокого уровня превосходят код, который можно было бы реально написать: среды программирования специального назначения. Такие программы, как Matlab и Mathematica, часто гораздо лучше решают определенные виды математических задач, чем то, что могут написать простые смертные. Библиотечные функции могли быть написаны на C или C ++ (что является топливом для лагеря «низкоуровневые языки более эффективны»), но это не мое дело, если я пишу код Mathematica, библиотека - это черный ящик.

Теоретически возможно, что Python приблизится к оптимальной производительности или даже приблизится к ней по сравнению с C? Как видно выше, да, но мы очень далеки от этого сегодня. Опять же, компиляторы добились большого прогресса за последние десятилетия, и этот прогресс не замедляется.

Языки высокого уровня, как правило, делают больше вещей автоматическими, поэтому им приходится выполнять больше работы и, следовательно, они менее эффективны. С другой стороны, они, как правило, содержат больше семантической информации, поэтому может быть легче обнаружить оптимизации (если вы пишете компилятор на Haskell, вам не нужно беспокоиться о том, что другой поток изменит переменную под вашим носом). Одним из нескольких попыток сравнить яблоки и апельсины на разных языках программирования является тестовая версия Computer Language Benchmark Game (ранее известная как перестрелка). Фортран имеет тенденцию сиять на численных задачах; но когда дело доходит до манипулирования структурированными данными или высокоскоростной коммутации потоков, F # и Scala преуспевают. Не воспринимайте эти результаты как Евангелие: многое из того, что они измеряют, заключается в том, насколько хорош был автор тестовой программы на каждом языке.

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

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

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

Последнее замечание: часто сравнение проводится не между самой эффективной программой, которая может быть написана на языке A и той же на языке B, ни между самой эффективной программой, когда-либо написанной на каждом языке, а между самой эффективной программой, которая может быть написана. человеком в определенное количество времени на каждом языке. Это вводит элемент, который не может быть проанализирован математически, даже в принципе. С практической точки зрения это часто означает, что лучшая производительность - это компромисс между тем, сколько низкоуровневого кода вам нужно написать для достижения целей производительности, и сколько низкоуровневого кода у вас есть время, чтобы написать даты выпуска.

Жиль "ТАК - перестань быть злым"
источник
Я думаю, что различие между высоким уровнем и низким уровнем является неправильным. C ++ может быть (очень) высокого уровня. Тем не менее, современный высокоуровневый C ++ не (обязательно) работает хуже, чем низкоуровневый эквивалент - совсем наоборот. C ++ и его библиотеки были тщательно разработаны, чтобы предлагать абстракции высокого уровня без потери производительности. То же самое относится и к вашему примеру на Haskell: его высокоуровневые абстракции часто включают, а не предотвращают оптимизацию. Оригинальное различие между динамическими языками и статическими языками имеет больше смысла в этом отношении.
Конрад Рудольф
@KonradRudolph Вы правы, в этом низком уровне / высоком уровне это несколько произвольное различие. Но динамические и статические языки тоже не все фиксируют; JIT может устранить большую часть разницы. По сути, известные теоретические ответы на этот вопрос тривиальны и бесполезны, а практический ответ - «это зависит».
Жиль "ТАК - перестань быть злым"
Ну, тогда я думаю, что вопрос становится просто «насколько хорошими могут стать JIT, и если они обгоняют статическую компиляцию, могут ли статически скомпилированные языки также извлечь из них выгоду?» По крайней мере, я так понимаю вопрос, когда мы примем во внимание JIT. И да, я согласен с вашей оценкой, но, безусловно, мы можем получить некоторые обоснованные предположения, которые выходят за рамки «это зависит». ;-)
Конрад Рудольф
@KonradRudolph Если бы я хотел догадаться, я бы спросил о программной инженерии .
Жиль "ТАК - перестань быть злым"
1
Языковая перестрелка, к сожалению, является сомнительным источником для количественных тестов: они не принимают все программы только те, которые считаются типичными для языка. Это сложное и очень субъективное требование; это означает, что вы не можете предполагать, что реализация перестрелки действительно хороша (и на практике у некоторых реализаций явно отклонены превосходящие альтернативы). С другой стороны; это микробенчмарки, и в некоторых реализациях используются необычные приемы, которые вы никогда бы не рассмотрели в более нормальном сценарии, просто чтобы повысить производительность. Итак: это игра, а не очень надежный источник данных.
Имон Нербонн
10

Основное различие между высказыванием C ++ x = a + bи утверждением Python x = a + bявляется то , что компилятор C / C ++ можно сказать , из этого утверждения (и немного дополнительной информации , которую он имеет легкодоступный о типах x, aи b) именно то , что машинный код должно быть выполнено , Принимая во внимание, что, чтобы сказать, какие операции будет выполнять оператор Python, вам нужно решить проблему остановки.

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

В Python компилятор теоретически мог бы принести почти такую ​​же пользу, если бы знал это aи bоба были ints. Есть некоторые дополнительные накладные расходы на бокс, но если бы типы были статически известны, вы, вероятно, тоже могли бы избавиться от них (все еще представляя интерфейс, в котором целые числа являются объектами с методами, иерархией суперклассов и т. Д.). Беда в том, что компилятор для Python не можетЗнайте это, поскольку классы определяются во время выполнения, могут быть изменены во время выполнения, и даже модули, которые определяют и импортируют, разрешаются во время выполнения (и даже то, какие операторы импорта выполняются, зависит от вещей, которые могут быть известны только во время выполнения). Таким образом, компилятор Python должен был бы знать, какой код был выполнен (то есть решить проблему остановки), чтобы знать, что будет делать оператор, который он компилирует.

Таким образом, даже при наличии самого сложного анализа, который теоретически возможен , вы просто не можете много рассказать о том, что данный оператор Python собирается сделать заранее. Это означает, что даже если бы был реализован сложный компилятор Python, ему почти во всех случаях все равно приходилось бы выдавать машинный код, который следует протоколу поиска в словаре Python, чтобы определить класс объекта и найти методы (проходя через MRO иерархии классов, который также может динамически изменяться во время выполнения, и поэтому его трудно скомпилировать в простую таблицу виртуальных методов), и в основном делать то, что делают (медленные) интерпретаторы. Вот почему на самом деле нет сложных оптимизирующих компиляторов для динамических языков. Это не просто сложно создать максимально возможную выгоду

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

JIT-компиляторы выигрывают от этого, ожидая времени компиляции / оптимизации. Это позволяет им создавать код , который работает на то , что код будет делать , а не то , что он может делать. И из-за этого JIT-компиляторы имеют гораздо большую потенциальную отдачу для динамических языков, чем для статических языков; для более статичных языков многое из того, что хотел бы знать оптимизатор, может быть известно заранее, поэтому вы можете также оптимизировать его тогда, оставляя JIT-компилятору меньше.

Существуют различные JIT-компиляторы для динамических языков, которые утверждают, что достигают скоростей выполнения, сравнимых с компилируемыми и оптимизированными C / C ++. Есть даже оптимизации, которые могут быть осуществлены JIT-компилятором, которые не могут быть выполнены заранее установленным компилятором для любого языка, поэтому теоретически JIT-компиляция (для некоторых программ) однажды может превзойти наилучший статический компилятор. Но, как правильно заметил Девин, свойства JIT-компиляции (только «горячие точки» быстрые и только после периода прогрева) означают, что JIT-скомпилированные динамические языки вряд ли когда-либо пригодятся для всех возможных приложений, даже если они становятся так же быстро или быстрее, чем статически скомпилированные языки в целом.

Бен
источник
1
Это теперь два отрицательных голоса без комментариев. Буду рад предложениям по улучшению этого ответа!
Бен
Я не понизил голос, но вы ошибаетесь по поводу «необходимости решить проблему остановки». Во многих случаях было продемонстрировано, что код на динамических языках может быть скомпилирован для оптимального целевого кода, тогда как, насколько мне известно, ни одна из этих демонстраций не включала в себя решение проблемы остановки :-)
mikera
@mikera Извините, но нет, вы не правы. Никто никогда не реализовывал компилятор (в том смысле, что мы понимаем, что GCC является компилятором) для полностью общего языка Python или других динамических языков. Каждая такая система работает только для подмножества языка, или только для определенных программ, или иногда испускает код, который в основном представляет собой интерпретатор, содержащий жестко запрограммированную программу. Если хотите, я напишу вам программу на Python, содержащую строку, в foo = x + yкоторой предсказание поведения оператора сложения во время компиляции зависит от решения проблемы остановки.
Бен
Я прав, и я думаю, что вы упускаете суть. Я сказал "при многих обстоятельствах". Я не сказал "при всех возможных обстоятельствах". Можете ли вы создать надуманный пример, связанный с проблемой остановки, в реальности не имеет значения. FWIW, вы могли бы также создать аналогичный пример для C ++, чтобы вы ничего не доказали в любом случае. Во всяком случае, я пришел сюда не для того, чтобы поспорить, просто чтобы предложить улучшения в вашем ответе. Возьми это или оставь.
Микера
@mikea Думаю, ты упускаешь суть. Чтобы выполнить x + yэффективные операции добавления машин, вам нужно знать во время компиляции, так ли это или нет. Все время , а не только часть времени. Для динамических языков это почти никогда не возможно с реалистичными программами, хотя разумная эвристика будет угадывать большую часть времени. Компиляция требует гарантий времени компиляции . Так что, говоря о «во многих обстоятельствах», вы вообще не обращаетесь к моему ответу.
Бен
9

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

Разбор Perl не вычисляется

Как следствие, (полный) Perl никогда не может быть скомпилирован статически.


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

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

Рафаэль
источник
5

В попытке предложить более объективный научный ответ на этот вопрос я утверждаю следующее. Динамический язык требует интерпретатора или среды выполнения, чтобы принимать решения во время выполнения. Этот интерпретатор, или среда выполнения, является компьютерной программой и, как таковой, был написан на каком-то языке программирования, статическом или динамическом.

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

Если предположить, что эти утверждения верны, единственный выход - это потребовать, чтобы интерпретатор / среда выполнения также были написаны на динамическом языке. Однако мы сталкиваемся с той же проблемой, что и раньше: если интерпретатор динамический, он требует интерпретатора / среды выполнения, которые также должны быть написаны на языке программирования, динамическом или статическом.

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

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

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

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

Patrick87
источник
Перечитывая это, я не думаю, что это правда. JIT компиляция ломает ваш аргумент. Даже самый простой код, например, main(args) { for ( i=0; i<1000000; i++ ) { if ( args[0] == "1" ) {...} else {...} }может значительно ускориться, когда значение argsстанет известно (при условии, что оно никогда не изменится, что мы можем утверждать). Статический компилятор не может создать код, который отбрасывает сравнение. (Конечно, в этом примере вы просто вытаскиваете ifиз цикла. Но эта вещь может быть более запутанной.)
Рафаэль
@ Рафаэль Я думаю, что JIT, вероятно, делает мой аргумент. Программы, выполняющие JIT-компиляцию (например, JVM), обычно являются статически скомпилированными программами. Если статически скомпилированная JIT-программа может запустить скрипт быстрее, чем какая-либо другая статическая программа могла бы выполнить ту же работу, просто «связать» скрипт с JIT-компилятором и вызвать этот пакет статически скомпилированной программой. Это должно быть как минимум так же, как JIT, работающий в отдельной динамической программе, что противоречит любому аргументу, что JIT должен работать лучше.
Patrick87
Хм, это все равно что сказать, что связывание скрипта Ruby с его интерпретатором дает вам статически скомпилированную программу. Я не согласен (так как это устраняет все различия языков в этом отношении), но это проблема семантики, а не понятий. Концептуально, адаптация программы во время выполнения (JIT) может сделать оптимизацию, которую вы не можете сделать во время компиляции (статический компилятор), и это моя точка зрения.
Рафаэль
@Raphael То, что нет никакого значимого различия, является своего рода точкой ответа: любая попытка жестко классифицировать некоторые языки как статические, и, следовательно, страдающие от ограничений производительности, терпит неудачу именно по этой причине: нет существенной разницы между расфасованным (Ruby , скрипт) связка и Си-программа. Если (Ruby, script) может заставить машину выполнить правильную последовательность инструкций для эффективного решения данной проблемы, то же самое можно сделать и с искусно созданной C-программой.
Patrick87
Но вы можете определить разницу. Один вариант отправляет код под рукой процессору без изменений (C), другой компилируется во время выполнения (Ruby, Java, ...). Первый - это то, что мы подразумеваем под «статической компиляцией», тогда как последний будет «компиляцией как раз вовремя» (которая позволяет оптимизировать данные).
Рафаэль
4

Можете ли вы создать компиляторы для динамических языков, таких как Ruby, которые будут иметь аналогичную и сопоставимую производительность с C / C ++?

Я думаю, что ответ «да» . Я также считаю, что они могут даже превзойти текущую архитектуру C / C ++ с точки зрения эффективности (даже если немного).

Причина проста: во время выполнения больше информации, чем во время компиляции.

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

См. « Ответ на динамические языки» , выступление Стива Йегге из Google (где-то, я верю, есть видео-версия). Он упоминает некоторые конкретные методы оптимизации JIT из V8. Воодушевление!

Я с нетерпением жду того, что у нас будет в ближайшие 5 лет!

Кос
источник
2
Я люблю оптимизм.
Дейв Кларк,
Я полагаю, что в выступлении Стива была очень специфическая критика неточностей. Я опубликую их, когда найду.
Конрад Рудольф
1
@DaveClarke это то, что заставляет меня работать :)
Кос
2

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

  • Символы (vars, или, скорее, id <-> привязки всех типов) не типизированы.
  • Структуры (данные, все, что живет во время выполнения) также не определяются типами их элементов.

Второй пункт предоставляет универсальность бесплатно. Обратите внимание, что структуры здесь являются составными элементами, коллекциями, но также самими типами и даже (!) Подпрограммами всех видов (функций, действий, операций) ... Мы можем печатать структуры по типам элементов, но из-за первого пункта проверка все равно произойдет во время выполнения. Мы могли бы набирать символы и при этом иметь структурированные символы, не типизированные в соответствии с их типами элементов (массив был aбы просто напечатан как массив, а не как массив целых чисел), но даже это несколько неверно в динамическом языке ( aможет также содержать строка).

L

  • ElementLL
  • ElementL
  • все структуры (опять же, включая подпрограммы модели) получают только элемент

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

Спир
источник
+1 Очень интересно. Вы читали мой ответ? Вы и мои мысли кажетесь схожими, хотя ваш ответ дает больше деталей и интересную перспективу.
Patrick87
Динамические языки не должны быть нетипизированы. Реализация модели динамического языка в C серьезно ограничивает возможности оптимизации; это очень затрудняет компилятору распознавание высокоуровневых оптимизаций (например, неизменяемых данных) и заставляет некоторые фундаментальные операции (например, вызовы функций) проходить через C. То, что вы описываете, находится недалеко от интерпретатора байт-кода с декодированием байт-кода preevaluated; нативные компиляторы, как правило, работают значительно лучше, я сомневаюсь, что декодирование байт-кода может оправдать разницу.
Жиль "ТАК - перестань быть злым"
@ Patrick87: вы правы, наши взгляды кажутся очень схожими (раньше я их не читал, извините, мое мнение исходит от реализации dyn lang в C).
Спирт
@ Жиль: Я скорее согласен с "... не должен быть нетипизирован", если вы имеете в виду не статически типизированный. Но это не то, что люди думают о Dyn Langs в целом, я думаю. Лично я считаю, что универсальность (в общем смысле, приведенном в ответе выше) является функцией, гораздо более мощной и без которой трудно жить. Мы можем легко найти способы работы со статическими типами, расширив наши представления о том, как можно определить данный (казалось бы, полиморфный) тип, или предоставив больше гибкости непосредственно экземплярам.
Спирт
1

У меня не было времени, чтобы прочитать все ответы подробно ... но я был удивлен.

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

Была даже концепция расширения кода: отношение размера кода, созданного компилятором, к размеру кода для той же программы, созданной хорошим программистом (как будто их было слишком много :-). Конечно, идея заключалась в том, что это соотношение всегда было больше 1. Языки того времени были Cobol и Fortran 4 или Algol 60 для интеллектуалов. Я считаю, что Лисп не был рассмотрен.

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

Странные особенности, динамические особенности языка не имеют значения. Важно то, как они используются, используются ли они. Производительность, независимо от единицы измерения (размер кода, скорость, энергия и т. Д.), Часто зависит от очень маленьких частей программ. Следовательно, есть большая вероятность, что средства, которые дают выразительную силу, не будут мешать. С хорошей практикой программирования, расширенные возможности используются только дисциплинированным образом, чтобы представить новые структуры (это был урок LISP).

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

В ходе обсуждения было несколько ссылок на анализ наихудшего случая («проблема остановки», разбор PERL). Но анализ наихудшего случая в основном не имеет значения. Важно то, что происходит в большинстве случаев или в полезных случаях ... как бы они ни были определены, поняты или испытаны. Вот еще одна история, напрямую связанная с оптимизацией программы. Это произошло давным-давно в крупном университете в Техасе, между аспирантом и его советником (который впоследствии был избран в одну из национальных академий). Насколько я помню, студент настаивал на изучении проблемы анализа / оптимизации, которую, как показал консультант, не поддается решению. Вскоре они перестали разговаривать. Но студент был прав: проблема была достаточно решаемой в большинстве практических случаев, так что созданная им диссертация стала справочной.

И прокомментируем далее утверждение, что Perl parsing is not computable, что бы ни подразумевалось под этим предложением, существует аналогичная проблема с ML, который является удивительно хорошо формализованным языком. Type checking complexity in ML is a double exponential in the lenght of the program.Это очень точный и формальный результат в худшем случае сложности ... который не имеет значения вообще. Afaik, пользователи ML все еще ждут практическую программу, которая взорвет проверку типов.

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

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

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

Но в случае программирования нам, возможно, придется переписать все доказательства с нуля (программы - это доказательства). Может случиться так, что нам действительно нужны языки высокого уровня и развивающиеся языки программирования. Разработчики оптимизатора будут рады следовать.

Babou
источник
0

Пара заметок:

  • Не все языки высокого уровня являются динамическими. Хаскель очень высокого уровня, но полностью статически типизирован. Даже языки системного программирования, такие как Rust, Nim и D, могут выражать абстракции высокого уровня кратко и эффективно. На самом деле они могут быть такими же краткими, как и динамические языки.

  • Существуют высокооптимальные опережающие компиляторы для динамических языков. Хорошие реализации на Лиспе достигают половины скорости эквивалентного C.

  • Компиляция JIT может быть большой победой здесь. Брандмауэр веб-приложений CloudFlare генерирует код Lua, который выполняется LuaJIT. LuaJIT сильно оптимизирует фактически используемые пути выполнения (как правило, пути без атак), в результате чего код выполняется намного быстрее, чем код, созданный статическим компилятором при фактической рабочей нагрузке. В отличие от статического компилятора с оптимизацией по профилю, LuaJIT адаптируется к изменениям путей выполнения во время выполнения.

  • Деоптимизация также имеет решающее значение. Вместо того, чтобы JIT-скомпилированный код должен был проверять наличие класса monkeypatched, сам процесс monkeypatching вызывает хук в системе времени выполнения, который отбрасывает машинный код, который зависел от старого определения.

Деми
источник
Как это ответ? Ну, пулей три, может быть, если вы добавили ссылки.
Рафаэль
Я очень скептически отношусь к утверждению, что PGO не может сравниться с производительностью LuaJIT для кода веб-приложения при обычной рабочей нагрузке.
Конрад Рудольф
@KonradRudolph Основным преимуществом JIT является то, что JIT адаптирует код по мере того, как разные пути становятся горячими.
Деми
@Demetri Я знаю это. Но очень трудно определить, является ли это преимуществом - посмотрите мой ответ и обсуждение комментариев там. В двух словах: хотя JIT может адаптироваться к изменениям в использовании, он также должен отслеживать вещи во время выполнения, что приводит к накладным расходам. Безубыточность для этого интуитивно понятна только там, где происходят частые изменения в поведении. Для веб-приложений, вероятно, существует только один (или очень маленький) шаблон использования, для которого оптимизация окупается, поэтому минимальное увеличение производительности из-за адаптивности не компенсирует издержки непрерывного профилирования.
Конрад Рудольф