L'immutabilità elimina completamente la necessità di blocchi nella programmazione multiprocessore?

37

Parte 1

Chiaramente Immutabilità riduce al minimo la necessità di blocchi nella programmazione multiprocessore, ma elimina quella necessità, o ci sono casi in cui l'immutabilità da sola non è sufficiente? Mi sembra che si possa solo rinviare l'elaborazione e incapsulare lo stato così a lungo prima che la maggior parte dei programmi debba effettivamente fare qualcosa (aggiornare un archivio dati, produrre un report, lanciare un'eccezione, ecc.). Queste azioni possono essere sempre eseguite senza serrature? La semplice azione di buttare fuori ogni oggetto e crearne uno nuovo invece di modificare l'originale (una visione grossolana dell'immutabilità) fornisce una protezione assoluta dalla contesa tra processi, oppure ci sono casi angolari che richiedono ancora il blocco?

So che molti programmatori e matematici funzionali amano parlare di "nessun effetto collaterale" ma nel "mondo reale" tutto ha un effetto collaterale, anche se è il tempo necessario per eseguire un'istruzione della macchina. Sono interessato sia alla risposta teorico / accademico che alla risposta pratica / reale.

Se l'immutabilità è sicura, dati certi limiti o ipotesi, voglio sapere quali sono esattamente i confini della "zona di sicurezza". Alcuni esempi di possibili limiti:

  • I / O
  • Eccezioni / errori
  • Interazioni con programmi scritti in altre lingue
  • Interazioni con altre macchine (fisiche, virtuali o teoriche)

Un ringraziamento speciale a @JimmaHoffa per suo commento che ha dato inizio a questa domanda!

Parte 2

La programmazione multiprocessore è spesso utilizzata come tecnica di ottimizzazione - per far funzionare più codice più velocemente. Quando è più veloce utilizzare i blocchi rispetto agli oggetti immutabili?

Considerati i limiti stabiliti nella legge di Amdahl , quando è possibile ottenere prestazioni migliori (con o senza il garbage collector preso in considerazione) con oggetti immutabili rispetto a quelli bloccabili?

Sommario

Sto combinando queste due domande in una per cercare di capire dove si trova il riquadro di delimitazione per Immutability come soluzione ai problemi di threading.

    
posta GlenPeterson 24.10.2012 - 20:29
fonte

5 risposte

33

Questa è una domanda stranamente formulata che è davvero, davvero ampia se risponde pienamente. Mi concentrerò su chiarire alcune delle specifiche che stai chiedendo.

L'immutabilità è un compromesso progettuale. Rende alcune operazioni più difficili (modificando rapidamente lo stato negli oggetti di grandi dimensioni, costruendo oggetti frammentari, mantenendo uno stato di esecuzione, ecc.) A favore di altri (semplificazione del debug, ragionamento più semplice sul comportamento del programma, non doversi preoccupare di cose che cambiano sotto di te quando si lavora contemporaneamente, ecc.). È questo ultimo a cui ci preoccupiamo con questa domanda, ma voglio sottolineare che è uno strumento. Un buon strumento che risolve spesso più problemi di quanti ne causi (nella maggior parte dei moderni programmi), ma non un proiettile d'argento ... Non qualcosa che cambia il comportamento intrinseco dei programmi.

Ora, cosa ti prende? L'immutabilità ti dà una cosa: puoi leggere l'oggetto immutabile liberamente, senza preoccuparti del suo stato che cambia sotto di te (assumendo che sia veramente immutabile ... Avere un oggetto immutabile con membri mutabili è di solito un pestatore). Questo è tutto. Ti libera dalla necessità di gestire la concorrenza (tramite blocchi, istantanee, partizionamento dei dati o altri meccanismi, l'attenzione della domanda originale sui blocchi è ... Incorretta data la portata della domanda).

Si scopre però che molte cose leggono gli oggetti. L'IO sì, ma l'IO stesso tende a non gestire bene l'uso concorrente. Quasi tutte le elaborazioni lo fanno, ma altri oggetti potrebbero essere modificabili, oppure l'elaborazione stessa potrebbe utilizzare uno stato non amichevole per la concorrenza. Copiare un oggetto è un grande problema nascosto in alcune lingue poiché una copia completa è (quasi) mai un'operazione atomica. Questo è dove gli oggetti immutabili ti aiutano.

Per quanto riguarda le prestazioni, dipende dalla tua app. Le serrature sono (di solito) pesanti. Altri meccanismi di gestione della concorrenza sono più veloci ma hanno un strong impatto sulla progettazione. In generale , un design altamente concorrente che utilizza oggetti immutabili (ed evita i loro punti deboli) funzionerà meglio di un design altamente concorrente che blocca oggetti mutabili. Se il tuo programma è leggermente concorrente, dipende e / o non ha importanza.

Ma le prestazioni non dovrebbero essere la vostra più alta preoccupazione. Scrivere programmi concorrenti è difficile . Il debug di programmi concorrenti è difficile . Gli oggetti immutabili aiutano a migliorare la qualità del tuo programma eliminando le opportunità di errore nell'implementazione manuale della gestione della concorrenza. Rendono il debug più facile perché non stai cercando di tenere traccia dello stato in un programma concorrente. Rendono il tuo design più semplice e quindi rimuovono i bug lì.

Quindi riassumendo: l'immutabilità aiuta ma non elimina le sfide necessarie per gestire correttamente la concorrenza. Questo aiuto tende ad essere pervasivo, ma i maggiori guadagni derivano da una prospettiva di qualità piuttosto che dalle prestazioni. E no, l'immutabilità non ti scusa magicamente dalla gestione della concorrenza nella tua app, mi spiace.

    
risposta data 25.10.2012 - 00:51
fonte
11

Una funzione che accetta un valore e restituisce un altro valore, e non disturba nulla al di fuori della funzione, non ha effetti collaterali ed è quindi thread-safe. Se vuoi considerare cose come il modo in cui la funzione viene eseguita influisce sul consumo di energia, questo è un problema diverso.

Suppongo che tu ti stia riferendo a una macchina completa di Turing che sta eseguendo una sorta di linguaggio di programmazione ben definito, in cui i dettagli dell'implementazione sono irrilevanti. In altre parole, non dovrebbe importare cosa sta facendo la pila, se la funzione che sto scrivendo nel mio linguaggio di programmazione di scelta può garantire l'immutabilità entro i confini del linguaggio. Non penso allo stack quando sto programmando in un linguaggio di alto livello, né dovrei farlo.

Per illustrare come funziona, offrirò alcuni semplici esempi in C #. Affinché questi esempi siano veri, dobbiamo fare un paio di ipotesi. Innanzitutto, il compilatore segue le specifiche C # senza errori e, in secondo luogo, produce programmi corretti.

Diciamo che voglio una funzione semplice che accetta una collezione di stringhe e restituisce una stringa che è una concatenazione di tutte le stringhe nella collezione separate da virgole. Un'implementazione semplice e ingenua in C # potrebbe essere simile a questa:

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;
} 

Questo esempio è immutabile, prima facie. Come lo so? Perché l'oggetto string è immutabile. Tuttavia, l'implementazione non è l'ideale. Poiché result è immutabile, è necessario creare un nuovo oggetto stringa ogni volta attraverso il ciclo, sostituendo l'oggetto originale a cui result punta. Questo può influire negativamente sulla velocità e mettere pressione sul garbage collector, dato che deve ripulire tutte quelle stringhe extra.

Ora, diciamo che faccio questo:

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();
} 

Tieni presente che ho sostituito string result con un oggetto mutabile, StringBuilder . Questo è molto più veloce del primo esempio, perché una nuova stringa non viene creata ogni volta attraverso il ciclo. Invece, l'oggetto StringBuilder aggiunge semplicemente i caratteri di ogni stringa a una raccolta di caratteri e alla fine restituisce l'intero oggetto.

Questa funzione è immutabile, anche se StringBuilder è modificabile?

Sì, lo è. Perché? Poiché ogni volta che viene chiamata questa funzione, viene creato un nuovo StringBuilder, solo per quella chiamata. Quindi ora abbiamo una funzione pura che è sicura per i thread, ma contiene componenti mutabili.

Ma cosa succede se l'ho fatto?

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();
    } 
}

