Using Boost.Lockfree queue is slower than using mutexes

Question

Until now I was using std::queue in my project. I measured the average time which a specific operation on this queue requires.

The times were measured on 2 machines: My local Ubuntu VM and a remote server. Using std::queue, the average was almost the same on both machines: ~750 microseconds.

Then I "upgraded" the std::queue to boost::lockfree::spsc_queue, so I could get rid of the mutexes protecting the queue. On my local VM I could see a huge performance gain, the average is now on 200 microseconds. On the remote machine however, the average went up to 800 microseconds, which is slower than it was before.

First I thought this might be because the remote machine might not support the lock-free implementation:

From the Boost.Lockfree page:

Not all hardware supports the same set of atomic instructions. If it is not available in hardware, it can be emulated in software using guards. However this has the obvious drawback of losing the lock-free property.

To find out if these instructions are supported, boost::lockfree::queue has a method called bool is_lock_free(void) const;. However, boost::lockfree::spsc_queue does not have a function like this, which, for me, implies that it does not rely on the hardware and that is is always lockfree - on any machine.

What could be the reason for the performance loss?

---

Exmple code (Producer/Consumer)

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

Answer 1

Lock free algorithms generally perform more poorly than lock-based algorithms. That's a key reason they're not used nearly as frequently.

The problem with lock free algorithms is that they maximize contention by allowing contending threads to continue to contend. Locks avoid contention by de-scheduling contending threads. Lock free algorithms, to a first approximation, should only be used when it's not possible to de-schedule contending threads. That only rarely applies to application-level code.

Let me give you a very extreme hypothetical. Imagine four threads are running on a typical, modern dual-core CPU. Threads A1 and A2 are manipulating collection A. Threads B1 and B2 are manipulating collection B.

First, let's imagine the collection uses locks. That will mean that if threads A1 and A2 (or B1 and B2) try to run at the same time, one of them will get blocked by the lock. So, very quickly, one A thread and one B thread will be running. These threads will run very quickly and will not contend. Any time threads try to contend, the conflicting thread will get de-scheduled. Yay.

Now, imagine the collection uses no locks. Now, threads A1 and A2 can run at the same time. This will cause constant contention. Cache lines for the collection will ping-pong between the two cores. Inter-core buses may get saturated. Performance will be awful.

Again, this is highly exaggerated. But you get the idea. You want to avoid contention, not suffer through as much of it as possible.

However, now run this thought experiment again where A1 and A2 are the only threads on the entire system. Now, the lock free collection is probably better (though you may find that it's better just to have one thread in that case!).

Almost every programmer goes through a phase where they think that locks are bad and avoiding locks makes code go faster. Eventually, they realize that it's contention that makes things slow and locks, used correctly, minimize contention.