haskell - Orden de evaluación siempre garantizada de `seq`(con un comportamiento extraño de` pseq` además)

lazy-evaluation ghc

Question

La documentación de la función seq dice lo siguiente:

Una nota sobre el orden de evaluación: la expresión seq ab no garantiza que a se evaluará antes que b . La única garantía dada por seq es que tanto a como b serán evaluados antes de que seq devuelva un valor. En particular, esto significa que b puede ser evaluado antes de a . Si necesita garantizar un orden específico de evaluación, debe usar la función pseq del paquete "paralelo".

Así que tengo una versión perezosa de la función de sum con acumulador:

sum :: Num a => [a] -> a
sum = go 0
where
go acc [] = acc
go acc (x:xs) = go (x + acc) xs

Obviamente, esto es extremadamente lento en las grandes listas. Ahora estoy reescribiendo esta función usando seq :

sum :: Num a => [a] -> a
sum = go 0
where
go acc [] = acc
go acc (x:xs) = let acc'' = x + acc
in acc'' `seq` go acc'' xs

¡Y veo un gran aumento de rendimiento! Pero me pregunto qué tan confiable es? ¿Lo conseguí por suerte? Porque GHC puede evaluar la llamada recursiva primero (según la documentación) y aún así acumular thunks. Parece que necesito usar pseq para asegurar que siempre se evalúa acc'' antes de la llamada recursiva. Pero con pseq veo una disminución en el rendimiento en comparación con la versión seq . Números en mi máquina (para calcular la sum [1 .. 10^7] :

• naive: 2.6s
• seq : 0.2s
• pseq : 0.5s

Estoy usando GHC-8.2.2 y compilo con el stack ghc -- File.hs

Después de que traté de compilar con la stack ghc -- -O File.hs rendimiento del comando de la brecha entre seq y pseq se ha ido. Ahora ambos se ejecutan en 0.2s .

Entonces, ¿mi implementación muestra las propiedades que quiero? ¿O tiene GHC alguna peculiaridad de implementación? ¿Por qué es pseq más lento? ¿Existe algún ejemplo en el que seq ab tenga diferentes resultados dependiendo del orden de evaluación (el mismo código pero diferentes indicadores de compilación / diferentes compiladores / etc.)?

Answer 1

Hasta ahora, las respuestas se han centrado en los problemas de rendimiento seq versus pseq , pero creo que originalmente quería saber cuál de los dos debería usar.

La respuesta corta es: mientras que ambos deberían generar un código de ejecución casi idéntico en la práctica (al menos cuando se activan los indicadores de optimización adecuados), el seq primitivo, y no el pseq , es la opción correcta para su situación. El uso de pseq no es idiomático, confuso y potencialmente contraproducente desde el punto de vista del desempeño, y su razón para usarlo se basa en un entendimiento erróneo de lo que significa su garantía de orden de evaluación y lo que implica con respecto al desempeño. Si bien no hay garantías sobre el rendimiento en diferentes conjuntos de indicadores de compilación (y mucho menos en otros compiladores), si alguna vez se encuentra en una situación en la que la versión seq del código anterior se ejecuta mucho más lento que la versión pseq usa indicadores de optimización de "calidad de producción" con el compilador de GHC, debe considerarlo un error de GHC y presentar un informe de error.

La respuesta larga es, por supuesto, más larga.

Primero, seamos claros que seq y pseq son semánticamente idénticos en el sentido de que ambos satisfacen las ecuaciones:

seq _|_ b = _|_
seq a b = b -- if a is not _|_
pseq _|_ b = _|_
pseq a b = b -- if a is not _|_

Esto es realmente lo único que garantiza semánticamente, y dado que la definición del lenguaje Haskell (como se indica en el informe de Haskell dice) solo ofrece, en el mejor de los casos, garantías semánticas y no trata el desempeño o la implementación, hay no hay razón para elegir entre uno u otro por razones de rendimiento garantizado en diferentes compiladores o marcas de compilación.

Además, en su versión particular basada en seq de la sum funciones, no es demasiado difícil ver que no hay ninguna situación en la que se llame a seq con un primer argumento indefinido sino un segundo argumento definido (asumiendo el uso de un tipo numérico estándar) , por lo que ni siquiera estás usando las propiedades semánticas de seq . Puede volver a definir seq como seq ab = b y tener exactamente la misma semántica. Por supuesto, usted lo sabe, por eso su primera versión no usó seq . En su lugar, está usando seq para un efecto secundario de desempeño incidental, por lo que estamos fuera del ámbito de las garantías semánticas y regresamos al ámbito de las características específicas de implementación y desempeño del compilador de GHC (donde realmente no hay garantías para hablar). de).

