On 2023-11-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 10.11.2023 um 21:44 schrieb Chris M. Thomasson:
>> On 11/10/2023 6:08 AM, Bonita Montero wrote:
>>> Am 10.11.2023 um 14:56 schrieb Branimir Maksimovic:
>>>
>>>>      frame #13: 0x00000001000063d4
>>>> cond_var`std::__1::vector<std::__1::thread,
>>>> std::__1::allocator<std::__1::thread>>::resize(this=0x000000016fdff030 size=2, __sz=0) at vector:1912:15
>>>>      frame #14: 0x0000000100005eec cond_var`main(argc=1,
>>>> argv=0x000000016fdff420) at test_cond.cpp:52:10
>>>>      frame #15: 0x000000018bff50e0 dyld`start + 2360
>>>
>>> It seems that resizing the thread-vector while doing an emplace_back(),
>>> which itself seems to be inlined, fails. I don't know why.
>>>
>>
>> You should of modeled in a race-detector first!
>
> To find bugs inside his jthread-implementation ?
>
There is no bug. I simply used thread instead of jtrhead
as Apple g++ implementation does not have it.
Since thread destructor throws exception
if thread is still running, it calls terminate
handler.
Real g++ implementation works:
Lola@MacBook-Air News % ./cond_var
3566.26
3292.95
Lola@MacBook-Air News %
Same thing is happening with all other
I showed previously.
I placed switch -std=c++20 in Apple's g++,
but anyway it does not have jthread.
take a look:
Lola@MacBook-Air News % clang++ -O3 cond_var.cpp test_cond.cpp -o cond_var -std=c++20 -D__unix__
test_cond.cpp:48:9: error: unknown type name 'jthread'; did you mean 'thread'?
vector<jthread> threads;
^~~~~~~
thread
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/thread:225:24: note: 'thread' declared here
class _LIBCPP_TYPE_VIS thread
^
1 error generated.
Lola@MacBook-Air News %

--

7-77-777, Evil Sinner!
https://www.linkedin.com/in/branimir-maksimovic-6762bbaa/

Am 11.11.2023 um 05:25 schrieb Branimir Maksimovic:

> Lola@MacBook-Air News % ./cond_var
> 3566.26
> 3292.95

Same as on my 3990X Linux PC: 8% faster.

I think I've put the finishing touches to the code now. For the mutex
part I introduced spinning, which I adopted from glibc. Spinning usually
makes little sense for producer-consumer relationships because the time
it takes to put an item in the queue or take it out of it is usually
very short, and the time it takes to produce the item before and consume
it afterwards is usually very short is usually orders of magnitude
higher; Therefore, a collision during locking can occur quite rarely.
Nevertheless, I can also imagine cases where items are produced and
consumed with high frequency, and spinning could make sense there.

So, here are the two changed files:

// monitor.h

#pragma once
#if defined(_WIN32)
#define NOMINMAX
#include <Windows.h>
#elif defined(__unix__)
#include <sys/types.h>
#include <sys/sem.h>
#include <sys/stat.h>
#else
#error unsupported platform
#endif
#include <atomic>
#include <type_traits>
#if defined(_WIN32)
#include "xhandle.h"
#endif

struct monitor
{ monitor( uint16_t maxSpin = 0 );
~monitor();
void lock();
void unlock();
bool try_lock();
void wait();
void notify();
void notify_all();
uint16_t maxSpin( int16_t maxSpin );
private:
inline static thread_local char t_dummy;
static constexpr bool USE64 = std::atomic_int64_t::is_always_lock_free;
using aword_t = std::conditional_t<USE64, uint64_t, uint32_t>;
static constexpr unsigned BITS = sizeof(aword_t) * 8 / 2;
static constexpr aword_t
ENTER_VALUE = 1,
SIGNAL_VALUE = 1ull << BITS,
ENTER_MASK = SIGNAL_VALUE - 1,
SIGNAL_MASK = ENTER_MASK << BITS;
std::atomic<aword_t> m_atomic;
std::atomic<void *> m_threadId;
uint32_t m_recCount;
bool spinLock( aword_t &ref, bool once );
#if defined(_WIN32)
static constexpr uint32_t SEM_MAX = std::numeric_limits<LONG>::max();
XHANDLE
m_xhEnterEvt,
m_xhSignalSem;
#elif defined(__unix__)
static constexpr uint32_t SEM_MAX = std::numeric_limits<short>::max();
int m_sems;
int semop( std::initializer_list<sembuf> sems );
#endif
std::atomic_uint16_t m_maxSpin, m_spinLimit;
};

