Compiler Explorer

Source code

#include <mutex>
#include <thread>
#include <list>

#include "benchmark/benchmark.h"
#include <algorithm>
#include <chrono>
#include <array>
#include <condition_variable>
#include <shared_mutex>
#include <atomic>
#include <cstring>
#include <emmintrin.h>
#include <numeric>
#include <random>
#include <deque>
#ifdef _WIN32
#include <intrin.h>
#pragma intrinsic(_umul128)
//#define NOMINMAX
#define WIN32_LEAN_AND_MEAN 1
#include <Windows.h>
#else
#include <semaphore.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <linux/futex.h>
#include <pthread.h>
#endif

// todo: try WTF lock (aka parking lot)

inline void futex_wait(std::atomic<uint32_t> &to_wait_on, uint32_t expected)
{
#ifdef _WIN32
    WaitOnAddress(&to_wait_on, &expected, sizeof(expected), INFINITE);
#else
	syscall(SYS_futex, &to_wait_on, FUTEX_WAIT_PRIVATE, expected, nullptr, nullptr, 0);
#endif
}
template<typename T>
inline void futex_wake_single(std::atomic<T> &to_wake)
{
#ifdef _WIN32
    WakeByAddressSingle(&to_wake);
#else
	syscall(SYS_futex, &to_wake, FUTEX_WAKE_PRIVATE, 1, nullptr, nullptr, 0);
#endif
}
template<typename T>
inline void futex_wake_all(std::atomic<T> &to_wake)
{
#ifdef _WIN32
    WakeByAddressAll(&to_wake);
#else
	syscall(SYS_futex, &to_wake, FUTEX_WAKE_PRIVATE, std::numeric_limits<int>::max(), nullptr, nullptr, 0);
#endif
}

struct ticket_mutex
{
    void lock()
    {
        unsigned my = in.fetch_add(1);
        for (;;)
        {
            unsigned now = out;
            if (my == now)
                break;
            futex_wait(out, now);
        }
    }
    void unlock()
    {
        unsigned new_value = out.fetch_add(1) + 1;
        if (new_value != in)
            futex_wake_all(out);
    }

private:
    std::atomic<uint32_t> in
    { 0 };
    std::atomic<uint32_t> out
    { 0 };
};

struct ticket_spinlock
{
    void lock()
    {
        unsigned my = in.fetch_add(1, std::memory_order_relaxed);
        for (int spin_count = 0; out.load(std::memory_order_acquire) != my;
                ++spin_count)
        {
            if (spin_count < 16)
                _mm_pause();
            else
            {
                std::this_thread::yield();
                spin_count = 0;
            }
        }
    }
    void unlock()
    {
        out.store(out.load(std::memory_order_relaxed) + 1,
                std::memory_order_release);
    }

private:
    std::atomic<unsigned> in
    { 0 };
    std::atomic<unsigned> out
    { 0 };
};

#ifdef _WIN32
struct critical_section
{
    critical_section()
    {
        InitializeCriticalSection(&cs);
    }
    ~critical_section()
    {
        DeleteCriticalSection(&cs);
    }
    void lock()
    {
        EnterCriticalSection(&cs);
    }
    void unlock()
    {
        LeaveCriticalSection(&cs);
    }

private:
    CRITICAL_SECTION cs;
};

struct critical_section_spin
{
    critical_section_spin()
    {
        InitializeCriticalSectionAndSpinCount(&cs, 4000);
    }
    ~critical_section_spin()
    {
        DeleteCriticalSection(&cs);
    }
    void lock()
    {
        EnterCriticalSection(&cs);
    }
    void unlock()
    {
        LeaveCriticalSection(&cs);
    }

private:
    CRITICAL_SECTION cs;
};

struct srw_lock
{
    void lock()
    {
        AcquireSRWLockExclusive(&l);
    }
    void unlock()
    {
        ReleaseSRWLockExclusive(&l);
    }

private:
    SRWLOCK l = SRWLOCK_INIT;
};
#else
struct pthread_mutex
{
	~pthread_mutex()
	{
		pthread_mutex_destroy(&mutex);
	}

void lock()
	{
		pthread_mutex_lock(&mutex);
	}
	void unlock()
	{
		pthread_mutex_unlock(&mutex);
	}

private:
	pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
};
struct pthread_mutex_recursive
{
	~pthread_mutex_recursive()
	{
		pthread_mutex_destroy(&mutex);
	}

void lock()
	{
		pthread_mutex_lock(&mutex);
	}
	void unlock()
	{
		pthread_mutex_unlock(&mutex);
	}

private:
	pthread_mutex_t mutex = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP;
};
struct pthread_mutex_adaptive
{
	~pthread_mutex_adaptive()
	{
		pthread_mutex_destroy(&mutex);
	}

void lock()
	{
		pthread_mutex_lock(&mutex);
	}
	void unlock()
	{
		pthread_mutex_unlock(&mutex);
	}

private:
	pthread_mutex_t mutex = PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP;
};
#endif

struct futex_mutex
{
    void lock()
    {
        if (state.exchange(locked, std::memory_order_acquire) == unlocked)
            return;
        while (state.exchange(sleeper, std::memory_order_acquire) != unlocked)
        {
            futex_wait(state, sleeper);
        }
    }
    void unlock()
    {
        if (state.exchange(unlocked, std::memory_order_release) == sleeper)
            futex_wake_single(state);
    }

private:
    std::atomic<uint32_t> state
    { unlocked };

static constexpr uint32_t unlocked = 0;
    static constexpr uint32_t locked = 1;
    static constexpr uint32_t sleeper = 2;
};

