Perché std :: mutex è più veloce di std :: atomic?

Question

Voglio mettere gli oggetti in std::vector in modalità multi-thread. Così ho deciso di confrontare due approcci: uno usa std::atomic e l'altro std::mutex. Vedo che il secondo approccio è più veloce del primo. Perché?

Utilizzo GCC 4.8.1 e, sulla mia macchina (8 thread), vedo che la prima soluzione richiede 391502 microsecondi e la seconda soluzione richiede 175689 microsecondi.

#include <vector> 
#include <omp.h> 
#include <atomic> 
#include <mutex> 
#include <iostream> 
#include <chrono> 

int main(int argc, char* argv[]) { 
    const size_t size = 1000000; 
    std::vector<int> first_result(size); 
    std::vector<int> second_result(size); 
    std::atomic<bool> sync(false); 

    { 
     auto start_time = std::chrono::high_resolution_clock::now(); 
     #pragma omp parallel for schedule(static, 1) 
     for (int counter = 0; counter < size; counter++) { 
      while(sync.exchange(true)) { 
       std::this_thread::yield(); 
      }; 
      first_result[counter] = counter; 
      sync.store(false) ; 
     } 
     auto end_time = std::chrono::high_resolution_clock::now(); 
     std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count() << std::endl; 
    } 

    { 
     auto start_time = std::chrono::high_resolution_clock::now(); 
     std::mutex mutex; 
     #pragma omp parallel for schedule(static, 1) 
     for (int counter = 0; counter < size; counter++) { 
      std::unique_lock<std::mutex> lock(mutex);  
      second_result[counter] = counter; 
     } 
     auto end_time = std::chrono::high_resolution_clock::now(); 
     std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count() << std::endl; 
    } 

    return 0; 
} 

Answer 1

Non credo che la tua domanda si può rispondere riferendo solo ai mutex-standard sono come dipendente dalla piattaforma in quanto possono essere. Tuttavia, c'è una cosa, che dovrebbe essere menzionata.

Mutex non sono lento. Potresti aver visto alcuni articoli, che confrontano le loro prestazioni con spin-lock personalizzati e altre cose "leggere", ma non è l'approccio giusto - non sono intercambiabili.

sono considerevolmente veloci, quando sono bloccati (acquisiti) per un periodo di tempo relativamente breve - acquisirli è molto economico, ma altri thread, che stanno anche cercando di bloccare, sono attivi per tutto questo tempo (correndo costantemente in loop).

su misura di spin-lock potrebbe essere implementato in questo modo:

class SpinLock 
{ 
private: 
    std::atomic_flag _lockFlag; 

public: 
    SpinLock() 
    : _lockFlag {ATOMIC_FLAG_INIT} 
    { } 

    void lock() 
    { 
     while(_lockFlag.test_and_set(std::memory_order_acquire)) 
     { } 
    } 

    bool try_lock() 
    { 
     return !_lockFlag.test_and_set(std::memory_order_acquire); 
    } 

    void unlock() 
    { 
     _lockFlag.clear(); 
    } 
}; 

Mutex è un primitivo, che è molto più complicato. In particolare, su Windows, abbiamo due primitive di questo tipo: Critical Section, che funziona in base al processo e Mutex, che non presenta tale limitazione.

Il mutex di blocco (o sezione critica) è molto più costoso, ma il sistema operativo ha la capacità di mettere realmente in attesa i thread in attesa, migliorando le prestazioni e aiutando lo scheduler delle attività nella gestione efficiente delle risorse.

Perché scrivo questo? Perché i mutex moderni sono spesso i cosiddetti "mutex ibridi". Quando tale mutex è bloccato, si comporta come un normale spin-lock - altri thread in attesa eseguono un certo numero di "spin" e quindi il mutex pesante viene bloccato per evitare sprechi di risorse.

Nel tuo caso, mutex è bloccato in ogni iterazione del ciclo per eseguire questa istruzione:

second_result[counter] = omp_get_thread_num(); 

Sembra un veloce uno, in modo "reale" mutex non può mai essere bloccato. Ciò significa che in questo caso il tuo "mutex" può essere veloce quanto una soluzione basata sull'atomica (perché diventa una soluzione basata sull'atomica stessa).

Inoltre, nella prima soluzione è stato utilizzato un tipo di comportamento simile a spin-lock, ma non sono sicuro che questo comportamento sia prevedibile in un ambiente a più thread. Sono abbastanza sicuro che quel "blocco" dovrebbe avere la semantica acquire, mentre lo sblocco è un release op. L'ordine di memoria Relaxed potrebbe essere troppo debole per questo caso d'uso.

---

Ho modificato il codice per essere più compatto e corretto.Utilizza lo std::atomic_flag, che è l'unico tipo (a differenza delle specializzazioni std::atomic<>), che è garantito per essere privo di blocco (anche lo std::atomic<bool> non lo fornisce).

Inoltre, facendo riferimento al commento seguente su "non cedere": si tratta di casi e requisiti specifici. I blocchi di rotazione sono una parte molto importante della programmazione multi-thread e le loro prestazioni possono essere spesso migliorate modificando leggermente il suo comportamento. Ad esempio, Boost attrezzi biblioteca spinlock::lock() come segue:

void lock() 
{ 
    for(unsigned k = 0; !try_lock(); ++k) 
    { 
     boost::detail::yield(k); 
    } 
} 

[fonte: http://www.boost.org/doc/libs/1_66_0/boost/smart_ptr/detail/spinlock_std_atomic.hpp]

Dove detail::yield() è (versione Win32):

inline void yield(unsigned k) 
{ 
    if(k < 4) 
    { 
    } 
#if defined(BOOST_SMT_PAUSE) 
    else if(k < 16) 
    { 
     BOOST_SMT_PAUSE 
    } 
#endif 
#if !BOOST_PLAT_WINDOWS_RUNTIME 
    else if(k < 32) 
    { 
     Sleep(0); 
    } 
    else 
    { 
     Sleep(1); 
    } 
#else 
    else 
    { 
     // Sleep isn't supported on the Windows Runtime. 
     std::this_thread::yield(); 
    } 
#endif 
} 

[fonte: http://www.boost.org/doc/libs/1_66_0/boost/smart_ptr/detail/yield_k.hpp]

In primo luogo, il thread gira per un numero fisso di volte (4 in questo caso). Se il mutex è ancora bloccato, viene chiamato pause instruction is used (se disponibile) o Sleep(0), che fondamentalmente causa il cambio di contesto e consente allo scheduler di fornire a un altro thread bloccato la possibilità di fare qualcosa di utile. Quindi, Sleep(1) viene chiamato per eseguire il sonno effettivo (breve). Molto bella!

Inoltre, questa dichiarazione:

Lo scopo di uno spinlock è occupato in attesa

non è del tutto vero. Lo spinlock ha lo scopo di fungere da primitivo blocco veloce e facile da implementare, ma deve ancora essere scritto correttamente, tenendo conto di alcuni possibili scenari. Ad esempio, Intel says (merito all'uso Boost di _mm_pause() come metodo di produrre all'interno lock()):

Nel ciclo di spin-attesa, l'intrinseca pausa migliora la velocità alla quale il codice rileva il rilascio della serratura e fornisce in particolare il guadagno significativo delle prestazioni di .

Così, implementazioni come void lock() { while(m_flag.test_and_set(std::memory_order_acquire)); } potrebbero non essere così buona come sembra.