// monitor.cpp

#include <iostream>
#include <limits>
#include <system_error>
#include <cassert>
#if defined(__x86_64__) || defined(__i386__)
#include <immintrin.h>
#endif
#include "monitor.h"

using namespace std;

monitor::monitor( uint16_t maxSpin ) :
m_atomic( 0 ),
m_threadId( nullptr ),
#if defined(_WIN32)
m_xhEnterEvt( CreateEventA( nullptr, FALSE, FALSE, nullptr ) ),
m_xhSignalSem( CreateSemaphoreA( nullptr, 0, SEM_MAX, nullptr ) ),
#elif defined(__unix__)
m_sems( semget( IPC_PRIVATE, 2, S_IRUSR | S_IWUSR ) ),
#endif
m_maxSpin( maxSpin ),
m_spinLimit( 0 )
{ #if defined(_WIN32)
if( !m_xhEnterEvt.get() || !m_xhSignalSem.get() )
throw system_error( GetLastError(), system_category(), "can't
initialize monitor object" );
#elif defined(__unix__)
auto zeroSem = [&]() -> bool
{
#if defined(__linux__)
return true;
#else
short vals[2] = { 0, 0 };
return !semctl( m_sems, 0, SETALL, vals );
#endif
};
if( m_sems == -1 || zeroSem() )
{
int errNo = errno;
if( m_sems != -1 )
this->~monitor();
throw system_error(errNo, system_category(), "can't initialize monitor
object" );
}
#endif
}

monitor::~monitor()
{ #if defined(__unix__)
int ret = semctl( m_sems, 0, IPC_RMID );
assert(ret != -1);
#endif
}

void monitor::lock()
{ if( m_threadId.load( memory_order_relaxed ) == &t_dummy )
{
if( m_recCount == (uint32_t)-1 )
throw system_error( (int)errc::result_out_of_range,
generic_category(), "montor's recursion count saturated" );
++m_recCount;
return;
}
aword_t ref = m_atomic.load( memory_order_relaxed );
if( spinLock( ref, false ) )
return;
do
{
if( (ref & ENTER_MASK) == ENTER_MASK )
throw system_error( (int)errc::result_out_of_range,
generic_category(), "montor's locker count saturated" );
assert((ref & ENTER_MASK) >= ref >> BITS);
} while( !m_atomic.compare_exchange_strong( ref, ref + 1,
memory_order_acquire, memory_order_relaxed ) );
if( (ref & ENTER_MASK) != ref >> BITS ) [[likely]]
{
#if defined(_WIN32)
if( WaitForSingleObject( m_xhEnterEvt.get(), INFINITE ) != WAIT_OBJECT_0 )
terminate();
#elif defined(__unix__)
if( semop( { { 0, -1, 0 } } ) == -1 )
terminate();
#endif
}
m_threadId.store( &t_dummy, memory_order_relaxed );
m_recCount = 0;
}

void monitor::unlock()
{ if( m_threadId.load( memory_order_relaxed ) == &t_dummy && m_recCount )
return (void)--m_recCount;
aword_t ref = m_atomic.load( memory_order_relaxed );
assert((ref & ENTER_MASK) && m_threadId == &t_dummy);
m_threadId.store( nullptr, memory_order_relaxed );
do
assert((ref & ENTER_MASK) > ref >> BITS);
while( !m_atomic.compare_exchange_strong( ref, ref - 1,
memory_order_release, memory_order_relaxed ) );
if( (ref & ENTER_MASK) - (ref >> BITS) == 1 ) [[likely]]
return;
#if defined(_WIN32)
if( !SetEvent( m_xhEnterEvt.get() ) )
terminate();
#elif defined(__unix__)
if( semop( { { 0, 1, IPC_NOWAIT } } ) == -1 )
terminate();
#endif
}

bool monitor::try_lock()
{ aword_t ref = m_atomic.load( memory_order_relaxed );
return spinLock( ref, true );
}

void monitor::wait()
{ assert(m_threadId == &t_dummy && !m_recCount);
m_threadId.store( nullptr, memory_order_relaxed );
aword_t ref = m_atomic.load( memory_order_relaxed );
do
assert((ref & ENTER_MASK) > ref >> BITS);
while( !m_atomic.compare_exchange_strong( ref, ref + SIGNAL_VALUE,
memory_order_release, memory_order_relaxed ) );
if( (ref & ENTER_MASK) - (ref >> BITS) > 1 )
{
#if defined(_WIN32)
if( !SetEvent( m_xhEnterEvt.get() ) )
terminate();
#elif defined(__unix__)
if( semop( { { 0, 1, IPC_NOWAIT } } ) == -1 )
terminate();
#endif
}
#if defined(_WIN32)
HANDLE waitFor[2] { m_xhEnterEvt.get(), m_xhSignalSem.get() };
if( WaitForMultipleObjects( 2, waitFor, TRUE, INFINITE ) != WAIT_OBJECT_0 )
terminate();
#elif defined(__unix__)
if( semop( { { 0, -1, 0 }, { 1, -1, 0 } } ) == -1 )
terminate();
#endif
m_threadId.store( &t_dummy, memory_order_relaxed );
m_recCount = 0;
}

void monitor::notify()
{ aword_t ref = m_atomic.load( memory_order_relaxed );
assert((ref & ENTER_MASK) > ref >> BITS && m_threadId == &t_dummy);
do
if( !(ref >> BITS) )
return;
while( !m_atomic.compare_exchange_strong( ref, ref - SIGNAL_VALUE,
memory_order_relaxed, memory_order_relaxed ) );
#if defined(_WIN32)
if( !ReleaseSemaphore( m_xhSignalSem.get(), 1, nullptr ) )
terminate();
#elif defined(__unix__)
if( semop( { { 1, 1, IPC_NOWAIT } }) == -1 )
terminate();
#endif
}

void monitor::notify_all()
{ aword_t ref = m_atomic.load( memory_order_relaxed );
assert((ref & ENTER_MASK) > ref >> BITS && m_threadId == &t_dummy);
uint32_t n;
do
if( !(n = (uint32_t)(ref >> BITS)) )
return;
while( !m_atomic.compare_exchange_strong( ref, ref & ENTER_MASK,
memory_order_relaxed, memory_order_relaxed ) );
#if defined(_WIN32)
if( n > SEM_MAX || !ReleaseSemaphore( m_xhSignalSem.get(), n, nullptr ) )
terminate();
#elif defined(__unix__)
for( uint32_t nRelease; n; n -= nRelease )
if( semop( { { 1, (short)(nRelease = n <= SEM_MAX ? n : SEM_MAX),
IPC_NOWAIT } } ) == -1 )
terminate();
#endif
}

uint16_t monitor::maxSpin( int16_t maxSpin )
{ uint16_t curMaxSpin = m_maxSpin.load( memory_order_relaxed );
if( maxSpin >= 0 )
m_maxSpin.store( maxSpin, memory_order_relaxed );
return curMaxSpin;
}

bool monitor::spinLock( aword_t &ref, bool once )
{ // spinning algorithm taken from glibc
uint32_t maxSpin = m_maxSpin.load( memory_order_relaxed );
once = once && !maxSpin;
maxSpin = !once ? maxSpin : 1;
if( !maxSpin )
return false;
uint32_t
prevSpinLimit = m_spinLimit.load( memory_order_relaxed ),
spinLimit = prevSpinLimit * 2u + 10u,
spinCount = 0;
spinLimit = spinLimit <= maxSpin ? spinLimit : maxSpin;
bool locked = false;
for( ; ; ref = m_atomic.load( memory_order_relaxed ) )
{
assert((ref & ENTER_MASK) >= ref >> BITS);
if( uint32_t enterers = ref & ENTER_MASK;
enterers == ref >> BITS && enterers != ENTER_MASK
&& m_atomic.compare_exchange_strong( ref, ref + 1,
memory_order_acquire, memory_order_relaxed ) )
{
m_threadId.store( &t_dummy, memory_order_relaxed );
m_recCount = 0;
locked = true;
break;
}
if( ++spinCount == spinLimit )
break;
#if defined(_WIN32)
YieldProcessor();
#elif (defined(__GNUC__) || defined(__clang__)) && (defined(__x86_64__)
|| defined(__i386__))
_mm_pause();
#elif (defined(__GNUC__) || defined(__clang__)) && (defined(__arm__) ||
defined(__aarch64__))
__yield();
#else
#error "need platform-specific pause-instruction"
#endif
}
if( !once ) [[likely]]
m_spinLimit.store( (uint16_t)(prevSpinLimit + (int32_t)(spinCount -
prevSpinLimit) / 8), memory_order_relaxed );
return locked;
}

