Преимущества компиляторов функциональных языков перед компиляторами императивных языков

Я бы сказал в основном «нет».

Основные преимущества «оптимизации», которые вы получаете от неизменяемости или ссылочной прозрачности, - это такие вещи, как возможность выполнять «исключение общих подвыражений», когда вы видите код типа ...f(x)...f(x).... Но такой анализ трудно обойтись без очень точной информации, и поскольку F # работает в среде выполнения .Net, а .Net не имеет возможности пометить методы как чистые (без эффектов), для этого требуется тонна встроенной информации и анализа. даже попробуйте сделать что-нибудь из этого.

С другой стороны, в таком ленивом и чистом языке, как Haskell (что в основном означает Haskell, так как есть несколько языков, подобных Haskell, которые кто-либо слышал или использует :)), анализ проще (все чистая, офигела).

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

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

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

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

Правильно ли я предполагаю, что компилятор F # может выполнять определенные оптимизации, зная, что он имеет дело с в основном неизменяемым кодом?

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

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

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

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

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

• Эффективно используйте память. По возможности работайте с «распакованными» значениями, избегая выделения и дополнительного уровня косвенного обращения к куче. В частности, слияние потоков и другие методы обезлесения очень эффективны, потому что они устраняют выделение ресурсов.

• Имейте сверхбыстрый распределитель и амортизируйте проверки нехватки кучи для нескольких распределений.

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

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

• Не упускайте из виду классические скалярные и циклические оптимизации. Они имели огромное значение для таких компиляторов, как TIL и Objective Caml.

Если у вас ленивый функциональный язык, такой как Haskell или Clean, с преобразователями есть еще много специализированных вещей.

Сноски:

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

• Написать хороший компилятор для F # сложнее, чем написать типичный компилятор (если он есть), потому что F # сильно ограничен: он должен хорошо выполнять функциональные задачи, но он также должен эффективно работать в рамках .NET framework, который был не разработан с учетом функциональных языков. Мы в долгу перед Доном Саймом и его командой за такую ​​отличную работу над проблемой с большими ограничениями.

No.

Компилятор F # не пытается анализировать ссылочную прозрачность метода или лямбда. .NET BCL просто не предназначен для этого.

В спецификации языка F # зарезервировано ключевое слово «чистый», поэтому ручная пометка метода как «чистый» может быть возможна в vNext, что позволяет более агрессивно сокращать графы лямбда-выражений.

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

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

Например, рассмотрим на языке C:

int factorial(int n) {
    if (n <= 0) return 1;
    return n* factorial(n-1);
}

int factorialuser(int m) {
    return factorial(m) * factorial(m);
}

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

Обратите внимание, что в настоящее время F # на самом деле не является «чистым» функциональным языком. Итак, я ввел Haskell (и это здорово!).

К сожалению, поскольку F # в основном чист, возможностей для агрессивной оптимизации не так уж и много. Фактически, есть некоторые места, где F # «пессимизирует» код по сравнению с C # (например, создает защитные копии структур для предотвращения наблюдаемых мутаций). С другой стороны, компилятор в целом выполняет хорошую работу, несмотря на это, обеспечивая производительность, сопоставимую с C #, в большинстве случаев, тем не менее, одновременно делая программы более понятными.

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

x := x + 1
y := x + 4

может стать

x_1 := x_0 + 1
y := x_1 + 4

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

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