Menu Close

Comparación de 3 implementaciones de Common Lisp (Clisp, GCL y SBCL) mediante la función de Takeuchi

En artículos anteriores comentamos la función de Takeuchi como prueba de rendimiento y la usamos para la comparación del rendimiento de Haskell, Maxima y Common Lisp.

En este artículo voy a usar una variación de la prueba anterior para comparar tres implementaciones de Common Lisp: Clisp, GCL (GNU Common Lisp) y SBCL (Steel Bank Common Lisp).

La función de Takeuchi es
tak(x,y,z) = \newline     \left\{     \begin{array}{ll}       y, & \mathrm{si} \ x \leq y \\       \mathrm{tak}(\mathrm{tak}(x-1,y,z),                    \mathrm{tak}(y-1,z,x),                    \mathrm{tak}(z-1,x,y)) & \mathrm{en\ caso\ contrario}     \end{array}     \right.

La prueba consistirá en comparar los tiempos empleados en calcular tak(n,0,n+1) para n entre 10 y 15.

El fichero con las definiciones Lisp utilizado es

#+excl
(eval-when (compile) (setq comp::register-use-threshold 6))
 
(defun tak (x y z)
  (declare (fixnum x y z))
  (if (<= x y)
      y
      (tak (tak (- x 1) y z)
           (tak (- y 1) z x)
           (tak (- z 1) x y))))
 
(defun takeuchi (n) 
  (tak n 0 (1+ n)))

Todo los cálculos se han realizado en un ordenador con Ubuntu versión 10.04, núcleo linux 2.6.32-24-generic, 2,0 GiB de memoria y un procesador Intel(R) Atom(TM) CPU N280 @ 1.66GHz.

Los resultados se resumen en la siguiente tabla donde la primera columna se indica el valor de n y en las restantes los segundos empleados en el cálculo de takeuchi(n).
\begin{array}{|l|r|r|r|r|} \hline  n  & Clisp   & GCL     & SBCL    & GHC  \\ \hline  10 &    1.23 &    0.96 &    0.16 & 0.00 \\ \hline  11 &    8.02 &    6.19 &    0.99 & 0.00 \\ \hline  12 &   56.04 &   43.43 &    7.05 & 0.00 \\ \hline  13 &  418.62 &  314.01 &   50.95 & 0.00 \\ \hline  14 & 3441.37 & 2408.87 &  502.51 & 0.00 \\ \hline  15 &         &         & 2300.01 & 0.00 \\ \hline  \end{array}

En la última columna he escrito los tiempos empleados por GHC (The Glasgow Haskell Compiler) en calcular (takeuchi n) usando la siguiente definición

tak :: Int -> Int -> Int -> Int
tak x y z
    | x <= y    = y
    | otherwise = tak (tak (x-1) y z)
                      (tak (y-1) z x)
                      (tak (z-1) x y)
 
takeuchi :: Int -> Int
takeuchi n = tak n 0 (n+1)

Del experimento se concluye que SBCL se comporta mucho mejor que Clisp y GCL, aunque no tanto como GHC.

Haskell, Lisp, Rendimiento