Am 11.11.2023 um 11:41 schrieb Bonita Montero:

>     if( m_sems == -1 || zeroSem() )
if( m_sems == -1 || !zeroSem() )

On 11/11/2023 2:41 AM, Bonita Montero wrote:
> I think I've put the finishing touches to the code now. For the mutex
> part I introduced spinning, which I adopted from glibc. Spinning usually
[...]

Food for thought... I learned something really neat over on comp.arch
wrt Lynn Wheeler many years ago. Basically, why spin doing nothing? Oh,
you use a yield... Well, that is still doing nothing. Think of a spin
along the lines of:

we try to use accomplished work as a backoff/yield for a spin...

<quick pseudo-code>
______________
void lock()
{ while (! mutex_trylock())
{
// try to do some "other" work as a
// yield, in a sense... Hummm.... ;^)
if (! try_to_do_some__other__work())
{
// failed to do some other work, lock it...
mutex_lock();
break;
}
}

// we are locked! =^D
}

void unlock()
{ mutex_unlock();
} ______________

Well, this can be beneficial in certain setups...

On 11/11/2023 7:39 AM, Bonita Montero wrote:
> Am 11.11.2023 um 11:41 schrieb Bonita Montero:
>
>>      if( m_sems == -1 || zeroSem() )
>        if( m_sems == -1 || !zeroSem() )
>
>

