performance - ¿Cuándo evaluar estrictamente en Haskell?

optimization lazy-evaluation

Question

¡Hasta donde yo sé ! (llamado bangs) se utilizan para indicar que una expresión debe evaluarse estrictamente. Pero no es tan obvio para mí dónde ponerlos o en absoluto.

import qualified Data.Vector.Unboxed as V

main :: IO ()
main = print $ mean (V.enumFromTo 1 (10^9))

mean :: V.Vector Double -> Double

Las diferentes versiones de mean:

-- compiled with O2 ~ 1.14s
mean xs = acc / fromIntegral len
    where !(len, acc)    = V.foldl'' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

-- compiled with O2 ~ 1.18s
mean xs = acc / fromIntegral len
    where (!len, !acc)   = V.foldl'' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

-- compiled with O2 ~ 1.75s
mean xs = acc / fromIntegral len
    where (len, acc)      = V.foldl'' f (0,0) xs :: (Int, Double)
          f !(len, acc) x = (len+1, acc+x)

-- compiled with O2 ~ 1.75s
mean xs = acc / fromIntegral len
    where (len, acc)      = V.foldl'' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

-- compiled without options ~ 6s
mean xs = acc / fromIntegral len
    where (len, acc)     = V.foldl'' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

-- compiled without options ~ 12s
mean xs = acc / fromIntegral len
    where !(len, acc)    = V.foldl'' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

Algo de esto tiene sentido de forma intuitiva, pero me gustaría que fuera menos un enfoque de prueba y error.

• ¿Hay alguna manera de detectar cuándo la evaluación perezosa se interpondrá en el camino del rendimiento? Aparte de probar cada riguroso.

• ¿Tiene sentido solo para funciones simples como mean donde todo debe ser evaluado de una vez?

Answer 1

No está escrito en piedra, pero la mejor práctica actual es hacer estrictos todos los campos de las estructuras de datos, pero tomar argumentos de funciones y devolver los resultados de forma perezosa (excepto los acumuladores).

El efecto neto es que siempre que no toque un valor de retorno, no se evalúa nada. Tan pronto como usted estrictamente necesita un poco de él, toda la estructura se evalúa de una vez, lo que lleva a patrones de uso de memoria / CPU más predecibles que si se evaluaran de forma holgazana durante la ejecución.

Las pautas de rendimiento de Johan Tibell son las mejores para señalar sutilezas: http://johantibell.com/files/haskell-performance-patterns.html#(1) . Tenga en cuenta que los GHC recientes realizan un pequeño desempaquetado de campo estricto automáticamente sin la necesidad de realizar anotaciones. También vea los pragmas estrictos .

Acerca de cuándo introducir los campos estrictos: hágalo desde el principio, ya que es mucho más difícil atornillarlo retrospectivamente. Aún puede usar campos vagos, pero solo cuando los desee explícitamente.

Nota: [] es flojo, y se usa más como una estructura de control que se espera que esté en línea, que como un contenedor. Utiliza vector etc. para este último.

Nota 2: existen libs especializados que le permiten lidiar con plegados estrictos (consulte foldl ) o con cómputos de transmisión ( conductos , tuberías ).

Actualizar

Un poco de elaboración sobre el fundamento, para que 1) usted sepa que esto no es solo para el pato de goma del cielo 2) sepa cuándo / por qué desviarse.

¿Por qué evaluar estricto?

Un caso es la acumulación estricta , como se indica en la pregunta. Esto también se presenta en formas menos obvias, como llevar la cuenta de ciertos eventos en el estado de la aplicación. Si no almacena un recuento estricto, puede obtener una larga cadena de acumulaciones de +1 thunks, que consume mucha memoria sin un buen motivo (en comparación con el recuento actualizado).

Más arriba se denomina memory leak manera informal, incluso si técnicamente no es una fuga (no se pierde memoria, simplemente se mantiene más tiempo de lo necesario).

