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

Question

Как продолжение этого вопроса Каковы преимущества встроенной неизменности F # по сравнению с C #? - правильно ли я считаю, что компилятор F # может выполнять определенные оптимизации, зная, что он имеет дело с в значительной степени неизменный код? Я имею в виду, что даже если разработчик напишет «Functional C #», компилятор не будет знать всю неизменность, которую разработчик пытался закодировать, чтобы он не мог выполнить те же оптимизации, верно?

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

---

Сноски:

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

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

Answer 2

номер

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

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

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

Answer 3

Да, если вы не рассматриваете 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 # на самом деле не является "чистым" функциональным языком. Итак, я привел Хаскелла (что здорово!).

Answer 4

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

Answer 5

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

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

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

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

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

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

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

Answer 6

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

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

может стать

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

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

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