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

Una nota sobre el orden de evaluación: la expresión seq a b 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 evaluarse antes de a. Si necesita garantizar un orden específico de evaluación, debe usar la función pseq del paquete "paralelo".

Entonces tengo una versión perezosa de la función 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 (de acuerdo con la documentación) y aun así acumular thunks. Parece que necesito usar pseq para asegurarme de que acc' siempre se evalúa 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 sum [1 .. 10^7]:

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

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

Después de que intenté compilar con stack ghc -- -O File.hs la brecha de rendimiento entre seq y pseq desapareció. Ahora ambos corren en 0.2s.

Entonces, ¿mi implementación exhibe 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 a b tenga resultados diferentes según el orden de evaluación (mismo código pero indicadores de compilador diferentes / compiladores diferentes / etc.)?

18
Shersh 23 ene. 2018 a las 23:28

3 respuestas

La mejor respuesta

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

La respuesta breve es: si bien ambos deberían generar un código de rendimiento casi idéntico en la práctica (al menos cuando se activan los indicadores de optimización adecuados), la primitiva seq, y no 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 rendimiento, y su razón para usarlo se basa en una comprensión errónea de lo que significa su garantía de orden de evaluación y lo que implica con respecto a actuación. Si bien no hay garantías sobre el rendimiento en diferentes conjuntos de indicadores del compilador (mucho menos en otros compiladores), si alguna vez se encuentra con una situación en la que la versión seq del código anterior se ejecuta significativamente más lento que el pseq versión que utiliza 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 cualquiera de ellos garantiza semánticamente, y dado que la definición del lenguaje Haskell (como se indica en el informe Haskell) solo ofrece, en el mejor de los casos, garantías semánticas y no se ocupa del rendimiento o la implementación, hay no hay razón para elegir entre uno u otro por razones de rendimiento garantizado en diferentes compiladores o indicadores de compilación.

Además, en su particular versión basada en seq de la función sum, no es demasiado difícil ver que no hay una situación en la que se llame a seq con un primer argumento indefinido pero definido segundo argumento (suponiendo el uso de un tipo numérico estándar), por lo que ni siquiera está usando las propiedades semánticas de seq. Puede redefinir seq como seq a b = b y tener exactamente la misma semántica. Por supuesto, usted sabe esto, es por eso que su primera versión no usó seq. En cambio, está utilizando seq para un efecto secundario de rendimiento incidental, por lo que estamos fuera del ámbito de las garantías semánticas y volvemos al ámbito de la implementación específica del compilador GHC y las características de rendimiento (donde realmente no hay cualquier garantía para hablar).

Segundo, eso nos lleva al propósito previsto de seq. Raramente se usa por sus propiedades semánticas porque esas propiedades no son muy útiles. ¿Quién querría que un cómputo seq a b devuelva b excepto que no debe terminar si alguna expresión no relacionada a no termina? (Las excepciones, sin juego de palabras, serían cosas como manejar excepciones, donde podría usar seq o deepSeq que se basa en seq para forzar la evaluación de una expresión sin terminación ya sea de forma no controlada o controlada, antes de comenzar la evaluación de otra expresión).

En cambio, seq a b está destinado a forzar la evaluación de a a la forma normal de la 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 genera un thunk que podría acumularse sobre otro thunk no evaluado representado por a, puede evitar esa acumulación usando seq a b. La "garantía" es débil: GHC garantiza que comprende que no desea que a permanezca como una potencia no evaluada cuando se exige el valor de seq a b. Técnicamente, no garantiza que a sea "evaluado antes" b, lo que sea que eso signifique, pero no necesita esa garantía. Cuando le preocupa eso, sin esta garantía, GHC podría evaluar primero la llamada recursiva y aun así acumular thunks, esto es tan ridículo como preocuparse de que pseq a b pueda evaluar su primer argumento, luego esperar 15 minutos (solo para asegurarse de que el primer argumento haya 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 forma de obtener el beneficio de rendimiento de seq a b es evaluar a a WHNF antes de que comience la evaluación de b, pero es concebible que haya optimizaciones en esta u otras situaciones que técnicamente comienzan a evaluar b (o incluso evalúan completamente b a WHNF) mientras dejan a sin evaluar por un corto tiempo para mejorar el rendimiento y al mismo tiempo preservar la semántica de {{ X6}}. Al utilizar pseq en su lugar, puede evitar que GHC realice tales optimizaciones. (En su situación de programa sum, indudablemente no existe tal optimización, pero en un uso más complejo de seq, podría existir).

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

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

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

Aquí, es concebible que GHC reconozca que para un tipo numérico específico, (1) foo+bar no termina automáticamente si bar lo hace, satisfaciendo la garantía semántica formal de seq; y (2) evaluar 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 el seq para obtener:

foo `par` foo+bar

Particularmente si considera que sería más eficiente comenzar la evaluación de foo+bar antes de terminar de evaluar bar 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 programe la chispa foo, la chispa parpadeará y no se producirá una ejecución paralela .

Realmente es solo en este caso, donde necesita retrasar explícitamente la demanda del valor de una expresión provocada para permitir que se programe antes de que el hilo principal "se ponga al día" que necesita la garantía adicional de pseq y están dispuestos a que GHC renuncie 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 desvaneciendo la foo chispa) antes de que bar esté en WHNF (que, esperamos , permite suficiente tiempo para programar la chispa).

