The following program simulates constant locking und unlocking of one
to jthread::hardware_concurrency() threadas with a std::mutex and a
futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
5 threads constantly contending, but beyond the CPU time of the futex
explodes and the conventional mutex is faster with Windows as and with
Linux.

#include <iostream>
#include <thread>
#include <mutex>
#include <atomic>
#include <functional>
#include <chrono>
#include <vector>

using namespace std;
using namespace chrono;

int main()
{ constexpr int64_t ROUNDS = 10000;
auto bench = [&]( char const *head, auto fn )
{
cout << head << endl;
atomic_int64_t tSum( 0 );
vector<jthread> threads;
int hc = jthread::hardware_concurrency();
for( int nThreads = 1; nThreads <= hc; ++nThreads )
{
for( unsigned t = nThreads; t; --t )
threads.emplace_back( [&]()
{
auto start = high_resolution_clock::now();
int64_t cmp = 0;
for( int64_t r = ROUNDS; r; --r )
cmp = fn( cmp );
tSum += duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count();
} );
threads.resize( 0 );
cout << "\t" << nThreads << ": " << tSum /
((double)nThreads * ROUNDS) << endl;
}
};
{
mutex mtx;
bench( "mutex: ",
[&]( int64_t )
{
mtx.lock();
mtx.unlock();
return 0;
} );
}
{
atomic_int64_t futex( 0 );
constexpr int64_t HIBIT = numeric_limits<int64_t>::min();
bench( "futex:",
[&]( int64_t cmp )
{
int64_t niu;
for( ; ; )
if( cmp >= 0 )
if( futex.compare_exchange_weak( cmp, niu = cmp
| HIBIT, memory_order_acquire, memory_order_relaxed ) )
{
cmp = niu;
break;
}
else;
else
if( futex.compare_exchange_weak( cmp, niu = cmp
+ 1, memory_order_relaxed, memory_order_relaxed ) )
{
futex.wait( niu, memory_order_acquire );
cmp = futex.load( memory_order_relaxed );
}
for( ; ; )
if( cmp & ~HIBIT )
if( futex.compare_exchange_weak( cmp, niu =
(cmp - 1) & ~HIBIT, memory_order_release, memory_order_relaxed ) )
{
cmp = niu;
futex.notify_one();
break;
}
else;
else
if( futex.compare_exchange_weak( cmp, 0,
memory_order_release, memory_order_relaxed ) )
{
cmp = 0;
break;
}
return cmp;
} );
}
}

This are the results under Ubuntu 20.04 LTS:

mutex:
1: 3.9134
2: 5.8706
3: 33.1753
4: 48.63
5: 71.6777
6: 109.556
7: 151.271
8: 208.871
9: 288.031
10: 353.536
11: 446.28
12: 563.841
13: 701.134
14: 833.08
15: 983.734
16: 1138.48
17: 1297.53
18: 1481.15
19: 1664.51
20: 1857.88
21: 2053.83
22: 2285.07
23: 2546.67
24: 2782.53
25: 3065.25
26: 3349.4
27: 3652.06
28: 3971.25
29: 4339.13
30: 4727.31
31: 5129.95
32: 5499.05
futex:
1: 3.3654
2: 5.02155
3: 6.69107
4: 15.2522
5: 16.8824
6: 185.235
7: 162.176
8: 360.421
9: 2272.83
10: 4805.11
11: 8987.24
12: 14225.5
13: 20076.4
14: 27199.4
15: 36711.8
16: 49480.8
17: 57641.8
18: 75633.2
19: 97196.6
20: 122223
21: 147617
22: 180377
23: 216084
24: 256032
25: 299681
26: 345518
27: 398785
28: 445499
29: 506351
30: 572440
31: 643455
32: 721461

With all threads locking and unlocking the conventional mutex is 131
timea faster.

