performance - sobre - multiplos en haskell

¿El desempeño de las funciones parciales o al curry está bien definido en Haskell?

Question

En el siguiente código:

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l x = x == maxel
where maxel = maximum l
main = do
let mylist = [1, 2, 3, 5]
let ismax = ismaxl mylist
--Is each call O(1)? Does each call remember maxel?
let c1 = ismax 1
let c2 = ismax 2
let c3 = ismax 3
let c5 = ismax 5
putStrLn (show [c1, c2, c3, c5])

¿La función parcial ismax, calcula el maxel? Especialmente, ¿alguien puede señalar una regla sobre la complejidad de las funciones parciales en Haskell? ¿DEBE el compilador solo llamar al máximo una vez en el ejemplo anterior? Dicho de otra manera, ¿una función parcial conserva las referencias de las llamadas anteriores para cláusulas internas?

Tengo algún código enlazado a la CPU que no funciona de manera aceptable, y estoy buscando posibles errores en mi razonamiento acerca de la complejidad.

Answer 1

Aquí hay una versión modificada de su código que le permitirá ver si se reutiliza o no maxel :

import Debug.Trace
ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l x = x == maxel
where maxel = trace "Hello" $ maximum l
main = do
let mylist = [1, 2, 3, 5]
let ismax = ismaxl mylist
--Is each call O(1)? Does each call remember maxel?
let c1 = ismax 1
let c2 = ismax 2
let c3 = ismax 3
let c5 = ismax 5
putStrLn (show [c1, c2, c3, c5])

Verás que maxel no se ''recuerda'' entre aplicaciones.

En general, no debe esperar que Haskell comience a hacer reducciones hasta que todos los argumentos hayan sido proporcionados a una función.

Por otro lado, si tiene activada la optimización agresiva, es difícil predecir lo que realmente haría un compilador en particular. Pero probablemente no debas confiar en ninguna parte del compilador que sea difícil de predecir cuando puedas reescribir fácilmente el código para hacer explícito lo que quieres.

Answer 2

Como demostración de lo que puede aprender al crear un perfil de su código de Haskell, aquí está el resultado de algunas modificaciones menores en su código. Primero, he reemplazado mylist con [0..10000000] para asegurarme de que se tarda un tiempo en calcular el máximo.

Aquí hay algunas líneas de la salida del perfil, después de ejecutar esa versión:

COST CENTRE MODULE %time %alloc
ismaxl Main 55.8 0.0
main Main 44.2 100.0
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 100.0 100.0
CAF:main_c5 Main 225 1 0.0 0.0 15.6 0.0
main Main 249 0 0.0 0.0 15.6 0.0
ismaxl Main 250 1 15.6 0.0 15.6 0.0
CAF:main_c3 Main 224 1 0.0 0.0 15.6 0.0
main Main 246 0 0.0 0.0 15.6 0.0
ismaxl Main 247 1 15.6 0.0 15.6 0.0
CAF:main_c2 Main 223 1 0.0 0.0 14.3 0.0
main Main 243 0 0.0 0.0 14.3 0.0
ismaxl Main 244 1 14.3 0.0 14.3 0.0
CAF:main_c1 Main 222 1 0.0 0.0 10.4 0.0
main Main 239 0 0.0 0.0 10.4 0.0
ismaxl Main 240 1 10.4 0.0 10.4 0.0
CAF:main8 Main 221 1 0.0 0.0 44.2 100.0
main Main 241 0 44.2 100.0 44.2 100.0

Es bastante obvio volver a calcular el máximo aquí.

Ahora, reemplazando ismaxl con esto:

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l = let maxel = maximum l in (== maxel)

... y perfilando de nuevo:

COST CENTRE MODULE %time %alloc
main Main 60.5 100.0
ismaxl Main 39.5 0.0
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 100.0 100.0
CAF:main_c5 Main 227 1 0.0 0.0 0.0 0.0
main Main 252 0 0.0 0.0 0.0 0.0
ismaxl Main 253 1 0.0 0.0 0.0 0.0
CAF:main_c3 Main 226 1 0.0 0.0 0.0 0.0
main Main 249 0 0.0 0.0 0.0 0.0
ismaxl Main 250 1 0.0 0.0 0.0 0.0
CAF:main_c2 Main 225 1 0.0 0.0 0.0 0.0
main Main 246 0 0.0 0.0 0.0 0.0
ismaxl Main 247 1 0.0 0.0 0.0 0.0
CAF:main_c1 Main 224 1 0.0 0.0 0.0 0.0
CAF:main_ismax Main 223 1 0.0 0.0 39.5 0.0
main Main 242 0 0.0 0.0 39.5 0.0
ismaxl Main 243 2 39.5 0.0 39.5 0.0
CAF:main8 Main 222 1 0.0 0.0 60.5 100.0
main Main 244 0 60.5 100.0 60.5 100.0

... esta vez pasa la mayor parte de su tiempo en una sola llamada a ismaxl , las otras son demasiado rápidas como para notarlo, por lo que debe calcular el máximo solo una vez aquí.

Answer 3

Gracias a otras buenas respuestas, GHC no ha estado ansioso por realizar este tipo de optimización en mi experiencia. Si no puedo hacer algo sin puntos fácilmente, a menudo he recurrido a escribir con una combinación de vars encuadernados en el LHS y un lambda:

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l = /x -> x == maxel
where maxel = maximum l

No me gusta particularmente este estilo, pero asegura que se comparte maxel entre llamadas a un ismaxl parcialmente aplicado.

Answer 4

No he podido encontrar ninguno de estos requisitos en el Informe Haskell , y de hecho, parece que GHC no realiza esta optimización de forma predeterminada.

Cambié tu función main a

main = do
let mylist = [1..99999]
let ismax = ismaxl mylist
let c1 = ismax 1
let c2 = ismax 2
let c3 = ismax 3
let c5 = ismax 5
putStrLn (show [c1, c2, c3, c5])

Espectáculos de perfiles simples (en mi antiguo Pentium 4):

$ ghc a.hs
$ time ./a.out
[False,False,False,False]
real 0m0.313s
user 0m0.220s
sys 0m0.044s

Pero cuando cambio la definición de c2 , c3 y c5 para let c2 = 2 == 99999 etc. (dejando c1 como está), obtengo

$ ghc a.hs
$ time ./a.out
[False,False,False,False]
real 0m0.113s
user 0m0.060s
sys 0m0.028s