<xatomic.h>: Consider adding _mm_pause on x86/x64

[AlexGuteniev]

I'm referring to this part:

STL/stl/inc/xatomic.h

Lines 26 to 40 in 260cfaf

	#if defined(_M_CEE_PURE) || defined(_M_IX86) || defined(_M_X64)
	#define _INTRIN_RELAXED(x) x
	#define _INTRIN_ACQUIRE(x) x
	#define _INTRIN_RELEASE(x) x
	#define _INTRIN_ACQ_REL(x) x
	#define _YIELD_PROCESSOR()
	#elif defined(_M_ARM) || defined(_M_ARM64)
	#define _INTRIN_RELAXED(x) _CONCAT(x, _nf)
	#define _INTRIN_ACQUIRE(x) _CONCAT(x, _acq)
	#define _INTRIN_RELEASE(x) _CONCAT(x, _rel)
	// We don't have interlocked intrinsics for acquire-release ordering, even on
	// ARM32/ARM64, so fall back to sequentially consistent.
	#define _INTRIN_ACQ_REL(x) x
	#define _YIELD_PROCESSOR() __yield()

In particular, this line:

STL/stl/inc/xatomic.h

Line 31 in 260cfaf

#define _YIELD_PROCESSOR()

In "winnt.h" it is defined as follows:
#define YieldProcessor _mm_pause

In documentation on YieldProcessor use of pause instruction is documented:

This macro can be called on all processor platforms where Windows is supported, but it has no effect on some platforms. The definition varies from platform to platform. The following are some definitions of this macro in Winnt.h:

#define YieldProcessor() __asm { rep nop }
#define YieldProcessor _mm_pause
#define YieldProcessor __yield

Other synchronization libraries also make use of pause instruction.

@BillyONeal explained in #613 (comment):

The answer I've heard from folks that supposedly know better is "never _mm_pause ever" -- that macro was defined long before my time but it was defined as empty for x86/x64 and I don't think we would want to change that without extremely strong profiling evidence that it was a good idea.

Though I understand that there are some folks that know something, it all highly suspicious that this STL is the only library I know that avoids pause.

[StephanTLavavej]

Marking as info needed; I agree with Billy, I'd want to see performance benchmarks that indicate this is a significant win and never harmful.

[BillyONeal]

I pinged whatever folks from whom I might have heard this here: https://twitter.com/MalwareMinigun/status/1246187718645698562 we'll see what they say

[AlexGuteniev]

@BillyONeal , it seems that one of persons you are asking is the same Olivier, who made reference implementation of atomic wait with _mm_pause in spinning :-)

If the concern is unpredictable duration then, well, lets not rely on duration and don't do more than one _mm_pause per spin iteration (and this STL does not do it, as I can see)

I agree that benchmark should be provided. I disagree that you can improve / not make worse every case -- there's always a tradeoff.

[AlexGuteniev]

I can provide a test program that shows _mm_pause is better.
Though I cannot prove it is legitimate, it should be enough to start at least considering _mm_pause

#include <chrono>
#include <iostream>
#include <thread>
#include <mutex>
#include <atomic>
#include <thread>
#include <intrin.h>

struct MammothAtomicValue
{
    unsigned v;

    void increment()
    {
        ++v;
    }

    bool is_equal(const MammothAtomicValue& other) const
    {
        return v == other.v;
    }

    bool is_greater_or_equal(const MammothAtomicValue& other) const
    {
        return v >= other.v;
    }
};

template<bool use_pause>
struct MammothAtomic
{
    void lock()
    {
        while (spin_mutex.exchange(true, std::memory_order_acquire))
        {
            if (use_pause)
            {
                _mm_pause();
            }
            else
            {
                // notihng
            }
        }
    }

    void unlock()
    {
        spin_mutex.store(false, std::memory_order_release);
    }

    MammothAtomicValue load()
    {
        lock();
        MammothAtomicValue result = value;
        unlock();
        return result;
    }

    MammothAtomicValue cas(const MammothAtomicValue& desired, 
    const MammothAtomicValue& expected)
    {
        lock();
        MammothAtomicValue result = value;
        if (value.is_equal(expected))
        {
            value = desired;
        }
        unlock();
        return result;
    }

    MammothAtomicValue value;
    std::atomic<bool>  spin_mutex = false;

    MammothAtomicValue increment()
    {
        MammothAtomicValue expected = load();
        MammothAtomicValue result = expected;
        for (;;)
        {
            result.increment();
            result = cas(result, expected);
            if (result.is_equal(expected))
            {
                break;
            }
            expected = result;
        }
        return result;
    }
};


