Hybrid Lock Implementation

Question

I have an algorithm that is painfully slow if I use 'pure' mutexes. That's because most of the critical sections are short and far shorter than the work to sleep a thread. However, it is also slower to allow the occasional long critical section cause long spins in other thread(s). This class is intended to provide a balance. The balance here is compile-time fixed. What would be interesting is an adaptive strategy for tuning the spin time.

#include <atomic>
#include <condition_variable>
#include <mutex>
///<summary>A hybrid lock making a number of spin attempts
///and then entering a wait before retrying.</summary>
///<remarks>Implemented to be interface swappable 
///with <code>std::mutex</code>.</remarks>
template<unsigned SPIN_LIMIT>
class hybrid_lock {
public:
    typedef unsigned spin_count_type;
    typedef void *native_handle_type;

    inline void lock() {
        spin_count_type limit(0);
        for (;;) {
            if (!this->mFlag.test_and_set(std::memory_order::memory_order_acquire)) {
                return;
            }
            if (limit >= SPIN_LIMIT) {
                break;
            }
            ++limit;
        }
        std::unique_lock<std::mutex> guard(this->mMutex);
        this->mCondition.wait(guard, [this]() { 
            return !this>mFlag.test_and_set(
               std::memory_order::memory_order_acquire
            ); 
        });
    }

    inline bool try_lock() {
        return !this->mFlag.test_and_set(
            std::memory_order::memory_order_acquire
        );
    }

    inline void unlock() {
        this->mFlag.clear(std::memory_order::memory_order_release);
        this->mCondition.notify_one();
    }

    ///<summary>Returns the address of the flag backing the lock.</summary>
    ///<remarks>The return value may not be compatible with
    ///<code>std::mutex</code>.</remarks>
    ///<returns>The address of the flag 
    ///backing the spin-lock.</returns>
    inline native_handle_type native_handle() {
        return static_cast<native_handle_type>(&this->mFlag);
    }

    inline hybrid_lock(void) {
        mFlag.clear();
    }
private:
    std::atomic_flag mFlag;//The actual lock object.
    std::mutex mMutex;//Used to synchronize sleeping threads.
    std::condition_variable mCondition;

    hybrid_lock(const hybrid_lock&) = delete;
    hybrid_lock& operator=(const hybrid_lock&) = delete;
};

Answer 1

I would expect the standard library's mutex (which is basically pthread_mutex) to already take care of this optimization behind the scenes, the same way these days I would expect the standard library's malloc to maintain its own thread-local arenas instead of taking a lock on every call.

Have you benchmarked the difference between what you wrote above and

template<unsigned SPIN_LIMIT>
class kiss_mutex {
    std::mutex mtx_;

  public:
    void lock() {
        for (unsigned i = 0; i < SPIN_LIMIT; ++i) {
            if (mtx_.try_lock()) return;
        }
        mtx_.lock();
    }

    bool try_lock() { return mtx_.try_lock(); }
    void unlock() { return mtx_.unlock(); }
};

? I haven't, but I'd be very curious to know whether kiss_mutex<N> performed comparably to std::mutex or comparably to hybrid_lock<N> (for tuneable values of N, of course).

---

Your benchmark might have been thrown off by a hilarious bug in hybrid_lock::lock():

    this->mCondition.wait(guard, [this]() { 
        return !this>mFlag.test_and_set(
           std::memory_order::memory_order_acquire
        ); 
    });

When you see it...

This is the funniest argument I've seen yet for suffixing data members with _ and never writing out this-> except where the grammar requires it. :)

---

Stylistically, your code seems pretty good. My nits:

• I would be extremely wary of declaring template non-type parameters of type unsigned int. My advice is to stick with int, because its name is short and because it's easy to write literals of that type. The only reason I stuck with unsigned in kiss_mutex is because if I didn't, it wouldn't have been a drop-in replacement for your code.

Here's the code showing why unsigned is worse than int: if someone sees hybrid_lock<100> they're probably going to assume that 100 represents an int (or at worst a size_t), and they're going to code accordingly, and their code simply will not work if you've used some other weird type. In other words, int is widely recognized as a vocabulary type (a "ubiquitous type used throughout the internal interfaces of a program"), whereas unsigned is not generally recognized as such. Of course, unsigned might be used as a vocabulary type in your codebase; it all depends on your employer's coding style guide. But I would hope it's not, for sanity's sake (again refer back to the code in the Wandbox above).

For another set of reasons that I mostly agree with, see Laurion Burchall's "unsigned considered harmful". Since you mentioned you've used Java, you might like this similarly titled blog post elsewhere, re Java, which makes some good points re "things C and C++ screwed up in their implementation of unsigned types."

• The thing you wrote is actually a mutex in C++ terms, not a lock; so it should be called hybrid_mutex. A mutex exposes imperative lock and unlock methods; a lock (for example, std::unique_lock) is a wrapper that hides lock and unlock under a protective layer of RAII. (In other words: If you're designing a drop-in replacement for std::mutex, it should almost certainly be named something_something_mutex.)

• In C++11, it is inappropriate to make any special member function private. If you want a special member function to go away, declare it =delete (which you did) but leave it public; this way, you're sure to get the error messages you want, instead of weird interference from the part of the compiler that checks access controls. "This constructor was explicitly deleted" is a much better error message than "This constructor is private and by the way it's been deleted too."

• The Rule of Zero: std::mutex is a non-copyable type, so merely having a member of type std::mutex suffices to implicitly delete your copy operations. It's redundant to declare them deleted; you can just rip out those lines, as I did in kiss_mutex.

• On the same note, I've never seen anyone use the inline keyword as you did, on member functions that are declared in-line and are thus implicitly inline anyway. Keep the code clean by removing redundant keywords. (Personally I make an exception for virtual, but my impression is that the C++ mainstream these days doesn't even make that exception. Indeed, as of 2021, I've completely converted to the Church of override, and no longer ever write virtual redundantly.)