Questo metodo è sicuro per i thread? No, non lo è. Perché? Perché la classe ora ha uno stato da cui dipende il mio metodo. Nel metodo è presente una condizione di competizione: un thread può modificare IsFirst , ma un altro thread può eseguire il primo Append() , in nel qual caso ora ho una virgola all'inizio della mia stringa che non dovrebbe essere lì.

Perché potrei volerlo fare in questo modo? Bene, potrei volere che i thread accumulino le stringhe nel mio result senza riguardo all'ordine, o nell'ordine in cui i thread entrano. Forse è un logger, chissà?

Ad ogni modo, per risolvere il problema, ho inserito un'istruzione lock attorno alle parentesi del metodo.

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();
        }
    } 
}

Ora è sicuro per i thread di nuovo.

L'unico modo in cui i miei metodi immutabili potrebbero non riuscire a essere thread-safe è se il metodo in qualche modo perde parte della sua implementazione. Potrebbe succedere? Non se il compilatore è corretto e il programma è corretto. Avrò mai bisogno di serrature su questi metodi? No.

Per un esempio di come l'implementazione potrebbe essere trapelata in uno scenario di concorrenza, vedi qui .

    
risposta data 25.10.2012 - 06:25
fonte
3

Non sono sicuro di aver capito le tue domande.

