Mover el código invariante de bucle desde GHC

Question

He estado luchando con la optimización de bucle manual de bajo nivel en GHC. Mi programa contiene algunos bucles que realizan cálculos numéricos. Los datos reales se envuelven en otras estructuras de datos, y el programa se divide en "funciones de flujo de control de bucle" y "funciones de cálculo" de tal manera que algunos campos de estructura de datos terminan siendo leídos dentro de bucles internos. Quiero que GHC saque esas lecturas de los bucles internos. Aquí hay una versión simplificada del código, para mostrar lo que está sucediendo.

data D = D !Double !C 
data C = C Double 

-- This function is called in every loop iteration. 
-- Parameter 'c' is loop-invariant. 
exampleLoopBody i a c = 
    case c of C b -> a + b * fromIntegral i 

-- The body of this function is a counted loop that should be optimized 
foo x = 
    case x 
    of D acc0 c -> 
    let loop i acc = 
      if i > 100 
      then acc 
      else loop (i+1) (exampleLoopBody i acc c) 
    in loop 0 acc0 

Cada iteración del bucle evalúa case c of C b, pero eso es redundante porque cómputo c es loop-invariante. Puedo hacer GHC levantarla a cabo poniendo una expresión redundante caso fuera del bucle:

foo x = 
    case x 
    of D acc0 c -> 
    case c    -- This case statement inserted for optimization purposes 
    of C b -> b `seq` -- It will read 'b' outside of the loop 
     let loop i acc = 
      if i > 100 
      then acc 
      else loop (i+1) (exampleLoopBody i acc c) 
     in loop 0 acc0 

Los inlines compilador exampleLoopBody. Después, la declaración caja interior es redundante y se eliminó:

foo x = 
    case x 
    of D acc0 c -> 
    case c 
    of C b -> b `seq` 
     let loop i acc = 
      if i > 100 
      then acc 
      else loop (i+1) (acc + b * fromIntegral i) -- The inlined case expression disappears 
     in loop 0 acc0 

El propósito de seq es asegurar que la expresión caso no es código muerto. El seq comprueba si b es _|_. GHC nota que, dado que se ha calculado b, es útil reutilizar ese valor en el cuerpo del bucle.

Ahora, aquí está el problema: realmente quiero que todos los campos de datos relevantes sean estrictos. Si inserto anotaciones rigor en la definición de datos, como esto,

data C = C !Double 

entonces el seq y case c of C b tienen ningún efecto en lo que se refiere a GHC. GHC los elimina, y me sale esto:

foo x = 
    case x 
    of D acc0 c -> 
    let loop i acc = 
      if i > 100 
      then acc 
      else loop (i+1) (case c of C b -> acc + b * fromIntegral i) -- Evaluate the case in every iteration 
    in loop 0 acc0 

Este código evalúa case c of C b en cada iteración, que es justo lo que estaba tratando de evitar.

Si no puedo confiar en seq, no sé cómo forzar b a calcular fuera del cuerpo del bucle. ¿Hay algún truco que pueda usar en este caso?

Answer 1

Usted podría intentar reordenar los argumentos y mover las partes variantes de bucle en una lambda:

-- note the order of the arguments changed 
exampleLoopBody (C b) = 
    \i a -> a + b * fromIntegral i 

foo (D acc0 c) = 
    let 
     loopBody = exampleLoopBody c 
     loop i acc = 
      if i > 100 
     then acc 
     else loop (i+1) (loopBody i acc) 
    in loop 0 acc0 

Además, este código se acumula una gran expresión no evaluada en este momento por lo que puede forzar el parámetro acumulador de cada tiempo a través del ciclo

Answer 2

Esto parece básicamente el motivo completo newtype se puso en el idioma. Simplemente cambie data C = C !Double a newtype C = C Double y escriba la versión ingenua del código. Todas las expresiones case en los valores del tipo C se borrarán. Como nota al margen, el patrón de código que tiene en sus ejemplos:

case foo of 
    D acc0 c -> case c of 
     C b -> ... 

puede escribirse de forma más sucinta:

case foo of 
    D acc0 (C b) -> ...