struct spin_to_futex_mutex
{
    void lock()
    {
        unsigned old_state = unlocked;
        if (state.compare_exchange_strong(old_state, locked,
                std::memory_order_acquire))
            return;
        for (;;)
        {
            old_state = state.exchange(sleeper, std::memory_order_acquire);
            if (old_state == unlocked)
                return;
            else if (old_state == locked)
            {
                for (;;)
                {
                    _mm_pause();
                    if (state.load(std::memory_order_acquire) == unlocked)
                        break;
                    std::this_thread::yield();
                    if (state.load(std::memory_order_acquire) == unlocked)
                        break;
                }
            }
            else
                futex_wait(state, sleeper);
        }
    }
    void unlock()
    {
        unsigned old_state = state.load(std::memory_order_relaxed);
        state.store(unlocked, std::memory_order_release);
        if (old_state == sleeper)
            futex_wake_single(state);
    }

private:
    std::atomic<unsigned> state
    { unlocked };
    static constexpr unsigned unlocked = 0;
    static constexpr unsigned locked = 1;
    static constexpr unsigned sleeper = 2;
};

#ifdef _WIN32

struct semaphore
{
    semaphore() :
            semaphore(0)
    {
    }
    explicit semaphore(LONG initial_amount) :
            windows_semaphore(
                    CreateSemaphoreA(nullptr, initial_amount,
                            std::numeric_limits<LONG>::max(), nullptr))
    {
    }
    ~semaphore()
    {
        CloseHandle(windows_semaphore);
    }
    void acquire()
    {
        WaitForSingleObject(windows_semaphore, INFINITE);
    }
    void release(ptrdiff_t update = 1)
    {
        ReleaseSemaphore(windows_semaphore, static_cast<LONG>(update), nullptr);
    }

private:
    HANDLE windows_semaphore
    { 0 };
};

#else

struct semaphore
{
	semaphore()
		: semaphore(0)
	{
	}
	explicit semaphore(std::ptrdiff_t value)
	{
		sem_init(&sem, false, value);
	}
	~semaphore()
	{
		sem_destroy(&sem);
	}
	void release()
	{
		int result = sem_post(&sem);
		assert(!result); static_cast<void>(result);
	}
	void release(ptrdiff_t update)
	{
		for (; update > 0; --update)
		{
			release();
		}
	}

void acquire()
	{
		while (sem_wait(&sem))
		{
			assert(errno == EINTR);
		}
	}

private:
	sem_t sem;
};
#endif

struct semaphore_custom
{
private:
    std::mutex mutex;
    std::condition_variable condition;
    std::ptrdiff_t count = 0;

public:
    explicit semaphore_custom(ptrdiff_t desired = 0) :
            count(desired)
    {
    }

void release()
    {
        {
            std::lock_guard<std::mutex> lock(mutex);
            ++count;
        }
        condition.notify_one();
    }
    void release(ptrdiff_t update)
    {
        {
            std::lock_guard<std::mutex> lock(mutex);
            count += update;
        }
        condition.notify_all();
    }

void acquire()
    {
        std::unique_lock<std::mutex> lock(mutex);
        while (!count)
            condition.wait(lock);
        --count;
    }
};

struct semaphore_mutex
{
    void lock()
    {
        sema.acquire();
    }
    void unlock()
    {
        sema.release();
    }
private:
    semaphore sema
    { 1 };
};

struct terrible_spinlock
{
    void lock()
    {
        while (locked.test_and_set(std::memory_order_acquire))
        {
        }
    }
    void unlock()
    {
        locked.clear(std::memory_order_release);
    }

private:
    std::atomic_flag locked = ATOMIC_FLAG_INIT;
};
struct spinlock_test_and_set
{
    void lock()
    {
        for (;;)
        {
            if (try_lock())
                break;
            _mm_pause();
            if (try_lock())
                break;
            std::this_thread::yield();
        }
    }
    bool try_lock()
    {
        return !locked.test_and_set(std::memory_order_acquire);
    }
    void unlock()
    {
        locked.clear(std::memory_order_release);
    }

private:
    std::atomic_flag locked = ATOMIC_FLAG_INIT;
};
struct spinlock_test_and_set_once
{
    void lock()
    {
        for (;;)
        {
            if (!locked.exchange(true, std::memory_order_acquire))
                break;
            for (;;)
            {
                _mm_pause();
                if (!locked.load(std::memory_order_acquire))
                    break;
                std::this_thread::yield();
                if (!locked.load(std::memory_order_acquire))
                    break;
            }
        }
    }
    bool try_lock()
    {
        return !locked.load(std::memory_order_acquire)
                && !locked.exchange(true, std::memory_order_acquire);
    }
    void unlock()
    {
        locked.store(false, std::memory_order_release);
    }

private:
    std::atomic<bool> locked
    { false };
};
struct spinlock_compare_exchange
{
    void lock()
    {
        for (;;)
        {
            bool unlocked = false;
            if (locked.compare_exchange_weak(unlocked, true,
                    std::memory_order_acquire))
                break;
            for (;;)
            {
                _mm_pause();
                if (!locked.load(std::memory_order_acquire))
                    break;
                std::this_thread::yield();
                if (!locked.load(std::memory_order_acquire))
                    break;
            }
        }
    }
    bool try_lock()
    {
        return !locked.load(std::memory_order_acquire)
                && !locked.exchange(true, std::memory_order_acquire);
    }
    void unlock()
    {
        locked.store(false, std::memory_order_release);
    }

private:
    std::atomic<bool> locked
    { false };
};
struct spinlock_compare_exchange_only
{
    void lock()
    {
        for (;;)
        {
            if (try_lock())
                break;
            _mm_pause();
            if (try_lock())
                break;
            std::this_thread::yield();
        }
    }
    bool try_lock()
    {
        bool unlocked = false;
        return locked.compare_exchange_weak(unlocked, true,
                std::memory_order_acquire);
    }
    void unlock()
    {
        locked.store(false, std::memory_order_release);
    }

private:
    std::atomic<bool> locked
    { false };
};