On 3/29/2024 6:14 AM, Bonita Montero wrote:
> The following program simulates constant locking und unlocking of one
> to jthread::hardware_concurrency() threadas with a std::mutex and a
> futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
> 5 threads constantly contending, but beyond the CPU time of the futex
> explodes and the conventional mutex is faster with Windows as and with
> Linux.
[...]

A futex is not a mutex!

On 3/29/2024 3:28 PM, Chris M. Thomasson wrote:
> On 3/29/2024 6:14 AM, Bonita Montero wrote:
>> The following program simulates constant locking und unlocking of one
>> to jthread::hardware_concurrency() threadas with a std::mutex and a
>> futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
>> 5 threads constantly contending, but beyond the CPU time of the futex
>> explodes and the conventional mutex is faster with Windows as and with
>> Linux.
> [...]
>
> A futex is not a mutex!
>

I have to take a look at the logic you used for your "mutex" based on a
futex, not enough time right now. Perhaps, the std::mutex is just way
more efficient that your use of a futex? Keep in mind futexs are tricky:

https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf

;^)

It depends on the logic you use.

On 3/29/2024 3:30 PM, Chris M. Thomasson wrote:
> On 3/29/2024 3:28 PM, Chris M. Thomasson wrote:
>> On 3/29/2024 6:14 AM, Bonita Montero wrote:
>>> The following program simulates constant locking und unlocking of one
>>> to jthread::hardware_concurrency() threadas with a std::mutex and a
>>> futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
>>> 5 threads constantly contending, but beyond the CPU time of the futex
>>> explodes and the conventional mutex is faster with Windows as and with
>>> Linux.
>> [...]
>>
>> A futex is not a mutex!
>>
>
> I have to take a look at the logic you used for your "mutex" based on a
> futex, not enough time right now. Perhaps, the std::mutex is just way
> more efficient that your use of a futex? Keep in mind futexs are tricky:
>
> https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf
>
> ;^)
>
> It depends on the logic you use.

You generally want a "waitbit" type of logic... I posted a mutex based
on a futex here a while back. I just need to find it. Iirc, it used a
Windows "futex"... If I can find it, you should test against it. It used
NO compare and swap. Ugghhhh.... Try to avoid that.

On 3/29/2024 4:29 PM, Chris M. Thomasson wrote:
> On 3/29/2024 3:30 PM, Chris M. Thomasson wrote:
>> On 3/29/2024 3:28 PM, Chris M. Thomasson wrote:
>>> On 3/29/2024 6:14 AM, Bonita Montero wrote:
>>>> The following program simulates constant locking und unlocking of one
>>>> to jthread::hardware_concurrency() threadas with a std::mutex and a
>>>> futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
>>>> 5 threads constantly contending, but beyond the CPU time of the futex
>>>> explodes and the conventional mutex is faster with Windows as and with
>>>> Linux.
>>> [...]
>>>
>>> A futex is not a mutex!
>>>
>>
>> I have to take a look at the logic you used for your "mutex" based on
>> a futex, not enough time right now. Perhaps, the std::mutex is just
>> way more efficient that your use of a futex? Keep in mind futexs are
>> tricky:
>>
>> https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf
>>
>> ;^)
>>
>> It depends on the logic you use.
>
> You generally want a "waitbit" type of logic... I posted a mutex based
> on a futex here a while back. I just need to find it. Iirc, it used a
> Windows "futex"... If I can find it, you should test against it. It used
> NO compare and swap. Ugghhhh.... Try to avoid that.

Another key, try to avoid waiting on a futex, strive for that. Maximize
the fast paths, and minimize the slow paths.

Am 29.03.2024 um 23:28 schrieb Chris M. Thomasson:
> On 3/29/2024 6:14 AM, Bonita Montero wrote:
>> The following program simulates constant locking und unlocking of one
>> to jthread::hardware_concurrency() threadas with a std::mutex and a
>> futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
>> 5 threads constantly contending, but beyond the CPU time of the futex
>> explodes and the conventional mutex is faster with Windows as and with
>> Linux.
> [...]
>
> A futex is not a mutex!
>

