¿Cómo conviven la pereza y el paralelismo en Haskell?

parallel-processing immutability

Question

La gente argumenta que Haskell tiene una ventaja en el paralelismo ya que tiene estructuras de datos inmutables. Pero Haskell también es vago. Significa que los datos en realidad pueden mutarse del thunk al resultado evaluado.

Parece que la pereza puede dañar la ventaja de la inmutabilidad. ¿Me equivoco o Haskell tiene contramedidas para este problema? ¿O es esta la característica de Haskell?

Answer 1

Sí, el RTS de GHC usa thunks para implementar una evaluación no estricta, y usan mutación debajo del capó, por lo que requieren cierta sincronización. Sin embargo, esto se simplifica debido al hecho de que la mayoría de los objetos del montón son inmutables y las funciones son referencialmente transparentes.

En un programa multiproceso, la evaluación de un thunk procede de la siguiente manera:

• El thunk se reemplaza atómicamente ^† por un objeto BLACKHOLE

• Si el mismo hilo intenta forzar el thunk después de que se haya actualizado a BLACKHOLE , esto representa un bucle infinito y el RTS lanza una excepción ( <<loop>> )

• Si un hilo diferente intenta forzar el thunk mientras es un BLACKHOLE , se bloquea hasta que el hilo original haya terminado de evaluar el thunk y lo haya actualizado con un valor

• Cuando se completa la evaluación, el hilo original atómicamente ^† reemplaza el thunk con su resultado

^† por ejemplo, usando una instrucción de comparar y cambiar (CAS)

Entonces hay una carrera potencial aquí: si dos hilos intentan forzar el mismo golpe al mismo tiempo, ambos pueden comenzar a evaluarlo. En ese caso, harán un trabajo redundante; sin embargo, un subproceso logrará sobrescribir el BLACKHOLE con el resultado, y el otro subproceso simplemente descartará el resultado que calculó, porque su CAS fallará.

El código seguro no puede detectar esto, porque no puede obtener la dirección de un objeto o determinar el estado de un thunk. Y en la práctica, este tipo de colisión es raro por un par de razones:

• El código concurrente generalmente divide las cargas de trabajo en los subprocesos de una manera adecuada para el problema particular, por lo que existe un bajo riesgo de superposición

• La evaluación de los troncos generalmente es bastante "superficial" antes de alcanzar la forma normal de la cabeza débil, por lo que la probabilidad de una "colisión" es baja

Por lo tanto, los thunks en última instancia proporcionan una buena compensación de rendimiento al implementar una evaluación no estricta, incluso en un contexto concurrente.