Al encontrar el último pero segundo elemento de una lista, ¿por qué usar `last` es el más rápido entre estos?

A continuación se muestran 3 funciones que encuentran el último pero segundo elemento en una lista. El que usa last . initparece mucho más rápido que el resto. Parece que no puedo entender por qué.

Para las pruebas, utilicé una lista de entrada de [1..100000000](100 millones). El último se ejecuta casi instantáneamente, mientras que los otros tardan varios segundos.

-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"

-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse

-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init

Al estudiar la velocidad y la optimización, es muy fácil obtener resultados tremendamente incorrectos . En particular, no puede decir realmente que una variante es más rápida que otra sin mencionar la versión del compilador y el modo de optimización de su configuración de evaluación comparativa. Incluso entonces, los procesadores modernos son tan sofisticados que cuentan con predictores de ramificación basados ​​en redes neuronales, sin mencionar todo tipo de cachés, por lo que, incluso con una configuración cuidadosa, los resultados de la evaluación comparativa serán borrosos.

Habiendo dicho eso...

El benchmarking es nuestro amigo.

criteriones un paquete que proporciona herramientas avanzadas de evaluación comparativa. Rápidamente redacté un punto de referencia como este:

module Main where

import Criterion
import Criterion.Main

-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"

-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse

-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init

butLast2 :: [a] -> a
butLast2 (x :     _ : [ ] ) = x
butLast2 (_ : xs@(_ : _ ) ) = butLast2 xs
butLast2 _ = error "List too short"

setupEnv = do
  let xs = [1 .. 10^7] :: [Int]
  return xs

benches xs =
  [ bench "slow?"   $ nf myButLast   xs
  , bench "decent?" $ nf myButLast'  xs
  , bench "fast?"   $ nf myButLast'' xs
  , bench "match2"  $ nf butLast2    xs
  ]

main = defaultMain
    [ env setupEnv $ \ xs -> bgroup "main" $ let bs = benches xs in bs ++ reverse bs ]

Como puede ver, agregué la variante que coincide explícitamente en dos elementos a la vez, pero de lo contrario es el mismo código literalmente. También ejecuto los puntos de referencia a la inversa, para tener en cuenta el sesgo debido al almacenamiento en caché. Entonces, ¡corramos y veamos!

% ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.6.5