You can build a mutex on top of a futex and that's the typical usage.

Am 30.03.2024 um 00:29 schrieb Chris M. Thomasson:
> On 3/29/2024 3:30 PM, Chris M. Thomasson wrote:
>> On 3/29/2024 3:28 PM, Chris M. Thomasson wrote:
>>> On 3/29/2024 6:14 AM, Bonita Montero wrote:
>>>> The following program simulates constant locking und unlocking of one
>>>> to jthread::hardware_concurrency() threadas with a std::mutex and a
>>>> futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
>>>> 5 threads constantly contending, but beyond the CPU time of the futex
>>>> explodes and the conventional mutex is faster with Windows as and with
>>>> Linux.
>>> [...]
>>>
>>> A futex is not a mutex!
>>>
>>
>> I have to take a look at the logic you used for your "mutex" based on
>> a futex, not enough time right now. Perhaps, the std::mutex is just
>> way more efficient that your use of a futex? Keep in mind futexs are
>> tricky:
>>
>> https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf
>>
>> ;^)
>>
>> It depends on the logic you use.
>
> You generally want a "waitbit" type of logic...

The sign-bit of my uint64 shows that signs that the lock is occupied
and the 63 lower bits sign the number of threads waiting to get owner-
ship. But i simplified the code a lot by using just an atomic_bool.
Now under Windows the futex is superior from 12 threads on. But under
Linux the futex is slower except for one or two threads.

Windows:

1: 248%
2: 54%
3: 27%
4: 28%
5: 33%
6: 31%
7: 37%
8: 37%
9: 53%
10: 42%
11: 82%
12: 101%
13: 116%
14: 142%
15: 153%
16: 160%
17: 175%
18: 191%
19: 192%
20: 194%
21: 206%
22: 211%
23: 221%
24: 220%
25: 223%
26: 220%
27: 220%
28: 223%
29: 222%
30: 220%
31: 219%
32: 216%

Linux:

1: 121%
2: 106%
3: 67%
4: 99%
5: 87%
6: 18%
7: 13%
8: 12%
9: 10%
10: 10%
11: 9%
12: 9%
13: 8%
14: 8%
15: 8%
16: 8%
17: 8%
18: 8%
19: 8%
20: 8%
21: 7%
22: 7%
23: 8%
24: 7%
25: 7%
26: 7%
27: 7%
28: 7%
29: 7%
30: 7%
31: 7%
32: 6%

#include <iostream>
#include <thread>
#include <atomic>
#include <chrono>
#include <vector>
#include <mutex>

using namespace std;
using namespace chrono;

int main()
{ unsigned hc = jthread::hardware_concurrency();
auto test = [&]( char const *head, auto fn, vector<double> &times )
{
cout << head << endl;
constexpr size_t ROUNDS = 10'000;
atomic_int64_t tSum, roundsSum;
vector<jthread> threads;
for( unsigned nThreads = 1; nThreads <= hc; ++nThreads )
{
auto st = []<typename T, integral X>( atomic<T> &a, X v ) { return
a.store( (T)v, memory_order_relaxed ); };
st( tSum, 0 );
st( roundsSum, 0 );
atomic_bool stop( false );
auto ld = []<typename T>( atomic<T> &a ) { return a.load(
memory_order_relaxed ); };
for( unsigned t = nThreads; t; --t )
threads.emplace_back( [&]
{
auto start = high_resolution_clock::now();
int64_t rounds = 0;
for( ; !ld( stop ); fn(), ++rounds );
auto add = []( atomic_int64_t &a, int64_t add ) { a.fetch_add(
add, memory_order_relaxed ); };
add( tSum, duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() );
add( roundsSum, rounds );
} );
this_thread::sleep_for( 100ms );
st( stop, true );
threads.resize( 0 );
times.emplace_back( ld( tSum ) / (double)ld( roundsSum ) );
cout << "\t" << nThreads << ": " << times.back() << endl;
}
};
vector<double> mutexTimes, futexTimes;
{
mutex mtx;
test( "mutex:",
[&]
{
mtx.lock();
mtx.unlock();
}, mutexTimes );
}
{
atomic_bool futex( false );
test( "futex:",
[&]
{
for( bool cmp; !futex.compare_exchange_weak( cmp = false, true,
memory_order_acquire, memory_order_relaxed ); )
futex.wait( true, memory_order_relaxed );
futex.store( false, memory_order_release );
futex.notify_one();
}, futexTimes );
}
cout << "relation: " << endl;
for( size_t i = 0; i != hc; ++i )
cout << "\t" << i + 1 << ": " << (int)(100.0 * mutexTimes[i] /
futexTimes[i] + 0.5) << "%" << endl;
}

