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.

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.

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

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.

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.

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.