¿La programación funcional es más rápida en subprocesos múltiples porque escribo cosas de manera diferente o porque las cosas se compilan de manera diferente?

Me estoy sumergiendo en el mundo de la programación funcional y sigo leyendo en todas partes que los lenguajes funcionales son mejores para programas multihilo / multinúcleo. Entiendo cómo los lenguajes funcionales hacen muchas cosas de manera diferente, como la recursión , números aleatorios, etc., pero parece que no puedo entender si el subprocesamiento múltiple es más rápido en un lenguaje funcional porque está compilado de manera diferente o porque lo escribo de manera diferente.

Por ejemplo, he escrito un programa en Java que implementa cierto protocolo. En este protocolo, las dos partes envían y reciben entre sí miles de mensajes, cifran esos mensajes y los reenvían (y los reciben) una y otra vez. Como se esperaba, el subprocesamiento múltiple es clave cuando se trata en la escala de miles. En este programa no hay bloqueo involucrado .

Si escribo el mismo programa en Scala (que usa la JVM), ¿será esta implementación más rápida? ¿Si es así por qué? ¿Es por el estilo de escritura? Si es por el estilo de escritura, ahora que Java incluye expresiones lambda, ¿no podría lograr los mismos resultados usando Java con lambda? ¿O es más rápido porque Scala compilará las cosas de manera diferente?

La razón por la cual las personas dicen que los lenguajes funcionales son mejores para el procesamiento en paralelo se debe al hecho de que generalmente evitan el estado mutable. El estado mutable es la "raíz de todo mal" en el contexto del procesamiento paralelo; hacen que sea realmente fácil encontrarse con condiciones de carrera cuando se comparten entre procesos concurrentes. La solución a las condiciones de carrera involucra mecanismos de bloqueo y sincronización, como usted mencionó, que causan sobrecarga de tiempo de ejecución, ya que los procesos esperan uno al otro para hacer uso del recurso compartido y una mayor complejidad de diseño, ya que todos estos conceptos tienden a ser profundamente anidado dentro de tales aplicaciones.

Cuando evita el estado mutable, la necesidad de mecanismos de sincronización y bloqueo desaparece junto con él. Debido a que los lenguajes funcionales generalmente evitan el estado mutable, son naturalmente más eficientes y efectivos para el procesamiento paralelo: no tendrá la sobrecarga de tiempo de ejecución de los recursos compartidos, y no tendrá la complejidad de diseño adicional que generalmente sigue.

Sin embargo, todo esto es incidental. Si su solución en Java también evita el estado mutable (específicamente compartido entre subprocesos), convertirlo a un lenguaje funcional como Scala o Clojure no produciría ningún beneficio en términos de eficiencia concurrente, porque la solución original ya está libre de la sobrecarga causada por Los mecanismos de bloqueo y sincronización.

TL; DR: si una solución en Scala es más eficiente en el procesamiento en paralelo que una en Java, no se debe a la forma en que el código se compila o ejecuta a través de la JVM, sino a que la solución de Java comparte el estado mutable entre subprocesos, ya sea causando condiciones de carrera o agregando la sobrecarga de sincronización para evitarlas.

Una especie de ambos. Es más rápido porque es más fácil escribir su código de una manera más fácil de compilar más rápido. No necesariamente obtendrá una diferencia de velocidad al cambiar de idioma, pero si hubiera comenzado con un lenguaje funcional, probablemente podría haber realizado el subprocesamiento múltiple con mucho menos esfuerzo del programador . En la misma línea, es mucho más fácil para un programador cometer errores de enhebrado que costarán velocidad en un lenguaje imperativo, y mucho más difícil notar esos errores.

La razón es que los programadores imperativos generalmente intentan poner todo el código roscado sin bloqueo en una caja lo más pequeña posible, y escapar de él lo antes posible, de regreso a su cómodo mundo sincrónico y mutable. La mayoría de los errores que le cuestan velocidad se hacen en esa interfaz de límites. En un lenguaje de programación funcional, no tiene que preocuparse tanto por cometer errores en ese límite. La mayor parte de su código de llamada también está "dentro de la caja", por así decirlo.

La programación funcional no hace que los programas sean más rápidos, como regla general. Lo que hace es una programación paralela y concurrente más fácil . Hay dos claves principales para esto:

1. Evitar el estado mutable tiende a reducir la cantidad de cosas que pueden salir mal en un programa, y ​​aún más en un programa concurrente.
2. Evitar las primitivas de sincronización basada en bloqueo y memoria compartida a favor de conceptos de nivel superior tiende a simplificar la sincronización entre hilos de código.

Un excelente ejemplo del punto # 2 es que en Haskell tenemos una clara distinción entre paralelismo determinista versus concurrencia no determinista . No hay mejor explicación que citar el excelente libro de Simon Marlow Parallel and Concurrent Programming en Haskell (las citas son del Capítulo 1 ):