On 3/30/2024 1:25 AM, Bonita Montero wrote:
> {
>                 for( bool cmp; !futex.compare_exchange_weak( cmp =
> false, true, memory_order_acquire, memory_order_relaxed ); )
>                     futex.wait( true, memory_order_relaxed );
>                 futex.store( false, memory_order_release );
>                 futex.notify_one();
>             }, futexTimes );

You need to introduce some sort of waitbit logic to minimize calls to
futex.notify_one() and futex.wait(). I posted an example but am having a
hard time finding the damn thing in comp.lang.c++. I will try to find it.

On 3/29/2024 6:14 AM, Bonita Montero wrote:
> The following program simulates constant locking und unlocking of one
> to jthread::hardware_concurrency() threadas with a std::mutex and a
> futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
> 5 threads constantly contending, but beyond the CPU time of the futex
> explodes and the conventional mutex is faster with Windows as and with
> Linux.
[...]

I think I found my highly experimental windows futex based mutex:

https://groups.google.com/g/comp.lang.c++/c/1MZvhswJ6DQ/m/qyaYH-i0CgAJ

(read all to refresh the context... ;^)

Notice:
___________________
void unlock()
{ if (InterlockedExchange(&m_state, 0) == 2)
{
WakeByAddressSingle(&m_state);
}
} ___________________

We only signal when we have to!

copy and paste from the link. Sorry about the copy and paste destroying
all of my indentation, argh!

Can you run this Bonita? Fwiw, it would be my first time using a Windows
Futex! lol:
______________________________________
#include <iostream>
#include <thread>
#include <functional>

#define WIN32_LEAN_AND_MEAN
#include <Windows.h>

#define CT_L2_ALIGNMENT 128
#define CT_THREADS 32
#define CT_ITERS 6666666

struct ct_futex_mutex
{ ULONG alignas(CT_L2_ALIGNMENT) m_state;

ct_futex_mutex() : m_state(0)
{

}

void lock()
{ if (InterlockedExchange(&m_state, 1))
{ while (InterlockedExchange(&m_state, 2))
{ ULONG cmp = 2;
WaitOnAddress(&m_state, &cmp, sizeof(ULONG), INFINITE);
} }
}

void unlock()
{ if (InterlockedExchange(&m_state, 0) == 2)
{ WakeByAddressSingle(&m_state);
} }
};

struct ct_shared
{ ct_futex_mutex m_mtx;
unsigned long m_count;

ct_shared() : m_count(0) {}

~ct_shared()
{ if (m_count != 0)
{ std::cout << "counter is totally fubar!\n";
} }
};

void ct_thread(ct_shared& shared)
{ for (unsigned long i = 0; i < CT_ITERS; ++i)
{ shared.m_mtx.lock();
++shared.m_count;
shared.m_mtx.unlock();

shared.m_mtx.lock();
--shared.m_count;
shared.m_mtx.unlock();
} }