El resultado es que, si está utilizando pseq para otra cosa que no sea programación concurrente, lo está utilizando incorrectamente. (Bueno, tal vez haya algunas situaciones extrañas, pero ...) Si todo lo que quiere hacer es forzar una evaluación estricta y / o una evaluación thunk para mejorar el rendimiento en código no concurrente, utilizando seq (o {{X2 }} que se define en términos de seq o los tipos de datos estrictos de 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 despiadada con versiones y compiladores específicos).

12
K. A. Buhr 24 ene. 2018 a las 18:42

Editar: mi teoría fracasó ya que los tiempos que observé estaban de hecho muy sesgados por la influencia del perfil en sí; con el perfil apagado, los datos van en contra de la teoría. Además, los tiempos varían bastante entre las versiones de GHC. Estoy recopilando mejores observaciones incluso ahora, y editaré más esta respuesta a medida que llegue a un punto concluyente.


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

    • Reformulemos acc' `seq` go acc' xs como strict (go (strict acc') xs).
    • Del mismo modo, acc' `pseq` go acc' xs se reformula como lazy (go (strict acc') xs).
    • Ahora, reformulemos go acc (x:xs) = let ... in ... a go acc (x:xs) = strict (go (x + acc) xs) en el caso de seq.
    • Y a 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, 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 por lo tanto, durante la ejecución de sum, la evacuación no será forzada en absoluto. Además, esto sucede para cada llamada recursiva de go, por lo que se acumulan troncos.

Esta es una teoría construida desde el aire, pero tengo una prueba parcial. Específicamente, descubrí que go asigna memoria lineal en el caso pseq pero no en el caso de seq. Puede verlo usted 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 compare la asignación de memoria del centro de costos 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 con qué efecto, estoy poniendo mi código fuente exacto y las medidas 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 bajo rendimiento sin optimizaciones, pero un excelente rendimiento con -O o -O2, en la medida en que supera a todos los demás.

  • La variante seq tiene un buen rendimiento que mejora muy poco con las optimizaciones, de modo que con -O o -O2 la variante Naive lo supera.

  • La variante pseq tiene un rendimiento consistentemente pobre, aproximadamente dos veces mejor que la variante Naive sin optimización, y cuatro veces peor que otras con -O o -O2. La optimización lo afecta casi tan poco como la variante seq.

3
Ignat Insarov 24 ene. 2018 a las 16:57

Solo veo una gran 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 realmente suceda. Simplemente asumimos que GHC hace lo correcto. Desafortunadamente, no tenemos una forma de expresar ese comportamiento en términos de una semántica de alto nivel para Haskell.

¿Por qué pseq es más lenta?

pseq x y = x `seq` lazy y

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

Incluso si estos finalmente se optimizan, puede que no sea necesariamente una buena idea usar pseq en lugar de seq. Si bien la semántica de ordenamiento más estricta parece implicar el efecto deseado (que go no acumula un golpe), puede deshabilitar algunas optimizaciones adicionales: quizás evaluar x y evaluar y puede descomponerse en operaciones de bajo nivel, algunas de las cuales no nos importaría cruzar el límite pseq.

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

Esto puede arrojar "a" o "b".

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

Creo que hay una justificación explicada en el documento sobre las excepciones en Haskell, Una semántica para excepciones imprecisas .

6
Li-yao Xia 24 ene. 2018 a las 04:49
48410245