haskell - Ventajas de campos estrictos en tipos de datos.

strictness

Question

Puede que ahora sea un poco confuso, pero me lo he estado preguntando durante un tiempo. Que yo sepa con ! , uno puede asegurarse de que se esté evaluando un parámetro para un constructor de datos antes de que se construya el valor:

data Foo = Bar !Int !Float

A menudo he pensado que la pereza es una gran cosa. Ahora, cuando reviso las fuentes, veo campos estrictos con más frecuencia que el ! Variante menos.

¿Cuál es la ventaja de esto y por qué no debería dejarlo perezoso como está?

Answer 1

A menos que esté almacenando un cálculo grande en los campos Int y Flotante, la sobrecarga significativa puede acumularse a partir de muchos cálculos triviales que se acumulan en Thunks. Por ejemplo, si agrega repetidamente 1 a un campo Float lento en un tipo de datos, utilizará más y más memoria hasta que realmente fuerce el campo, calculándolo.

A menudo, desea almacenar cálculos costosos en un campo. Pero si sabe que no va a hacer nada de eso por adelantado, puede marcar el campo como estricto y evitar tener que agregar manualmente todas las seq para obtener la eficiencia que desea.

Como -funbox-strict-fields adicional, cuando se le -funbox-strict-fields la bandera -funbox-strict-fields GHC desempaquetará los campos estrictos ¹ de los tipos de datos directamente en el mismo tipo de datos, lo cual es posible porque sabe que siempre serán evaluados, y por lo tanto, no hay que hacer nada. asignado; en este caso, un valor de Barra contendría las palabras de máquina que comprenden el Int y el Flotador directamente dentro del valor de Barra en la memoria, en lugar de contener dos punteros a los thunks que contienen los datos.

La pereza es una cosa muy útil, pero algunas veces, solo se interpone en el camino e impide el cálculo, especialmente para campos pequeños que siempre se observan (y, por lo tanto, se fuerzan), o que se modifican a menudo pero nunca con cálculos muy costosos. Los campos estrictos ayudan a superar estos problemas sin tener que modificar todos los usos del tipo de datos.

Si es más común que los campos perezosos o no, depende del tipo de código que esté leyendo; por ejemplo, no es probable que veas estructuras de árbol funcionales que utilicen extensivamente campos estrictos porque se benefician enormemente de la pereza.

Digamos que tienes un AST con un constructor para operaciones de infijo:

data Exp = Infix Op Exp Exp
| ...
data Op = Add | Subtract | Multiply | Divide

No querría que los campos de Exp estrictos, ya que aplicar una política como esa significaría que todo el AST se evalúa cada vez que se ve en el nodo de nivel superior, que claramente no es lo que quiere beneficiarse de la pereza. Sin embargo, el campo Op nunca contendrá un cómputo costoso que se desea diferir a una fecha posterior, y la sobrecarga de un thunk por operador infijo puede resultar costosa si tiene árboles de análisis muy anidados. Por lo tanto, para el constructor de infijo, querría que el campo Op estricto, pero deje los dos campos Exp . Perezosos.

¹ Solo se pueden desempaquetar tipos de constructor único.

Answer 2

Además de la información proporcionada por otras respuestas, tenga en cuenta:

Que yo sepa con ! , uno puede asegurarse de que se esté evaluando un parámetro para un constructor de datos antes de que se construya el valor

Es interesante observar la profundidad con la que se evalúa el parámetro . ¡Es como con seq y $! evaluado a WHNF .

Dados los tipos de datos

data Foo = IntFoo !Int | FooFoo !Foo | BarFoo !Bar
data Bar = IntBar Int

la expresion

let x'' = IntFoo $ 1 + 2 + 3
in x''

evaluado a WHNF produce el valor IntFoo 6 (== completamente evaluado, == NF).
Además esta expresión

let x'' = FooFoo $ IntFoo $ 1 + 2 + 3
in x''

evaluado a WHNF produce el valor FooFoo (IntFoo 6) (== completamente evaluado, == NF).
Sin embargo, esta expresión

let x'' = BarFoo $ IntBar $ 1 + 2 + 3
in x''

evaluado a WHNF produce el valor BarFoo (IntBar (1 + 2 + 3)) (! = completamente evaluado BarFoo (IntBar (1 + 2 + 3)) = NF).

Punto principal: el rigor del parámetro !Bar no ayudará necesariamente si los constructores de datos de Bar no contienen parámetros estrictos.

Answer 3

Hay una sobrecarga asociada con la pereza: el compilador tiene que crear un procesador para que el valor almacene el cálculo hasta que se necesite el resultado. Si sabe que siempre necesitará el resultado tarde o temprano, entonces puede tener sentido forzar la evaluación del resultado.

Answer 4

La pereza tiene un costo, de lo contrario todos los idiomas lo tendrían.

El costo es doble:

1. Puede llevar más tiempo configurar el procesador (es decir, la descripción de lo que debe calcularse cuando se va a calcular eventualmente) que hacer la operación de inmediato.
2. Thunks no evaluados que van como argumentos no estrictos a otros thunks que van como argumentos no estrictos a otros thunks, etc. usarán cada vez más memoria. Desafortunadamente, esos tunks también pueden contener referencias a la memoria que ya no es accesible, es decir, la memoria que podría liberarse cuando solo se evaluaría el procesador, lo que impide que el recolector de basura haga su trabajo. Un ejemplo sería un procesador que debería actualizar un determinado valor en el árbol. Digamos que este valor se mantiene en el valor de 100MB de otros valores. Si ya no hay referencia al árbol viejo, esta memoria se desperdicia siempre que no se evalúe el procesador.