¿La inmutabilidad elimina por completo la necesidad de bloqueos en la programación multiprocesador?

39

Parte 1

Claramente, la inmutabilidad minimiza la necesidad de bloqueos en la programación multiprocesador, pero ¿elimina esa necesidad o hay casos en los que la inmutabilidad por sí sola no es suficiente? Me parece que solo puede diferir el procesamiento y el estado de encapsulado mucho antes de que la mayoría de los programas tengan que HACER realmente algo (actualizar un almacén de datos, producir un informe, lanzar una excepción, etc.). ¿Pueden tales acciones siempre hacerse sin cerraduras? ¿La mera acción de tirar cada objeto y crear uno nuevo en lugar de cambiar el original (una visión burda de la inmutabilidad) proporciona una protección absoluta contra la contención entre procesos, o hay casos de esquina que aún requieren bloqueo?

Sé que a muchos programadores y matemáticos funcionales les gusta hablar de "sin efectos secundarios", pero en el "mundo real" todo tiene un efecto secundario, incluso si es el tiempo que lleva ejecutar una instrucción de máquina. Estoy interesado tanto en la respuesta teórica / académica como en la respuesta práctica / del mundo real.

Si la inmutabilidad es segura, dados ciertos límites o suposiciones, quiero saber cuáles son exactamente los límites de la "zona de seguridad". Algunos ejemplos de posibles límites:

  • I / O
  • Excepciones / errores
  • Interacciones con programas escritos en otros idiomas.
  • Interacciones con otras máquinas (físicas, virtuales o teóricas)

¡Un agradecimiento especial a @JimmaHoffa por su comentario que inició esta pregunta!

Parte 2

La programación multiprocesador se usa a menudo como una técnica de optimización, para hacer que algunos códigos se ejecuten más rápido. ¿Cuándo es más rápido usar bloqueos frente a objetos inmutables?

Teniendo en cuenta los límites establecidos en la Ley de Amdahl , ¿cuándo puede lograr un mejor rendimiento general (con o sin el recolector de basura en cuenta) con objetos inmutables en lugar de bloquear los mutables?

Resumen

Estoy combinando estas dos preguntas en una para tratar de llegar a dónde está el cuadro delimitador para la inmutabilidad como una solución a los problemas de enhebrado.

GlenPeterson
fuente
21
but everything has a side effect- Uh, no, no lo hace. Una función que acepta algún valor y devuelve algún otro valor, y no altera nada fuera de la función, no tiene efectos secundarios y, por lo tanto, es segura para subprocesos. No importa que la computadora use electricidad. También podemos hablar sobre los rayos cósmicos que golpean las células de memoria, si lo desea, pero mantengamos el argumento práctico. Si desea considerar cosas como la forma en que se ejecuta la función afecta el consumo de energía, ese es un problema diferente que la programación segura para subprocesos.
Robert Harvey
55
@RobertHarvey - Tal vez solo estoy usando una definición diferente de efecto secundario y debería haber dicho "efecto secundario del mundo real". Sí, los matemáticos tienen funciones sin efectos secundarios. El código que se ejecuta en una máquina del mundo real necesita recursos de la máquina para ejecutarse, tanto si muta datos como si no. La función en su ejemplo pone su valor de retorno en la pila en la mayoría de las arquitecturas de máquina.
GlenPeterson
1
Si realmente puede superarlo, creo que su pregunta va al corazón de este infame artículo de investigación
Microsoft.com/en-us/um/people/simonpj/papers/…
66
Para los fines de nuestra discusión, supongo que se refiere a una máquina completa de Turing que está ejecutando algún tipo de lenguaje de programación bien definido, donde los detalles de implementación son irrelevantes. En otras palabras, no debería importar lo que esté haciendo la pila, si la función que estoy escribiendo en mi lenguaje de programación de elección puede garantizar la inmutabilidad dentro de los límites del lenguaje. No pienso en la pila cuando estoy programando en un lenguaje de alto nivel, ni debería tener que hacerlo.
Robert Harvey
1
@RobertHarvey cuchara; Mónadas jeh Y puedes deducirlo de las primeras dos páginas. Lo menciono porque en el transcurso del todo detalla una técnica para manejar los efectos secundarios de una manera prácticamente pura, estoy bastante seguro de que responderá a la pregunta de Glen, así que lo publiqué como una buena nota al pie para cualquiera que encuentre esta pregunta en El futuro para futuras lecturas.
Jimmy Hoffa