En segundo lugar, eso nos lleva al propósito previsto de la seq . Rara vez se usa por sus propiedades semánticas porque esas propiedades no son muy útiles. ¿Quién querría que una computación seq ab devuelva b excepto que no debería terminar si alguna expresión no relacionada a no termina? (Las excepciones, sin juego de palabras, serían cosas como el manejo de excepciones, donde puede usar seq o deepSeq que se basa en seq para forzar la evaluación de una expresión sin terminación de forma incontrolada o controlada, antes de comenzar la evaluación de otra expresión.)

En cambio, seq ab está destinado a forzar la evaluación de a forma normal de cabeza débil antes de devolver el resultado de b para evitar la acumulación de troncos. La idea es que, si tiene una expresión b que construye un procesador que podría acumularse sobre otro procesador no evaluado representado por a , puede evitar esa acumulación utilizando seq ab . La "garantía" es débil: GHC garantiza que entiende que no desea que se mantenga como un valor no evaluado cuando se exige el valor de seq ab . Técnicamente, no garantiza que a sea ​​"evaluado antes" b , sea lo que sea lo que signifique, pero no necesita esa garantía. Cuando se preocupa de que, sin esta garantía, GHC podría evaluar primero la llamada recursiva y aún así acumular thunk, esto es tan ridículo como preocupante de que pseq ab evalúe su primer argumento, luego espere 15 minutos (solo para estar absolutamente seguro de que el primer argumento tiene sido evaluado!), antes de evaluar su segundo.

Esta es una situación en la que debe confiar en que GHC hará lo correcto. Puede parecerle que la única manera de obtener el beneficio de rendimiento de seq ab es evaluar a WHNF antes de que comience la evaluación de b , pero es posible que haya optimizaciones en esta u otra situación que técnicamente comience a evaluar b ( o incluso evaluar completamente b a WHNF) mientras se deja sin evaluar por un corto tiempo para mejorar el rendimiento mientras se conserva la semántica de seq ab . Al usar pseq en pseq lugar, puede evitar que GHC realice dichas optimizaciones. (En la situación de su programa de sum , indudablemente no existe tal optimización, pero en un uso más complejo de seq , podría haber).

En tercer lugar, es importante entender para qué pseq . Se describió por primera vez en Marlow 2009 en el contexto de la programación concurrente. Supongamos que queremos poner en paralelo dos costosos cálculos foo y bar y luego combinar (decir, agregar) sus resultados:

foo `par` (bar `seq` foo+bar) -- parens redundant but included for clarity

La intención aquí es que, cuando se solicita el valor de esta expresión, se crea una chispa para calcular foo en paralelo y luego, a través de la expresión seq , comienza a evaluar la bar a WHNF (es decir, su valor numérico, por ejemplo) antes de evaluar finalmente foo+bar que esperará en la chispa para foo antes de agregar y devolver los resultados.

Aquí, es posible que GHC reconozca que para un tipo numérico específico, (1) foo+bar no finaliza automáticamente si la bar hace, satisfaciendo la garantía semántica formal de seq ; y (2) la evaluación de foo+bar a WHNF forzará automáticamente la evaluación de bar a WHNF evitando cualquier acumulación de thunk y satisfaciendo así la garantía de implementación informal de seq . En esta situación, GHC puede sentirse libre de optimizar la seq para obtener:

