Le paradigme fonctionnel n'est-il pas trop différent du matériel sous-jacent pour être généralement efficace?

14

Inspiré d'une question de SO: /programming/6623391/how-to-gain-control-of-a-5gb-heap-in-haskell

Cela peut être un long débat sur les nombreux avantages et inconvénients de FP, mais pour l'instant, je voudrais limiter la portée à l' efficacité principale de FP sur du matériel moderne.

Thèse:

Le paradigme fonctionnel implique l'immuabilité et l'apatridie (?), Mais le matériel sur lequel nous exécutons les programmes fonctionnels sont des automates finis avec état. La traduction d'un programme «purement fonctionnel» en une représentation «matérielle avec état» laisse peu de contrôle au programmeur, entraîne des frais généraux (?) Et limite l'utilisation des capacités matérielles (?).

Ai-je raison ou tort dans les déclarations interrogées?

Peut-on prouver que FP implique / n'implique pas de pénalités de performances principales sur l'architecture informatique moderne à usage général?

EDIT: Comme je l'ai déjà indiqué en réponse à certains commentaires, la question n'est pas sur les performances et les détails de la mise en œuvre. Il s'agit de la présence ou de l'absence de surcharge , que l'exécution de FP sur des automates avec état peut apporter.

vignes
la source
3
Avez-vous déjà vraiment regardé comment le matériel moderne fonctionne à un bas niveau? Si vous vous souciez de l'efficacité, cela ne ressemble pas non plus à la programmation impérative de tous les jours.
CA McCann
Croyez-le ou non, mais les informaticiens qui ont conçu des langages de programmation fonctionnels et des compilateurs connaissent également un peu l'optimisation des performances. Ce n'est pas le but de chaque produit de langage fonctionnel mais c'est pour les plateformes de production sérieuses.
Jeremy
@camccann, @Jeremy: C # et Java, par exemple, utilisent des machines virtuelles. Peu importe à quel point il est optimal, peu importe l'efficacité des programmes C # et Java pour la production, il existe une principale source d'inefficacité, et c'est la machine virtuelle. La question n'est pas sur les performances de mise en œuvre, mais running FP on stateful automata.
vignes
1
voir ma question ici
Gulshan
2
@vines: Vous vous rendez compte que les machines virtuelles modernes avec JITing sophistiqué peuvent en fait surpasser le code natif dans certains cas, non? Et que le but d'un compilateur est de convertir un programme en une représentation correspondant à l'architecture sous-jacente, ce qui ne ressemble à aucun langage moderne? Votre question n'a aucun sens.
CA McCann, le

Réponses:

7

Il y a un énorme malentendu dans l'immuabilité.

L'immuabilité est une caractéristique de la sémantique, mais elle n'implique pas l'immuabilité dans l'implémentation.

Un exemple simple est la mise en œuvre de la paresse.

Lorsque les calculs sont paresseux, le résultat d'une expression est conceptuellement une valeur, mais l'implémentation sous-jacente est un thunk qui contient les arguments à évaluer et une fonction pour créer la valeur, ainsi qu'un emplacement pour stocker la valeur.

La première fois que vous demanderez (dans le langage) la valeur, le calcul sera réellement effectué, son résultat évalué et la valeur qui vous sera rendue (ou un handle).

Ceci est transparent dans la sémantique du langage, et tout ce que vous savez, c'est que cette variable a été liée à une valeur (ou une valeur future) et qu'une fois cela fait, vous ne pouvez pas changer la valeur qui sera retournée. La représentation de la mémoire sous-jacente changera, mais vous n'en saurez rien.

La même différence sémantique / implémentation existe dans à peu près n'importe quel langage, et est en fait au cœur de l' optimisation . Quelle que soit la langue, la sémantique garantit certaines choses, mais laisse d'autres non spécifiées pour laisser la place à l'optimisation.

Maintenant, il est vrai que les langages pratiquement fonctionnels ne sont pas aussi rapides que C ++, par exemple. Cependant, Go(qui est encore tout à fait le battage médiatique) est plus lent que Haskell ou Lisp, tout comme C # Mono ( source ).

Lorsque vous voyez à quel point le C ++ ou le C peuvent être peu fiables pour obtenir ces performances, vous souhaiterez peut-être un peu lâcher prise.

Lorsque vous réalisez que Haskell se développe rapidement aujourd'hui et qu'il y a encore beaucoup de place pour l'optimisation dans son compilateur / runtime (GHC vient de passer récemment à LLVM par exemple, Microsoft Research finance activement les améliorations de runtime), vous pourriez être prêt à parier que ça va bientôt s'améliorer.