Respuestas:

35

Esta es una pregunta extrañamente formulada que es realmente muy amplia si se responde completamente. Me voy a centrar en aclarar algunos de los detalles sobre los que está preguntando.

La inmutabilidad es una compensación de diseño. Hace que algunas operaciones sean más difíciles (modificar el estado en objetos grandes rápidamente, construir objetos poco a poco, mantener un estado de ejecución, etc.) en favor de otros (depuración más fácil, razonamiento más fácil sobre el comportamiento del programa, no tener que preocuparse por las cosas que cambian debajo de ti cuando trabajas concurrentemente, etc.). Es esta última la que nos interesa con esta pregunta, pero quiero enfatizar que es una herramienta. Una buena herramienta que a menudo resuelve más problemas de los que causa (en la mayoría de los programas modernos ), pero no una bala de plata ... No es algo que cambie el comportamiento intrínseco de los programas.

Ahora, ¿qué te pasa? La inmutabilidad le da una cosa: puede leer el objeto inmutable libremente, sin preocuparse de que su estado cambie debajo de usted (suponiendo que sea realmente profundamente inmutable ... Tener un objeto inmutable con miembros mutables generalmente es un factor decisivo). Eso es. Le libera de tener que administrar la concurrencia (a través de bloqueos, instantáneas, particionamiento de datos u otros mecanismos; el enfoque de la pregunta original en los bloqueos es ... Incorrecto dado el alcance de la pregunta).

Sin embargo, resulta que muchas cosas leen objetos. IO lo hace, pero IO en sí mismo tiende a no manejar bien el uso concurrente. Casi todo el procesamiento lo hace, pero otros objetos pueden ser mutables, o el procesamiento en sí podría usar un estado que no sea amigable con la concurrencia. Copiar un objeto es un gran problema oculto en algunos idiomas, ya que una copia completa (casi) nunca es una operación atómica. Aquí es donde los objetos inmutables te ayudan.

En cuanto al rendimiento, depende de su aplicación. Las cerraduras son (generalmente) pesadas. Otros mecanismos de gestión de concurrencia son más rápidos pero tienen un alto impacto en su diseño. En general , un diseño altamente concurrente que hace uso de objetos inmutables (y evita sus debilidades) funcionará mejor que un diseño altamente concurrente que bloquea objetos mutables. Si su programa es ligeramente concurrente, entonces depende y / o no importa.

Pero el rendimiento no debería ser su mayor preocupación. Escribir programas concurrentes es difícil . La depuración de programas concurrentes es difícil . Los objetos inmutables ayudan a mejorar la calidad de su programa al eliminar las oportunidades de error al implementar la gestión de concurrencia manualmente. Facilitan la depuración porque no está intentando rastrear el estado en un programa concurrente. Simplifican su diseño y eliminan los errores allí.

En resumen: la inmutabilidad ayuda pero no eliminará los desafíos necesarios para manejar la concurrencia adecuadamente. Esa ayuda tiende a ser generalizada, pero las mayores ganancias son desde una perspectiva de calidad en lugar de rendimiento. Y no, la inmutabilidad no te exime mágicamente de administrar la concurrencia en tu aplicación, lo siento.