int main()
{ std::thread threads[CT_THREADS];

std::cout << "Starting up...\n";

{
ct_shared shared;

for (unsigned long i = 0; i < CT_THREADS; ++i)
{ threads[i] = std::thread(ct_thread, std::ref(shared));
}

std::cout << "Running...\n";

for (unsigned long i = 0; i < CT_THREADS; ++i)
{ threads[i].join();
} }

std::cout << "Completed!\n";

return 0;
} ______________________________________

On 3/30/2024 11:51 AM, Chris M. Thomasson wrote:
> On 3/30/2024 1:25 AM, Bonita Montero wrote:
>> {
>>                  for( bool cmp; !futex.compare_exchange_weak( cmp =
>> false, true, memory_order_acquire, memory_order_relaxed ); )
>>                      futex.wait( true, memory_order_relaxed );
>>                  futex.store( false, memory_order_release );
>>                  futex.notify_one();
>>              }, futexTimes );
>
>
> You need to introduce some sort of waitbit logic to minimize calls to
> futex.notify_one() and futex.wait(). I posted an example but am having a
> hard time finding the damn thing in comp.lang.c++. I will try to find it.

I found my older experimental code, take a deep look at ct_futex_mutex:

https://groups.google.com/g/comp.lang.c++/c/1MZvhswJ6DQ/m/qyaYH-i0CgAJ

Am 30.03.2024 um 19:51 schrieb Chris M. Thomasson:

> You need to introduce some sort of waitbit logic to minimize calls to
> futex.notify_one() and futex.wait(). I posted an example but am having a
> hard time finding the damn thing in comp.lang.c++. I will try to find it.

Futex notify and wait are at least very cheap with Windows.

On 3/30/2024 1:18 PM, Bonita Montero wrote:
> Am 30.03.2024 um 19:51 schrieb Chris M. Thomasson:
>
>> You need to introduce some sort of waitbit logic to minimize calls to
>> futex.notify_one() and futex.wait(). I posted an example but am having
>> a hard time finding the damn thing in comp.lang.c++. I will try to
>> find it.
>
> Futex notify and wait are at least very cheap with Windows.
>

Well, I have not taken a look at Microsoft's Futex implementation.
Afaict, your code showcases that aspect wrt calling into notify on every
mutex unlock, and wait on every point of contention wrt lock. Interesting.

On 3/30/2024 11:51 AM, Chris M. Thomasson wrote:
> On 3/30/2024 1:25 AM, Bonita Montero wrote:
>> {
>>                  for( bool cmp; !futex.compare_exchange_weak( cmp =
>> false, true, memory_order_acquire, memory_order_relaxed ); )
>>                      futex.wait( true, memory_order_relaxed );
>>                  futex.store( false, memory_order_release );
>>                  futex.notify_one();
>>              }, futexTimes );
>
>
> You need to introduce some sort of waitbit logic to minimize calls to
> futex.notify_one() and futex.wait(). I posted an example but am having a
> hard time finding the damn thing in comp.lang.c++. I will try to find it.

Also, does notify_one automatically imply release semantics?

On 3/31/2024 10:01 PM, Chris M. Thomasson wrote:
> On 3/30/2024 11:51 AM, Chris M. Thomasson wrote:
>> On 3/30/2024 1:25 AM, Bonita Montero wrote:
>>> {
>>>                  for( bool cmp; !futex.compare_exchange_weak( cmp =
>>> false, true, memory_order_acquire, memory_order_relaxed ); )
>>>                      futex.wait( true, memory_order_relaxed );
>>>                  futex.store( false, memory_order_release );
>>>                  futex.notify_one();
>>>              }, futexTimes );
>>
>>
>> You need to introduce some sort of waitbit logic to minimize calls to
>> futex.notify_one() and futex.wait(). I posted an example but am having
>> a hard time finding the damn thing in comp.lang.c++. I will try to
>> find it.
>
> Also, does notify_one automatically imply release semantics?

I don't think so, humm. Cannot remember.

