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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

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

• Эффективно использовать память. Когда можно, работайте со значениями "unboxed", избегая выделения и дополнительного уровня косвенности в кучу. Слияние потоков в частности и другие методы обезлесения - все это очень эффективно, поскольку они устраняют распределения.

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

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

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

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

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

Сноски:

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

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

Ответ 3

Нет.

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

Спецификация языка F # сохраняет ключевое слово "чистый", поэтому вручную можно указать, что метод pure может быть доступен в vNext, что позволяет более агрессивно уменьшать графы лямбда-выражений.

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

Ответ 4

Да, если вы не считаете 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, не было бы второго вызова факториала при вызове factorialuser. Возможно, это возможно сделать в С#, но я сомневаюсь, что текущие компиляторы делают это, даже для простого примера. По мере усложнения ситуации компиляторам С# было бы сложно оптимизировать уровень, который может выполнить Haskell.

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

Ответ 5

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

Ответ 6

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

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

может стать

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

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

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