struct spinlock_amd
{
    void lock()
    {
        for (;;)
        {
            bool was_locked = locked.load(std::memory_order_relaxed);
            if (!was_locked
                    && locked.compare_exchange_weak(was_locked, true,
                            std::memory_order_acquire))
                break;
            _mm_pause();
        }
    }
    void unlock()
    {
        locked.store(false, std::memory_order_release);
    }

private:
    std::atomic<bool> locked
    { false };
};

struct spinlock
{
    void lock()
    {
        for (int spin_count = 0; !try_lock(); ++spin_count)
        {
            if (spin_count < 16)
                _mm_pause();
            else
            {
                std::this_thread::yield();
                spin_count = 0;
            }
        }
    }
    bool try_lock()
    {
        return !locked.load(std::memory_order_relaxed)
                && !locked.exchange(true, std::memory_order_acquire);
    }
    void unlock()
    {
        locked.store(false, std::memory_order_release);
    }

private:
    std::atomic<bool> locked
    { false };
};

template<int SpinNoOpCount, int SpinPauseCount, bool ResetCountAfterYield>
struct parameterized_spinlock
{
    void lock()
    {
        int spin_count = 0;
        auto on_spin = [&]
        {
            if constexpr (SpinNoOpCount > 0)
            {
                if (SpinNoOpCount == std::numeric_limits<int>::max() || spin_count < SpinNoOpCount)
                return;
            }
            if constexpr (SpinNoOpCount != std::numeric_limits<int>::max() && SpinPauseCount > 0)
            {
                if (SpinPauseCount == std::numeric_limits<int>::max() || spin_count < SpinPauseCount)
                {
                    _mm_pause();
                    return;
                }
            }
            if constexpr (SpinNoOpCount != std::numeric_limits<int>::max() && SpinPauseCount != std::numeric_limits<int>::max())
            {
                std::this_thread::yield();
                if constexpr (ResetCountAfterYield)
                spin_count = 0;
            }
        };
        for (;;)
        {
            bool expected = false;
            if (locked.compare_exchange_weak(expected, true,
                    std::memory_order_acquire))
                return;
            for (;; ++spin_count)
            {
                on_spin();
                if (!locked.load(std::memory_order_acquire))
                    break;
            }
        }
    }
    bool try_lock()
    {
        bool expected = false;
        return locked.compare_exchange_strong(expected, true,
                std::memory_order_acquire);
    }
    void unlock()
    {
        locked.store(false, std::memory_order_release);
    }

private:
    std::atomic<bool> locked
    { false };
};

template<typename T>
void benchmark_mutex_lock_unlock(benchmark::State &state)
{
    static T m;
    while (state.KeepRunning())
    {
        m.lock();
        m.unlock();
    }
}

#ifdef _WIN32
#define RegisterBenchmarkWithWindowsMutexes(benchmark, ...)\
    BENCHMARK_TEMPLATE(benchmark, critical_section) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, critical_section_spin) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, srw_lock) __VA_ARGS__;
#define RegisterBenchmarkWithPthreadMutexes(benchmark, ...)
#else
#define RegisterBenchmarkWithWindowsMutexes(benchmark, ...)
#define RegisterBenchmarkWithPthreadMutexes(benchmark, ...)\
    BENCHMARK_TEMPLATE(benchmark, pthread_mutex) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, pthread_mutex_recursive) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, pthread_mutex_adaptive) __VA_ARGS__;
#endif

#define RegisterBenchmarkWithAllMutexes(benchmark, ...)\
    BENCHMARK_TEMPLATE(benchmark, std::mutex) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, std::shared_mutex) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, std::recursive_mutex) __VA_ARGS__;\
    RegisterBenchmarkWithWindowsMutexes(benchmark, __VA_ARGS__);\
    RegisterBenchmarkWithPthreadMutexes(benchmark, __VA_ARGS__);\
    BENCHMARK_TEMPLATE(benchmark, futex_mutex) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, spin_to_futex_mutex) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, ticket_spinlock) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, ticket_mutex) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, semaphore_mutex) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, spinlock) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, spinlock_amd) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, spinlock_test_and_set) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, spinlock_test_and_set_once) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, spinlock_compare_exchange) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, spinlock_compare_exchange_only) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, terrible_spinlock) __VA_ARGS__;\
    /*BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<0, 0>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<0, 1>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<0, 4>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<0, 16>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<0, 64>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<0, 256>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<1, 1>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<1, 4>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<1, 16>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<1, 64>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<1, 256>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<4, 4>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<4, 16>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<4, 64>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<4, 256>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<16, 16>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<16, 64>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<16, 256>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<64, 64>) __VA_ARGS__;\
    BENCHMARK_TEMPLATE(benchmark, parameterized_spinlock<64, 256>) __VA_ARGS__;*/\

