De las cuales cosas debería tener cuidado si estoy usando el tipo sacó de la caja (como Int #) en Haskell / GHC?

Question

Estoy tratando de escribir un pequeño script que analiza y ejecuta código Brainfuck, para entender las opciones de optimización de GHC, que estoy tratando de optimizar el código con el fin de ser un poco más rápido y entender lo que está pasando allí.

En una de las partes es la represantation interna de BF-código, utilice un tipo de datos especial para esto. Aquí está el código fuente, incluidas las dos funciones que están haciendo las conversiones:

data BFinstruction
  = AdjustValue Int
  | MovePointer Int
  | GetChar
  | PutChar
  | Loop BFcode
  deriving (Eq)

type BFcode = [BFinstruction]

unsafeCompileBrainfuck :: String -> BFcode
unsafeCompileBrainfuck = fst . parse [] where
  -- arguments: input string, built code; output: output code, rest of input
  parse :: BFcode -> String -> (BFcode,String)
  parse c ('+':s) = parse (AdjustValue   1 :c) s
  parse c ('-':s) = parse (AdjustValue (-1):c) s
  parse c ('>':s) = parse (MovePointer   1 :c) s
  parse c ('<':s) = parse (MovePointer (-1):c) s
  parse c ('.':s) = parse (PutChar         :c) s
  parse c (',':s) = parse (GetChar         :c) s
  parse c (']':s) = (reverse c, s)
  parse c ('[':s) = parse (Loop l          :c) s' where (l,s') = parse [] s
  parse c []      = (reverse c ,"")
  parse c ( _ :s) = parse                   c  s

simplifyBrainfuck :: BFcode -> BFcode
simplifyBrainfuck ((AdjustValue x):(AdjustValue y):zs) = if x + y /= 0
  then simplifyBrainfuck (AdjustValue (x + y):zs)
  else simplifyBrainfuck zs
simplifyBrainfuck ((MovePointer x):(MovePointer y):zs) = if x + y /= 0
  then simplifyBrainfuck (MovePointer (x + y):zs)
  else simplifyBrainfuck zs
simplifyBrainfuck (x                              :zs) = x: simplifyBrainfuck zs
simplifyBrainfuck []                                   = []

La idea es que el código se puede leer en alguna entrada (cadena), preparsed y simplifica el código anterior y luego ejecutado por algunas otras funciones. (Se supone, que la entrada es válida).

Con el fin de optimizar este ejemplo, he tratado de desempacar los parametros de los constructores Int MovePointer y AdjustValue haciendo domething como esto:

data BFinstruction -- BangPatterns
  = AdjustValue {-# UNPACK #-} !Int
  | MovePointer {-# UNPACK #-} !Int
  | GetChar
  | PutChar
  | Loop BFcode
  deriving (Eq)

Esto a su vez el tipo Int en caja en una, tipo Int# prima sin caja, que es un detalle de implementación de GHC. A medida que leía, esta opción sólo es bueno en algunos casos, por lo que quiero preguntar, de los cuales las cosas que tengo que prestar atención si quiero realizar este tipo de optimización. Mi objetivo es permitir la ejecución de BF-código utilizando los beneficios de Haskell - pereza (Quiero archieve, que el código sólo se puede mantener como sea necesario en la memoria) y facilidad.

Answer 1

Esto realmente se parece a una optimización prematura a mí. DESEMBALE es útil sobre todo cuando se tiene un número muy grande de BFInstructions sentados alrededor. Dudo que alguna vez tiene suficiente brainf código ** k para que valga la pena. Estoy de acuerdo con Gian, debe ser lo suficientemente simple para la prueba, por lo que hacer en primer lugar.

En cualquier caso, lo que hay que tener en cuenta los valores UNPACK'ed es que usted no quiere que el compilador tiene que Rebox ellos. Usted debe estar bien con operaciones numéricas, pero aparte de eso habría que analizar cuidadosamente las funciones que está utilizando para ver si alguna vez utiliza los valores sin envasar como un argumento que no es estricta. La única manera de estar seguro es buscar en el núcleo, o los archivos de interfaz, para ver qué parámetros son estrictos y los que no lo son. Como siempre, asegúrese de compilar con, al menos, "O".

Answer 2

¿Es esto realmente necesario? ¿Está teniendo problemas de rendimiento con este código que cree son el resultado de los valores en caja? Si no es así, no se moleste.

Si cree que esto es el caso, entonces esta página en el manual de GHC parece proporcionar las restricciones necesarias en un formato de lista conveniente.

Los principales puntos parece ser que cualquier tipo de interacción entre las funciones o nombres y tipos polimórficos unboxed que no es rechazada por el compilador todavía podría dar lugar a fugas de espacio desagradables. También, sin pretenderlo, sospecho que usted no conseguirá excepciones lanzadas en el caso de un desbordamiento, por ejemplo, por lo que presumiblemente se debe detectar este tipo de cosas a sí mismo. Una prueba sencilla podría verificar si este es realmente el caso o no.