Telastyn
fuente
+1 Esto tiene sentido, pero ¿podría dar un ejemplo de dónde en un lenguaje profundamente inmutable todavía tiene que preocuparse por manejar la concurrencia correctamente? Afirmas que sí, pero ese escenario no está claro para mí
Jimmy Hoffa
@JimmyHoffa En un lenguaje inmutable, todavía necesita alguna forma de actualizar el estado entre hilos. Los dos lenguajes más inmutables que conozco (Clojure y Haskell) proporcionan un tipo de referencia (átomos y Mvars) que proporcionan una forma de enviar el estado modificado entre hilos. La semántica de sus tipos de referencia previene ciertos tipos de errores de concurrencia, pero otros aún son posibles.
Stonemetal
@stonemetal interesante, en mis 4 meses con Haskell ni siquiera había oído hablar de Mvars, siempre escuché usar STM para la comunicación de estado de concurrencia que se comporta más como el mensaje de Erlang que pasaba, pensé. Aunque el ejemplo perfecto de inmutabilidad que no resuelve problemas concurrentes en los que puedo pensar es actualizar una interfaz de usuario, si tiene 2 hilos que intentan actualizar una interfaz de usuario con diferentes versiones de datos, uno puede ser más nuevo y, por lo tanto, necesita obtener la segunda actualización para que tenga una condición de carrera donde debes garantizar la secuencia de alguna manera ... Pensamiento interesante ... Gracias por los detalles
Jimmy Hoffa
1
@jimmyhoffa: el ejemplo más común es IO. Incluso si el idioma es inmutable, su base de datos / sitio web / archivo no lo es. Otro es su mapa típico / reducir. La inmutabilidad significa que la agregación del mapa es más infalible, pero aún debe manejar la coordinación 'una vez que todo el mapa está en paralelo, reduzca'.
Telastyn
1
@JimmyHoffa: MVars es una primitiva de concurrencia mutable de bajo nivel (técnicamente, una referencia inmutable a una ubicación de almacenamiento mutable), no muy diferente de lo que vería en otros idiomas; los callejones sin salida y las condiciones de carrera son muy posibles. STM es una abstracción de concurrencia de alto nivel para memoria compartida mutable sin bloqueo (muy diferente del paso de mensajes) que permite transacciones componibles sin posibilidad de puntos muertos o condiciones de carrera. Los datos inmutables solo son seguros para subprocesos, nada más que decir al respecto.
CA McCann
13

Una función que acepta algún valor y devuelve algún otro valor, y no altera nada fuera de la función, no tiene efectos secundarios y, por lo tanto, es segura para subprocesos. Si desea considerar cosas como la forma en que se ejecuta la función afecta el consumo de energía, ese es un problema diferente.

Supongo que se refiere a una máquina completa de Turing que está ejecutando algún tipo de lenguaje de programación bien definido, donde los detalles de implementación son irrelevantes. En otras palabras, no debería importar lo que esté haciendo la pila, si la función que estoy escribiendo en mi lenguaje de programación de elección puede garantizar la inmutabilidad dentro de los límites del lenguaje. No pienso en la pila cuando estoy programando en un lenguaje de alto nivel, ni debería tener que hacerlo.

Para ilustrar cómo funciona esto, voy a ofrecer algunos ejemplos simples en C #. Para que estos ejemplos sean ciertos, tenemos que hacer un par de suposiciones. Primero, que el compilador sigue la especificación de C # sin error, y segundo, que produce los programas correctos.

Digamos que quiero una función simple que acepte una colección de cadenas y devuelva una cadena que sea una concatenación de todas las cadenas de la colección separadas por comas. Una implementación simple e ingenua en C # podría verse así:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    string result = string.Empty;
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result += s;
        else
            result += ", " + s;
    }
    return result;
} 

Este ejemplo es inmutable, prima facie. ¿Cómo sé eso? Porque el stringobjeto es inmutable. Sin embargo, la implementación no es ideal. Debido a que resultes inmutable, debe crearse un nuevo objeto de cadena cada vez a través del bucle, reemplazando el objeto original al que resultapunta. Esto puede afectar negativamente la velocidad y ejercer presión sobre el recolector de basura, ya que tiene que limpiar todas esas cadenas adicionales.

Ahora, digamos que hago esto:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    var result = new StringBuilder();
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result.Append(s);
        else
            result.Append(", " + s);
    }
    return result.ToString();
} 

Tenga en cuenta que he reemplazado string resultcon un objeto mutable, StringBuilder. Esto es mucho más rápido que el primer ejemplo, porque no se crea una nueva cadena cada vez a través del bucle. En cambio, el objeto StringBuilder simplemente agrega los caracteres de cada cadena a una colección de caracteres, y genera todo al final.

¿Es esta función inmutable, aunque StringBuilder es mutable?

Sí lo es. ¿Por qué? Como cada vez que se llama a esta función, se crea un nuevo StringBuilder, solo para esa llamada. Así que ahora tenemos una función pura que es segura para subprocesos, pero contiene componentes mutables.

