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?

63

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?

Aventinus
la source
64
La programmation fonctionnelle Afaik ne rend pas le multithreading plus rapide. Cela rend le multithreading plus facile à mettre en œuvre et plus sûr car certaines fonctionnalités de la programmation fonctionnelle telles que l'immutabilité et des fonctions sans effets secondaires sont utiles à cet égard.
Pieter B
7
Notez que 1) mieux n'est pas vraiment défini 2) il n'est sûrement pas défini simplement comme "plus rapide". Un langage X qui nécessite un milliard de fois la taille du code pour un gain de performance de 0,1% par rapport à Y n'est pas meilleur que Y pour toute définition raisonnable de mieux.
Bakuriu
2
Voulez-vous parler de "programmation fonctionnelle" ou de "programmes écrits dans un style fonctionnel"? Souvent, une programmation plus rapide ne produit pas un programme plus rapide.
Ben Voigt
1
N'oubliez pas qu'il y a toujours un GC qui doit fonctionner en arrière-plan et répondre à vos demandes d'allocation ... et je ne suis pas sûr qu'il soit multithread ...
mercredi
4
La réponse la plus simple est la suivante: la programmation fonctionnelle permet d’écrire des programmes prenant en compte moins de problèmes de concurrence, mais cela ne signifie pas que les programmes écrits en style impératif seront plus lents.
Dawid Pura

Réponses:

97

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.

MichelHenrich
la source
2
Si un seul thread modifie une donnée; aucun soin particulier n'est nécessaire. Ce n'est que lorsque plusieurs threads peuvent modifier les mêmes données que vous avez besoin d'une attention particulière (synchronisation, mémoire transactionnelle, verrouillage, etc.). Un exemple de ceci est la pile d'un thread, qui est constamment mutée par le code fonctionnel mais non modifiée par plusieurs threads.
Brendan
31
Si un thread mute les données pendant que d'autres le lisent, il suffit de commencer à prendre des "précautions particulières".
Peter Green
10
@Brendan: Non, si un thread modifie des données pendant que d'autres le lisent à partir de ces mêmes données, vous avez une condition de concurrence critique. Une attention particulière est nécessaire même si un seul thread est en train de modifier.
Cornstalks
3
L'état mutable est la "racine de tout mal" dans le contexte du traitement parallèle => si vous n'avez pas encore regardé Rust, je vous conseille d'y jeter un coup d'œil. Il parvient à permettre la mutabilité de manière très efficace en réalisant que le véritable problème peut être mélangé à un aliasing: si vous avez uniquement un aliasing ou si vous ne possédez qu'une mutabilité, il n'y a pas de problème.
Matthieu M.
2
@MatthieuM. Oui, merci! J'ai édité pour exprimer les choses plus clairement dans ma réponse. L'état mutable n'est que "la racine de tout mal" lorsqu'il est partagé entre plusieurs processus concurrents - ce que Rust évite avec ses mécanismes de contrôle de propriété.
MichelHenrich
8

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.

Karl Bielefeldt
la source
7

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".

sacundim
la source
2

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

PyRulez
la source
7
grep java this_post. grep scala this_postet grep jvm this_postne donne aucun résultat :)
Andres F.
4
La question est vague. Dans le titre et le premier paragraphe, il est question de la programmation fonctionnelle en général , tandis que dans les deuxième et troisième paragraphes, il est question de Java et de Scala en particulier . C’est regrettable, d’autant plus que l’un des principaux atouts de Scala est précisément le fait qu’il ne s’agit pas (seulement) d’un langage fonctionnel. Martin Odersky appelle cela "post-fonctionnel", d'autres l'appellent "objet-fonctionnel". Il existe deux définitions différentes du terme "programmation fonctionnelle". L'un est "la programmation avec des procédures de première classe" (la définition originale appliquée au LISP), l'autre est ...
Jörg W Mittag
2
"programmation avec des fonctions référentiellement transparentes, pures et sans effets secondaires et des données persistantes immuables" (interprétation beaucoup plus stricte et plus récente). Cette réponse aborde la deuxième interprétation, qui a du sens, car a) la première interprétation est totalement indépendante du parallélisme et de la simultanéité; b) la première interprétation est devenue fondamentalement vide de sens puisque, à l'exception du C, presque toutes les langues sont utilisées, même de manière modeste, Aujourd'hui, nous avons des procédures de premier ordre (y compris Java) et c) le PO demande quelle est la différence entre Java et Scala, mais il n'y a pas…
Jörg W Mittag
2
entre les deux concernant la définition n ° 1, seule la définition n ° 2.
Jörg W Mittag
L'évaluation n'est pas tout à fait vraie telle qu'elle est écrite ici; Par défaut, le moteur d'exécution n'utilise pas du tout le multithreading, et le IIRC, même si vous activez le multithreading, vous devez toujours lui indiquer ce qu'il doit évaluer en parallèle.
Cubique