Question Avantages des compilateurs pour les langages fonctionnels sur les compilateurs pour les langages impératifs


Suite à cette question Quels sont les avantages de l'immuabilité intégrée de F # sur C #?- Ai-je raison de supposer que le compilateur F # peut faire certaines optimisations en sachant qu'il s'agit d'un code largement immuable? Je veux dire, même si un développeur écrit "Functional C #", le compilateur ne connaîtrait pas toute l'immuabilité que le développeur avait essayé de coder pour qu'il ne puisse pas faire les mêmes optimisations, n'est-ce pas?

En général, le compilateur d'un langage fonctionnel serait-il capable de faire des optimisations qui ne seraient pas possibles avec un langage impératif - même avec un langage aussi immuable que possible?


12
2018-02-06 01:40


origine


Réponses:


Je dirais en grande partie «non».

Les principaux avantages de l’optimisation ou de la transparence du référentiel sont, par exemple, la possibilité de procéder à une «élimination de sous-expression commune» lorsque vous voyez du code comme ...f(x)...f(x).... Mais une telle analyse est difficile à faire sans informations très précises, et puisque F # s'exécute sur le runtime .Net et que .Net n'a aucun moyen de marquer les méthodes comme étant pures (sans effet), il faut une tonne d'informations et d'analyses intégrées. essayez même de faire tout cela.

D'un autre côté, dans un langage comme Haskell (qui signifie principalement "Haskell", car il y a peu de langages comme Haskell "que tout le monde a entendu ou utilise :)) qui est paresseux et pur, l'analyse est plus simple (tout est pur, allez les noix).

Cela dit, de telles «optimisations» peuvent souvent interagir mal avec d'autres aspects utiles du système (prévisibilité des performances, débogage, ...).

Il y a souvent des histoires de "un compilateur suffisamment intelligent pourrait faire X", mais mon opinion est que le "compilateur suffisamment intelligent" est et sera toujours un mythe. Si vous voulez un code rapide, écrivez un code rapide; le compilateur ne va pas vous sauver. Si vous souhaitez éliminer la sous-expression commune, créez une variable locale (faites-le vous-même).