Pero, ¿y si hiciera esto?

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;

    public string ConcatenateWithCommas(ImmutableList<string> list)
    {
        foreach (string s in list)
        {
            if (isFirst)
                result.Append(s);
            else
                result.Append(", " + s);
        }
        return result.ToString();
    } 
}

¿Es este método seguro para subprocesos? No lo es. ¿Por qué? Porque la clase ahora tiene un estado del que depende mi método. Ahora está presente una condición de carrera en el método: un subproceso puede modificarse IsFirst, pero otro subproceso puede realizar el primero Append(), en cuyo caso ahora tengo una coma al comienzo de mi cadena que no se supone que esté allí.

¿Por qué podría querer hacerlo así? Bueno, es posible que desee que los hilos acumulen las cadenas en mi resultsin importar el orden, o en el orden en que entran los hilos. Quizás sea un registrador, ¿quién sabe?

De todos modos, para solucionarlo, puse una lockdeclaración alrededor de las entrañas del método.

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;
    private static object locker = new object();

    public string AppendWithCommas(ImmutableList<string> list)
    {
        lock (locker)
        {
            foreach (string s in list)
            {
                if (isFirst)
                    result.Append(s);
                else
                    result.Append(", " + s);
            }
            return result.ToString();
        }
    } 
}

Ahora es seguro para subprocesos nuevamente.

La única forma en que mis métodos inmutables podrían no ser seguros para subprocesos es si el método de alguna manera pierde parte de su implementación. ¿Podría pasar esto? No si el compilador es correcto y el programa es correcto. ¿Alguna vez necesitaré bloqueos en tales métodos? No.

Para ver un ejemplo de cómo se podría filtrar la implementación en un escenario de concurrencia, consulte aquí .

Robert Harvey
fuente
2
A menos que me equivoque, porque a Listes mutable, en la primera función que afirmó 'puro', otro hilo podría eliminar todos los elementos de la lista o agregar un montón más mientras está en el bucle foreach. No estoy seguro de cómo jugaría eso con el IEnumeratorser while(iter.MoveNext())editado, pero a menos que IEnumeratorsea ​​inmutable (dudoso), eso amenazaría con sacudir el bucle foreach.
Jimmy Hoffa
Es cierto que debe suponer que la colección nunca se escribe mientras los hilos leen. Esa sería una suposición válida, si cada hilo que llama al método construye su propia lista.
Robert Harvey
No creo que pueda llamarlo 'puro' cuando tiene ese objeto mutable que está usando como referencia. Si recibió un IEnumerable, es posible que pueda hacer ese reclamo porque no puede agregar o eliminar elementos de un IEnumerable, pero podría ser una Matriz o una Lista entregada como IEnumerable para que el contrato IEnumerable no garantice ningún formulario de pureza La verdadera técnica para hacer que esa función sea pura sería la inmutabilidad con paso por copia, C # no hace esto, por lo que tendría que copiar la Lista justo cuando la función la reciba; pero la única forma de hacerlo es con un foreach en él ...
Jimmy Hoffa
1
@JimmyHoffa: ¡Maldita sea, me tienes obsesionado con este problema de huevo y gallina! Si ve una solución en alguna parte, avíseme.
Robert Harvey
1
Acabo de encontrar esta respuesta ahora y es una de las mejores explicaciones sobre el tema que he encontrado, los ejemplos son muy concisos y realmente hacen que sea fácil de asimilar. ¡Gracias!
Stephen Byrne
4

No estoy seguro si entendí tus preguntas.

En mi humilde opinión la respuesta es sí. Si todos sus objetos son inmutables, entonces no necesita ningún candado. Pero si necesita preservar un estado (por ejemplo, si implementa una base de datos o si necesita agregar los resultados de varios subprocesos), entonces debe usar la mutabilidad y, por lo tanto, también los bloqueos. La inmutabilidad elimina la necesidad de bloqueos, pero generalmente no puede permitirse el lujo de tener aplicaciones completamente inmutables.

Respuesta a la parte 2: las cerraduras deben ser siempre más lentas que sin cerraduras.

Maros
fuente
3
La segunda parte es preguntar "¿Cuál es la compensación de rendimiento entre cerraduras y estructuras inmutables?" Probablemente merece su propia pregunta, incluso si es responsable.
Robert Harvey
4

