¿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?

63

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?

Aventino
fuente
64
La programación funcional de Afaik no hace que el subprocesamiento múltiple sea más rápido. Hace que el subprocesamiento múltiple sea más fácil de implementar y más seguro porque hay algunas características de la programación funcional como la inmutabilidad y las funciones que no tienen efectos secundarios que ayudan en este sentido.
Pieter B
77
Tenga en cuenta que 1) mejor no está realmente definido 2) seguramente no está definido como simplemente "más rápido". Un lenguaje X que requiere mil millones de veces el tamaño del código para una ganancia de rendimiento del 0.1% con respecto a Y no es mejor que Y para cualquier definición razonable de mejor.
Bakuriu
2
¿Quería preguntar sobre "programación funcional" o "programas escritos en estilo funcional"? A menudo, la programación más rápida no produce un programa más rápido.
Ben Voigt
1
No olvide que siempre hay un GC que debe ejecutarse en segundo plano y mantenerse al día con sus demandas de asignación ... y no estoy seguro de que sea multiproceso ...
Mehrdad
44
La respuesta más simple aquí es: la programación funcional permite escribir programas que considerarían menos problemas de condición de carrera, sin embargo, no significa que los programas escritos con estilo imperativo sean más lentos.
Dawid Pura

Respuestas:

97

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.

MichelHenrich
fuente
2
Si solo un hilo modifica una pieza de datos; No se necesita cuidado especial. Es solo cuando varios subprocesos pueden modificar los mismos datos que necesita algún tipo de cuidado especial (sincronización, memoria transaccional, bloqueo, lo que sea). Un ejemplo de esto es la pila de un hilo, que está constantemente mutada por código funcional pero no modificada por múltiples hilos.
Brendan
31
Hacer que un hilo mute los datos mientras otros lo leen es suficiente para que tenga que comenzar a tener "especial cuidado".
Peter Green
10
@Brendan: No, si un hilo modifica datos mientras otros hilos leen esos mismos datos, entonces tienes una condición de carrera. Se necesita un cuidado especial incluso si solo se modifica un hilo.
Cornstalks
3
El estado mutable es la "raíz de todo mal" en el contexto del procesamiento paralelo => si aún no ha mirado a Rust, le aconsejo que lo mire. Se las arregla para permitir la mutabilidad de manera muy eficiente al darse cuenta de que el verdadero problema es mutable mezclado con alias: si solo tiene alias o solo tiene mutabilidad, no hay problema.
Matthieu M.
2
@MatthieuM. Bien, gracias! Edité para expresar las cosas más claramente en mi respuesta. El estado mutable es solo "la raíz de todo mal" cuando se comparte entre procesos concurrentes, algo que Rust evita con sus mecanismos de control de propiedad.
MichelHenrich
8

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.

Karl Bielefeldt
fuente
7

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".

sacundim
fuente
2

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

PyRulez
fuente
77
grep java this_post. grep scala this_posty grep jvm this_postno devuelve ningún resultado :)
Andres F.
44
La pregunta es vaga. En el título y el primer párrafo, pregunta sobre la programación funcional en general , en el segundo y tercer párrafo, pregunta sobre Java y Scala en particular . Eso es lamentable, sobre todo porque uno de los puntos fuertes de Scala es precisamente el hecho de que es no (solo) un lenguaje funcional. Martin Odersky lo llama "post-funcional", otros lo llaman "objeto-funcional". Hay dos definiciones diferentes del término "programación funcional". Uno es "programación con procedimientos de primera clase" (la definición original aplicada a LISP), el otro es ...
Jörg W Mittag
2
"programación con funciones referencialmente transparentes, puras, sin efectos secundarios y datos persistentes inmutables" (una interpretación mucho más estricta y también más nueva). Esta respuesta aborda la segunda interpretación, que tiene sentido, porque a) la primera interpretación no tiene ninguna relación con el paralelismo y la concurrencia, b) la primera interpretación ha dejado de tener sentido básicamente, ya que, con la excepción de C, casi todos los lenguajes en uso modestamente extendido hoy tiene procedimientos de primera clase (incluido Java), y c) el OP pregunta por la diferencia entre Java y Scala, pero no hay ...
Jörg W Mittag
2
entre los dos con respecto a la definición # 1, solo la definición # 2.
Jörg W Mittag
Lo de la evaluación no es del todo cierto, ya que está escrito aquí; De manera predeterminada, el tiempo de ejecución no utiliza subprocesos múltiples, y IIRC, incluso si habilita el subprocesamiento múltiple, aún tiene que decirle al tiempo de ejecución qué cosas debe evaluar en paralelo.
Cubic