% ghc -O2 -package criterion A.hs && ./A
benchmarking main/slow?
time                 54.83 ms   (54.75 ms .. 54.90 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 54.86 ms   (54.82 ms .. 54.93 ms)
std dev              94.77 μs   (54.95 μs .. 146.6 μs)

benchmarking main/decent?
time                 794.3 ms   (32.56 ms .. 1.293 s)
                     0.907 R²   (0.689 R² .. 1.000 R²)
mean                 617.2 ms   (422.7 ms .. 744.8 ms)
std dev              201.3 ms   (105.5 ms .. 283.3 ms)
variance introduced by outliers: 73% (severely inflated)

benchmarking main/fast?
time                 84.60 ms   (84.37 ms .. 84.95 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 84.46 ms   (84.25 ms .. 84.77 ms)
std dev              435.1 μs   (239.0 μs .. 681.4 μs)

benchmarking main/match2
time                 54.87 ms   (54.81 ms .. 54.95 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 54.85 ms   (54.81 ms .. 54.92 ms)
std dev              104.9 μs   (57.03 μs .. 178.7 μs)

benchmarking main/match2
time                 50.60 ms   (47.17 ms .. 53.01 ms)
                     0.993 R²   (0.981 R² .. 0.999 R²)
mean                 60.74 ms   (56.57 ms .. 67.03 ms)
std dev              9.362 ms   (6.074 ms .. 10.95 ms)
variance introduced by outliers: 56% (severely inflated)

benchmarking main/fast?
time                 69.38 ms   (56.64 ms .. 78.73 ms)
                     0.948 R²   (0.835 R² .. 0.994 R²)
mean                 108.2 ms   (92.40 ms .. 129.5 ms)
std dev              30.75 ms   (19.08 ms .. 37.64 ms)
variance introduced by outliers: 76% (severely inflated)

benchmarking main/decent?
time                 770.8 ms   (345.9 ms .. 1.004 s)
                     0.967 R²   (0.894 R² .. 1.000 R²)
mean                 593.4 ms   (422.8 ms .. 691.4 ms)
std dev              167.0 ms   (50.32 ms .. 226.1 ms)
variance introduced by outliers: 72% (severely inflated)

benchmarking main/slow?
time                 54.87 ms   (54.77 ms .. 55.00 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 54.95 ms   (54.88 ms .. 55.10 ms)
std dev              185.3 μs   (54.54 μs .. 251.8 μs)

¡Parece que nuestra versión "lenta" no es lenta en absoluto! Y las complejidades de la coincidencia de patrones no agregan nada. (Una ligera aceleración que vemos entre dos ejecuciones consecutivas de match2atribuyo a los efectos del almacenamiento en caché).

Hay una manera de obtener más datos "científicos" : podemos -ddump-simplver la forma en que el compilador ve nuestro código.

La inspección de estructuras intermedias es nuestra amiga.

"Core" es un lenguaje interno de GHC. Cada archivo fuente de Haskell se simplifica a Core antes de transformarse en el gráfico funcional final para que se ejecute el sistema de tiempo de ejecución. Si miramos esta etapa intermedia, nos dirá eso myButLasty butLast2son equivalentes. Hace falta mirar, ya que, en la etapa de cambio de nombre, todos nuestros identificadores agradables se destrozan al azar.

% for i in `seq 1 4`; do echo; cat A$i.hs; ghc -O2 -ddump-simpl A$i.hs > A$i.simpl; done

module A1 where

-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"

module A2 where

-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse

module A3 where

-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init

module A4 where

butLast2 :: [a] -> a
butLast2 (x :     _ : [ ] ) = x
butLast2 (_ : xs@(_ : _ ) ) = butLast2 xs
butLast2 _ = error "List too short"

% ./EditDistance.hs *.simpl
(("A1.simpl","A2.simpl"),3866)
(("A1.simpl","A3.simpl"),3794)
(("A2.simpl","A3.simpl"),663)
(("A1.simpl","A4.simpl"),607)
(("A2.simpl","A4.simpl"),4188)
(("A3.simpl","A4.simpl"),4113)

Parece que A1y A4son los más parecidos. Una inspección exhaustiva mostrará que, de hecho, el código se estructura A1y A4es idéntico. Eso A2y A3son similares también es razonable ya que ambos se definen como una composición de dos funciones.

Si va a examinar la coresalida extensamente, tiene sentido suministrar también indicadores como -dsuppress-module-prefixesy -dsuppress-uniques. Hacen que sea mucho más fácil de leer.

Una breve lista de nuestros enemigos también.

Entonces, ¿qué puede salir mal con la evaluación comparativa y la optimización?

• ghci, diseñado para el juego interactivo y la iteración rápida, compila la fuente de Haskell con un cierto sabor de código de bytes, en lugar del ejecutable final, y evita optimizaciones costosas a favor de una recarga más rápida.
• La creación de perfiles parece una buena herramienta para analizar el rendimiento de partes individuales de un programa complejo, pero puede destruir las optimizaciones del compilador tan mal que los resultados serán órdenes de magnitud fuera de la base.
  • Su salvaguarda es perfilar cada pequeño fragmento de código como un ejecutable separado, con su propio corredor de referencia.
• La recolección de basura es sintonizable. Justo hoy se lanzó una nueva característica importante. Los retrasos en la recolección de basura afectarán el rendimiento de formas que no son fáciles de predecir.
• Como mencioné, diferentes versiones del compilador crearán un código diferente con un rendimiento diferente, por lo que debe saber qué versión usará probablemente el usuario de su código para compilarlo, y compararlo con eso, antes de hacer cualquier promesa.

Esto puede parecer triste. Pero en realidad no es lo que debería preocupar a un programador de Haskell, la mayoría de las veces. Historia real: Tengo un amigo que recientemente comenzó a aprender Haskell. Habían escrito un programa para la integración numérica, y fue muy lento. Así que nos sentamos juntos y escribimos una descripción categorial del algoritmo, con diagramas y demás. Cuando reescribieron el código para alinearlo con la descripción abstracta, mágicamente se convirtió en guepardo rápido y delgado en memoria también. Calculamos π en poco tiempo. ¿Moraleja de la historia? Estructura abstracta perfecta, y su código se optimizará solo.