Am 31.03.2024 um 22:11 schrieb Chris M. Thomasson:

> Well, I have not taken a look at Microsoft's Futex implementation.
> Afaict, your code showcases that aspect wrt calling into notify on every
> mutex unlock, and wait on every point of contention wrt lock. Interesting.

I'm using notify and wait only when there's contention.

On 3/31/2024 11:32 PM, Bonita Montero wrote:
> Am 31.03.2024 um 22:11 schrieb Chris M. Thomasson:
>
>> Well, I have not taken a look at Microsoft's Futex implementation.
>> Afaict, your code showcases that aspect wrt calling into notify on
>> every mutex unlock, and wait on every point of contention wrt lock.
>> Interesting.
>
> I'm using notify and wait only when there's contention.

Even here?
_____________
for( bool cmp; !futex.compare_exchange_weak( cmp =
false, true, memory_order_acquire, memory_order_relaxed ); )
futex.wait( true, memory_order_relaxed );
futex.store( false, memory_order_release );
futex.notify_one();
}, futexTimes );
____________

What am I missing?

futex.store( false, memory_order_release );
futex.notify_one();

?

Am 01.04.2024 um 08:40 schrieb Chris M. Thomasson:
> On 3/31/2024 11:32 PM, Bonita Montero wrote:
>> Am 31.03.2024 um 22:11 schrieb Chris M. Thomasson:
>>
>>> Well, I have not taken a look at Microsoft's Futex implementation.
>>> Afaict, your code showcases that aspect wrt calling into notify on
>>> every mutex unlock, and wait on every point of contention wrt lock.
>>> Interesting.
>>
>> I'm using notify and wait only when there's contention.
>
> Even here?
> _____________
>                  for( bool cmp; !futex.compare_exchange_weak( cmp =
> false, true, memory_order_acquire, memory_order_relaxed ); )
>                      futex.wait( true, memory_order_relaxed );
>                  futex.store( false, memory_order_release );
>                  futex.notify_one();
>              }, futexTimes );
> ____________
>
> What am I missing?
>
>                  futex.store( false, memory_order_release );
>                  futex.notify_one();
>
> ?
>

Ok, I was talking about my older version.
But notify is fast.

Am 01.04.2024 um 10:57 schrieb Bonita Montero:
> Am 01.04.2024 um 08:40 schrieb Chris M. Thomasson:
>> On 3/31/2024 11:32 PM, Bonita Montero wrote:
>>> Am 31.03.2024 um 22:11 schrieb Chris M. Thomasson:
>>>
>>>> Well, I have not taken a look at Microsoft's Futex implementation.
>>>> Afaict, your code showcases that aspect wrt calling into notify on
>>>> every mutex unlock, and wait on every point of contention wrt lock.
>>>> Interesting.
>>>
>>> I'm using notify and wait only when there's contention.
>>
>> Even here?
>> _____________
>>                   for( bool cmp; !futex.compare_exchange_weak( cmp =
>> false, true, memory_order_acquire, memory_order_relaxed ); )
>>                       futex.wait( true, memory_order_relaxed );
>>                   futex.store( false, memory_order_release );
>>                   futex.notify_one();
>>               }, futexTimes );
>> ____________
>>
>> What am I missing?
>>
>>                   futex.store( false, memory_order_release );
>>                   futex.notify_one();
>>
>> ?
>>
>
> Ok, I was talking about my older version.
> But notify is fast.
>

An uncontended notify is 2.5ns on my Zen4 computer.

On Fri, 29 Mar 2024 14:14:11 +0100
Bonita Montero <Bonita.Montero@gmail.com> wrote:

> The following program simulates constant locking und unlocking of one
> to jthread::hardware_concurrency() threadas with a std::mutex and a
> futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
> 5 threads constantly contending, but beyond the CPU time of the futex
> explodes and the conventional mutex is faster with Windows as and with
> Linux.
>

In case of heavy contention what to consider 'faster' is not at all
obvious.

