wake-up-neo.com

Die Verwendung der Boost.Lockfree-Warteschlange ist langsamer als die Verwendung von Mutexen

Bisher habe ich std::queue in meinem Projekt verwendet. Ich habe die durchschnittliche Zeit gemessen, die eine bestimmte Operation in dieser Warteschlange benötigt. 

Die Zeiten wurden auf zwei Rechnern gemessen: Mein lokales Ubuntu VM und ein Remote-Server . Mit std::queue war der Durchschnitt auf beiden Rechnern nahezu gleich: ~ 750 Mikrosekunden. 

Dann habe ich den std::queue auf boost::lockfree::spsc_queue "aktualisiert", um die Mutexe loszuwerden, die die Warteschlange schützen. Auf meinem lokalen VM konnte ich einen enormen Leistungszuwachs feststellen, der Durchschnitt liegt jetzt bei 200 Mikrosekunden. Auf der Remote-Maschine stieg der Durchschnitt jedoch auf 800 Mikrosekunden, was langsamer ist als zuvor. 

Zunächst dachte ich, dies könnte daran liegen, dass der Remote-Computer die lock-freie Implementierung möglicherweise nicht unterstützt:

Von der Boost.Lockfree-Seite:

Nicht alle Hardware unterstützt denselben Satz atomarer Anweisungen. Wenn es nicht in der Hardware verfügbar ist, kann es mithilfe von Guards in Software emuliert werden. Dies hat jedoch den offensichtlichen Nachteil, dass das schlossfreie Eigentum verloren geht.

Um herauszufinden, ob diese Anweisungen unterstützt werden, verfügt boost::lockfree::queue über eine Methode mit dem Namen bool is_lock_free(void) const;. boost::lockfree::spsc_queue hat jedoch keine solche Funktion, was für mich bedeutet, dass er nicht auf die Hardware angewiesen ist und dass diese Funktion immer auf einem beliebigen Computer gesperrt ist. 

Was könnte der Grund für den Leistungsverlust sein?


Beispielcode (Produzent/Verbraucher)

// c++11 compiler and boost library required

#include <iostream>
#include <cstdlib>
#include <chrono>
#include <async>
#include <thread>
/* Using blocking queue:
 * #include <mutex>
 * #include <queue>
 */
#include <boost/lockfree/spsc_queue.hpp>


boost::lockfree::spsc_queue<int, boost::lockfree::capacity<1024>> queue;

/* Using blocking queue:
 * std::queue<int> queue;
 * std::mutex mutex;
 */

int main()
{
    auto producer = std::async(std::launch::async, [queue /*,mutex*/]() 
    {
        // Producing data in a random interval
        while(true)
        {
            /* Using the blocking queue, the mutex must be locked here.
             * mutex.lock();
             */

            // Push random int (0-9999)
            queue.Push(std::Rand() % 10000);

            /* Using the blocking queue, the mutex must be unlocked here.
             * mutex.unlock();
             */

            // Sleep for random duration (0-999 microseconds)
            std::this_thread::sleep_for(std::chrono::microseconds(Rand() % 1000));
        }
    }

    auto consumer = std::async(std::launch::async, [queue /*,mutex*/]() 
    {
        // Example operation on the queue.
        // Checks if 1234 was generated by the producer, returns if found.

        while(true)
        {
            /* Using the blocking queue, the mutex must be locked here.
             * mutex.lock();
             */

            int value;
            while(queue.pop(value)
            {
                if(value == 1234)
                    return;
            }

            /* Using the blocking queue, the mutex must be unlocked here.
             * mutex.unlock();
             */

            // Sleep for 100 microseconds
            std::this_thread::sleep_for(std::chrono::microseconds(100));
        }
    }

    consumer.get();
    std::cout << "1234 was generated!" << std::endl;
    return 0;
}
32
thesys

Lock-free-Algorithmen sind im Allgemeinen schlechter als Lock-basierte Algorithmen. Das ist ein wichtiger Grund, warum sie nicht so häufig verwendet werden.

Das Problem bei Lock-Free-Algorithmen besteht darin, dass sie die Konkurrenz maximieren, indem sie es zulassenden Threads zulässt, weiter zu konkurrieren. Sperren vermeiden Konflikte, indem konkurrierende Threads terminiert werden. Lock-free-Algorithmen sollten in erster Näherung nur verwendet werden, wenn es nicht möglich ist, konkurrierende Threads zu terminieren. Dies gilt nur selten für Code auf Anwendungsebene.

Lassen Sie mich eine sehr extreme Hypothese geben. Stellen Sie sich vor, vier Threads laufen auf einer typischen, modernen Dual-Core-CPU. Die Threads A1 und A2 manipulieren die Sammlung A. Die Threads B1 und B2 manipulieren die Sammlung B.

Stellen wir uns zunächst vor, dass die Sammlung Sperren verwendet. Das bedeutet, dass, wenn die Threads A1 und A2 (oder B1 und B2) gleichzeitig laufen sollen, einer von ihnen durch die Sperre blockiert wird. Sehr schnell laufen also ein A-Thread und ein B-Thread. Diese Threads werden sehr schnell ausgeführt und konkurrieren nicht. Jedes Mal, wenn Threads zu streiten versuchen, wird der in Konflikt stehende Thread abgemeldet. Yay.

Stellen Sie sich vor, die Sammlung verwendet keine Sperren. Jetzt können die Threads A1 und A2 gleichzeitig ausgeführt werden. Dies führt zu ständigen Konflikten. Cache-Zeilen für die Sammlung werden Ping-Pong zwischen den beiden Kernen. Intercore-Busse können gesättigt sein. Leistung wird schrecklich sein.

Dies ist wiederum stark übertrieben. Aber du hast die Idee. Sie wollen Konflikte vermeiden, nicht so viel wie möglich darunter leiden.

Führen Sie nun dieses Gedankenexperiment erneut aus, wobei A1 und A2 die einzigen Threads im Gesamtsystem sind. Nun ist die lock-free-Sammlung wahrscheinlich besser (obwohl Sie vielleicht feststellen, dass es in diesem Fall besser ist, nur einen Thread zu haben!).

Fast jeder Programmierer durchläuft eine Phase, in der er der Meinung ist, dass Sperren schlecht sind, und wenn Sperren vermieden werden, wird der Code schneller. Schließlich erkennen sie, dass es contention ist, das die Dinge langsamer macht und Sperren verursacht, wenn sie richtig verwendet werden und Konflikte minimieren.

88
David Schwartz

Ich kann nicht sagen, dass die Lock-Free-Warteschlange in allen möglichen Fällen langsamer ist. Nach meiner Erfahrung versucht der Push (const T & item), eine Kopie zu erstellen. Wenn Sie TMP-Objekte erstellen und in die Warteschlange verschieben, werden Sie von einer Leistungsverschiebung getroffen. Ich denke, die Bibliothek benötigt nur die überladene Version Push (T && item), um bewegliche Objekte effizienter zu machen. Vor dem Hinzufügen der neuen Funktion müssen Sie möglicherweise Zeiger, den einfachen Typ oder die nach C++ 11 angebotenen intelligenten Zeiger verwenden. Dies ist ein eher begrenzter Aspekt der Warteschlange, und ich verwende nur die sperrenfreie Warteschlange, die selten variiert. 

0
Kemin Zhou