Is that yet another bug correction? Remember my advise, get it working
then try to make it faster.

Bonita Montero wrote:
> Am 09.11.2023 um 05:42 schrieb Chris M. Thomasson:
>> On 11/8/2023 8:38 PM, Bonita Montero wrote:
>>> Am 09.11.2023 um 05:36 schrieb Chris M. Thomasson:
>>>
>>>> Humm... Are you okay Bonita? Anything wrong with you?
>>>
>>> Hoare monitors relase a waiting thread immediately after a notify()
>>> and that's less efficient.
>
>> Yawn.
>
> Re-acquiring the mutex part of a monitor after notify()
is exactly what Java does -- and it does it for reason.
> is an superfluous extra part that takes CPU time.

Chris M. Thomasson wrote:
> On 11/11/2023 7:39 AM, Bonita Montero wrote:
>> Am 11.11.2023 um 11:41 schrieb Bonita Montero:
>>
>>>      if( m_sems == -1 || zeroSem() )
>>         if( m_sems == -1 || !zeroSem() )
>>
>>
>
> Is that yet another bug correction? Remember my advise, get it working
> then try to make it faster.
Chris, I think you are preaching to the deaf. I would give up 5 times
already. Your patience is angelic.

Am 11.11.2023 um 20:42 schrieb Chris M. Thomasson:

> Is that yet another bug correction? Remember my advise, get it working
> then try to make it faster.

The code immediately crashed because of an exception;
easiest debugging.

Am 11.11.2023 um 23:45 schrieb Pavel:
> Bonita Montero wrote:
>> Am 09.11.2023 um 05:42 schrieb Chris M. Thomasson:
>>> On 11/8/2023 8:38 PM, Bonita Montero wrote:
>>>> Am 09.11.2023 um 05:36 schrieb Chris M. Thomasson:
>>>>
>>>>> Humm... Are you okay Bonita? Anything wrong with you?
>>>>
>>>> Hoare monitors relase a waiting thread immediately after a notify()
>>>> and that's less efficient.
>>
>>> Yawn.
>>
>> Re-acquiring the mutex part of a monitor after notify()
> is exactly what Java does -- and it does it for reason.

No, Java and .net keep holding the mutex while doing a notify().
That's called a Mesa monitor.

>> is an superfluous extra part that takes CPU time.
>
>

On 2023-11-12, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> No, Java and .net keep holding the mutex while doing a notify().
> That's called a Mesa monitor.

I don't suspect that is part of Mesa semantics. (It's definitely part of
Hoare semantics.) Do you have a reference?

Since under Mesa semantics, threads re-acquire the mutex with fewer
guarantees and must re-test the desired condition, Mesa semantics
supports the more efficient protocol of signaling outside of the
monitor.

If you're using POSIX mutexes and conditions, you should call
pthread_cond_signal and pthread_cond_broadcast outside of the mutex,
whenever possible.

(In a nutshell, if you're going to be telling some thread(s) to go ahead
and grab a mutex, get the hell out of their way first).

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Am 12.11.2023 um 06:02 schrieb Kaz Kylheku:

> I don't suspect that is part of Mesa semantics. (It's definitely part of
> Hoare semantics.) Do you have a reference?