foo `par` foo+bar

particularmente si se siente que sería más eficaz comenzar la evaluación de foo+bar antes de terminar la bar evaluación a WHNF.

Lo que GHC no es lo suficientemente inteligente como para darse cuenta es que, si la evaluación de foo en foo+bar comienza antes de que se haya programado la chispa de foo , la chispa se inflamará y no se producirá una ejecución paralela.

Es solo en este caso, donde necesita retrasar explícitamente la exigencia del valor de una expresión activada para permitir que se programe una oportunidad antes de que el hilo principal "se ponga al día" de que necesita la garantía adicional de pseq y está dispuesto a tener GHC renuncia a las oportunidades de optimización adicionales permitidas por la garantía más débil de seq :

foo `par` (bar `pseq` foo+bar)

Aquí, pseq evitará que GHC introduzca cualquier optimización que pueda permitir que foo+bar comience a evaluar (potencialmente quemando la chispa de foo ) antes de que la bar esté en WHNF (lo cual, esperamos, permite suficiente tiempo para que se programe la chispa).

El resultado es que, si está utilizando pseq para otra cosa que no sea la programación concurrente, lo está haciendo mal. (Bueno, tal vez hay algunas situaciones extrañas, pero ...) Si lo único que quiere hacer es forzar una evaluación estricta y / o una evaluación compleja para mejorar el rendimiento en el código no concurrente, usando seq (o $! Que se define en términos de los tipos de datos estrictos de seq o Haskell que se definen en términos de $! ) es el enfoque correcto.

(O, si se deben creer los puntos de referencia de @ Kindaro, tal vez el enfoque correcto sea una evaluación comparativa sin piedad con versiones y banderas específicas del compilador).

Answer 2

Solo veo tal diferencia con las optimizaciones desactivadas. Con ghc -O tanto pseq como seq realizan lo mismo.

La semántica relajada de seq permite transformaciones que resultan en un código más lento. No puedo pensar en una situación en la que eso suceda realmente. Simplemente asumimos que GHC hace lo correcto. Desafortunadamente, no tenemos una manera de expresar ese comportamiento en términos de una semántica de alto nivel para Haskell.

¿Por qué pseq es más lento?

pseq x y = x `seq` lazy y

pseq se implementa así utilizando seq . La sobrecarga observada se debe a la indirección adicional de pseq de llamada.

Incluso si estos finalmente se optimizan, puede que no sea necesariamente una buena idea usar pseq lugar de seq . Si bien la semántica de ordenamiento más estricto parece implicar el efecto deseado (que no acumula un efecto), puede deshabilitar algunas optimizaciones adicionales: tal vez evaluar x y evaluar y puede descomponerse en operaciones de bajo nivel, algunas de las cuales no lo haríamos. Mente para cruzar el límite pseq .

¿Existe algún ejemplo en el que seq ab tenga diferentes resultados dependiendo del orden de evaluación (el mismo código pero diferentes indicadores de compilación / diferentes compiladores / etc.)?

Esto puede lanzar ya sea "a" o "b" .

seq (error "a") (error "b")

Supongo que hay una razón explicada en el documento sobre las excepciones en Haskell, A Semantics para excepciones imprecisas .

Answer 3

Edit: Mi teoría se frustró cuando los tiempos que observé estaban, de hecho, fuertemente sesgados por la influencia del perfilado en sí mismo; Con el perfilado apagado, los datos van en contra de la teoría. Además, los tiempos varían bastante entre las versiones de GHC. Incluso ahora estoy recogiendo mejores observaciones, y seguiré editando esta respuesta cuando llegue a un punto concluyente.

Con respecto a la pregunta "por qué pseq es más lento", tengo una teoría.

1. • Veamos de nuevo la frase acc'' `seq` go acc'' xs tan strict (go (strict acc'') xs) .
   • De manera similar, acc'' `pseq` go acc'' xs se re-expresa como lazy (go (strict acc'') xs) .