RegisterBenchmarkWithAllMutexes(benchmark_mutex_lock_unlock,->Threads(1)->ThreadPerCpu());

void benchmark_shared_mutex_lock_shared(benchmark::State &state)
{
    static std::shared_mutex m;
    while (state.KeepRunning())
    {
        m.lock_shared();
        m.unlock_shared();
    }
}
BENCHMARK(benchmark_shared_mutex_lock_shared);

void benchmark_semaphore_release_and_acquire(benchmark::State &state)
{
    static semaphore m;
    while (state.KeepRunning())
    {
        m.release();
        m.acquire();
    }
}
BENCHMARK(benchmark_semaphore_release_and_acquire);

void benchmark_custom_semaphore_release_and_acquire(benchmark::State &state)
{
    static semaphore_custom m;
    while (state.KeepRunning())
    {
        m.release();
        m.acquire();
    }
}
BENCHMARK(benchmark_custom_semaphore_release_and_acquire);

template<typename State>
struct ThreadedBenchmarkRunner
{
    ThreadedBenchmarkRunner(State *state, int num_threads) :
            state(state)
    {
        threads.reserve(num_threads);
        for (int i = 0; i < num_threads; ++i)
        {
            threads.emplace_back([this, state, i]
            {
                finished.release();
                for (;;)
                {
                    all_started_sema.acquire();
                    if (ended)
                    break;
                    state->run_benchmark(i);
                    finished.release();
                }
            });
        }
        for (size_t i = threads.size(); i > 0; --i)
            finished.acquire();
    }

void wait_until_started()
    {
        state->start_run();
    }
    void release()
    {
        all_started_sema.release(threads.size());
    }
    void wait_until_finished()
    {
        for (size_t i = threads.size(); i > 0; --i)
            finished.acquire();
        state->end_run();
    }

void full_run()
    {
        wait_until_started();
        release();
        wait_until_finished();
    }

void shut_down()
    {
        ended = true;
        all_started_sema.release(threads.size());
        for (std::thread &thread : threads)
            thread.join();
    }

private:
    State *state;
    std::vector<std::thread> threads;
    semaphore all_started_sema;
    semaphore finished;
    bool ended = false;
};

template<typename State>
struct ThreadedBenchmarkRunnerMultipleTimes
{
    template<typename ... StateArgs>
    ThreadedBenchmarkRunnerMultipleTimes(int num_runners, int num_threads,
            StateArgs &&... state_args)
    {
        for (int i = 0; i < num_runners; ++i)
        {
            runners.emplace_back(num_threads, state_args...);
        }
    }

void wait_until_started()
    {
        for (OneRunnerAndState &runner : runners)
            runner.runner.wait_until_started();
    }

void start_run()
    {
        for (OneRunnerAndState &runner : runners)
            runner.runner.release();
    }

void finish_run()
    {
        for (OneRunnerAndState &runner : runners)
            runner.runner.wait_until_finished();
    }

void full_run()
    {
        wait_until_started();
        start_run();
        finish_run();
    }

void shut_down()
    {
        for (OneRunnerAndState &runner : runners)
            runner.runner.shut_down();
    }

struct OneRunnerAndState
    {
        State state;
        ThreadedBenchmarkRunner<State> runner;

template<typename ... StateArgs>
        OneRunnerAndState(int num_threads, StateArgs &&... state_args) :
                state(num_threads, std::forward<StateArgs>(state_args)...), runner(
                        &state, num_threads)
        {
        }
    };
    std::list<OneRunnerAndState> runners;
};

template<typename T>
struct ContendedMutexRunner
{
    size_t num_loops = 1;
    size_t sum = 0;
    size_t expected_sum;
    T mutex;

explicit ContendedMutexRunner(int num_threads, size_t num_loops) :
            num_loops(num_loops), expected_sum(num_threads * num_loops)
    {
    }

void start_run()
    {
        sum = 0;
    }
    void end_run()
    {
        assert(sum == expected_sum);
    }

void run_benchmark(int)
    {
        for (size_t i = num_loops; i != 0; --i)
        {
            mutex.lock();
            ++sum;
            mutex.unlock();
        }
    }
};
template<typename T>
struct ContendedMutexRunnerSized
{
    size_t num_loops = 1;
    std::vector<size_t> sums;
    size_t expected_sum;
    T mutex;

explicit ContendedMutexRunnerSized(int num_threads, size_t num_loops,
            size_t num_sums) :
            num_loops(num_loops), sums(num_sums), expected_sum(
                    num_threads * num_loops)
    {
    }

void start_run()
    {
        for (size_t &sum : sums)
            sum = 0;
    }
    void end_run()
    {
        assert(sums.front() == expected_sum);
    }

void run_benchmark(int)
    {
        for (size_t i = num_loops; i != 0; --i)
        {
            mutex.lock();
            for (size_t &sum : sums)
                ++sum;
            mutex.unlock();
        }
    }
};

