Stealing from Biologists to Compile Haskell Faster
ApplicativeDo est une fonctionnalité de GHC qui permet au compilateur de transformer la notation do en combinaisons applicatives pour détecter l'indépendance entre opérations et réduire la latence, mais l'algorithme optimal était désactivé par défaut car trop lent en pratique. Le cœur du problème est de déterminer les dépendances entre instructions et de regrouper celles qui peuvent s'exécuter en parallèle ; l'algorithme glouton est rapide mais sous‑optimal, tandis que l'optimal trouve le meilleur ordonnancement au prix d'une complexité O(n³). La transformation se modèle par un arbre ordonné (feuille, séquence, parallèle) dont le coût en rounds se minimise par une récurrence qui, naïvement, cherche tous les points de coupure et induit la cubique. En combinant l'astuce des coupures extrêmes avec une borne fournie par la plus longue chaîne dans les cas d'égalité, on élimine la majeure partie des recherches inutiles et l'on obtient des temps pratiques proches de O(n²) pour des blocs réalistes, même si des cas denses persistent. Le problème est analogue à la prédiction de repliement de l'ARN et admet des algorithmes sub‑cubiques théoriques via des produits min‑plus bornés, mais leurs constantes sont impraticables, si bien que GHC préfère des optimisations modestes mais efficaces en pratique.