Locks vs Compare-and-swap

Question

Ho letto delle tecniche lock-free, come Confronta-e-swap e sfruttando le classi Interlocked e SpinWait per ottenere la sincronizzazione dei thread senza bloccare.

Ho eseguito alcuni test personali, in cui ho semplicemente molti thread che tentano di aggiungere un carattere a una stringa. Ho provato a utilizzare i normali lock e confrontare-e-swap. Sorprendentemente (almeno per me), i lucchetti hanno mostrato risultati molto migliori rispetto all'utilizzo di CAS.

Ecco la versione CAS del mio codice (basata su this). Si segue un modello della copia> Modifica-> swap:

private string _str = ""; 
    public void Append(char value) 
    { 
     var spin = new SpinWait(); 
     while (true) 
     { 
      var original = Interlocked.CompareExchange(ref _str, null, null); 

      var newString = original + value;     
      if (Interlocked.CompareExchange(ref _str, newString, original) == original) 
       break; 
      spin.SpinOnce(); 
     } 
    } 

E il più semplice (e più efficiente) versione di blocco:

private object lk = new object(); 
    public void AppendLock(char value) 
    { 
     lock (lk) 
     { 
      _str += value; 
     } 
    } 

Se provo l'aggiunta di 50.000 caratteri, la versione CAS prende 1,2 secondi e la versione di blocco 700ms (media). Per 100k caratteri, prendono rispettivamente 7 secondi e 3,8 secondi. Questo è stato eseguito su un quad-core (i5 2500k).

Avevo il sospetto che il motivo per cui CAS stava visualizzando questi risultati era dovuto al fatto che l'ultimo passaggio di "scambio" era fallito. Avevo ragione. Quando provo ad aggiungere 50k char (50k swap riusciti), sono riuscito a contare tra 70k (scenario del caso migliore) e quasi 200k (scenario peggiore) tentativi falliti. Nella peggiore delle ipotesi, 4 tentativi su 5 falliscono.

Quindi le mie domande sono:

1. Che cosa mi manca? CAS non dovrebbe dare risultati migliori? Dov'è il vantaggio?
2. Perché esattamente e quando CAS è un'opzione migliore? (So ​​che è stato chiesto questo, ma non riesco a trovare alcuna risposta soddisfacente che spiega anche il mio scenario specifico).

Sono a conoscenza del fatto che le soluzioni che utilizzano CAS, anche se difficili da codificare, si adattano molto meglio e funzionano meglio delle serrature al crescere della contesa. Nel mio esempio, le operazioni sono molto piccole e frequenti, il che significa alta contesa e alta frequenza. Allora perché i miei test mostrano il contrario?

Suppongo che operazioni più lunghe peggiorerebbero ulteriormente il caso -> il tasso di sostituzione "swap" aumenterebbe ancora di più.

PS: questo è il codice che ho usato per eseguire i test:

Stopwatch watch = Stopwatch.StartNew(); 
var cl = new Class1(); 
Parallel.For(0, 50000, i => cl.Append('a')); 

var time = watch.Elapsed; 
Debug.WriteLine(time.TotalMilliseconds); 

Answer 1

Il problema è una combinazione del tasso di guasto sul loop e il fatto che le stringhe no. Ho fatto un paio di test da solo utilizzando i seguenti parametri.

• Ha eseguito 8 thread diversi (ho una macchina a 8 core).
• Ogni thread chiamato Append 10.000 volte.

Quello che ho osservato è che la lunghezza finale della stringa era 80.000 (8 x 10.000), quindi era perfetta. Il numero di tentativi di aggiunta era in media ~ 300.000 per me. Quindi questo è un tasso di fallimento del ~ 73%. Solo il 27% del tempo della CPU ha dato risultati utili. Ora, poiché le stringhe sono immutabili, significa che viene creata una nuova istanza della stringa sull'heap e vengono copiati i contenuti originali più un carattere extra.A proposito, questa operazione di copia è O (n), quindi diventa sempre più lunga man mano che la lunghezza della corda aumenta. A causa dell'operazione di copia, la mia ipotesi era che il tasso di errore aumentasse all'aumentare della lunghezza della stringa. Il motivo è che, poiché l'operazione di copia richiede sempre più tempo, vi è una maggiore probabilità di collisione poiché i thread impiegano più tempo a competere per finalizzare l'ICX. I miei test lo hanno confermato. Dovresti provare tu stesso questo test.

Il problema maggiore qui è che le concatenazioni di stringhe sequenziali non si prestano molto bene al parallelismo. Poiché i risultati dell'operazione X _n dipendono da X _n-1, sarà più rapido prendere il blocco completo soprattutto se ciò significa che si evitano tutti i guasti e i tentativi. Una strategia pessimistica vince la battaglia contro un ottimista in questo caso. Le tecniche basse funzionano meglio quando è possibile suddividere il problema in mandrini indipendenti che possono funzionare senza impedimenti in parallelo.

Come nota a margine, l'uso di Interlocked.CompareExchange per eseguire la lettura iniziale di _str non è necessario. Il motivo è che in questo caso non è richiesta una barriera di memoria per la lettura. Questo perché la chiamata Interlocked.CompareExchange che esegue effettivamente il lavoro (la seconda nel codice) creerà una barriera completa. Quindi, lo scenario peggiore è che la prima lettura è "stantia", l'operazione ICX fallisce il test e il ciclo torna indietro per riprovare. Questa volta, tuttavia, la precedente ICX ha forzato una lettura "fresca".

Il seguente codice spiega come generalizzare un'operazione complessa utilizzando i meccanismi di blocco basso. In effetti, il codice presentato di seguito consente di passare un delegato che rappresenta l'operazione in modo che sia molto generalizzato. Vorresti usarlo in produzione? Probabilmente non perché invocare il delegato è lento, ma almeno tu hai l'idea. È sempre possibile codificare l'operazione.

public static class InterlockedEx 
{ 
    public static T Change<T>(ref T destination, Func<T, T> operation) where T : class 
    { 
    T original, value; 
    do 
    { 
     original = destination; 
     value = operation(original); 
    } 
    while (Interlocked.CompareExchange(ref destination, value, original) != original); 
    return original; 
    } 
} 

---

Io in realtà non amano i termini "stantio" e "fresco" quando si parla di barriere di memoria perché non è quello che sono veramente. È più un effetto collaterale rispetto alla garanzia reale. Ma, in questo caso, illustra meglio il mio punto.