Wikipedia (https://en.wikipedia.org/wiki/Monitor_(synchronization):
"With nonblocking condition variables (also called "Mesa style"
condition variables or "signal and continue" condition variables),
signaling does not cause the signaling thread to lose occupancy
of the monitor. Instead the signaled threads are moved to the e
queue."

> Since under Mesa semantics, threads re-acquire the mutex with fewer
> guarantees and must re-test the desired condition, Mesa semantics
> supports the more efficient protocol of signaling outside of the
> monitor.

This is a theoretical advantage. In fact, a combination of mutex
and condition variable, like a monitor implicitly is, is intended
for procuder-consumer patterns. And at this point it never happens
that you want to signal something but don't modify a common state.

> If you're using POSIX mutexes and conditions, you should call
> pthread_cond_signal and pthread_cond_broadcast outside of the
> mutex, whenever possible.

That actually never happens because you have to lock the mutex
anyway.

On 2023-11-12, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 12.11.2023 um 06:02 schrieb Kaz Kylheku:
>
>> I don't suspect that is part of Mesa semantics. (It's definitely part of
>> Hoare semantics.) Do you have a reference?
>
> Wikipedia (https://en.wikipedia.org/wiki/Monitor_(synchronization):
> "With nonblocking condition variables (also called "Mesa style"
> condition variables or "signal and continue" condition variables),
> signaling does not cause the signaling thread to lose occupancy
> of the monitor. Instead the signaled threads are moved to the e
> queue."

That doesn't say that signaling *requires* the monitor to be held,
though!

>> Since under Mesa semantics, threads re-acquire the mutex with fewer
>> guarantees and must re-test the desired condition, Mesa semantics
>> supports the more efficient protocol of signaling outside of the
>> monitor.
>
> This is a theoretical advantage.

No it isn't. The signal operation can trap into a kernel, which can
require hundreds of cycles. The mutex/monitor should ideally be only
held only as long as necessary to protect the shared variables, and not
be extended over unrelated, lengthy operations. That encourages
unnecessary contention.

>> If you're using POSIX mutexes and conditions, you should call
>> pthread_cond_signal and pthread_cond_broadcast outside of the
>> mutex, whenever possible.
>
> That actually never happens because you have to lock the mutex
> anyway.

Pardon me, what is it that you believe doesn't actually happen? People
coding this:

// ...

pthread_mutex_unlock(&obj->mtx);
pthread_cond_signal(&obj->foo_cond);

rather than this:

// ...

pthread_cond_signal(&obj->foo_cond);
pthread_mutex_unlock(&obj->mtx);

?

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Bonita Montero <Bonita.Montero@gmail.com> writes:
>Am 12.11.2023 um 06:02 schrieb Kaz Kylheku:
>
>> I don't suspect that is part of Mesa semantics. (It's definitely part of
>> Hoare semantics.) Do you have a reference?
>
>Wikipedia (https://en.wikipedia.org/wiki/Monitor_(synchronization):
>"With nonblocking condition variables (also called "Mesa style"
>condition variables or "signal and continue" condition variables),
>signaling does not cause the signaling thread to lose occupancy
>of the monitor. Instead the signaled threads are moved to the e
>queue."
>
>> Since under Mesa semantics, threads re-acquire the mutex with fewer
>> guarantees and must re-test the desired condition, Mesa semantics
>> supports the more efficient protocol of signaling outside of the
>> monitor.
>
>This is a theoretical advantage. In fact, a combination of mutex
>and condition variable, like a monitor implicitly is, is intended
>for procuder-consumer patterns. And at this point it never happens
>that you want to signal something but don't modify a common state.
>
>
>> If you're using POSIX mutexes and conditions, you should call
>> pthread_cond_signal and pthread_cond_broadcast outside of the
>> mutex, whenever possible.
>
>That actually never happens because you have to lock the mutex
>anyway.

No, you don't. If you updated the predicate that the condition
variable is monitoring while holding the mutex, you should release
the mutex before signaling or broadcasting the condition variable
to avoid unnecessary context switches.

On 11/11/2023 8:40 PM, Bonita Montero wrote:
> Am 11.11.2023 um 20:42 schrieb Chris M. Thomasson:
>
>> Is that yet another bug correction? Remember my advise, get it working
>> then try to make it faster.
>
> The code immediately crashed because of an exception;
> easiest debugging.
>

Yet, you missed it? Actually, I am not quite sure how to parse your
response. I have not had the free time to port your code over to a
Relacy test unit, yet...

:^)