IMHO la risposta è sì. Se tutti i tuoi oggetti sono immutabili, allora non hai bisogno di serrature. Ma se è necessario preservare uno stato (ad es. Si implementa un database o è necessario aggregare i risultati di più thread), allora è necessario utilizzare la mutabilità e quindi anche i blocchi. L'immutabilità elimina la necessità di serrature, ma di solito non puoi permetterti di avere applicazioni completamente immutabili.

Rispondi alla parte 2 - i blocchi dovrebbero essere sempre più lenti dei blocchi.

    
risposta data 24.10.2012 - 23:03
fonte
3

Inizi con

Chiaramente Immutabilità riduce al minimo la necessità di blocchi nella programmazione multiprocessore

sbagliato. È necessario leggere attentamente la documentazione per ogni classe che si utilizza. Ad esempio, const std :: string in C ++ è non thread safe. Gli oggetti immutabili possono avere uno stato interno che cambia quando li accedono.

Ma stai guardando questo da un punto di vista totalmente sbagliato. Non importa se un oggetto è immutabile o no, ciò che conta è se lo si cambia. Quello che dici è come dire "se non fai mai un test di guida, non puoi mai perdere la patente di guida per guida in stato di ebbrezza". Vero, ma piuttosto manca il punto.

Ora nel codice di esempio qualcuno ha scritto con una funzione chiamata "ConcatenateWithCommas": Se l'input era mutabile e hai usato un lock, cosa avresti ottenuto? Se qualcun altro tenta di modificare l'elenco mentre cerchi di concatenare le stringhe, un blocco può impedirti di andare in crash. Ma non sai ancora se si concatenano le stringhe prima o dopo che l'altro thread le ha modificate. Quindi il tuo risultato è piuttosto inutile. Hai un problema che non è legato al blocco e non può essere risolto con il blocco. Ma se usi oggetti immutabili e l'altro thread sostituisce l'intero oggetto con uno nuovo, stai usando il vecchio oggetto e non il nuovo oggetto, quindi il risultato è inutile. Devi pensare a questi problemi a un livello funzionale reale.

    
risposta data 18.03.2014 - 09:40
fonte
2

L'incapsulamento di un gruppo di stati correlati in un singolo riferimento mutabile a un oggetto immutabile può rendere possibile l'esecuzione di molti tipi di modifiche di stato senza blocco utilizzando il modello:

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

Se due thread tentano entrambi di aggiornare someObject.state contemporaneamente, entrambi gli oggetti leggeranno il vecchio stato e determineranno quale sarà il nuovo stato senza le modifiche reciproche. Il primo thread per eseguire CompareExchange memorizzerà ciò che pensa dovrebbe essere il prossimo stato. Il secondo thread scoprirà che lo stato non corrisponde più a quello che aveva letto in precedenza e quindi ricalcolerà lo stato successivo corretto del sistema con le modifiche apportate al primo thread.

Questo pattern ha il vantaggio che un thread che viene waylaid non può bloccare il progresso di altri thread. Ha l'ulteriore vantaggio che anche quando c'è una strong contesa, alcuni thread continueranno a fare progressi. Ha lo svantaggio, tuttavia, che in presenza di contese molte discussioni possono impiegare molto tempo a svolgere un lavoro che finiranno per scartare. Ad esempio, se 30 thread su CPU separate provano tutti a cambiare un oggetto simultaneamente, quello avrà successo al primo tentativo, uno al secondo, uno al terzo, ecc. In modo che ogni thread finisca in media per circa 15 tentativi per aggiornare i suoi dati. L'utilizzo di un blocco "advisory" può migliorare notevolmente le cose: prima che un thread tenti un aggiornamento, dovrebbe verificare se è impostato un indicatore di "contesa". In tal caso, dovrebbe acquisire un blocco prima di eseguire l'aggiornamento. Se un thread effettua alcuni tentativi non riusciti a un aggiornamento, dovrebbe impostare il flag di conflitto. Se un thread che tenta di acquisire il blocco trova che nessun altro è in attesa, dovrebbe cancellare il flag di conflitto. Si noti che il blocco qui non è richiesto per "correttezza"; il codice funzionerebbe correttamente anche senza di esso. Lo scopo del blocco è di ridurre al minimo la quantità di time code speso per operazioni che non hanno probabilità di successo.

    
risposta data 28.12.2013 - 19:53
fonte