Pourquoi Haskell (GHC) est-il si rapide?

247

Haskell (avec le GHCcompilateur) est beaucoup plus rapide que prévu . Utilisé correctement, il peut se rapprocher des langues de bas niveau. (Une des choses préférées des Haskellers est d'essayer d'obtenir jusqu'à 5% de C (ou même de le battre, mais cela signifie que vous utilisez un programme C inefficace, car GHC compile Haskell en C).) Ma question est, pourquoi?

Haskell est déclaratif et basé sur le calcul lambda. Les architectures de machines sont clairement impératives, étant basées sur des machines de turing, à peu près. En effet, Haskell n'a même pas d'ordre d'évaluation spécifique. De plus, au lieu de traiter des types de données machine, vous créez tout le temps des types de données algébriques.

Mais le plus étrange est les fonctions d'ordre supérieur. On pourrait penser que créer des fonctions à la volée et les lancer rendrait un programme plus lent. Mais l'utilisation de fonctions d'ordre supérieur accélère en fait Haskell. En effet, il semble que, pour optimiser le code Haskell, vous devez le rendre plus élégant et abstrait au lieu de plus semblable à une machine. Aucune des fonctionnalités les plus avancées de Haskell ne semble même affecter ses performances, si elles ne les améliorent pas.

Désolé si cela semble décourageant, mais voici ma question: pourquoi Haskell (compilé avec GHC) est-il si rapide, compte tenu de sa nature abstraite et de ses différences avec les machines physiques?

Remarque: La raison pour laquelle je dis que C et d'autres langages impératifs sont quelque peu similaires à Turing Machines (mais pas dans la mesure où Haskell est similaire au calcul Lambda) est que dans un langage impératif, vous avez un nombre fini d'états (aka numéro de ligne) , ainsi qu'une bande (la mémoire RAM), de telle sorte que l'état et la bande actuelle déterminent ce qu'il faut faire avec la bande. Voir l'entrée Wikipedia, équivalents de machine de Turing , pour la transition de machines de Turing aux ordinateurs.

PyRulez
la source
27
"puisque GHC compile Haskell en C" - ce n'est pas le cas. GHC a plusieurs backends. Le plus ancien (mais pas celui par défaut) est un générateur C. Il génère du code Cmm pour IR, mais ce n'est pas "la compilation en C" que vous attendez normalement. ( downloads.haskell.org/~ghc/latest/docs/html/users_guide/… )
viraptor
20
Je recommande fortement la lecture de la mise en œuvre des langages de programmation fonctionnelle par Simon Payton Jones (le principal exécuteur de GHC), il répondra à beaucoup de vos questions.
Joe Hillenbrand
94
Pourquoi? 25 ans de dur labeur.
août
31
"Même s'il pourrait y avoir une réponse factuelle, cela ne fera que solliciter des opinions." - C'est la pire raison possible pour clore une question. Parce qu'elle peut avoir une bonne réponse, mais elle attirera potentiellement aussi des réponses de mauvaise qualité. Beurk! Il se trouve que j'ai une bonne réponse historique et factuelle sur la recherche universitaire et sur le moment où certains développements se sont produits. Mais je ne peux pas le poster parce que les gens craignent que cette question n'attire également des réponses de mauvaise qualité. Encore une fois, beurk.
sclv
7
@cimmanon je besoin d' un mois ou plusieurs messages de blog de marcher à travers les bases des détails de la façon dont fonctionne un compilateur fonctionnel. Je n'ai besoin que d'une réponse SO pour esquisser dans les grandes lignes comment une machine graphique peut être implémentée proprement sur du matériel de stock et pointer vers les sources pertinentes pour une lecture plus approfondie ...
sclv

Réponses:

264

Je suis d'accord avec Dietrich Epp: c'est une combinaison de plusieurs choses qui rendent le GHC rapide.

D'abord et avant tout, Haskell est de très haut niveau. Cela permet au compilateur d'effectuer des optimisations agressives sans casser votre code.

Pensez à SQL. Maintenant, quand j'écris une SELECTdéclaration, cela peut ressembler à une boucle impérative, mais ce n'est pas le cas . Il peut sembler qu'il boucle sur toutes les lignes de cette table en essayant de trouver celle qui correspond aux conditions spécifiées, mais en fait le "compilateur" (le moteur de base de données) pourrait faire une recherche d'index à la place - qui a des caractéristiques de performances complètement différentes. Mais parce que SQL est si haut niveau, le "compilateur" peut remplacer des algorithmes totalement différents, appliquer plusieurs processeurs ou canaux d'E / S ou des serveurs entiers de manière transparente, et plus encore.

Je pense que Haskell est le même. Vous pourriez penser que vous venez de demander à Haskell de mapper la liste d'entrée à une deuxième liste, de filtrer la deuxième liste en une troisième liste, puis de compter le nombre d'éléments obtenus. Mais vous n'avez pas vu GHC appliquer des règles de réécriture de fusion de flux dans les coulisses, transformant le tout en une seule boucle de code machine serrée qui fait tout le travail en un seul passage sur les données sans allocation - le genre de chose qui être fastidieux, sujet aux erreurs et non maintenable pour écrire à la main. Cela n'est vraiment possible qu'en raison du manque de détails de bas niveau dans le code.

Une autre façon de voir les choses pourrait être… pourquoi Haskell ne devrait-il pas être rapide? Que fait-il pour que ça ralentisse?

Ce n'est pas un langage interprété comme Perl ou JavaScript. Ce n'est même pas un système de machine virtuelle comme Java ou C #. Il compile jusqu'au code machine natif, donc pas de surcharge là-bas.

Contrairement aux langages OO [Java, C #, JavaScript…], Haskell a un effacement de type complet [comme C, C ++, Pascal…]. La vérification de tous les types se produit uniquement lors de la compilation. Il n'y a donc pas de vérification de type au moment de l'exécution pour vous ralentir non plus. (Aucune vérification de pointeur nul, d'ailleurs. En Java, par exemple, la JVM doit vérifier les pointeurs nuls et lever une exception si vous en déférencez une. Haskell n'a pas à s'embêter avec cette vérification.)

Vous dites qu'il semble lent de «créer des fonctions à la volée au moment de l'exécution», mais si vous regardez très attentivement, vous ne le faites pas vraiment. Cela pourrait vous ressembler , mais ce n'est pas le cas. Si vous dites (+5), eh bien, c'est codé en dur dans votre code source. Il ne peut pas changer au moment de l'exécution. Ce n'est donc pas vraiment une fonction dynamique. Même les fonctions au curry ne sont vraiment que la sauvegarde des paramètres dans un bloc de données. Tout le code exécutable existe réellement au moment de la compilation; il n'y a pas d'interprétation d'exécution. (Contrairement à certaines autres langues qui ont une "fonction eval".)

Pensez à Pascal. C'est vieux et personne ne l'utilise plus vraiment, mais personne ne se plaindrait que Pascal est lent . Il y a beaucoup de choses à ne pas aimer à ce sujet, mais la lenteur n'en fait pas vraiment partie. Haskell ne fait pas vraiment grand-chose de différent de Pascal, à part avoir un ramasse-miettes plutôt qu'une gestion manuelle de la mémoire. Et les données immuables permettent plusieurs optimisations au moteur GC [ce qui complique ensuite l'évaluation paresseuse].

Je pense que le truc c'est que Haskell a l' air avancé et sophistiqué et de haut niveau, et tout le monde pense "oh wow, c'est vraiment puissant, ça doit être incroyablement lent! " Mais ce n'est pas le cas. Ou du moins, ce n'est pas comme vous vous y attendez. Oui, il a un système de type incroyable. Mais tu sais quoi? Tout cela se produit au moment de la compilation. Au moment de l'exécution, c'est parti. Oui, cela vous permet de construire des ADT compliqués avec une ligne de code. Mais tu sais quoi? Un ADT n'est qu'un simple C ordinaire unionde l' structart. Rien de plus.

Le vrai tueur est l'évaluation paresseuse. Lorsque vous obtenez la rigueur / la paresse de votre code, vous pouvez écrire un code stupidement rapide qui est toujours élégant et beau. Mais si vous vous trompez, votre programme va des milliers de fois plus lentement , et il est vraiment difficile de comprendre pourquoi cela se produit.

Par exemple, j'ai écrit un petit programme trivial pour compter combien de fois chaque octet apparaît dans un fichier. Pour un fichier d'entrée de 25 Ko, le programme a pris 20 minutes à exécuter et a avalé 6 gigaoctets de RAM! C'est absurde!! Mais ensuite j'ai réalisé quel était le problème, j'ai ajouté un seul modèle de coup et le temps d'exécution est tombé à 0,02 seconde .

C'est là que Haskell va lentement et de façon inattendue. Et il faut certainement un certain temps pour s'y habituer. Mais au fil du temps, il devient plus facile d'écrire du code très rapide.

Qu'est-ce qui rend Haskell si rapide? Pureté. Types statiques. Paresse. Mais surtout, étant suffisamment élevé pour que le compilateur puisse changer radicalement l'implémentation sans casser les attentes de votre code.

Mais je suppose que c'est juste mon opinion ...

MathematicalOrchid
la source
13
@cimmanon Je ne pense pas que ce soit uniquement basé sur l' opinion. C'est une question intéressante à laquelle d'autres personnes ont probablement demandé une réponse. Mais je suppose que nous verrons ce que les autres électeurs pensent.
MathematicalOrchid
8
@cimmanon - cette recherche ne donne qu'un et demi de threads, et ils ont tous à voir avec les audits de révision. et la réponse votée au fil dit "veuillez arrêter de modérer des choses que vous ne comprenez pas". Je dirais que si quelqu'un pense que la réponse à cette question est nécessairement trop large, il serait surpris et apprécierait la réponse, car la réponse n'est pas trop large.
sclv
34
"Dans, disons, Java, la JVM doit vérifier les pointeurs nuls et lever une exception si vous en déférer un." La vérification nulle implicite de Java est (principalement) gratuite. Les implémentations Java peuvent et profitent de la mémoire virtuelle pour mapper l'adresse nulle à une page manquante, donc le déréférencement d'un pointeur nul déclenche une erreur de page au niveau du processeur, que Java intercepte et lève comme exception de haut niveau. Ainsi, la plupart des contrôles nuls sont effectués gratuitement par l'unité de mappage de la mémoire dans le CPU.
Boann
4
@cimmanon: C'est peut-être parce que les utilisateurs de Haskell semblent être la seule communauté qui est en fait un groupe amical de personnes ouvertes d'esprit ... que vous considérez comme "une blague" ..., au lieu d'une communauté de chien-manger-chien de règle nazis qui se déchirer un nouveau à chaque chance qu'ils obtiennent… ce qui semble être ce que vous considérez comme «normal».
Evi1M4chine
14
@MathematicalOrchid: avez-vous une copie de votre programme d'origine qui a pris 20 minutes pour s'exécuter? Je pense qu'il serait très instructif d'étudier pourquoi c'est si lent.
George
79

Pendant longtemps, on a pensé que les langages fonctionnels ne pouvaient pas être rapides - et surtout les langages fonctionnels paresseux. Mais c'était parce que leurs premières implémentations étaient, en substance, interprétées et non pas véritablement compilées.

Une deuxième vague de conceptions est apparue sur la base de la réduction des graphes et a ouvert la possibilité d'une compilation beaucoup plus efficace. Simon Peyton Jones a écrit à propos de cette recherche dans ses deux livres The Implementation of Functional Programming Languages and Implementationing Functional Languages : a tutorial (the first with sections by Wadler and Hancock, and the second écrite with David Lester). (Lennart Augustsson m'a également informé qu'une des principales motivations de l'ancien livre était de décrire la manière dont son compilateur LML, qui n'a pas été largement commenté, a réalisé sa compilation).

La notion clé derrière les approches de réduction de graphe telles que décrites dans ces travaux est que nous ne pensons pas à un programme comme une séquence d'instructions, mais à un graphe de dépendance qui est évalué par une série de réductions locales. La deuxième idée clé est que l'évaluation d'un tel graphique n'a pas besoin d'être interprétée mais que le graphique lui-même peut être construit à partir de code . En particulier, nous pouvons représenter un nœud d'un graphe non pas comme "soit une valeur ou un" opcode "et les valeurs sur lesquelles opérer", mais plutôt comme une fonction qui, lorsqu'elle est invoquée, renvoie la valeur souhaitée. La première fois qu'il est invoqué, il demande aux sous-noeuds leurs valeurs, puis les opère, puis il se remplace par une nouvelle instruction qui dit simplement "retourner le résultat.

Ceci est décrit dans un article ultérieur qui expose les bases de la façon dont GHC fonctionne encore aujourd'hui (bien que modulo de nombreux ajustements divers): "Implémentation de langages fonctionnels paresseux sur le matériel de stock: la G-Machine Spineless Tagless." . Le modèle d'exécution actuel pour GHC est documenté plus en détail sur le Wiki GHC .

L'idée est donc que la stricte distinction entre «données» et «code» que nous considérons comme «fondamentales» pour le fonctionnement des machines n'est pas la manière dont elles doivent fonctionner, mais est imposée par nos compilateurs. Nous pouvons donc jeter cela et avoir du code (un compilateur) qui génère du code auto-modifiable (l'exécutable) et tout cela peut très bien fonctionner.

Ainsi, il s'avère que, bien que les architectures des machines soient impératives dans un certain sens, les langages peuvent y correspondre de manière très surprenante qui ne ressemble pas au contrôle de flux de style C conventionnel, et si nous pensons suffisamment bas, cela peut également être efficace.

En plus de cela, il existe de nombreuses autres optimisations ouvertes par la pureté en particulier, car elle permet une plus grande gamme de transformations "sûres". Quand et comment appliquer ces transformations de manière à ce qu'elles améliorent et non aggravent les choses est bien sûr une question empirique, et sur ce point et sur de nombreux autres petits choix, des années de travail ont été consacrées à la fois au travail théorique et au benchmarking pratique. Bien sûr, cela joue également un rôle. Un article qui fournit un bon exemple de ce type de recherche est « Making a Fast Curry: Push / Enter vs Eval / Apply for Higher-Order Languages».

Enfin, il convient de noter que ce modèle introduit toujours un surcoût dû aux indirections. Cela peut être évité dans les cas où nous savons qu'il est "sûr" de faire les choses strictement et donc d'éluder les indirections des graphes. Les mécanismes qui infèrent la rigueur / la demande sont à nouveau documentés en détail sur le Wiki GHC .

sclv
la source
2
Ce lien d'analyseur de demande vaut son pesant d'or! Enfin quelque chose sur le sujet qui n'agit pas comme s'il s'agissait d'une magie noire fondamentalement inexplicable. Comment n'ai-je jamais entendu parler de ça ?? Il devrait être lié de partout où quiconque demande comment résoudre les problèmes de paresse!
Evi1M4chine
@ Evi1M4chine Je ne vois pas de lien lié à un analyseur de demande, il a peut-être été perdu d'une manière ou d'une autre. Quelqu'un peut-il restaurer le lien ou clarifier la référence? Cela semble assez intéressant.
Cris P
1
@CrisP Je pense que le dernier lien est celui auquel on fait référence. Il va à une page sur le Wiki GHC sur l'analyseur de demande dans GHC.
Serp C
@Serpentine Cougar, Chris P: Oui, c'est ce que je voulais dire.
Evi1M4chine
19

Eh bien, il y a beaucoup à dire ici. Je vais essayer de répondre autant que possible.

Utilisé correctement, il peut se rapprocher des langues de bas niveau.

D'après mon expérience, il est généralement possible d'obtenir dans les 2x les performances de Rust dans de nombreux cas. Mais il existe également des cas d'utilisation (larges) où les performances sont médiocres par rapport aux langues de bas niveau.

ou même le battre, mais cela signifie que vous utilisez un programme C inefficace, car GHC compile Haskell en C)

Ce n'est pas tout à fait exact. Haskell compile en C-- (un sous-ensemble de C), qui est ensuite compilé via le générateur de code natif vers l'assembly. Le générateur de code natif génère généralement du code plus rapide que le compilateur C, car il peut appliquer certaines optimisations qu'un compilateur C ordinaire ne peut pas.

Les architectures de machines sont clairement impératives, étant basées sur des machines de turing, à peu près.

Ce n'est pas une bonne façon d'y penser, d'autant plus que les processeurs modernes évalueront les instructions dans le désordre et éventuellement en même temps.

En effet, Haskell n'a même pas d'ordre d'évaluation spécifique.

En fait, Haskell ne définit implicitement un ordre d'évaluation.

De plus, au lieu de traiter des types de données machine, vous créez tout le temps des types de données algébriques.

Ils correspondent dans de nombreux cas, à condition d'avoir un compilateur suffisamment avancé.

On pourrait penser que créer des fonctions à la volée et les lancer rendrait un programme plus lent.

Haskell est compilé et les fonctions d'ordre supérieur ne sont donc pas réellement créées à la volée.

il semble optimiser le code Haskell, vous devez le rendre plus élégant et abstrait, au lieu de plus comme une machine.

En général, rendre le code plus "semblable à une machine" est un moyen improductif d'obtenir de meilleures performances dans Haskell. Mais le rendre plus abstrait n'est pas toujours une bonne idée non plus. Ce qui est une bonne idée, c'est d'utiliser des structures de données et des fonctions communes qui ont été fortement optimisées (comme les listes chaînées).

f x = [x]et f = puresont exactement la même chose à Haskell, par exemple. Un bon compilateur ne donnerait pas de meilleures performances dans le premier cas.

Pourquoi Haskell (compilé avec GHC) est-il si rapide, compte tenu de sa nature abstraite et de ses différences avec les machines physiques?

La réponse courte est "car il a été conçu pour faire exactement cela." GHC utilise la g-machine sans étiquette sans rotation (STG). Vous pouvez lire un article à ce sujet ici (c'est assez complexe). GHC fait également beaucoup d'autres choses, telles que l'analyse de rigueur et l' évaluation optimiste .

La raison pour laquelle je dis que C et d'autres langages impératifs sont quelque peu similaires aux machines de Turing (mais pas dans la mesure où Haskell est similaire au calcul Lambda) est que dans un langage impératif, vous avez un nombre fini d'états (aka numéro de ligne), le long avec une bande (le ram), de telle sorte que l'état et la bande actuelle déterminent ce qu'il faut faire à la bande.

Le point de confusion est-il alors que la mutabilité devrait conduire à un code plus lent? La paresse de Haskell signifie en fait que la mutabilité n'a pas autant d'importance que vous le pensez, en plus d'être de haut niveau, le compilateur peut appliquer de nombreuses optimisations. Ainsi, la modification d'un enregistrement sur place sera rarement plus lente que dans une langue comme C.


la source
3

Pourquoi Haskell (GHC) est-il si rapide?

Quelque chose a dû changer radicalement depuis la dernière fois que j'ai mesuré les performances de Haskell. Par exemple:

Alors qu'est-ce qui a changé? Je remarque que ni la question ni aucune de ses réponses actuelles ne font référence à des repères vérifiables ou même à du code.

Une chose préférée pour les Haskellers est d'essayer d'obtenir moins de 5% de C

Avez-vous des références à des résultats vérifiables où quiconque a pu s'en approcher?

Jon Harrop
la source
6
Quelqu'un a-t-il répété trois fois le nom de Harrop devant un miroir?
Chuck Adams
2
pas 10x, mais quand même, toute cette entrée est du battage publicitaire et des tripes. GHC est en effet tout à fait capable de se rapprocher de C ou même de le surmonter parfois, en termes de vitesse, mais cela nécessite généralement un style de programmation de bas niveau assez complexe pas très différent de la programmation en C lui-même. malheureusement. plus le code est élevé, plus il est lent, généralement. fuites d'espace, types ADT pratiques mais peu performants ( algébriques , pas abstraits , comme c'était la promesse), etc., etc.
Will Ness
1
Je ne fais que publier ceci parce que je l'ai vu aujourd'hui chrispenner.ca/posts/wc . C'est une implémentation de l'utilitaire wc écrit en Haskell qui bat soi-disant la version c.
Garrison
3
@Garrison merci pour le lien . 80 lignes est ce que j'ai appelé «un style de programmation de bas niveau pas très différent de la programmation en C lui-même». . "le code de niveau supérieur", ce serait le "stupide" fmap (length &&& length . words &&& length . lines) readFile. Si c'était plus rapide que (ou même comparable à) C, le battage médiatique ici serait tout à fait justifié alors . Nous devons encore travailler dur pour la vitesse à Haskell comme en C, c'est le point.
Will Ness
2
A en juger par cette discussion sur Reddit reddit.com/r/programming/comments/dj4if3/… que le code Haskell est vraiment bogué (par exemple, les sauts de lignes commencent ou se terminent par un espace, les sauts sur à) et d'autres ne peuvent pas reproduire les résultats de performance revendiqués.
Jon Harrop