La programmation fonctionnelle en multithreading est-elle plus rapide parce que j'écris des choses différemment ou parce que les choses sont compilées différemment?

Je plonge dans le monde de la programmation fonctionnelle et je continue de lire que les langages fonctionnels sont meilleurs pour les programmes multithreading / multicœurs. Je comprends comment les langages fonctionnels font beaucoup de choses différemment, comme récursion , nombres aléatoires , etc , mais je ne peux pas sembler comprendre si multithreading est plus rapide dans un langage fonctionnel car il est compilé différemment ou parce que j'écris différemment.

Par exemple, j'ai écrit un programme en Java qui implémente un certain protocole. Dans ce protocole, les deux parties s'envoient et se reçoivent des milliers de messages, les chiffrent et les renvoient (et les reçoivent) encore et encore. Comme prévu, le multithreading est essentiel lorsque vous traitez à l'échelle de milliers. Dans ce programme, aucun verrouillage n’est impliqué .

Si j'écris le même programme dans Scala (qui utilise la machine virtuelle Java), cette implémentation sera-t-elle plus rapide? Si oui pourquoi? Est-ce à cause du style d'écriture? Si c'est à cause du style d'écriture, maintenant que Java comprend des expressions lambda, je ne pourrais pas obtenir les mêmes résultats en utilisant Java avec lambda? Ou est-ce plus rapide parce que Scala compilera les choses différemment?

La raison pour laquelle les gens disent que les langages fonctionnels conviennent mieux au traitement parallèle tient au fait qu’ils évitent généralement les états mutables. L'état mutable est la "racine de tout mal" dans le contexte du traitement parallèle; ils facilitent la tâche dans des conditions de concurrence quand ils sont partagés entre des processus concurrents. La solution aux conditions de concurrence implique alors des mécanismes de verrouillage et de synchronisation, comme vous l'avez mentionné, qui entraînent une surcharge de temps d'exécution, car les processus s'attendent à utiliser la ressource partagée, et une complexité de conception accrue, car tous ces concepts ont tendance à être complexes. profondément niché dans de telles applications.

Lorsque vous évitez l'état mutable, le besoin de mécanismes de synchronisation et de verrouillage disparaît. Etant donné que les langages fonctionnels évitent généralement les états mutables, ils sont naturellement plus efficaces pour le traitement parallèle: vous n'aurez pas la surcharge d'exécution liée aux ressources partagées et vous n'aurez pas la complexité de conception supplémentaire qui s'ensuit.

Cependant, tout cela est accessoire. Si votre solution en Java évite également les états mutables (spécifiquement partagés entre les threads), la convertir en un langage fonctionnel tel que Scala ou Clojure ne procurerait aucun avantage en termes d’efficacité concurrente, car la solution originale est déjà exempte de la surcharge causée par les mécanismes de verrouillage et de synchronisation.

TL; DR: Si une solution dans Scala est plus efficace en traitement parallèle qu’en Java, ce n’est pas en raison de la façon dont le code est compilé ou exécuté via la machine virtuelle, mais bien du fait que la solution Java partage l’état mutable entre les threads, soit en provoquant des conditions de concurrence, soit en ajoutant la surcharge de la synchronisation afin de les éviter.

Tri des deux. C'est plus rapide car il est plus facile d'écrire votre code d'une manière plus facile à compiler plus rapidement. En changeant de langue, vous n'aurez pas forcément une différence de vitesse, mais si vous aviez commencé avec un langage fonctionnel, vous auriez probablement pu faire le multithreading avec beaucoup moins d' effort de la part du programmeur . Dans le même ordre d'idées, il est beaucoup plus facile pour un programmeur de commettre des erreurs de threading coûteuses en rapidité dans un langage impératif, et bien plus difficiles à repérer ces erreurs.

La raison est impérative. En général, les programmeurs essaient de mettre tout le code non verrouillé et fileté dans une boîte aussi petite que possible et de l’échapper le plus rapidement possible dans leur monde confortable et synchrone. La plupart des erreurs qui vous coûtent de la vitesse sont faites sur cette interface limite. Dans un langage de programmation fonctionnel, vous n'avez pas à vous soucier autant de faire des erreurs sur cette limite. La plupart de votre code d'appel est également "à l'intérieur de la boîte", pour ainsi dire.

En règle générale, la programmation fonctionnelle ne permet pas d'accélérer les programmes. Cela facilite la programmation parallèle et simultanée. Il y a deux clés principales à cela:

1. L'évitement de l'état mutable tend à réduire le nombre de problèmes pouvant survenir dans un programme, et encore plus dans un programme simultané.
2. Le fait d'éviter les primitives de synchronisation en mémoire partagée et de verrouillage basées sur des concepts de niveau supérieur a tendance à simplifier la synchronisation entre les threads de code.

Un excellent exemple du point # 2 est que dans Haskell nous avons une distinction claire entre le parallélisme déterministe par rapport à la concurrence non déterministe . Il n'y a pas de meilleure explication que de citer l'excellent livre de Simon Marlow intitulé Parallel and Concurrent Programming in Haskell (les citations sont tirées du chapitre 1 ):

