Haskell Fibonacci: Tail-récursif plus lent que l'approche de liste paresseux classique?

Question

Avis de non-responsabilité: certains Haskell peut-être douteux.

J'ai mis en 2 versions de Fibonacci, qui est linéaire et récursive (une variante claqua incl.), Et un autre en utilisant l'approche de la liste paresseuse classique:

{-# LANGUAGE BangPatterns #-} 

-- Linear 
fibLinear :: Int -> Integer 
fibLinear 0 = 0 
fibLinear 1 = 1 
fibLinear x = fibLin' 2 1 2 
    where 
     fibLin' i y z | i == x = y 
     fibLin' i y z   = fibLin' (i+1) z (z+y) 

-- Linear banged 
fibLinearBang :: Int -> Integer 
fibLinearBang 0 = 0 
fibLinearBang 1 = 1 
fibLinearBang x = fibLin' 2 1 2 
    where 
     fibLin' (!i) (!y) (!z) | i == x = y 
     fibLin' (!i) (!y) (!z)   = fibLin' (i+1) z (z+y) 

-- Haskeller classic lazy 
fibClassic :: Int -> Integer 
fibClassic n = fib' !! n 
    where fib' = 0:1:zipWith (+) fib' (tail fib') 

Lorsque vous utilisez criterion à benchmark il (code), je reçois des résultats un peu intuitifs: Fib 30 prend 443,0 ns pour fibLinear et 279,5 ns pour fibLinearBang, contre 73,51 ns pour fibClassic. C'est étrange parce que je pense que fibLinear & fibLinearBang pourrait être optimisé en quelque chose comme une boucle ou un saut.

Ma seule estimation est peut-être fib' dans fibClassic est memoised comme une liste constante malgré être dans une définition de fonction afin que les invocations ultérieures de la fonction réutiliser la même liste pour la recherche. Est-ce que quelqu'un peut me donner une explication définitive pour mes résultats de référence?

Pour ceux qui sont intéressés, j'ai mis le projet sur Github.

Answer 1

tl; dr: fib' a en effet été réutilisé dans des invocations

Merci aux commentateurs, je l'ai appris que full-laziness est pas (seulement) un terme utilisé pour décrire la façon dont Haskell évalue, mais une optimisation du compilateur réel terme, qui est activée par défaut, mais peut être désactivé (en utilisant le drapeau -fno-full-laziness GHC-options

Relancement les points de repère avec ce drapeau, nous voyons les tables ont tourné.

• fibLinearBang 259,8 ns
• fibClassic 738,4 ns

Cette performance, ainsi this guide on GHC compiler options est une preuve assez convaincante que fib' ne se transforment en quelque chose comme une référence de niveau supérieur qui est réutilisé (et d'être une liste, memoised) à travers différentes invocations de la méthode. Ce guide et le paper it links to describing let-lifting admettent que let-lifting pourrait résulter en une augmentation de la mémoire résidentielle, ce qui pour moi est plutôt effrayant (n'écrivez pas un fib-as-a-service en utilisant fibClassic et exposez-le à Internet. .), mais je pourrais venir à lui ..