Performance Battle: Mutex vs CAS vs TAS vs Intel TSX


Performance Battle:

Mutex vs CAS vs TAS vs Intel TSX



std::mutex: A standard C++ lock object that provides mutual exclusion between threads.

CAS (Compare-And-Swap): An atomic operation that updates a memory location only if its current value matches an expected value.

TAS (Test-And-Set): An atomic operation that reads and sets a value simultaneously.

Intel TSX (Transactional Synchronization Extensions): An Intel technology that uses hardware transactional memory to reduce lock contention.



The following algorithm uses multiple threads to add 1 to a shared memory variable kLoop times. In this case, the sum of sum_atomic and sum_critical_section will be equal to kLoop. Although this is a highly inefficient algorithm, let's just accept it.

int sumcriticalsection;
std::atomic<int> sumatomic;

void Thread() {
constexpr auto kLoop{ 2200'0000 };
constexpr auto kNumThread{ 88 };
   
for (int i = 0; i < kLoop / kNumThread; ++i) {
        if (TryAcquire()) {
            sumcriticalsection += 1;
            Release();
        } else {
            sumatomic.fetchadd(1, std::memoryorder::relaxed);
        }

Idle(idletime);
    }
}

An idle period was inserted between work units to control the level of contention.

(high contention: 0.6 us / low contention: 3.0 us)


`TryAcquire` are implemented as follows.

1. Mutex

`return mx.trylock();

2. CAS

return not atomic_bool.load(std::memory_order::relaxed) and
atomic_bool.compare_exchange_strong(expected, true, std::memory_order::acquire, std::memory_order::relaxed)); // expected = false

3. TAS

return not (atomic_flag.test(std::memory_order::relaxed) or atomic_flag.test_and_set(std::memory_order::acquire));

4. Intel TSX

return _xbegin() == _XBEGIN_STARTED;

For both CAS and TAS, the lock variable is checked before attempting the atomic operation. If the lock is already set (true), the function immediately returns false without performing the CAS or TAS operation. Otherwise, performance will degrade.



System Description

|CPU|2 × Intel Xeon E5-2696 v4 (total 88-thread)|
|:-|:-|
|Build|C++23, g++ 13.3.0, -Ofast|



The experiments were conducted on a two-node NUMA system. Accordingly, both sumcriticalsection and sumatomic` were split into two separate counters.


Which of these four approaches do you think will win: Mutex, CAS, TAS, or Intel TSX?

Let's keep the rules simple: the winner is whichever finishes the workload the fastest.


.

.

.

.

.
.

.

.



High Contention: idle time = 0.6 us

||sum\critical_section|sum_atomic|elapsed_seconds|
|:-|:-|:-|:-|
|Mutex|478K|21.5M|1.618|
|CAS|557K|21.4M|0.569|
|TAS|564K|21.4M|0.567|
|TSX|746K|21.2M|0.492|


Low Contention: idle time = 3.0 us

||sum_critical_section|sum_atomic|elapsed_seconds|
|:-|:-|:-|:-|
|Mutex|915K|21.1M|1.835|
|CAS|1.90M|20.1M|1.254|
|TAS|1.95M|20.0M|1.264|
|TSX|10.2M|11.7M|1.142|


The winner of this benchmark is Intel TSX.

Of course, a benchmark win doesn't automatically make TSX superior in every situation. That said, it did win this round.

(when the idle time was zero, TSX, CAS, and TAS achieved nearly identical elapsed times, whereas std::mutex was consistently slower.)



What are your thoughts on this matchup?


=

https://redd.it/1tzey4h
@r_cpp