On 11/12/2023 2:00 AM, Bonita Montero wrote:
> Am 12.11.2023 um 06:02 schrieb Kaz Kylheku:
>
>> I don't suspect that is part of Mesa semantics. (It's definitely part of
>> Hoare semantics.) Do you have a reference?
>
> Wikipedia (https://en.wikipedia.org/wiki/Monitor_(synchronization):
> "With nonblocking condition variables (also called "Mesa style"
> condition variables or "signal and continue" condition variables),
> signaling does not cause the signaling thread to lose occupancy
> of the monitor. Instead the signaled threads are moved to the e
> queue."

Humm... A wait morph? ;^)

>
>> Since under Mesa semantics, threads re-acquire the mutex with fewer
>> guarantees and must re-test the desired condition, Mesa semantics
>> supports the more efficient protocol of signaling outside of the
>> monitor.
>
> This is a theoretical advantage. In fact, a combination of mutex
> and condition variable, like a monitor implicitly is, is intended
> for procuder-consumer patterns. And at this point it never happens
> that you want to signal something but don't modify a common state.
>
>
>> If you're using POSIX mutexes and conditions, you should call
>> pthread_cond_signal and pthread_cond_broadcast outside of the
>> mutex, whenever possible.
>
> That actually never happens because you have to lock the mutex
> anyway.

On 11/12/2023 9:53 AM, Scott Lurndal wrote:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
>> Am 12.11.2023 um 06:02 schrieb Kaz Kylheku:
>>
>>> I don't suspect that is part of Mesa semantics. (It's definitely part of
>>> Hoare semantics.) Do you have a reference?
>>
>> Wikipedia (https://en.wikipedia.org/wiki/Monitor_(synchronization):
>> "With nonblocking condition variables (also called "Mesa style"
>> condition variables or "signal and continue" condition variables),
>> signaling does not cause the signaling thread to lose occupancy
>> of the monitor. Instead the signaled threads are moved to the e
>> queue."
>>
>>> Since under Mesa semantics, threads re-acquire the mutex with fewer
>>> guarantees and must re-test the desired condition, Mesa semantics
>>> supports the more efficient protocol of signaling outside of the
>>> monitor.
>>
>> This is a theoretical advantage. In fact, a combination of mutex
>> and condition variable, like a monitor implicitly is, is intended
>> for procuder-consumer patterns. And at this point it never happens
>> that you want to signal something but don't modify a common state.
>>
>>
>>> If you're using POSIX mutexes and conditions, you should call
>>> pthread_cond_signal and pthread_cond_broadcast outside of the
>>> mutex, whenever possible.
>>
>> That actually never happens because you have to lock the mutex
>> anyway.
>
> No, you don't. If you updated the predicate that the condition
> variable is monitoring while holding the mutex, you should release
> the mutex before signaling or broadcasting the condition variable
> to avoid unnecessary context switches.

Yup. Actually, there was an old discussion about this around 20 ish
years ago back on comp.programming.threads. David Butenhof was involved.

Bonita Montero wrote:
> Am 11.11.2023 um 23:45 schrieb Pavel:
>> Bonita Montero wrote:
>>> Am 09.11.2023 um 05:42 schrieb Chris M. Thomasson:
>>>> On 11/8/2023 8:38 PM, Bonita Montero wrote:
>>>>> Am 09.11.2023 um 05:36 schrieb Chris M. Thomasson:
>>>>>
>>>>>> Humm... Are you okay Bonita? Anything wrong with you?
>>>>>
>>>>> Hoare monitors relase a waiting thread immediately after a notify()
>>>>> and that's less efficient.
>>>
>>>> Yawn.
>>>
>>> Re-acquiring the mutex part of a monitor after notify()
>> is exactly what Java does -- and it does it for reason.
>
> No, Java and .net keep holding the mutex while doing a notify().

Don't change the subject. Java releases lock *on waiting thread* (which
is the behavior of a Hoare monitor by design) while waiting and then
reacquires it after it was notified.

RTFM for once (although, I know you won't):

"
public final void wait()
throws InterruptedException

Causes the current thread to wait until another thread invokes the
notify() method or the notifyAll() method for this object. In other
words, this method behaves exactly as if it simply performs the call
wait(0).

The current thread must own this object's monitor. The thread releases
ownership of this monitor and waits until another thread notifies
threads waiting on this object's monitor to wake up either through a
call to the notify method or the notifyAll method. The thread then waits
until it can re-obtain ownership of the monitor and resumes execution.
"

> That's called a Mesa monitor.
>
>>> is an superfluous extra part that takes CPU time.
>>
>>
>

Kaz Kylheku wrote:
> On 2023-11-12, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> No, Java and .net keep holding the mutex while doing a notify().
>> That's called a Mesa monitor.
>
> I don't suspect that is part of Mesa semantics. (It's definitely part of
> Hoare semantics.) Do you have a reference?
She doesn't. See my citation in response to her post for the reference
to the contrary.