Encapsular un conjunto de estados relacionados en una sola referencia mutable a un objeto inmutable puede hacer posible que muchos tipos de modificación de estado se realicen sin bloqueo utilizando el patrón:

do
{
   oldState = someObject.State;
   newState = oldState.WithSomeChanges();
} while (Interlocked.CompareExchange(ref someObject.State, newState, oldState) != oldState;

Si dos subprocesos intentan actualizarse someObject.statesimultáneamente, ambos objetos leerán el estado anterior y determinarán cuál sería el nuevo estado sin los cambios del otro. El primer subproceso para ejecutar CompareExchange almacenará lo que cree que debería ser el siguiente estado. El segundo subproceso encontrará que el estado ya no coincide con lo que había leído anteriormente y, por lo tanto, volverá a calcular el siguiente estado correcto del sistema con los cambios del primer subproceso en vigor.

Este patrón tiene la ventaja de que un hilo que se desvía no puede bloquear el progreso de otros hilos. Tiene la ventaja adicional de que incluso cuando hay una fuerte disputa, algún hilo siempre estará progresando. Sin embargo, tiene la desventaja de que, en presencia de contención, muchos hilos pueden pasar mucho tiempo haciendo trabajos que terminarán descartando. Por ejemplo, si 30 subprocesos en CPU separadas intentan cambiar un objeto simultáneamente, el uno tendrá éxito en su primer intento, uno en el segundo, uno en el tercero, etc., de modo que cada subproceso termine en promedio realizando aproximadamente 15 intentos para actualizar sus datos. El uso de un bloqueo "consultivo" puede mejorar las cosas significativamente: antes de que un hilo intente una actualización, debe verificar si se ha establecido un indicador de "contención". Si es así, debe adquirir un bloqueo antes de realizar la actualización. Si un hilo hace algunos intentos fallidos de una actualización, debe establecer el indicador de contención. Si un hilo que intenta adquirir el bloqueo encuentra que no había nadie más esperando, debería borrar el indicador de contención. Tenga en cuenta que el bloqueo aquí no es necesario para la "corrección"; el código funcionaría correctamente incluso sin él. El propósito del bloqueo es minimizar la cantidad de tiempo que el código dedica a operaciones que probablemente no tendrán éxito.

Super gato
fuente
4

Empiezas con

Claramente, la inmutabilidad minimiza la necesidad de bloqueos en la programación multiprocesador

Incorrecto. Debe leer detenidamente la documentación de cada clase que use. Por ejemplo, const std :: string en C ++ no es seguro para subprocesos. Los objetos inmutables pueden tener un estado interno que cambia al acceder a ellos.

Pero estás viendo esto desde un punto de vista totalmente equivocado. No importa si un objeto es inmutable o no, lo que importa es si lo cambia. Lo que está diciendo es como decir "si nunca toma un examen de manejo, nunca puede perder su licencia de conducir por conducir ebrio". Es cierto, pero más bien se pierde el punto.

Ahora, en el código de ejemplo, alguien escribió con una función llamada "ConcatenateWithCommas": Si la entrada fuera mutable y usaras un candado, ¿qué ganarías? Si alguien más intenta modificar la lista mientras intenta concatenar las cadenas, un bloqueo puede evitar que se bloquee. Pero aún no sabe si concatena las cadenas antes o después de que el otro hilo las haya cambiado. Entonces su resultado es bastante inútil. Tiene un problema que no está relacionado con el bloqueo y no se puede solucionar con el bloqueo. Pero luego, si usa objetos inmutables, y el otro hilo reemplaza todo el objeto por uno nuevo, está usando el objeto antiguo y no el nuevo, por lo que su resultado es inútil. Debe pensar en estos problemas en un nivel funcional real.

gnasher729
fuente
2
const std::stringes un mal ejemplo y un poco de arenque rojo. Las cadenas de C ++ son mutables y, de consttodos modos, no pueden garantizar la inmutabilidad. Todo lo que hace es decir que solo constse pueden llamar funciones. Sin embargo, esas funciones aún pueden alterar el estado interno y constpueden descartarse. Finalmente, existe el mismo problema que cualquier otro idioma: solo porque mi referencia es constno significa que tu referencia también lo sea. No, se debe utilizar una estructura de datos verdaderamente inmutable.