C'est surtout mon opinion, et nous vous invitons à la déprécier ou à la désapprouver (en effet, j'ai entendu dire que le «multicœur» était une raison croissante pour laquelle «l'optimisation pourrait redevenir sexy», ce qui semble plausible). Mais si vous espérez toujours qu'un compilateur effectue une optimisation non triviale (qui n'est pas prise en charge par les annotations dans le code source), préparez-vous à attendre longtemps avant que vos espoirs soient satisfaits.

Ne vous méprenez pas - l'immuabilité est bonne et est susceptible de vous aider à écrire du code «rapide» dans de nombreuses situations. Mais pas parce que le compilateur l’optimise - plutôt parce que le code est facile à écrire, à déboguer, à corriger, à paralléliser, à profiler et à décider quels sont les goulots d’étranglement les plus importants (les réécrivant mutuellement). Si vous souhaitez un code efficace, utilisez un processus de développement vous permettant de développer, tester et profiler rapidement.


2
2018-02-06 02:53



Ai-je raison de supposer que le compilateur F # peut assurer   optimisations sachant qu'il s'agit de code largement immuable?

Malheureusement non. Pour un auteur de compilateurs, il existe une énorme différence entre "largement immuable" et "immuable". Même une immuabilité garantie n'est pas très importante pour l'optimiseur. la principale chose qu'il vous achète est que vous pouvez écrire un inliner très agressif.

En général, le compilateur d'un langage fonctionnel serait-il capable de faire des optimisations qui ne seraient pas possibles avec un langage impératif - même avec un langage aussi immuable que possible?

Oui, mais c'est surtout une question de pouvoir appliquer plus facilement les optimisations classiques, dans plus d'endroits. Par exemple, l'immuabilité rend beaucoup plus facile à appliquer élimination de sous-expression commune car l'immuabilité peut vous garantir que le contenu de certaines cellules mémoire n'est pas modifié.

Par contre, si votre langage fonctionnel n'est pas seulement immuable mais pur (pas d’effets secondaires tels que les E / S), vous activez ensuite une nouvelle classe d’optimisations impliquant la réécriture d’expressions de niveau source en expressions plus efficaces. L’un des plus importants et des plus intéressants à lire est déboisement raccourci, ce qui évite d'allouer de l'espace mémoire pour des résultats intermédiaires. Un bon exemple à lire est fusion de flux.

Si vous compilez un langage fonctionnel de type statique pour des performances élevées, voici quelques points principaux:

  • Utilisez la mémoire efficacement. Lorsque vous le pouvez, travaillez avec des valeurs "non encapsulées", en évitant l'allocation et un niveau supplémentaire d'indirection vers le tas. La fusion de flux en particulier et d'autres techniques de déforestation sont toutes très efficaces car elles éliminent les allocations.

  • Avoir un allocateur ultra-rapide et amortir les vérifications de l'épuisement du tas sur plusieurs allocations.

  • Inline fonctionne efficacement. En particulier, les petites fonctions intégrées au-delà des limites des modules.

  • Représenter efficacement les fonctions de première classe, généralement par la conversion de la fermeture. Manipuler fonctions partiellement appliquées efficacement.

  • Ne négligez pas les optimisations classiques des scalaires et des boucles. Ils ont fait une énorme différence pour les compilateurs tels que TIL et Objective Caml.

Si vous avez un langage fonctionnel paresseux comme Haskell ou Clean, il y a aussi beaucoup de choses spécialisées à faire avec les thunks.


Notes de bas de page:

  • Une option intéressante que vous obtenez avec une immuabilité totale est une plus grande capacité à exécuter un parallélisme très fin. La fin de cette histoire n'a pas encore été racontée.

  • Ecrire un bon compilateur pour F # est plus difficile que d’écrire un compilateur typique (s’il ya une telle chose) car F # est trop contraint: il doit bien faire les choses fonctionnelles, mais il doit aussi fonctionner efficacement dans le framework .NET, qui était pas conçu avec des langages fonctionnels à l'esprit. Nous devons à Don Syme et à son équipe de faire un excellent travail pour résoudre un problème très difficile.


20
2018-02-06 01:14



Non.

Le compilateur F # n'essaie pas d'analyser la transparence référentielle d'une méthode ou d'un lambda. Le .NET BCL n'est tout simplement pas conçu pour cela.

La spécification du langage F # réserve le mot-clé 'pure', ainsi il est possible de marquer manuellement une méthode comme étant pure dans vNext, ce qui permet une réduction plus agressive des expressions lambda.

Cependant, si vous utilisez les types enregistrement ou algébrique, F # créera des opérateurs de comparaison et d'égalité par défaut et fournira une sémantique de copie. Parmi de nombreux autres avantages (appariement de modèles, hypothèse de monde fermé), cela réduit un fardeau important!


7
2018-02-06 00:57



Oui, si vous ne considérez pas F #, mais considérez Haskell par exemple. Le fait qu'il n'y ait pas d'effets secondaires ouvre beaucoup de possibilités d'optimisation.

Par exemple, considérez dans un langage C comme:

int factorial(int n) {
    if (n <= 0) return 1;
    return n* factorial(n-1);
}

int factorialuser(int m) {
    return factorial(m) * factorial(m);
}

Si une méthode correspondante était écrite en Haskell, il y aurait pas de second appel à factoriel lorsque vous appelez factorialuser. Il est possible de le faire en C #, mais je doute que les compilateurs actuels le fassent, même pour un exemple simple comme celui-ci. Au fur et à mesure que les choses se compliquent, il serait difficile pour les compilateurs C # d'optimiser le niveau d'action d'Haskell.

Notez que F # n'est pas vraiment un langage fonctionnel "pur", actuellement. Donc, j'ai amené Haskell (ce qui est génial!).


5
2018-02-06 01:26



Malheureusement, parce que F # est uniquement pur, il n’ya pas vraiment beaucoup d’optimisations agressives. En fait, il existe des endroits où F # "pessimise" le code par rapport à C # (par exemple en faisant des copies défensives de structures pour empêcher des mutations observables). En revanche, le compilateur fait du bon travail, malgré tout, en fournissant des performances comparables à C # dans la plupart des endroits, tout en rendant les programmes plus faciles à raisonner.


3
2018-02-06 01:29



Des optimisations supplémentaires pour les langages fonctionnels sont parfois possibles, mais pas nécessairement en raison de leur immuabilité. En interne, de nombreux compilateurs convertissent le code en un formulaire SSA (Single static assignating), où chaque variable locale d'une fonction ne peut être affectée qu'une seule fois. Cela peut être fait à la fois pour les langages impératifs et fonctionnels. Par exemple:

x := x + 1
y := x + 4

peut devenir

x_1 := x_0 + 1
y := x_1 + 4

x_0 et x_1 sont des noms de variables différents. Cela simplifie énormément de nombreuses transformations, car vous pouvez déplacer des parties de code sans vous soucier de la valeur qu'elles ont à des points spécifiques du programme. Cela ne fonctionne pas pour les valeurs stockées dans la mémoire (par exemple, globales, valeurs de segment de mémoire, tableaux, etc.). Encore une fois, cela est fait pour les deux langages fonctionnels et impératifs.

Un des avantages que procurent les langages fonctionnels est un système de type fort. Cela permet au compilateur de faire des suppositions qu'il ne pourrait pas faire autrement. Par exemple, si vous avez deux références de types différents, le compilateur sait qu'ils ne peuvent pas créer d'alias (pointez sur la même chose). Ce n'est pas une hypothèse qu'un compilateur C pourrait jamais faire.


2