On lightly loaded system with more cores than work to do (a typical
client) 'faster' means faster forward progress of group of contending
threads. Achieved by very long polling before switching to wait,
probably up to several tens of usec and by hyperactive tickless OS
scheduler.

On heavily loaded system with much more work to do than available
cores, 'faster' means more work done by unrelated threads and processes.
Achieved by very short polling before switching to wait, probably less
than 500 nsec and by 'passive' OS scheduler that rarely intervenes
outside of clock tick.

And of course there are cases in the middle.

And then traditional HPC with MPI that is completely different kettle of
fish.

On 4/1/2024 2:01 AM, Bonita Montero wrote:
> Am 01.04.2024 um 10:57 schrieb Bonita Montero:
>> Am 01.04.2024 um 08:40 schrieb Chris M. Thomasson:
>>> On 3/31/2024 11:32 PM, Bonita Montero wrote:
>>>> Am 31.03.2024 um 22:11 schrieb Chris M. Thomasson:
>>>>
>>>>> Well, I have not taken a look at Microsoft's Futex implementation.
>>>>> Afaict, your code showcases that aspect wrt calling into notify on
>>>>> every mutex unlock, and wait on every point of contention wrt lock.
>>>>> Interesting.
>>>>
>>>> I'm using notify and wait only when there's contention.
>>>
>>> Even here?
>>> _____________
>>>                   for( bool cmp; !futex.compare_exchange_weak( cmp =
>>> false, true, memory_order_acquire, memory_order_relaxed ); )
>>>                       futex.wait( true, memory_order_relaxed );
>>>                   futex.store( false, memory_order_release );
>>>                   futex.notify_one();
>>>               }, futexTimes );
>>> ____________
>>>
>>> What am I missing?
>>>
>>>                   futex.store( false, memory_order_release );
>>>                   futex.notify_one();
>>>
>>> ?
>>>
>>
>> Ok, I was talking about my older version.
>> But notify is fast.
>>
>
> An uncontended notify is 2.5ns on my Zen4 computer.
>

For the Microsoft version, right? I don't have Linux installed at the
moment.

Am 01.04.2024 um 21:27 schrieb Chris M. Thomasson:
> On 4/1/2024 2:01 AM, Bonita Montero wrote:
>> Am 01.04.2024 um 10:57 schrieb Bonita Montero:
>>> Am 01.04.2024 um 08:40 schrieb Chris M. Thomasson:
>>>> On 3/31/2024 11:32 PM, Bonita Montero wrote:
>>>>> Am 31.03.2024 um 22:11 schrieb Chris M. Thomasson:
>>>>>
>>>>>> Well, I have not taken a look at Microsoft's Futex implementation.
>>>>>> Afaict, your code showcases that aspect wrt calling into notify on
>>>>>> every mutex unlock, and wait on every point of contention wrt
>>>>>> lock. Interesting.
>>>>>
>>>>> I'm using notify and wait only when there's contention.
>>>>
>>>> Even here?
>>>> _____________
>>>>                   for( bool cmp; !futex.compare_exchange_weak( cmp =
>>>> false, true, memory_order_acquire, memory_order_relaxed ); )
>>>>                       futex.wait( true, memory_order_relaxed );
>>>>                   futex.store( false, memory_order_release );
>>>>                   futex.notify_one();
>>>>               }, futexTimes );
>>>> ____________
>>>>
>>>> What am I missing?
>>>>
>>>>                   futex.store( false, memory_order_release );
>>>>                   futex.notify_one();
>>>>
>>>> ?
>>>>
>>>
>>> Ok, I was talking about my older version.
>>> But notify is fast.
>>>
>>
>> An uncontended notify is 2.5ns on my Zen4 computer.
>>
>
> For the Microsoft version, right? I don't have Linux installed at the
> moment.

Linux with libstdc++ is 1.7ns.