2. • Ahora, reescribamos go acc (x:xs) = let ... in ... to go acc (x:xs) = strict (go (x + acc) xs) en el caso de seq .
   • Y para go acc (x:xs) = lazy (go (x + acc) xs) en el caso de pseq .

Ahora, es fácil ver que, en el caso de pseq , a go se le asigna un thunk perezoso que se evaluará en algún momento posterior. En la definición de sum , go nunca aparece a la izquierda de pseq , y así, durante la ejecución de la sum , la evaluación no será forzada en absoluto. Además, esto sucede con cada llamada recursiva de go , así que los thunks se acumulan.

Esta es una teoría construida desde el aire, pero tengo una prueba parcial. Específicamente, descubrí que go asigna memoria lineal en caso pseq pero no en el caso de seq . Puede verlo por sí mismo si ejecuta los siguientes comandos de shell:

for file in SumNaive.hs SumPseq.hs SumSeq.hs
do
stack ghc /
--library-profiling /
--package parallel /
-- /
$file /
-main-is ${file%.hs} /
-o ${file%.hs} /
-prof /
-fprof-auto
done
for file in SumNaive.hs SumSeq.hs SumPseq.hs
do
time ./${file%.hs} +RTS -P
done

- Y comparar la asignación de memoria del centro de coste go .

COST CENTRE ... ticks bytes
SumNaive.prof:sum.go ... 782 559999984
SumPseq.prof:sum.go ... 669 800000016
SumSeq.prof:sum.go ... 161 0

postscriptum

Dado que parece haber discordia sobre la cuestión de qué optimizaciones realmente juegan a qué efecto, estoy poniendo mi código fuente exacto y las medidas de time , para que haya una línea de base común.

SumNaive.hs

module SumNaive where
import Prelude hiding (sum)
sum :: Num a => [a] -> a
sum = go 0
where
go acc [] = acc
go acc (x:xs) = go (x + acc) xs
main = print $ sum [1..10^7]

SumSeq.hs

module SumSeq where
import Prelude hiding (sum)
sum :: Num a => [a] -> a
sum = go 0
where
go acc [] = acc
go acc (x:xs) = let acc'' = x + acc
in acc'' `seq` go acc'' xs
main = print $ sum [1..10^7]

SumPseq.hs

module SumPseq where
import Prelude hiding (sum)
import Control.Parallel (pseq)
sum :: Num a => [a] -> a
sum = go 0
where
go acc [] = acc
go acc (x:xs) = let acc'' = x + acc
in acc'' `pseq` go acc'' xs
main = print $ sum [1..10^7]

Tiempo sin optimizaciones:

./SumNaive +RTS -P 4.72s user 0.53s system 99% cpu 5.254 total
./SumSeq +RTS -P 0.84s user 0.00s system 99% cpu 0.843 total
./SumPseq +RTS -P 2.19s user 0.22s system 99% cpu 2.408 total

Tiempo con -O :

./SumNaive +RTS -P 0.58s user 0.00s system 99% cpu 0.584 total
./SumSeq +RTS -P 0.60s user 0.00s system 99% cpu 0.605 total
./SumPseq +RTS -P 1.91s user 0.24s system 99% cpu 2.147 total

Tiempo con -O2 :

./SumNaive +RTS -P 0.57s user 0.00s system 99% cpu 0.570 total
./SumSeq +RTS -P 0.61s user 0.01s system 99% cpu 0.621 total
./SumPseq +RTS -P 1.92s user 0.22s system 99% cpu 2.137 total

Se puede ver que:

• La variante ingenua tiene un rendimiento pobre sin optimizaciones, pero un rendimiento excelente con -O -O2 , en la medida en que supera a todos los demás.

• seq variante seq tiene un buen rendimiento que se mejora muy poco con las optimizaciones, de modo que con cualquiera de las variantes -O u -O2 la variante ingenua lo supera.

• pseq variante pseq tiene un rendimiento sistemáticamente pobre, aproximadamente dos veces mejor que la variante ingenua sin optimización, y cuatro veces peor que otras con -O -O2 . La optimización afecta tan poco como la variante de seq .