#ifdef _WIN32
template<typename Randomness>
uint64_t UniformRandom(uint64_t max, Randomness &random)
{
    static_assert(Randomness::min() == 0 && Randomness::max() == std::numeric_limits<uint64_t>::max());
    uint64_t random_value = random();
    if (max == std::numeric_limits<uint64_t>::max())
        return random_value;
    ++max;
    uint64_t high_bits;
    uint64_t lower_bits = _umul128(random_value, max, &high_bits);
    if (lower_bits < max)
    {
        uint64_t threshold = -max % max;
        while (lower_bits < threshold)
        {
            random_value = random();
            uint64_t lower_bits = _umul128(random_value, max, &high_bits);
        }
    }
    return high_bits;
}
#else
template<typename Randomness>
uint64_t UniformRandom(uint64_t max, Randomness& random)
{
	static_assert(Randomness::min() == 0 && Randomness::max() == std::numeric_limits<uint64_t>::max());
	uint64_t random_value = random();
	if (max == std::numeric_limits<uint64_t>::max())
		return random_value;
	++max;
	__uint128_t to_range = static_cast<__uint128_t>(random_value)* static_cast<__uint128_t>(max);
	uint64_t lower_bits = static_cast<uint64_t>(to_range);
	if (lower_bits < max)
	{
		uint64_t threshold = -max % max;
		while (lower_bits < threshold)
		{
			random_value = random();
			to_range = static_cast<__uint128_t>(random_value)* static_cast<__uint128_t>(max);
			lower_bits = static_cast<uint64_t>(to_range);
		}
	}
	return static_cast<uint64_t>(to_range >> 64);
}
#endif

template<typename T>
struct ManyContendedMutexRunner
{
    struct OneMutexAndState
    {
        explicit OneMutexAndState(size_t num_sums) :
                sums(num_sums)
        {
        }
        std::vector<size_t> sums;
        T mutex;
    };

std::deque<OneMutexAndState> state;
    size_t expected_sum;
    struct ThreadState
    {
        template<typename Seed>
        ThreadState(Seed &random_seed, size_t num_loops,
                std::deque<OneMutexAndState> &state) :
                randomness(random_seed)
        {
            CHECK_FOR_PROGRAMMER_ERROR(num_loops % state.size() == 0);
            iteration_order.reserve(num_loops);
            for (size_t i = 0; i < num_loops; ++i)
            {
                iteration_order.push_back(&state[i % state.size()]);
            }
        }

std::mt19937_64 randomness;
        std::vector<OneMutexAndState*> iteration_order;
    };

std::vector<ThreadState> thread_state;

explicit ManyContendedMutexRunner(int num_threads, size_t num_loops,
            size_t num_sums) :
            expected_sum(num_loops)
    {
        for (int i = 0; i < num_threads; ++i)
        {
            state.emplace_back(num_sums);
        }
        //random_seed_seq seed;
        std::random_device true_random;
        thread_state.reserve(num_threads);
        for (int i = 0; i < num_threads; ++i)
        {
            thread_state.emplace_back(true_random(), num_loops, state);
        }
    }

void start_run()
    {
        for (OneMutexAndState &state : state)
        {
            for (size_t &sum : state.sums)
                sum = 0;
        }
    }
    void end_run()
    {
        CHECK_FOR_PROGRAMMER_ERROR(state.front().sums.front() == expected_sum);
    }

void run_benchmark(int thread_num)
    {
        ThreadState &state = thread_state[thread_num];
        std::mt19937_64 &my_thread_randomness = state.randomness;
        size_t num_states = state.iteration_order.size();
        for (auto it = state.iteration_order.begin(), end =
                state.iteration_order.end(); it != end; ++it)
        {
            --num_states;
            if (num_states)
            {
                size_t random_pick = UniformRandom(num_states,
                        my_thread_randomness);
                std::iter_swap(it, it + random_pick);
            }
            OneMutexAndState &one = **it;
            one.mutex.lock();
            for (size_t &sum : one.sums)
                ++sum;
            one.mutex.unlock();
        }
    }
};

template<typename T>
void BenchmarkContendedMutex(benchmark::State &state)
{
    static constexpr size_t num_loops = 1024 * 16;

ThreadedBenchmarkRunnerMultipleTimes<ContendedMutexRunner<T>> runner(
            state.range(0), state.range(1), num_loops);
    while (state.KeepRunning())
    {
        runner.full_run();
    }
    runner.shut_down();
}

template<typename T>
struct ContendedMutexRunnerMoreIdle
{
    size_t sum = 0;
    size_t num_loops = 1;
    size_t expected_sum = 0;
    T mutex;

explicit ContendedMutexRunnerMoreIdle(int num_threads, size_t num_loops) :
            num_loops(num_loops), expected_sum(num_threads * num_loops)
    {
    }

void start_run()
    {
        sum = 0;
    }
    void end_run()
    {
        assert(sum == expected_sum);
    }

void run_benchmark(int)
    {
        for (size_t i = num_loops; i != 0; --i)
        {
            mutex.lock();
            ++sum;
            mutex.unlock();
            std::this_thread::sleep_for(std::chrono::microseconds(1));
            /*if (iteration < 1024)
             {
             std::this_thread::sleep_for(std::chrono::microseconds(1024 - iteration) / 32);
             }*/
        }
    }
};

template<typename T>
void BenchmarkContendedMutexMoreIdle(benchmark::State &state)
{
    static constexpr size_t num_loops = 1024;

ThreadedBenchmarkRunnerMultipleTimes<ContendedMutexRunnerMoreIdle<T>> runner(
            state.range(0), state.range(1), num_loops);
    while (state.KeepRunning())
    {
        runner.full_run();
    }
    runner.shut_down();
}