Amusant: un jeu sur les expressions régulières ou comment une équipe Haskell a créé un comparateur d'expressions régulières qui surpasse re2la bibliothèque C de Google, dans un certain nombre de scénarios.

Matthieu M.
la source
Cela semble optimiste :)
vines
3

Le paradigme fonctionnel est utile pour diviser la chose dans une portée étroite. C'est vraiment une bonne chose compte tenu de l'évolution de l'ordinateur.

Le processeur multicœur a de gros problèmes avec les ressources partagées et les coûts de synchronisation sont vraiment coûteux. Le paradigme fonctionnel permet une manière naturelle d'exprimer des programmes qui n'ont pas ces problèmes. C'est vraiment bon pour le parallélisme.

De plus, nous utilisons de plus en plus de batteries de serveurs avec le SaaS et le cloud computing. Ainsi, la même application doit fonctionner sur plusieurs machines. Dans cette position, les coûts de synchronisation sont encore plus coûteux. Google a fait du travail et publié des articles de recherche sur la programmation fonctionnelle et l'algorithme que vous pouvez écrire. C'est un élément clé pour eux car ils ont un problème de scallabilité.

De plus, vous pouvez facilement faire une pile dans le tas de l'ordinateur, et même une pile non continue en utilisant des listes liées. Ceci est déjà fait pour générer une trace de pile dans de nombreux langages de programmation. Ce n'est donc pas un problème.

OK, la programmation fonctionnelle implique certaines limitations. Mais cela apporte également un moyen naturel d'exprimer les problèmes que nous avons dans l'informatique moderne, qui sont extrêmement difficiles à gérer dans les paradigmes auxquels nous sommes habitués. L'évolutivité en fait partie, et cela devient une vraie affaire.

Tous ceux qui ont déjà affaire à un système parallèle complexe savent de quoi je parle.

Je nuancerais donc la réponse. Oui, la fonctionnalité a un problème avec le matériel moderne, mais la vieille programmation ordinaire en a aussi. Comme toujours, vous trouverez des avantages et des inconvénients. Le but est de savoir de quoi il s'agit afin que vous puissiez faire le choix approprié quand vous le devez.

deadalnix
la source
0

Je n'ai pas vraiment de réponse, car je ne connais pas l'état actuel ni même à quel point ce serait difficile, mais simplement parce que le compilateur garantirait ces choses à partir de l'entrée, ne signifie pas nécessairement que la sortie les aurait . En théorie, un compilateur suffisamment intelligent pourrait contourner tous ces problèmes, mais en pratique, il existera probablement toujours.

Cependant, une autre façon de voir les choses est de regarder l'histoire de la machine Lisp. Si je me souviens bien, ils ont été initialement conçus pour surmonter les mêmes problèmes que Lisp avait avec sa différence avec les machines de l'époque. Le développement de ces machines s'est finalement arrêté, car le bureau est devenu assez rapide pour rendre les inefficacités moins coûteuses à vivre que pour prendre en charge une autre machine.

Généralement, à l'exception de l'application la plus critique en termes de performances, les langages FP sont encore assez rapides. Choisissez n'importe quelle langue de niveau supérieur, vous serez prêt à réduire la priorité sur le contrôle et les performances de réglage fin pour une priorité plus sûre, plus facile, plus maintenable ou une autre

En fin de compte, la programmation est une question de compromis, il suffit donc de choisir ce qui compte le plus pour le projet en cours.

tylermac
la source
0

Il est vrai que le paradigme fonctionnel implique l'immuabilité et l'apatridie, mais nous n'avons pas de langages de programmation complètement purs. Même le plus pur, Haskell, permet des effets secondaires.

Cela dit, pour répondre à votre question sur l'efficacité, j'ai utilisé Haskell et Clojure, et je n'ai remarqué aucun problème de performance avec l'un ou l'autre.

Larry Coleman
la source
1
Les problèmes sont liés aux exigences ... Qu'en est-il des domaines critiques pour les performances? Un parallélisme élevé y est précieux, mais quel est le score global?
vignes du
1
@vines: Je n'ai utilisé aucune langue pour une application critique pour les performances, donc je ne peux pas vraiment en parler.
Larry Coleman
1
Pas beaucoup de plaisir sans effets secondaires, car vous ne seriez pas en mesure d'enregistrer le résultat n'importe où.
@ Thorbjørn Ravn Andersen: ... d'une autre manière que de le renvoyer à l'appelant, ce qui est autorisé.
vignes