template<bool use_pause>
std::chrono::steady_clock::duration run_benchmark()
{
    MammothAtomicValue initial = { 0 };
    MammothAtomicValue final = { 2000000 };

    MammothAtomic<use_pause> value = { initial };

    std::atomic<bool> race_start_flag = false;

    auto worker = [&] {
        while (!race_start_flag.load()) {}

        while (!value.increment().is_greater_or_equal(final)) {}
    };

   // with two workers, _mm_pause is double win, with one worker no effect
   // with more than two some sort of win
    std::thread workers[2]; 

    for (auto& w : workers) {
        w = std::thread(worker);
    }

    auto start_time = std::chrono::steady_clock::now();
    race_start_flag.store(true);
    for (auto& w : workers) {
        w.join();
    }

    return std::chrono::steady_clock::now() - start_time;
}

int main()
{
    namespace chrono = std::chrono;

    for (int i = 0; i < 4; i++)
    {
        std::cout << chrono::duration_cast<chrono::duration<double, std::milli>>(
          run_benchmark<false>()).count() << "ms without _mm_pause\t";
        std::cout << chrono::duration_cast<chrono::duration<double, std::milli>>(
          run_benchmark<true>()).count() << "ms with _mm_pause" << std::endl;
    }
}

[StephanTLavavej]

I disagree that you can improve / not make worse every case -- there's always a tradeoff.

Some things are pure wins - e.g. given compiler support, if constexpr utterly annihilates tag dispatch. But yes, when there's a tradeoff, we need to make choices.

[chuggafan]

_mm_pause also has the issue of being different lengths depending on which Intel arch you're using, 10 cycles vs the newer ones having 140 cycles, so if people using atomics rely on a very fast atomic check time then they could have a significant drop in performance, https://aloiskraus.wordpress.com/2018/06/16/why-skylakex-cpus-are-sometimes-50-slower-how-intel-has-broken-existing-code/ also the people who work on .NET found out. So for some extremely high-threadcount high contention atomics this could explode the time it takes as this article explains.

So adding _mm_pause can negatively affect some workloads while positively affect others, so it'd probably be best to find out which type of workload is the most often used and optimize for that while informing others of the change (if the change happens).

[AlexGuteniev]

@BillyONeal , I have an idea.

In scope of #593 (atomic waits) I can add some minimal level of Windows XP support,
That is just spinning on wait, first actively, then using SwitchToThread, and no-op on notify_one, notify_all. Then, atomic wait could be used to resolve #370 , and also for internal atomic spinlock.

Then, the question about _YIELD_PROCESSOR would be question about nothing: _YIELD_PROCESSOR would only be called for odd-sized atomics waiting and for old operating systems.

(Note that WaitOnAddress by itself spins before going to kernel wait, and it spins with pause, but it is not the responsibility of STL anymore)

What do you think?

[MikeGitb]

So adding _mm_pause can negatively affect some workloads while positively affect others, so it'd probably be best to find out which type of workload is the most often used and optimize for that while informing others of the change (if the change happens).

Correct me if I'm wrong, but the problem in the linked article was that .net used something like 50 pauses in the first iteration and then tripled that in each iteration. Of course that leads to very long backoff times very quickly. That doesn't mean that something like

while(!flag){
       _mm_pause();
}

isn't still better than

while(!flag){
       ;
}

It is only when you try to figure out the "optimal" number of pause instructions that this becomes an issue but e.g. 1 is certainly still better than 0.
Also, if exact perf behavior is important enough that I worry about 100 instead of 10 cycles granularity of a spinlock, I'm very unlikely to use a STL construct anyway whose implementation might change from one toolchain version to another and certainly differs from one STL to another.

And generally speaking, I'd certainly expect a _YIELD_PROCESSOR macro to do at least something on every architecture and not just to be a No Op.

[chuggafan]

@MikeGitb Well, that might have been the case, but just to make sure I ran a modified version of @AlexGuteniev 's test program where I instead ran 60 worker threads, a total of 30 runs, and then averaged the results at the end of the program, this is on an i7-7700HQ with Visual Studio's debug window in release x64 mode,
here are my results, so it seems that on average _mm_pause is legitimately better but in individual cases it can be a toss up. Of course, this isn't extensive testing done with other, real-world programs, but it's nice to see now that there's "real" results, where on average _mm_pause wins by approximately 2.3 seconds or so.

The main reason I threw the article out there was to warn against being too quick on a decision like this because there's been problems with _mm_pause before due to Intel shenanigans.

Of course, there should still be more testing and a more "concrete" answer found, but I just want to warn against premature changes where it's not explicitly a bug but can affect performance, as anything to do with performance goes: Test before making claims.