template<typename T, size_t N>
struct TopNHeap
{
    void fill(const T &value)
    {
        heap.fill(value);
    }

void add(const T &value)
    {
        if (value > heap.front())
        {
            std::pop_heap(heap.begin(), heap.end(), std::greater<>());
            heap.back() = value;
            std::push_heap(heap.begin(), heap.end(), std::greater<>());
        }
    }
    void add(T &&value)
    {
        if (value > heap.front())
        {
            std::pop_heap(heap.begin(), heap.end(), std::greater<>());
            heap.back() = std::move(value);
            std::push_heap(heap.begin(), heap.end(), std::greater<>());
        }
    }

void sort()
    {
        std::sort_heap(heap.begin(), heap.end(), std::greater<>());
    }

template<size_t ON>
    void merge(const TopNHeap<T, ON> &to_merge)
    {
        for (const T &val : to_merge.heap)
            add(val);
    }

std::array<T, N> heap;
};

template<typename T>
struct LongestWaitRunner
{
    TopNHeap<size_t, 4> longest_waits;
    T mutex;
    size_t current_longest_wait = 0;
    size_t num_loops = 1;

explicit LongestWaitRunner(int, size_t num_loops) :
            num_loops(num_loops)
    {
        longest_waits.fill(0);
    }

void start_run()
    {
        current_longest_wait = 0;
    }
    void end_run()
    {
        longest_waits.add(current_longest_wait);
    }

void run_benchmark(int)
    {
        for (size_t i = num_loops; i != 0; --i)
        {
            auto time_before = std::chrono::high_resolution_clock::now();
            mutex.lock();
            size_t wait_time_nanos =
                    std::chrono::duration_cast<std::chrono::nanoseconds>(
                            std::chrono::high_resolution_clock::now()
                                    - time_before).count();
            current_longest_wait = std::max(wait_time_nanos,
                    current_longest_wait);
            mutex.unlock();
        }
    }
};

template<typename T>
void BenchmarkLongestWait(benchmark::State &state)
{
    static constexpr size_t num_loops = 1024 * 16;
    ThreadedBenchmarkRunnerMultipleTimes<LongestWaitRunner<T>> runner(
            state.range(0), state.range(1), num_loops);
    while (state.KeepRunning())
    {
        runner.full_run();
    }
    runner.shut_down();
    TopNHeap<size_t, 4> longest_waits_merged;
    longest_waits_merged.fill(0);
    for (auto &runner : runner.runners)
    {
        longest_waits_merged.merge(runner.state.longest_waits);
    }
    longest_waits_merged.sort();
    for (size_t i = 0; i < longest_waits_merged.heap.size(); ++i)
    {
        state.counters["Wait" + std::to_string(i)] =
                static_cast<double>(longest_waits_merged.heap[i]);
    }
}

template<typename T>
struct LongestIdleRunner
{
    TopNHeap<size_t, 4> longest_idles;
    T mutex;
    size_t current_longest_idle = 0;
    size_t num_loops = 1;
    bool first = true;
    std::chrono::high_resolution_clock::time_point time_before =
            std::chrono::high_resolution_clock::now();

explicit LongestIdleRunner(int, size_t num_loops) :
            num_loops(num_loops)
    {
        longest_idles.fill(0);
    }

void start_run()
    {
        current_longest_idle = 0;
        first = true;
    }
    void end_run()
    {
        longest_idles.add(current_longest_idle);
    }

void run_benchmark(int)
    {
        for (size_t i = num_loops; i != 0; --i)
        {
            mutex.lock();
            size_t wait_time_nanos =
                    std::chrono::duration_cast<std::chrono::nanoseconds>(
                            std::chrono::high_resolution_clock::now()
                                    - time_before).count();
            if (first)
                first = false;
            else if (wait_time_nanos > current_longest_idle)
                current_longest_idle = wait_time_nanos;
            time_before = std::chrono::high_resolution_clock::now();
            mutex.unlock();
        }
    }
};

template<typename T>
void BenchmarkLongestIdle(benchmark::State &state)
{
    static constexpr size_t num_loops = 1024 * 16;
    ThreadedBenchmarkRunnerMultipleTimes<LongestIdleRunner<T>> runner(
            state.range(0), state.range(1), num_loops);
    while (state.KeepRunning())
    {
        runner.full_run();
    }
    runner.shut_down();
    TopNHeap<size_t, 4> longest_idles_merged;
    longest_idles_merged.fill(0);
    for (auto &runner : runner.runners)
    {
        longest_idles_merged.merge(runner.state.longest_idles);
    }
    longest_idles_merged.sort();
    for (size_t i = 0; i < longest_idles_merged.heap.size(); ++i)
    {
        state.counters["Idle" + std::to_string(i)] =
                static_cast<double>(longest_idles_merged.heap[i]);
    }
}

static void CustomBenchmarkArguments(benchmark::internal::Benchmark *b)
{
    int hardware_concurrency = std::thread::hardware_concurrency();
    int max_num_threads = hardware_concurrency * 2;
    for (int i = 1; i <= max_num_threads; i *= 2)
    {
        b->Args(
        { 1, i });
    }
    for (int i = 2; i <= max_num_threads; i *= 2)
    {
        b->Args(
        { i, i });
    }
    for (int i = 2; i <= max_num_threads; i *= 2)
    {
        int num_threads = std::max(1, hardware_concurrency / i);
        if (num_threads != i)
        {
            b->Args(
            { i, num_threads });
        }
    }
}