>
> Since under Mesa semantics, threads re-acquire the mutex with fewer
> guarantees and must re-test the desired condition, Mesa semantics
> supports the more efficient protocol of signaling outside of the
> monitor.
>
> If you're using POSIX mutexes and conditions, you should call
> pthread_cond_signal and pthread_cond_broadcast outside of the mutex,
> whenever possible.
This is recommended against by the standard for the same reason why Java
implements Hoare monitor behavior. Citation:

"
The pthread_cond_broadcast() or pthread_cond_signal() functions may be
called by a thread whether or not it currently owns the mutex that
threads calling pthread_cond_wait() or pthread_cond_timedwait() have
associated with the condition variable during their waits; however, if
predictable scheduling behavior is required, then that mutex shall be
locked by the thread calling pthread_cond_broadcast() or
pthread_cond_signal().
"

>
> (In a nutshell, if you're going to be telling some thread(s) to go ahead
> and grab a mutex, get the hell out of their way first).
>

Scott Lurndal wrote:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
>> Am 12.11.2023 um 06:02 schrieb Kaz Kylheku:
>>
>>> I don't suspect that is part of Mesa semantics. (It's definitely part of
>>> Hoare semantics.) Do you have a reference?
>>
>> Wikipedia (https://en.wikipedia.org/wiki/Monitor_(synchronization):
>> "With nonblocking condition variables (also called "Mesa style"
>> condition variables or "signal and continue" condition variables),
>> signaling does not cause the signaling thread to lose occupancy
>> of the monitor. Instead the signaled threads are moved to the e
>> queue."
>>
>>> Since under Mesa semantics, threads re-acquire the mutex with fewer
>>> guarantees and must re-test the desired condition, Mesa semantics
>>> supports the more efficient protocol of signaling outside of the
>>> monitor.
>>
>> This is a theoretical advantage. In fact, a combination of mutex
>> and condition variable, like a monitor implicitly is, is intended
>> for procuder-consumer patterns. And at this point it never happens
>> that you want to signal something but don't modify a common state.
>>
>>
>>> If you're using POSIX mutexes and conditions, you should call
>>> pthread_cond_signal and pthread_cond_broadcast outside of the
>>> mutex, whenever possible.
>>
>> That actually never happens because you have to lock the mutex
>> anyway.
>
> No, you don't. If you updated the predicate that the condition
> variable is monitoring while holding the mutex, you should release
> the mutex before signaling or broadcasting the condition variable
> to avoid unnecessary context switches.
>
Why would you have additional context switches if you signal before
releasing the lock?

On 11/12/2023 4:29 PM, Pavel wrote:
> Kaz Kylheku wrote:
>> On 2023-11-12, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> No, Java and .net keep holding the mutex while doing a notify().
>>> That's called a Mesa monitor.
>>
>> I don't suspect that is part of Mesa semantics. (It's definitely part of
>> Hoare semantics.) Do you have a reference?
> She doesn't. See my citation in response to her post for the reference
> to the contrary.
>
>>
>> Since under Mesa semantics, threads re-acquire the mutex with fewer
>> guarantees and must re-test the desired condition, Mesa semantics
>> supports the more efficient protocol of signaling outside of the
>> monitor.
>>
>> If you're using POSIX mutexes and conditions, you should call
>> pthread_cond_signal and pthread_cond_broadcast outside of the mutex,
>> whenever possible.
> This is recommended against by the standard for the same reason why Java
> implements Hoare monitor behavior. Citation:
>
> "
> The pthread_cond_broadcast() or pthread_cond_signal() functions may be
> called by a thread whether or  not  it  currently  owns  the  mutex that
> threads calling pthread_cond_wait() or pthread_cond_timedwait() have
> associated with the condition variable during their waits; however, if
> predictable  scheduling  behavior  is required, then that mutex shall be
> locked by the thread calling pthread_cond_broadcast() or
> pthread_cond_signal(). > "
>
>>
>> (In a nutshell, if you're going to be telling some thread(s) to go ahead
>> and grab a mutex, get the hell out of their way first).
>>
>

Basically, if you signal while locked then another waiting thread is
going to try to acquire the mutex that is already locked by the
signalling thread, instant contention. However, wait morphing techniques
can be used to handle this since a mutex and a condvar are very intimate
with each other anyway. Usually, signalling outside of the mutex is ideal.

