Функция Накладные расходы в функциональных языках, таких как Haskell или в таких гибридах, как Scala

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

Итак, с недавним шумом о концепции и языках FP мне действительно интересно, как Haskell решает эту проблему? Это просто, что компиляторы очень много делают? В дополнение к этому, как FP-Языки (Clojure/Scala) на JVM решить эту проблему? Даже отсутствие хорошей оптимизации Tail-Call довольно подробно говорит о возможностях JVM в плане оптимизации кода FP.

Спасибо!

Ответ 1

Я не могу предоставить исчерпывающий ответ для Haskell, но для Scala ответ довольно прост: он выполняет преобразования в байт-коде, так что, например, (простой) хвостовой вызов реализуется как цикл с переменными вместо. По сути, это то, что нужно сделать для достижения хорошей производительности, поскольку компьютеры изменяемы (RAM, а не WORM!).

Превращение метода во что-то, что может быть передано, включает в себя создание объекта, но создание объекта на JVM дешево, и как JVM, так и Scala имеют или будут иметь трюки, чтобы вообще не создавать этот объект, если это действительно необходимо.

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

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

Ответ 2

любые преимущества JBM, основанные на JVM, из компиляции JIT, так что уже дает огромное преимущество языкам типа Scala и Clojure.

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