template<typename T>
struct ContendedMutexMoreWork
{
    static constexpr size_t NUM_LISTS = 8;
    std::list<size_t> linked_lists[NUM_LISTS];
    T mutex[NUM_LISTS];
    size_t num_loops = 1;

explicit ContendedMutexMoreWork(int num_threads, size_t num_loops) :
            num_loops(num_loops)
    {
        for (std::list<size_t> &l : linked_lists)
        {
            for (int i = 0; i < num_threads; ++i)
                l.push_back(i);
        }
    }

void start_run()
    {
    }
    void end_run()
    {
    }

void run_benchmark(int)
    {
        for (size_t i = num_loops; i != 0; --i)
        {
            size_t index = i % NUM_LISTS;
            mutex[index].lock();
            linked_lists[index].push_back(i);
            linked_lists[index].pop_front();
            mutex[index].unlock();
        }
    }
};

template<typename T>
void BenchmarkContendedMutexMoreWork(benchmark::State &state)
{
    static constexpr size_t num_loops = 1024;
    ThreadedBenchmarkRunnerMultipleTimes<ContendedMutexMoreWork<T>> runner(
            state.range(0), state.range(1), num_loops);
    while (state.KeepRunning())
    {
        runner.full_run();
    }
    runner.shut_down();
}

template<typename T>
struct ThroughputRunner
{
    std::chrono::high_resolution_clock::time_point *done_time;
    size_t sum = 0;
    T mutex;

explicit ThroughputRunner(int,
            std::chrono::high_resolution_clock::time_point *done_time) :
            done_time(done_time)
    {
    }

void start_run()
    {
        sum = 0;
    }
    void end_run()
    {
    }

void run_benchmark(int)
    {
        std::chrono::high_resolution_clock::time_point until = *done_time;
        while (std::chrono::high_resolution_clock::now() < until)
        {
            mutex.lock();
            ++sum;
            mutex.unlock();
        }
    }
};

template<typename T>
void BenchmarkThroughput(benchmark::State &state)
{
    std::chrono::high_resolution_clock::time_point end_time =
            std::chrono::high_resolution_clock::now();
    int num_states = state.range(0);
    ThreadedBenchmarkRunnerMultipleTimes<ThroughputRunner<T>> runner(num_states,
            state.range(1), &end_time);
    runner.wait_until_started();
    end_time = std::chrono::high_resolution_clock::now()
            + std::chrono::seconds(1);
    runner.start_run();
    runner.finish_run();
    size_t sum = std::accumulate(runner.runners.begin(), runner.runners.end(),
            size_t(0), [](size_t l, const auto &r)
            {
                return l + r.state.sum;
            });
    runner.shut_down();
    state.counters["Throughput"] = sum;
}

template<typename T>
struct ThroughputRunnerMultipleMutex
{
    std::chrono::high_resolution_clock::time_point *done_time;
    struct alignas(64) MutexAndSum
    {
        size_t sum = 0;
        T mutex;
    };
    static constexpr size_t num_mutexes = 8;
    MutexAndSum sums[num_mutexes];

explicit ThroughputRunnerMultipleMutex(int,
            std::chrono::high_resolution_clock::time_point *done_time) :
            done_time(done_time)
    {
    }

void start_run()
    {
        for (MutexAndSum &sum : sums)
            sum.sum = 0;
    }
    void end_run()
    {
    }

void run_benchmark(int)
    {
        std::chrono::high_resolution_clock::time_point until = *done_time;
        std::mt19937_64 randomness
        { std::random_device()() };
        std::uniform_int_distribution<int> distribution(0, num_mutexes - 1);
        while (std::chrono::high_resolution_clock::now() < until)
        {
            MutexAndSum &to_increment = sums[distribution(randomness)];
            to_increment.mutex.lock();
            ++to_increment.sum;
            to_increment.mutex.unlock();
        }
    }
};

template<typename T>
void BenchmarkThroughputMultipleMutex(benchmark::State &state)
{
    std::chrono::high_resolution_clock::time_point end_time =
            std::chrono::high_resolution_clock::now();
    int64_t num_states = state.range(0);
    ThreadedBenchmarkRunnerMultipleTimes<ThroughputRunnerMultipleMutex<T>> runner(
            num_states, state.range(1), &end_time);
    runner.wait_until_started();
    end_time = std::chrono::high_resolution_clock::now()
            + std::chrono::seconds(1);
    runner.start_run();
    runner.finish_run();
    size_t sum =
            std::accumulate(runner.runners.begin(), runner.runners.end(),
                    size_t(0),
                    [](size_t l,
                            const auto &r)
                            {
                                return l + std::accumulate(std::begin(r.state.sums), std::end(r.state.sums), size_t(0), [](size_t l, const auto& r)
                                        {
                                            return l + r.sum;
                                        });
                            });
    runner.shut_down();
    state.counters["Throughput"] = sum;
}

