Beneficio de evitar múltiples traversals de lista

Ejecutar unas cuantas instrucciones aritméticas adicionales en el cuerpo del bucle es más barato que ejecutar unas cuantas recuperaciones de memoria adicionales, básicamente.

Traversals significa hacer mucho acceso a la memoria, así que cuanto menos lo hagas, mejor. La fusión de traversals reduce el tráfico de memoria y aumenta la carga de cómputo en línea recta, por lo que obtiene un mejor rendimiento.

En concreto, considere este programa para calcular algunas matemáticas en una lista:

go :: [Int] -> [Int]
go = map (+2) . map (^3)

Claramente, lo diseñamos con dos traversals de la lista. Entre el primer y el segundo recorrido, un resultado se almacena en una estructura de datos intermedia. Sin embargo, es una estructura perezosa, por lo que solo cuesta O(1) memoria.

Ahora, el compilador de Haskell fusiona inmediatamente los dos bucles en:

go = map ((+2) . (^3))

¿Por qué es eso? Después de todo, ambos son O(n) complejidad, ¿verdad? La diferencia está en los factores constantes.

Considerando esta abstracción: para cada paso de la primera tubería hacemos:

  i <- read memory          -- cost M
  j = i ^ 3                 -- cost A
  write memory j            -- cost M
  k <- read memory          -- cost M
  l = k + 2                 -- cost A
  write memory l            -- cost M

Así que pagamos 4 accesos a memoria, y 2 operaciones aritméticas.

Para el resultado fusionado tenemos:

  i <- read memory          -- cost M
  j = (i ^ 3) + 2           -- cost 2A
  write memory j            -- cost M

Donde A y M son los factores constantes para hacer matemáticas en el acceso ALU y a la memoria.

También hay otros factores constantes (dos ramas de bucle) en lugar de uno.

Entonces, a menos que el acceso a la memoria sea libre (no lo es, por mucho tiempo), la segunda versión siempre es más rápida.

Tenga en cuenta que los compiladores que operan en secuencias inmutables pueden implementar la fusión de matrices, la transformación esto es para ti. GHC es un compilador.

Hay otra razón muy importante. Si recorre una lista solo una vez, y no tiene otra referencia a ella, el GC puede liberar la memoria reclamada por los elementos de la lista a medida que los atraviesa. Además, si la lista se genera perezosamente, siempre tiene solo un consumo de memoria constante. Por ejemplo

import Data.List

main = do
    let xs = [1..10000000]
        sum = foldl' (+) 0 xs
        len = foldl' (\_ -> (+ 1)) 0 xs
    print (sum / len)

Calcula sum, pero necesita mantener la referencia a xs y la memoria que ocupa no se puede liberar, porque es necesaria para calcular len más tarde. (O viceversa.) Tan el programa consume una cantidad considerable de memoria, cuanto mayor xs más memoria necesita.

Sin embargo, si recorremos la lista solo una vez, se crea perezosamente y los elementos pueden ser GC inmediatamente, por lo que no importa cuán grande sea la lista, el programa solo toma O(1) memoria.

{-# LANGUAGE BangPatterns #-}
import Data.List

main = do
    let xs = [1..10000000]
        (sum, len) = foldl' (\(!s,!l) x -> (s + x, l + 1)) (0, 0) xs
    print (sum / len)

Lo siento de antemano por una respuesta de estilo parlanchín.

Eso es probablemente obvio, pero si estamos hablando del rendimiento, siempre debe verificar las hipótesis midiendo.

Hace un par de años estaba pensando en la semántica operativa de GHC, la máquina STG. Y me hice la misma pregunta - seguramente los famosos algoritmos de "one-traversal" no son tan grandes? Solo parece un recorrido en la superficie, pero debajo del capó también tienes esta cadena de golpes estructura que suele ser bastante similar a la lista original.

Escribí algunas versiones (que varían en rigor) del famoso problema RepMin - dado un árbol lleno de números, generar el árbol de la misma forma, pero reemplazar cada número con el mínimo de todos los números. Si mi memoria es correcta (recuerde-siempre verifique las cosas usted mismo!), el algoritmo ingenuo de dos travesías se realizó mucho más rápido que varios algoritmos inteligentes de un solo recorrido.

También compartí mis observaciones con Simon Marlow (ambos estábamos en una escuela de verano de FP durante ese tiempo), y dijo que usan este enfoque en GHC. Pero no para mejorar el rendimiento, como podrías haber pensado. En cambio, dijo, para un gran AST (como el de Haskell) escribir todos los constructores toma mucho espacio (en términos de líneas de código), y así reducen la cantidad de código escribiendo solo un recorrido (sintáctico).

Personalmente evito este truco porque si cometes un error, obtienes un bucle que es una cosa muy desagradable para depurar.