Являются ли функциональные языки медленными?

Ответ 1

Являются ли функциональные языки медленными?

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

Почему функциональные языки всегда отстают от C в тестах?

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

Наиболее очевидным примером этого является parallelism. Сегодня у всех нас многожильные. Даже мой телефон многоядерный. Multicore parallelism, как известно, сложно в C, но может быть легким в функциональных языках (мне нравится F #). Другие примеры включают в себя все, что выгодно для постоянных структур данных, например. отмена буферов тривиальна с чисто функциональными структурами данных, но может быть огромной работой на императивных языках, таких как C.

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

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

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

Причины, по которым функциональные языки распределяются так сильно, могут быть разделены на исторические и неотъемлемые причины.

Исторически, реализация Lisp уже много лет занимается большим боксом. Эта характеристика распространяется на многие другие языки, которые используют Lisp -подобные промежуточные представления. На протяжении многих лет разработчики языка постоянно прибегали к боксу в качестве быстрого решения проблем, связанных с внедрением языка. В объектно-ориентированных языках по умолчанию всегда была куча, выделяющая каждый объект, даже если он может быть выделен стекми. Бремя эффективности было затем вытолкнуто на сборщик мусора, и огромные усилия были направлены на создание сборщиков мусора, которые могут достичь производительности, близкой к производительности распределения штабелей, как правило, используя генерацию питомника, распределяющую рельеф. Я думаю, что нужно приложить гораздо больше усилий для исследования функциональных языков, которые сводят к минимуму конструкции бокса и сборщика мусора, которые оптимизированы для различных требований.

Сборщики сборщиков мусора отлично подходят для языков, которые куча выделяет много, потому что они могут быть почти такими же быстрыми, как распределение стека. Но они добавляют существенные накладные расходы в другом месте. Сегодня программы все чаще используют структуры данных, такие как очереди (например, для параллельного программирования), и это дает патологическое поведение для коллекционеров мусора поколения. Если элементы в очереди переживают первое поколение, тогда все они становятся отмеченными, затем все они копируются ( "эвакуированы" ), затем все ссылки на их старые местоположения обновляются, а затем становятся доступными для сбора. Это примерно на 3 × медленнее, чем это необходимо (например, по сравнению с C). Коллекторы Mark region, такие как Beltway (2002) и Immix (2008), могут решить эта проблема, потому что питомник заменяется на регион, который может быть собран, как если бы он был детским садом или, если он содержит в основном достижимые значения, его можно заменить другим регионом и оставить до возраста, пока он не содержит в основном недостижимые значения.

Несмотря на предсуществование С++, создатели Java допустили ошибку при принятии стирания стилей для дженериков, что привело к ненужному боксу. Например, я сравнивал простую хеш-таблицу, которая на 17 раз быстрее выполнялась на .NET, чем JVM, частично из-за того, что .NET не допустил эту ошибку (использует редифицированные генерики), а также потому что .NET имеет типы значений. Я действительно обвиняю Lisp за медленную работу Java.

Все современные функциональные языковые реализации продолжают чрезмерно загружаться. Языки на основе JVM, такие как Clojure и Scala, имеют мало выбора, потому что виртуальная машина, на которую они нацелены, даже не может выражать типы значений. OCaml набрасывает информацию о типе в начале процесса компиляции и прибегает к помеченным целым числам и боксу во время выполнения для обработки полиморфизма. Следовательно, OCaml часто вводит отдельные числа с плавающей запятой и всегда привязывает кортежи. Например, тройка байтов в OCaml представляется указателем (с неявным 1-битным тегом, встроенным в него, который периодически проверяется во время выполнения) в блок, выделенный с помощью кучи, с 64-битным заголовком и 192-битным телом, содержащим три тегированных 63-битных целых числа (где теги 3 снова снова проверяются во время выполнения!). Это явно безумие.

Проделана определенная работа по оптимизации распаковки на функциональных языках, но она никогда не набирала оборотов. Например, MLton-компилятор для стандартного ML был компилятором, оптимизирующим всю программу, который выполнял сложные оптимизации для распаковки. К сожалению, это было до его времени, а "длинные" времена компиляции (вероятно, до 1 года на современной машине!) Не позволяли людям использовать его.

Единственной крупной платформой, которая нарушила эту тенденцию, является .NET, но, что удивительно, она, похоже, была случайностью. Несмотря на то, что реализация Dictionary очень сильно оптимизирована для ключей и значений, которые имеют типы значений (поскольку они распакованы) Сотрудники Microsoft, такие как Eric Lippert, продолжают утверждать, что важная вещь о типах значений это их семантика pass-by-value, а не характеристики производительности, связанные с их внутренним представлением. Эрик, похоже, оказался ошибочным: разработчики .NET, похоже, больше заботятся о распаковке, чем о пропущенных значениях. В самом деле, большинство структур неизменны и, следовательно, ссылочно прозрачны, поэтому семантическая разница между передачей по значению и передачей по ссылке отсутствует. Производительность видна, и структуры могут предлагать значительные улучшения производительности. Производительность структур, даже сохраненных Qaru и structs, используются, чтобы избежать латентности GC в коммерческом программном обеспечении, таком как Быстрое добавление!

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

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

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

Взгляните на Erlang и OCaml, если вы еще этого не сделали. Оба они являются разумными для систем с ограниченной памятью, но не генерируют особенно большой машинный код.

Ответ 2

Ничто по сути ничего. Вот пример, где интерпретируемый OCaml работает быстрее, чем эквивалентный код C, поскольку оптимизатор OCaml имеет различную доступную ему информацию из-за различий в языке. Конечно, было бы глупо утверждать, что OCaml категорически быстрее C. Дело в том, что это зависит от того, что вы делаете, и как вы это делаете.

Тем не менее, OCaml является примером функционального языка (в основном), который фактически предназначен для производительность, в отличие от чистоты.

Ответ 3

Функциональные языки требуют устранения изменчивого состояния, которое видно на уровне абстракции языка. Следовательно, данные, которые будут мутированы на месте императивным языком, должны быть скопированы вместо этого, с мутацией, происходящей на копии. Для простого примера см. Быстрый вид в Haskell vs. C.

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

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

Ответ 4

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

Причина, по которой C работает быстро, заключается в том, что она была создана действительно отличными кодерами, а gcc была оптимизирована в течение пары более десятилетия и десятками более ярких кодировщиков, чем 99% языков.

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

Ответ 5

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

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

Ответ 6

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

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

Тривиально не в том смысле, что это легко, но что он может быть встроен в языковую среду, если разработчику не нужно думать об этом.

Стоимость надежной многопоточности в агрегированном потоке, как C, является запретительной для многих проектов.

Ответ 7

Поток управления сущностными языками намного лучше соответствует фактическим шаблонам обработки современных компьютеров.

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

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

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

Ответ 8

Well Haskell в 1,8 раза медленнее, чем GCC С++, что быстрее, чем реализация GCC C для типичных эталонных задач. Это делает Haskell очень быстрым, даже быстрее, чем С# (Mono).

относительный язык Скорость

• 1.0 С++ GNU g++
• 1.1 C GNU gcc
• 1.2 ATS
• 1.5 Java 6-сервер
• 1.5 Очистить
• 1.6 Паскаль Бесплатно Паскаль
• 1.6 Fortran Intel
• 1.8 Haskell GHC
• 2.0 С# Mono
• 2.1 Scala
• 2.2 Ada 2005 GNAT
• 2.4 Lisp SBCL
• 3.9 Lua LuaJIT

источник

Для записи я использую Lua для игр на iPhone, поэтому вы можете легко использовать Haskell или Lisp, если хотите, так как они быстрее.

Ответ 9

Я не согласен с tuinstoel. Важный вопрос заключается в том, обеспечивает ли функциональный язык более быстрое время разработки и приводит к более быстрому коду, когда он используется для использования функциональных языков. См. Раздел раздел "Вопросы эффективности" в Википедии, чтобы увидеть, что я имею в виду.

Ответ 10

Еще одна причина для большего размера исполняемого файла - это ленивая оценка и не строгость. Компилятор не может понять во время компиляции, когда определенные выражения оцениваются, поэтому некоторые исполняемые файлы заполняются в исполняемый файл, чтобы справиться с этим (чтобы вызвать оценку так называемых thunks). Что касается производительности, лень может быть как хорошим, так и плохим. С одной стороны, это обеспечивает дополнительную потенциальную оптимизацию, с другой стороны, размер кода может быть больше, а программисты с большей вероятностью принимают плохие решения, например. см. Haskell foldl vs. foldr vs. foldl 'vs. foldr'.

Ответ 11

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