template<typename T>
void BenchmarkDemingWS(benchmark::State &state)
{
    // code from http://demin.ws/blog/english/2012/05/05/atomic-spinlock-mutex/
    T mutex;
    int value = 0;
    semaphore sem;
    semaphore one_loop_done;
    bool done = false;
    auto loop = [&](bool inc, int limit)
    {
        for (int i = 0; i < limit; ++i)
        {
            mutex.lock();
            if (inc)
            ++value;
            else
            --value;
            mutex.unlock();
        }
    };
    auto background_thread = [&](bool inc, int limit)
    {
        for (;;)
        {
            sem.acquire();
            if (done)
            break;
            loop(inc, limit);
            one_loop_done.release();
        }
    };
    int num_increment = 20000000;
    int num_decrement = 10000000;
    std::thread t(background_thread, true, num_increment);
    while (state.KeepRunning())
    {
        value = 0;
        sem.release();
        loop(false, num_decrement);
        one_loop_done.acquire();
    }
    assert(value == num_increment - num_decrement);
    done = true;
    sem.release();
    t.join();
}

/*#include <sys/mman.h>
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <fcntl.h>
 #include <unistd.h>
 #include <pthread.h>
 #include <errno.h>

#include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 #include <memory.h>*/

// code from https://github.com/goldshtn/shmemq-blog
template<typename Mutex>
struct alignas(64) shmemq
{
    shmemq(unsigned long max_count, unsigned int element_size) :
            element_size(element_size), max_size(max_count * element_size)
    {
        data.reset(new char[max_size]);
    }

bool try_enqueue(void *element, size_t len)
    {
        if (len != element_size)
            return false;

std::lock_guard<Mutex> lock(mutex);

if (write_index - read_index == max_size)
            return false; // There is no more room in the queue

memcpy(data.get() + write_index % max_size, element, len);
        write_index += element_size;
        return true;
    }

bool try_dequeue(void *element, size_t len)
    {
        if (len != element_size)
            return false;

std::lock_guard<Mutex> lock(mutex);

if (read_index == write_index)
            return false; // There are no elements that haven't been consumed yet

memcpy(element, data.get() + read_index % max_size, len);
        read_index += element_size;
        return true;
    }

Mutex mutex;
    size_t element_size = 0;
    size_t max_size = 0;
    size_t read_index = 0;
    size_t write_index = 0;
    std::unique_ptr<char[]> data;
};

template<typename T, typename State>
void BenchmarkShmemq(State &state)
{
    static constexpr int QUEUE_SIZE = 1000;
    static constexpr int REPETITIONS = 10000;
    int DATA_SIZE = state.range(0);

shmemq<T> server_queue(QUEUE_SIZE, DATA_SIZE);
    shmemq<T> client_queue(QUEUE_SIZE, DATA_SIZE);

auto build_message = [&]
    {
        std::unique_ptr<char[]> result(new char[DATA_SIZE]);
        memset(result.get(), 0, DATA_SIZE);
        int forty_two = 42;
        assert(sizeof(forty_two) <= static_cast<size_t>(DATA_SIZE));
        memcpy(result.get(), &forty_two, sizeof(forty_two));
        assert(5 + sizeof(forty_two) <= static_cast<size_t>(DATA_SIZE));
        memcpy(result.get() + sizeof(forty_two), "Hello", 5);
        return result;
    };

auto server = [&]
    {
        std::unique_ptr<char[]> msg = build_message();
        for (int i = 0; i < REPETITIONS; ++i)
        {
            while (!server_queue.try_dequeue(msg.get(), DATA_SIZE))
            {
            }
            while (!client_queue.try_enqueue(msg.get(), DATA_SIZE))
            {
            }
        }
    };
    auto client = [&]
    {
        std::unique_ptr<char[]> msg = build_message();
        for (int i = 0; i < REPETITIONS; ++i)
        {
            while (!server_queue.try_enqueue(msg.get(), DATA_SIZE))
            {
            }
            while (!client_queue.try_dequeue(msg.get(), DATA_SIZE))
            {
            }
        }
    };
    while (state.KeepRunning())
    {
        std::thread s(server);
        std::thread c(client);
        s.join();
        c.join();
    }
    state.SetItemsProcessed(REPETITIONS * state.iterations());
}

RegisterBenchmarkWithAllMutexes(BenchmarkShmemq);
RegisterBenchmarkWithAllMutexes(BenchmarkDemingWS);
RegisterBenchmarkWithAllMutexes(BenchmarkThroughputMultipleMutex,
        ->Apply(CustomBenchmarkArguments));
RegisterBenchmarkWithAllMutexes(BenchmarkThroughput,
        ->Apply(CustomBenchmarkArguments));
RegisterBenchmarkWithAllMutexes(BenchmarkContendedMutex,
        ->Apply(CustomBenchmarkArguments));
RegisterBenchmarkWithAllMutexes(BenchmarkLongestIdle,
        ->Apply(CustomBenchmarkArguments));
RegisterBenchmarkWithAllMutexes(BenchmarkLongestWait,
        ->Apply(CustomBenchmarkArguments));
RegisterBenchmarkWithAllMutexes(BenchmarkContendedMutexMoreWork,
        ->Apply(CustomBenchmarkArguments));
RegisterBenchmarkWithAllMutexes(BenchmarkContendedMutexMoreIdle,
        ->Apply(CustomBenchmarkArguments));

void benchmark_yield(benchmark::State &state)
{
    while (state.KeepRunning())
    {
        std::this_thread::yield();
    }
}
BENCHMARK(benchmark_yield);

int main(int argc, char *argv[])
{
    ::benchmark::Initialize(&argc, argv);
    ::benchmark::RunSpecifiedBenchmarks();
}