Otro caso es el cómputo simultáneo , en el que el trabajo se divide entre múltiples hilos. Ahora, es fácil encontrarse con situaciones en las que cree que dividió un cálculo en un hilo separado (haciendo que su programa sea muy eficiente), para luego darse cuenta de que el hilo concurrente solo computa la capa más externa de una estructura de datos perezosa, y la mayor parte del cálculo aún ocurre en su hilo principal cuando el valor es forzado.

Una ruta de solución para esto es usar NFData de deepseq . Pero imagínese tener una estructura de datos final en capas A (B (C)) , donde cada capa se calcula mediante una hebra separada, forzando profundamente la estructura antes de regresar. Ahora C es profundamente forzado (en efecto atravesado en la memoria) tres veces, B dos veces. Si C es una estructura profunda / grande, esto es un desperdicio. En este punto, puede agregar el truco Once o simplemente usar una estructura de datos estrictamente estricta, donde hacer un forzado poco profundo con WHNF (en lugar de hacerlo con NF profunda) tiene el mismo efecto de forzamiento profundo, pero el truco Once es cuidado por el compilador, por así decirlo.

Ahora, si eres coherente y consciente, es posible que estés bien con deepseq + Once.

Nota: un caso de uso muy similar a la evaluación simultánea es la evaluación de un único subproceso en el caso aterrador de errores puros , como undefined y error . Idealmente, estos no se usan, pero si lo son, las formas de atacar el problema son muy similares a las descritas anteriormente (vea por cierto el paquete de cucharas ).

Answer 2

En sus ejemplos, los patrones de bang se están moviendo alrededor del cálculo final del promedio, o más bien sus ingredientes:

where (!len, !acc)   = V.foldl'' f (0,0) xs :: (Int, Double)
where !(len, acc)   = V.foldl'' f (0,0) xs :: (Int, Double)

pero (con una aparente excepción) no es el segundo elemento, la función de plegado en sí:

       f (len, acc) x = (len+1, acc+x)

Pero este f es donde está la acción. En sus ejemplos, las diferentes formas en que anota (len,acc) parecen estar provocando que el compilador adopte vistas sutilmente diferentes de qué hacer con f . Es por eso que todo parece un poco oculto. Lo que hay que hacer es lidiar con f directamente.

El principal punto de pan y mantequilla es que en un doblez izquierdo o un bucle de acumulación, todo el material acumulado debe evaluarse estrictamente . De lo contrario, básicamente estás construyendo una gran expresión con foldl'' y luego pidiendo que se colapsen cuando finalmente hagas algo con el material que acumulaste aquí, con el cálculo final de la media.

Sin embargo, en sus ejemplos, a foldl'' nunca se le da una función explícitamente estricta con la que se puede plegar: la acumulación len y acc quedan atrapadas dentro de una tupla Haskell floja normal.

El problema de la rigurosidad surge aquí porque estás acumulando más de una cosa, pero necesitas unirlas en un argumento para la operación f que estás pasando a foldl'' . Este es un caso típico para escribir un tipo o registro estricto para hacer la acumulación; esto toma una línea corta

data P = P !Int !Double

entonces puedes escribir

mean0 xs = acc / fromIntegral len
    where P len acc    = V.foldl'' f (P 0 0) xs 
          f (P len acc) !x = P (len+1) (acc+x)

Tenga en cuenta que no marque (P len acc) con un golpe ya que está visiblemente en forma normal de cabeza débil - se puede ver el P y no es necesario pedirle al compilador que lo encuentre con! / Seq - y así f es estricto en el primer argumento. Lo mismo es cierto en el caso en que agregas rigor a f

          f !(len, acc) x = (len+1, acc+x)

Pero la función

          f (len, acc) x = (len+1, acc+x)

ya era estricto en el primer argumento, el par, ya que puedes ver el constructor más externo (,) y no necesitas una anotación de rigor (que básicamente le dice al compilador que la busque). Pero el constructor solo construye una tupla perezosa así que no fue (explícitamente) estricto en len y acc

$ time ./foldstrict
5.00000000067109e8
real    0m1.495s

mientras que en mi máquina tu mejor media es:

$ time ./foldstrict
5.00000000067109e8
real    0m1.963s