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

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

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

Если я напишу ту же программу на Scala (которая использует JVM), будет ли эта реализация быстрее? Если да, то почему? Это из-за стиля письма? Если это из-за стиля письма, теперь, когда Java включает в себя лямбда - выражения, не мог я достичь тех же результатов с помощью Java с лямбда? Или это быстрее, потому что Scala будет компилировать вещи по-другому?

Причина, по которой люди говорят, что функциональные языки лучше подходят для параллельной обработки, заключается в том, что они обычно избегают изменяемого состояния. Изменчивое состояние является «корнем всего зла» в контексте параллельной обработки; они действительно облегчают столкновение с условиями гонки, когда они совместно используются параллельными процессами. Решение условий гонки затем включает механизмы блокировки и синхронизации, как вы упомянули, которые приводят к накладным расходам во время выполнения, так как процессы ждут друг друга для использования общего ресурса, и большую сложность проектирования, поскольку все эти концепции имеют тенденцию быть глубоко вложен в такие приложения.

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

Тем не менее, это все случайно. Если ваше решение в Java также позволяет избежать изменчивого состояния (в частности, общего для потоков), преобразование его в функциональный язык, такой как Scala или Clojure, не даст никаких преимуществ с точки зрения одновременной эффективности, поскольку в исходном решении уже нет лишних затрат, вызванных механизмы блокировки и синхронизации.

TL; DR: если решение в Scala более эффективно при параллельной обработке, чем решение в Java, это происходит не из-за того, как код компилируется или выполняется через JVM, а из-за того, что решение Java разделяет изменяемое состояние между потоками, или вызывая условия гонки или добавляя издержки синхронизации, чтобы избежать их.

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

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

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

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

Один прекрасный пример пункта №2 состоит в том, что в Хаскеле мы имеем четкое различие между детерминированным параллелизмом и недетерминированным параллелизмом . Нет лучшего объяснения, чем цитирование превосходной книги Саймона Марлоу « Параллельное и параллельное программирование на Хаскеле» (цитаты из главы 1 ):

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

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

В дополнение к этому Марлоу упоминает также поднимает измерение детерминизма :

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

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

В Haskell функции параллелизма и параллелизма разработаны вокруг этих концепций. В частности, то, что другие языки объединяются в один набор функций, Haskell разделяется на два:

• Детерминированные особенности и библиотеки для параллелизма .
• Недетерминированные функции и библиотеки для параллелизма .

Если вы просто пытаетесь ускорить чистые, детерминированные вычисления, наличие детерминированного параллелизма часто делает вещи намного проще. Часто вы просто делаете что-то вроде этого:

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

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

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

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

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

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

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

Дальнейшее чтение
Параллелизм в Haskell (HaskellWiki)
Параллельное и многоядерное программирование в параллельном и параллельном программировании "Haskell в реальном мире"
в Haskell. Автор Simon Marlow