Un programme parallèle est un programme qui utilise une multiplicité de matériel informatique (plusieurs cœurs de processeur, par exemple) pour effectuer un calcul plus rapidement. L'objectif est d'arriver à la réponse plus tôt, en déléguant différentes parties du calcul à différents processeurs qui s'exécutent en même temps.

En revanche, la simultanéité est une technique de structuration de programme dans laquelle il existe plusieurs threads de contrôle. Conceptuellement, les threads de contrôle s'exécutent «en même temps»; c'est-à-dire que l'utilisateur voit leurs effets entrelacés. Qu'ils s'exécutent en même temps ou non en même temps est un détail d'implémentation; un programme simultané peut s'exécuter sur un seul processeur via une exécution entrelacée ou sur plusieurs processeurs physiques.

Marlow mentionne également la dimension du déterminisme :

Une distinction est établie entre les modèles de programmation déterministes et non déterministes . Un modèle de programmation déterministe est un modèle dans lequel chaque programme ne peut donner qu'un seul résultat, alors qu'un modèle de programmation non déterministe admet des programmes pouvant avoir des résultats différents, en fonction de certains aspects de l'exécution. Les modèles de programmation simultanés sont nécessairement non déterministes, car ils doivent interagir avec des agents externes qui provoquent des événements à des moments imprévisibles. Le non-déterminisme présente toutefois certains inconvénients notables: il devient de plus en plus difficile de tester et de raisonner les programmes.

Pour la programmation parallèle, nous aimerions utiliser des modèles de programmation déterministes dans la mesure du possible. Puisque l'objectif est simplement d'arriver à la réponse plus rapidement, nous préférons ne pas rendre notre programme plus difficile à déboguer au cours du processus. La programmation parallèle déterministe est le meilleur des deux mondes: les tests, le débogage et le raisonnement peuvent être effectués sur le programme séquentiel, mais le programme s'exécute plus rapidement avec l'ajout de processeurs supplémentaires.

Dans Haskell, les fonctionnalités de parallélisme et de concurrence sont conçues autour de ces concepts. Haskell se divise notamment en deux groupes de langues:

• Fonctionnalités déterministes et bibliothèques pour le parallélisme .
• Fonctions et bibliothèques non déterministes pour la simultanéité .

Si vous essayez simplement d'accélérer un calcul purement déterministe, le parallélisme déterministe facilite souvent beaucoup les choses. Souvent, vous faites juste quelque chose comme ça:

1. Ecrivez une fonction qui produit une liste de réponses dont chacune coûte cher à calculer, mais ne dépend pas beaucoup l'une de l'autre. C'est Haskell, donc les listes sont paresseuses - les valeurs de leurs éléments ne sont pas réellement calculées jusqu'à ce qu'un consommateur les demande.
2. Utilisez la bibliothèque Stratégies pour utiliser les éléments des listes de résultats de votre fonction en parallèle sur plusieurs cœurs.

C'est ce que j'ai fait avec l'un de mes programmes de projets de jouets il y a quelques semaines . Il était trivial de paralléliser le programme - l’essentiel, c’était d’ajouter du code indiquant «calculer les éléments de cette liste en parallèle» (ligne 90), et j’ai obtenu un gain de débit quasi linéaire en certains de mes cas de test les plus chers.

Mon programme est-il plus rapide que si j'avais utilisé des utilitaires classiques de multithreading basés sur des verrous? J'en doute fort. La chose intéressante dans mon cas était de tirer tellement de profit de mon argent - mon code est probablement très sous-optimal, mais parce qu'il est si facile de le paralléliser, j'ai beaucoup accéléré avec beaucoup moins d'effort que de le profiler et de l'optimiser correctement, et aucun risque de conditions de course. Et je dirais que c’est la manière principale dont la programmation fonctionnelle vous permet d’écrire des programmes "plus rapides".

En Haskell, la modification est littéralement impossible sans obtenir des variables modifiables spéciales via une bibliothèque de modifications. Au lieu de cela, les fonctions créent les variables dont ils ont besoin en même temps que leurs valeurs (calculées paresseusement) et les ordures collectées lorsqu'elles ne sont plus nécessaires.

Même lorsque vous avez besoin de variables de modification, vous pouvez généralement obtenir en utilisant peu et avec les variables non modifiables. (Une autre bonne chose dans haskell est STM, qui remplace les verrous par des opérations atomiques, mais je ne suis pas sûr que ce soit uniquement pour la programmation fonctionnelle.) Généralement, une seule partie du programme devra être mise en parallèle pour améliorer les choses. performance sage.

Cela rend le parallélisme à Haskell facile souvent, et des efforts sont en cours pour le rendre automatique. Pour un code simple, le parallélisme et la logique peuvent même être séparés.

De plus, étant donné que l'ordre d'évaluation n'a pas d'importance dans Haskell, le compilateur crée simplement une file d'attente qui doit être évaluée et les envoie à tous les cœurs disponibles, afin que vous puissiez créer un ensemble de "threads" qui ne le sont pas. deviennent réellement des fils jusqu’au besoin. L'ordre d'évaluation sans importance est caractéristique de la pureté, ce qui nécessite généralement une programmation fonctionnelle.

Lectures complémentaires
Parallélisme en Haskell (HaskellWiki)
Programmation concurrente et Multicore dans « Real-World Haskell »
Programmation parallèle et concurrente à Haskell par Simon Marlow