Pourquoi Haskell (GHC) est-il si vachement rapide?

Question

Haskell (avec l' GHC compilateur) est beaucoup plus rapide que ce que vous attendez. Utilisé correctement, il peut faire fermer-ish à de faibles niveaux de langues. (Une chose préférée pour Haskellers à faire est d'essayer de l'obtenir dans un délai de 5% de C (ou même de le battre, mais cela signifie que vous êtes en utilisant de l'inefficacité d'un programme C, depuis GHC compile Haskell à C).) Ma question est, pourquoi?

Haskell est déclarative et basé sur le lambda calcul. Architectures de machines sont clairement impératif, étant basée sur des machines de turing, à peu près. En effet, Haskell ne dispose même pas d'une évaluation spécifique de l'ordre. Aussi, au lieu de traiter avec la machine de types de données, vous faites des types de données algébriques tout le temps.

Plus étrange de tous est bien des fonctions d'ordre supérieur. On pourrait penser que la création des fonctions à la volée, et de les jeter autour, serait de faire un programme plus lent. Mais en utilisant des fonctions d'ordre supérieur permet effectivement Haskell plus rapide. En effet, il semble pour optimiser le code Haskell, vous avez besoin pour le rendre plus élégant et abstraite, au lieu de plus de machine comme. Aucun de Haskell fonctionnalités plus avancées semblent à même d'affecter ses performances, si ce n'est pas de l'améliorer.

Désolé si cela sonne alias ranty, mais voici ma question: Pourquoi est-Haskell (compilé avec GHC) si rapide, compte tenu de son caractère abstrait et les différences de machines physiques?

Note: La raison pour laquelle je dis C et autres langages sont assez semblables à des Machines de Turing (mais pas au point que Haskell est similaire à Lambda Calcul), c'est que dans un langage impératif, vous disposez d'un nombre fini d'états (un.k.un. numéro de ligne), avec une Bande (la ram), tels que l'état et la bande de déterminer quoi faire de la bande. Voir l'article de Wikipédia, machine de Turing équivalents, pour le passage des Machines de Turing pour les ordinateurs.

Answer 1

Je pense que c'est un peu l'opinion. Mais je vais tenter de répondre.

Je suis d'accord avec Dietrich Ppe: c'est une combinaison de plusieurs choses qui font de 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 un SELECT relevé, cela peut ressembler à un impératif de la boucle, mais il n'est pas. Il pourrait ressembler , il passe en boucle sur toutes les lignes de la table en essayant de trouver celui qui correspond aux conditions spécifiées, mais en fait le "compilateur" (le moteur DB) pourrait être en train de faire une recherche d'index au lieu — qui a complètement différentes caractéristiques de performance. Mais parce que SQL est donc de haut niveau, le "compilateur" peut se substituer totalement différents algorithmes, appliquer plusieurs processeurs ou de canaux d'e/S ou d'un ensemble de serveurs de manière transparente, et plus encore.

Je pense que de Haskell comme étant le même. Vous pourriez penser que vous venez de lui demander Haskell à la carte la liste d'entrée pour une deuxième liste, filtre de la deuxième liste dans une troisième liste, puis de compter le nombre d'éléments qui en a résulté. Mais vous n'avez pas voir GHC appliquer stream-fusion des règles de réécriture dans les coulisses, transformant le tout en une seule serré du code machine de la boucle qui fait tout le travail en une seule passe sur les données avec aucune allocation — le genre de chose qui serait fastidieux, source d'erreurs et de non-maintenable d'écrire à la main. C'est vraiment possible en raison de l'absence de détails de bas niveau dans le code.

Une autre façon de voir les choses peut-être... pourquoi ne pas Haskell être rapide? Qu'est-ce cela qui doit être lent?

Ce n'est pas un langage interprété comme Perl ou JavaScript. Il n'est même pas un système de la machine virtuelle comme le Java ou le C#. Il compile tout le chemin vers du code machine natif, donc pas de frais généraux.

Contrairement aux langages à objets [Java, C#, JavaScript...], Haskell a plein de type d'effacement [comme en C, C++, Pascal...]. Tous type de vérification qui se passe au moment de la compilation. Donc il n'y a aucun moment de l'exécution de la vérification de type à vous ralentir. (Pas de pointeur null vérifie, pour cette question. Dans, par exemple, Java, la JVM doit vérifier les pointeurs nuls et de lever une exception si vous déférence. Haskell n'a pas à s'embêter avec cette case.)

Vous dites que c'sons lents à "créer des fonctions à la volée au moment de l'exécution", mais si vous regardez attentivement, vous, vous n'avez pas réellement le faire. Il pourrait ressembler à vous le faites, mais vous n'avez pas. 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. Il n'est donc pas vraiment une fonction dynamique. Même des fonctions curryfiées sont vraiment juste sauvegarde des paramètres dans un bloc de données. Tous les code exécutable existe réellement au moment de la compilation; il n'est pas au moment de l'exécution de l'interprétation. (Contrairement à certains autres langues qui ont une "fonction eval".)

Penser à Pascal. Il est vieux et que personne ne l'utilise plus, mais personne ne s'en plaindrait que Pascal est lente. Il y a beaucoup de choses à détester à ce sujet, mais la lenteur n'est pas vraiment un d'entre eux. Haskell n'est pas vraiment faire grand chose de différent de Pascal, que la collecte des ordures plutôt que manuel de gestion de la mémoire. Et immuables de données permet à plusieurs optimisations pour le moteur GC [qui lazy evaluation ensuite complique un peu].

Je pense que le truc, c'est que Haskell semble avancées et sophistiquées et de haut niveau, et tout le monde pense "oh wow, c'est vraiment puissant, il doit être incroyablement lent!" Mais il n'est pas. Ou au moins, elle n'est pas dans la façon dont vous le souhaitez. Oui, il a un incroyable système de type. Mais vous savez quoi? Tout ce qui se passe au moment de la compilation. Par moment, il a disparu. Oui, il permet de construire compliqué ADTs avec une ligne de code. Mais vous savez quoi? L'ADT est juste un ordinaire C union de structs. Rien de plus.

Le véritable assassin est paresseux évaluation. Lorsque vous obtenez la rigueur / paresse de votre code droit, vous pouvez écrire bêtement rapide code qui est toujours belle et élégante. Mais si vous obtenez ce genre de choses de mal, votre programme va des milliers de fois plus lent, et il est vraiment non-évident pourquoi ce qui se passe.

Par exemple, j'ai écrit un banal petit programme pour compter combien de fois chaque octet apparaît dans un fichier. Pour un 25 KO fichier d'entrée, le programme a pris 20 minutes pour exécuter et d'ingestion 6 gigaoctets de RAM! C'est absurde!! Mais ensuite j'ai réalisé que le problème a été, ajouté un seul bang-du motif et de la durée d'utilisation est tombé à 0.02 secondes.

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

Ce qui fait Haskell si vite? La pureté. Types statiques. La paresse. Mais par-dessus tout, être suffisamment haut niveau que le compilateur peut changer radicalement la mise en œuvre sans casser votre code attentes.

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

Answer 2

Pendant longtemps, on a pensé que les langages fonctionnels ne pouvait pas être rapide, et en particulier paresseux langages fonctionnels. Mais c'était parce que leurs premières mises en œuvre ont été, en substance, interprété et non pas véritablement compilé.

Une deuxième vague de dessins émergé sur le graphique de réduction, et ouvert la possibilité pour beaucoup plus efficace de la compilation. Simon Peyton Jones a écrit à propos de cette recherche dans ses deux livres de La mise en Œuvre de Langages de Programmation Fonctionnelle et la mise en Œuvre de langages fonctionnels: un tutoriel (l'ancienne avec des sections par Wadler et Hancock, et le dernier écrit avec David Lester). (Lennart Augustsson aussi m'a informé que la clé de la motivation pour le livre ancien a été de décrire la manière dont ses LML compilateur, qui n'a pas été beaucoup commenté, accompli sa compilation).

La notion clé derrière graphique de réduction des approches telles que décrites dans ces œuvres, c'est qu'on ne pense pas un programme comme une séquence d'instructions, mais d'un graphe de dépendance qui est évalué au travers d'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é , mais à la place du graphique lui-même peut être construit de code. En particulier, nous pouvons représenter un nœud d'un graphe non pas comme "une valeur ou un "opcode" et les valeurs à opérer", mais plutôt comme une fonction qui, lorsqu'il est invoqué, renvoie la valeur souhaitée. La première fois qu'il est invoqué, il demande à la sous-nœuds pour leurs valeurs et fonctionne alors sur eux, et puis il écrase lui-même avec une nouvelle instruction qui dit simplement: "renvoie le résultat."

Ceci est décrit plus tard dans un livre qui jette les bases pour combien de GHC fonctionne encore aujourd'hui (même si modulo de nombreuses modifications diverses): "la mise en Œuvre de Paresseux Langages Fonctionnels sur le Stock de Matériel: La Veules sans étiquette G-Machine.". L'actuel modèle d'exécution pour les GHC est décrite plus en détail à la GHC Wiki.

Donc, l'idée est que la stricte distinction de "données" et "code" que nous considérons comme "fondamental" à la façon dont les machines de travail n'est pas la façon dont ils doivent travailler, mais est imposé par nos compilateurs. Donc, nous pouvons jeter, et disposez d'un code (un compilateur qui génère self-modifying code (l'exécutable) et qu'il peut tout fonctionne très bien.

Ainsi, il s'avère que bien que la machine architectures sont impératives dans un certain sens, les langues peuvent correspondre entre eux de très surprenant, d'une manière qui ne ressemblent pas à des classiques de style C contrôle de flux, et si nous pensons à faible niveau assez, cela peut aussi être efficace.

Sur le dessus de cela, il existe de nombreuses autres optimisations ouvert par la pureté en particulier, cela permet une plus grande gamme de "coffre-fort" transformations. Quand et comment appliquer ces transformations telles qu'ils font les choses mieux et pas pire, c'est bien sûr une question empirique, et sur ce et de nombreux autres petits choix, des années de travail ont été mis en place à la fois théorique et pratique de l'analyse comparative. Alors bien sûr, cela joue un rôle. Un document qui fournit un bon exemple de ce type de recherche est "Rapide de Curry: appuyez sur/Enter vs Eval/demander de l'Ordre Supérieur des Langues."

Enfin, il convient de noter que ce modèle présente une surcharge due à des indirections. Ceci peut être évité dans le cas où nous savons qu'il est "sûr" pour faire des choses strictement et donc éluder graphique indirections. Les mécanismes qui en déduire la rigueur et de la demande sont encore documentées en détail le GHC Wiki.