Un programa paralelo es aquel que utiliza una multiplicidad de hardware computacional (por ejemplo, varios núcleos de procesador) para realizar un cálculo más rápidamente. El objetivo es llegar a la respuesta antes, delegando diferentes partes de la computación a diferentes procesadores que se ejecutan al mismo tiempo.

Por el contrario, la concurrencia es una técnica de estructuración de programas en la que existen múltiples hilos de control. Conceptualmente, los hilos de control se ejecutan "al mismo tiempo"; es decir, el usuario ve sus efectos intercalados. Si realmente se ejecutan al mismo tiempo o no es un detalle de implementación; Un programa concurrente puede ejecutarse en un único procesador a través de la ejecución intercalada o en múltiples procesadores físicos.

Además de esto, Marlow también menciona la dimensión del determinismo :

Una distinción relacionada es entre modelos de programación deterministas y no deterministas . Un modelo de programación determinista es uno en el que cada programa puede dar un solo resultado, mientras que un modelo de programación no determinista admite programas que pueden tener resultados diferentes, dependiendo de algún aspecto de la ejecución. Los modelos de programación concurrente son necesariamente no deterministas porque deben interactuar con agentes externos que causan eventos en momentos impredecibles. Sin embargo, el no determinismo tiene algunos inconvenientes notables: los programas se vuelven significativamente más difíciles de probar y razonar.

Para la programación paralela, nos gustaría utilizar modelos de programación deterministas si es posible. Dado que el objetivo es llegar a la respuesta más rápidamente, preferimos no hacer que nuestro programa sea más difícil de depurar en el proceso. La programación paralela determinista es lo mejor de ambos mundos: las pruebas, la depuración y el razonamiento se pueden realizar en el programa secuencial, pero el programa se ejecuta más rápido con la adición de más procesadores.

En Haskell, las características de paralelismo y concurrencia están diseñadas en torno a estos conceptos. En particular, qué otros idiomas se agrupan como un conjunto de características, Haskell se divide en dos:

• Características deterministas y bibliotecas para paralelismo .
• Características y librerías no deterministas para concurrencia .

Si solo está tratando de acelerar un cálculo puro y determinista, tener paralelismo determinista a menudo facilita mucho las cosas. A menudo solo haces algo como esto:

1. Escriba una función que produzca una lista de respuestas, cada una de las cuales es costosa de calcular pero no depende mucho la una de la otra. Se trata de Haskell, por lo que las listas son perezosos valores -las de sus elementos no se computan en realidad hasta que un consumidor lo exige.
2. Use la biblioteca de Estrategias para consumir los elementos de las listas de resultados de su función en paralelo en múltiples núcleos.

De hecho, hice esto con uno de mis programas de proyectos de juguetes hace unas semanas . Fue trivial paralelizar el programa; lo clave que tuve que hacer fue, en efecto, agregar un código que diga "calcular los elementos de esta lista en paralelo" (línea 90), y obtuve un aumento de rendimiento casi lineal en Algunos de mis casos de prueba más caros.

¿Mi programa es más rápido que si hubiera utilizado las utilidades de subprocesos múltiples basadas en bloqueos convencionales? Lo dudo mucho. Lo bueno en mi caso fue obtener mucho de tan poco dinero: mi código es probablemente muy subóptimo, pero debido a que es tan fácil de paralelizar, obtuve una gran aceleración con mucho menos esfuerzo que perfilarlo y optimizarlo correctamente, y sin riesgo de condiciones de carrera. Y esa, diría, es la forma principal en que la programación funcional le permite escribir programas "más rápidos".

En Haskell, la modificación es literalmente imposible sin obtener variables modificables especiales a través de una biblioteca de modificaciones. En cambio, las funciones crean las variables que necesitan al mismo tiempo que sus valores (que se calculan perezosamente), y la basura se recolecta cuando ya no es necesaria.

Incluso cuando necesita variables de modificación, por lo general puede obtenerlas usando poco y junto con las variables no modificables. (Otra cosa buena en Haskell es STM, que reemplaza las cerraduras con operaciones atómicas, pero no estoy seguro de si esto es solo para la programación funcional o no). Por lo general, solo una parte del programa tendrá que ser paralela para mejorar las cosas. En cuanto al rendimiento.

Esto hace que el paralelismo en Haskell sea fácil la mayor parte del tiempo, y de hecho se están realizando esfuerzos para hacerlo automático. Para un código simple, el paralelismo y la lógica pueden incluso separarse.

Además, debido al hecho de que el orden de evaluación no importa en Haskell, el compilador solo crea una cola de cosas que deben evaluarse, y las envía a los núcleos disponibles, para que pueda hacer un montón de "hilos" que no en realidad se convierten en hilos hasta que sea necesario. El orden de evaluación sin importar es característico de la pureza, que generalmente requiere programación funcional.

Lectura adicional
Paralelismo en Haskell (HaskellWiki)
Programación concurrente y multinúcleo en "Haskell del mundo real"
Programación paralela y concurrente en Haskell por Simon Marlow