Warum ist std :: mutex schneller als std :: atomic?

Question

Ich möchte Objekte in std::vector im Multi-Thread-Modus setzen. Also entschied ich mich, zwei Ansätze zu vergleichen: Der eine verwendet std::atomic und der andere std::mutex. Ich sehe, dass der zweite Ansatz schneller ist als der erste. Warum?

Ich benutze GCC 4.8.1 und, auf meinem Rechner (8 Threads), sehe ich, dass die erste Lösung 391502 Mikrosekunden benötigt und die zweite Lösung 175689 Mikrosekunden benötigt.

#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

Ich glaube nicht, Ihre Frage bezieht beantwortet werden können nur auf die Norm- mutexes sind plattformabhängig, wie sie sein können. Es gibt jedoch eine Sache, die erwähnt werden sollte.

Mutexe sind nicht langsam. Sie haben vielleicht einige Artikel gesehen, die ihre Leistung mit benutzerdefinierten Spinlocks und anderen "leichten" Sachen vergleichen, aber das ist nicht der richtige Ansatz - diese sind nicht austauschbar.

Spin Locks sind ziemlich schnell, wenn sie für eine relativ kurze Zeit gesperrt (erworben) werden - sie zu erwerben ist sehr billig, aber andere Threads, die auch versuchen zu sperren, sind diese ganze Zeit aktiv (läuft ständig in der Schleife).

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 ist eine primitive, dass viel komplizierter ist:

Individuelle Spin-Lock auf diese Weise werden könnten umgesetzt werden. Insbesondere unter Windows haben wir zwei solche Primitive - Critical Section, die auf Prozessbasis arbeiten, und Mutex, die keine solche Beschränkung haben.

Locking Mutex (oder kritischer Abschnitt) ist viel teurer, aber OS hat die Fähigkeit, andere wartende Threads wirklich zu "schlafen", was die Leistung verbessert und Aufgabenplaner in effizienter Ressourcenverwaltung hilft.

Warum schreibe ich das? Denn moderne Mutexe sind oft sogenannte "Hybrid-Mutexe". Wenn ein solcher Mutex gesperrt ist, verhält er sich wie eine normale Spin-Sperre - andere wartende Threads führen eine gewisse Anzahl von "Spins" aus und dann wird starker Mutex gesperrt, um zu verhindern, dass Ressourcen verschwendet werden.

In Ihrem Fall Mutex wird in jeder Schleife Iteration gesperrt diesen Befehl auszuführen:

second_result[counter] = omp_get_thread_num(); 

Es ist wie ein schnell man sieht, so "real" Mutex kann nie gesperrt werden. Das bedeutet, dass Ihr "Mutex" in diesem Fall so schnell sein kann wie eine Lösung auf atomarer Basis (weil es selbst eine atombasierte Lösung wird).

Auch in der ersten Lösung verwendeten Sie eine Art Spin-Lock-ähnliches Verhalten, aber ich bin mir nicht sicher, ob dieses Verhalten in Multi-Thread-Umgebung vorhersagbar ist. Ich bin mir ziemlich sicher, dass "Locking" sollte acquire Semantik haben, während die Entsperrung ist ein release op. Relaxed Speicherordnung möglicherweise für diesen Anwendungsfall zu schwach.

---

Ich bearbeitet den Code, um kompakter und richtig zu sein.Es verwendet die std::atomic_flag, die die einzige Art ist (im Gegensatz zu std::atomic<> Spezialisierungen), die garantiert frei sein wird (auch std::atomic<bool> gibt Ihnen das nicht).

Auch unter Bezugnahme auf den folgenden Kommentar über "nicht nachgeben": Es ist eine Frage von spezifischen Fall und Anforderungen. Spin-Locks sind ein sehr wichtiger Teil der Multi-Thread-Programmierung und ihre Leistung kann oft verbessert werden, indem das Verhalten leicht verändert wird. Boost-Bibliothek implementiert Zum Beispiel spinlock::lock() wie folgt:

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

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

Wo detail::yield() ist (Win32-Version):

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 
} 

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

Zuerst fädeln Sie Spins für eine bestimmte Anzahl von Malen (in diesem Fall 4). Wenn Mutex noch gesperrt ist, wird pause instruction is used (falls verfügbar) oder Sleep(0) aufgerufen, was im Grunde einen Kontextwechsel verursacht und es dem Scheduler ermöglicht, einem anderen blockierten Thread die Möglichkeit zu geben, etwas Nützliches zu tun. Dann wird Sleep(1) aufgerufen, um einen tatsächlichen (kurzen) Schlaf durchzuführen. Sehr schön!

Auch diese Aussage:

Der Zweck eines spinlock beschäftigt ist

warten ist nicht ganz richtig. Der Zweck von Spinlock ist es, als schnelles, einfach zu implementierendes Lock-Primitiv zu dienen - aber es muss immer noch richtig geschrieben werden, mit bestimmten möglichen Szenarien. Zum Beispiel Intel says (in Bezug auf Erhöhung der Verwendung von _mm_pause() als Verfahren zum Nachgeben innerhalb lock()):

Im Spin-Warteschleife, verbessert sich die Pause intrinsische die Geschwindigkeit, mit der der Code die Freigabe des Schlosses detektiert, und bietet vor allem erhebliche Leistungssteigerung.

So Implementierungen wie void lock() { while(m_flag.test_and_set(std::memory_order_acquire)); } kann nicht so gut sein, wie es scheint.