On 2023-11-13, Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> wrote:
> Kaz Kylheku wrote:
>> If you're using POSIX mutexes and conditions, you should call
>> pthread_cond_signal and pthread_cond_broadcast outside of the mutex,
>> whenever possible.
> This is recommended against by the standard for the same reason why Java
> implements Hoare monitor behavior. Citation:
>
> "
> The pthread_cond_broadcast() or pthread_cond_signal() functions may be
> called by a thread whether or not it currently owns the mutex that
> threads calling pthread_cond_wait() or pthread_cond_timedwait() have
> associated with the condition variable during their waits; however, if
> predictable scheduling behavior is required, then that mutex shall be
> locked by the thread calling pthread_cond_broadcast() or
> pthread_cond_signal().
> "

But that text is stupid/defective, because you will not actually get
predictable scheduling behavior just by doing that.

Signal the condition while still holding the mutex doesn't give you any
guarantees about which thread will get the mutex next.

Suppose:

1. The signal operation wake up the next waiting thread.

2. The signaler then gives up the mutex.

3. Before that awoken next-waiting-thread gets the mutex, some
another thread comes along and seizes the mutex.

Signaling in the mutex can blow up the critical region from "handful of
instructions" to "hundreds of instructions".

If we compare:

mutex_lock(&stack->lock);
node->next = stack->top;
stack->top = node;
mutex_unlock(&stack->lock);

cond_signal(&stack->item_pushed);

All that is in the critical region are the mutex are the list
manipulation instructions, plus some of the mutex code itself.

If we move cond_signal before mutex_unlock, everything done by that
function, including potentially going into the kernel to wake up a
thread, is now in the mutex.

That's a lot to pay for some vague, unfulfillable promise of
"predictable scheduling behavior", on which you can base approximately
nothing.

Hoare semantics gives you something: that if there are waiting tasks
queued on a condition, the monitor is transferred to the first waiting
one. *And* (I seem to recall) when that thread leaves the monitor, the
original signaler gets it again!

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

On 2023-11-13, Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> wrote:
> Scott Lurndal wrote:
>> No, you don't. If you updated the predicate that the condition
>> variable is monitoring while holding the mutex, you should release
>> the mutex before signaling or broadcasting the condition variable
>> to avoid unnecessary context switches.
>>
> Why would you have additional context switches if you signal before
> releasing the lock?

Because of the situation that the thread which was signaled is
trying to acquire the mutex, which, stupidly, the signaling thread
is still holding. So, oops, back it goes into suspended state, and we
have to context switch to the mutex holder which has to release the
mutex and then switch to that signaled thread again.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Am 12.11.2023 um 18:18 schrieb Kaz Kylheku:

>> This is a theoretical advantage.

> No it isn't. ...

With this code singalling from inside is about 50% faster on
my 3990X Zen2 64 core PC under Ubuntu.

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <vector>

using namespace std;

int main( int argc, char ** )
{ mutex mtx;
condition_variable cv;
constexpr uint64_t N_ITEMS = 100'000'000;
atomic_uint64_t itemOutput( 0 );
auto producer = [&]()
{
static atomic_uint64_t itemCounter( 0 );
while( itemCounter.fetch_add( 1, memory_order_relaxed ) < N_ITEMS )
{
{
unique_lock lock( mtx );
itemOutput.fetch_add( 1, memory_order_relaxed );
if( argc <= 1 )
cv.notify_one();
}
if( argc > 1 )
cv.notify_one();
}
};
unsigned nProducers = jthread::hardware_concurrency() - 1;
vector<jthread> procuders;
procuders.reserve( nProducers );
for( unsigned t = 0; t != nProducers; ++t )
procuders.emplace_back( producer );
uint64_t nextItem = 0;
for( ; ; )
{
unique_lock lock( mtx );
uint64_t lastItem;
while( (lastItem = itemOutput.load( memory_order_relaxed )) < nextItem )
cv.wait( lock );
if( lastItem >= N_ITEMS )
break;
nextItem = lastItem;
}
}

Am 12.11.2023 um 18:53 schrieb Scott Lurndal:

> No, you don't. If you updated the predicate that the condition
> variable is monitoring while holding the mutex, you should release
> the mutex before signaling or broadcasting the condition variable
> to avoid unnecessary context switches.

The context switch occurs only if _both_ conditions are met:
the mutex is unlocked and the condition variable is signalled.