On 4/1/2024 2:18 AM, Michael S wrote:
> On Fri, 29 Mar 2024 14:14:11 +0100
> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>
>> The following program simulates constant locking und unlocking of one
>> to jthread::hardware_concurrency() threadas with a std::mutex and a
>> futex. On my 16 core / 32 thread Zen4 system a futex is faster up to
>> 5 threads constantly contending, but beyond the CPU time of the futex
>> explodes and the conventional mutex is faster with Windows as and with
>> Linux.
>>
>
> In case of heavy contention what to consider 'faster' is not at all
> obvious.
>
> On lightly loaded system with more cores than work to do (a typical
> client) 'faster' means faster forward progress of group of contending
> threads. Achieved by very long polling before switching to wait,
> probably up to several tens of usec and by hyperactive tickless OS
> scheduler.
>
> On heavily loaded system with much more work to do than available
> cores, 'faster' means more work done by unrelated threads and processes.
> Achieved by very short polling before switching to wait, probably less
> than 500 nsec and by 'passive' OS scheduler that rarely intervenes
> outside of clock tick.
>
> And of course there are cases in the middle.
>
> And then traditional HPC with MPI that is completely different kettle of
> fish.
>

Ditto. However, I did find it interesting (20+ years ago) to test worst
case scenarios. What happens when I blast this mutex algorithm A with
artificial load vs algo B forcing it into horrible periods of radical
contention. How do they handle it...

On 4/1/2024 7:37 PM, Bonita Montero wrote:
[...]
>>>> Ok, I was talking about my older version.
>>>> But notify is fast.
>>>>
>>>
>>> An uncontended notify is 2.5ns on my Zen4 computer.

Keep in mind that notify and wait are slow paths. One needs to strive to
minimize calls to notify and wait. Calling notify and/or wait when they
do _have_ to be called is a rather inefficient design.

>>>
>>
>> For the Microsoft version, right? I don't have Linux installed at the
>> moment.
>
> Linux with libstdc++ is 1.7ns.
>

Am 12.04.2024 um 23:16 schrieb Chris M. Thomasson:
> On 4/1/2024 7:37 PM, Bonita Montero wrote:
> [...]
>>>>> Ok, I was talking about my older version.
>>>>> But notify is fast.
>>>>>
>>>>
>>>> An uncontended notify is 2.5ns on my Zen4 computer.
>
> Keep in mind that notify and wait are slow paths.

There's no slow path with futexes since you've to notify _always_.
And 1.7ns isn't slow.

> One needs to strive to minimize calls to notify and wait. Calling notify and/or wait when they
> do _have_ to be called is a rather inefficient design.
>
>
>>>>
>>>
>>> For the Microsoft version, right? I don't have Linux installed at the
>>> moment.
>>
>> Linux with libstdc++ is 1.7ns.
>>
>

On 4/12/2024 6:00 PM, Bonita Montero wrote:
> Am 12.04.2024 um 23:16 schrieb Chris M. Thomasson:
>> On 4/1/2024 7:37 PM, Bonita Montero wrote:
>> [...]
>>>>>> Ok, I was talking about my older version.
>>>>>> But notify is fast.
>>>>>>
>>>>>
>>>>> An uncontended notify is 2.5ns on my Zen4 computer.
>>
>> Keep in mind that notify and wait are slow paths.
>
> There's no slow path with futexes since you've to notify _always_.

Huh? Nope! Where did you get that idea from? calling notify is a slow
path, and calling wait is a slow path.

> And 1.7ns isn't slow.

You do not want to _always_ call notify and/or wait when you do not have to.

>
>> One needs to strive to  minimize calls to notify and wait. Calling
>> notify and/or wait when they do _have_ to be called is a rather
>> inefficient design.

>>
>>
>>>>>
>>>>
>>>> For the Microsoft version, right? I don't have Linux installed at
>>>> the moment.
>>>
>>> Linux with libstdc++ is 1.7ns.
>>>
>>
>