Event objects

[mvor...@gmail.com]

Thanks to many suggestions of people on here and reddit here's the event object implementation I came up with: http://blog.vorbrodt.me/?p=556

[Chris M. Thomasson]

On 2/8/2019 6:24 AM, mvor...@gmail.com wrote:
> Thanks to many suggestions of people on here and reddit here's the event object implementation I came up with: http://blog.vorbrodt.me/?p=556
>

Fwiw, actually, I remember several use cases for the auto-reset event.
One is to treat it like the "slow" sema in the fast semaphore. Instead
of a semaphore, this is a mutex developed by Alex Terekhov. He showed it
to me back on comp.programming.threads. Iirc, it should be in the
following source code for a pthread_mutex_t:

https://www.sourceware.org/pthreads-win32

Have translated it back in the day to C++ _before_ threads, atomics and
membars. Have translated it to several assembly languages, but not C++11.

I have not tested your code in a Relacy test unit yet. They look fine,
but it is good to test them. A great test would be to use the auto-reset
event as the slow path for a mutex.

[Chris M. Thomasson]

Interested? :^)

[mvor...@gmail.com]

yes, interested :) please email me directly at mar...@vorbrodt.me and we can work on implementing it in modern C++ :)

[mvor...@gmail.com]

This?

class fast_mutex
{
public:
fast_mutex() : m_event(true) {}

void lock() noexcept
{
m_event.wait();
}

void unlock() noexcept
{
m_event.signal();
}

private:
auto_event m_event;
};

Or this?

class fast_mutex
{
public:
fast_mutex() : m_semaphore(1) {}

void lock() noexcept
{
m_semaphore.wait();
}

void unlock() noexcept
{
m_semaphore.post();
}

private:
fast_semaphore m_semaphore;
};

[Chris M. Thomasson]

On 2/12/2019 8:01 AM, mvor...@gmail.com wrote:
> On Tuesday, February 12, 2019 at 1:32:31 AM UTC-5, Chris M. Thomasson wrote:
>> On 2/8/2019 6:24 AM, mvor...@gmail.com wrote:
>>> Thanks to many suggestions of people on here and reddit here's the event object implementation I came up with: http://blog.vorbrodt.me/?p=556
>>>
>>
>> Fwiw, actually, I remember several use cases for the auto-reset event.
>> One is to treat it like the "slow" sema in the fast semaphore. Instead
>> of a semaphore, this is a mutex developed by Alex Terekhov. He showed it
>> to me back on comp.programming.threads. Iirc, it should be in the
>> following source code for a pthread_mutex_t:
>>
>> https://www.sourceware.org/pthreads-win32
>>
>> Have translated it back in the day to C++ _before_ threads, atomics and
>> membars. Have translated it to several assembly languages, but not C++11.
>>
>> I have not tested your code in a Relacy test unit yet. They look fine,
>> but it is good to test them. A great test would be to use the auto-reset
>> event as the slow path for a mutex.
>
> This?

[...]
> Or this?
[...]

Neither. It is using some atomics for the fast-path of the mutex before
the slow-path is engaged. Think of an auto-reset event as a binary
semaphore. Will have some more time later on today, or tomorrow. Take a
look at the source code for a pthread_mutex_t in pthreads-win32. It is
in there. Very similar to the fast semaphore avoiding calls into the
"slow" mutex/cond slow-path.

[Chris M. Thomasson]

Fwiw, I just coded up a Relacy test unit for it. Works like a charm.
Here is the code, using standalone membars to show you exactly where
they need to be:
____________________________
// Mutex Relacy Test...
// Algorithm By: Alex Terekhov
// Relacy Impl By: Chris M. Thomasson
//_______________________________________________


//#define RL_DEBUGBREAK_ON_ASSERT
//#define RL_MSVC_OUTPUT
//#define RL_FORCE_SEQ_CST
//#define RL_GC


#include <relacy/relacy_std.hpp>
#include <iostream>


// Simple macro based redirection of the verbose std membars.
#define CT_MB_ACQ std::memory_order_acquire
#define CT_MB_REL std::memory_order_release
#define CT_MB_RLX std::memory_order_relaxed
#define CT_MB_ACQ_REL std::memory_order_acq_rel
#define CT_MB_SEQ_CST std::memory_order_seq_cst
#define CT_MB(mp_0) std::atomic_thread_fence(mp_0)


// Some global vars directing the show...
// PRODUCERS must equal CONSUMERS for this test
#define PRODUCERS 3
#define CONSUMERS 3
#define THREADS (PRODUCERS + CONSUMERS)
#define ITERS 2



// bin-sema
struct ct_auto_reset_event
{
VAR_T(bool) m_state;
std::mutex m_mutex;
std::condition_variable m_cond;

ct_auto_reset_event() : m_state(false) {}

void signal()
{
{
m_mutex.lock($);
VAR(m_state) = true;
m_mutex.unlock($);
}

m_cond.notify_one($);
}

void wait()
{
m_mutex.lock($);
while (VAR(m_state) == false) m_cond.wait(m_mutex, $);
VAR(m_state) = false; // auto-reset
m_mutex.unlock($);
}
};


// just a layer over an auto-reset event
struct ct_fast_mutex
{
std::atomic<unsigned int> m_state;
ct_auto_reset_event m_waitset;

ct_fast_mutex() : m_state(0) {}

void lock()
{
if (m_state.exchange(1, std::memory_order_relaxed))
{
while (m_state.exchange(2, std::memory_order_relaxed))
{
m_waitset.wait();
}
}

std::atomic_thread_fence(std::memory_order_acquire);
}

void unlock()
{
std::atomic_thread_fence(std::memory_order_release);

if (m_state.exchange(0, std::memory_order_relaxed) == 2)
{
m_waitset.signal();
}
}
};



// Relacy Stack Test...
struct ct_fast_mutex_test
: rl::test_suite<ct_fast_mutex_test, THREADS>
{
VAR_T(unsigned int) g_count;
ct_fast_mutex g_mutex;

ct_fast_mutex_test() : g_count(0) {}

void before()
{

}

void after()
{
RL_ASSERT(VAR(g_count) == 0);
}


void consumer(unsigned int tidx)
{
for (unsigned int i = 0; i < ITERS; ++i)
{
g_mutex.lock();
--VAR(g_count);
g_mutex.unlock();
}
}


void producer(unsigned int tidx)
{
for (unsigned int i = 0; i < ITERS; ++i)
{
g_mutex.lock();
++VAR(g_count);
g_mutex.unlock();
}
}


void thread(unsigned int tidx)
{
if (tidx < PRODUCERS)
{
producer(tidx);
}

else
{
consumer(tidx);
}
}
};



// Test away... Or fly? Humm...
int main()
{
{
rl::test_params p;

p.iteration_count = 10000000;
//p.execution_depth_limit = 33333;
//p.search_type = rl::sched_bound;
//p.search_type = rl::fair_full_search_scheduler_type;
//p.search_type = rl::fair_context_bound_scheduler_type;

rl::simulate<ct_fast_mutex_test>(p);
}

return 0;
}
____________________________

:^)

[mvor...@gmail.com]

I still have to learn a lot about the C++ memory model :(
can it be rewritten and simplified into this(?):



class fast_mutex
{
public:
fast_mutex() : m_state(0) {}

void lock()
{
if (m_state.exchange(1, std::memory_order_acquire))

while (m_state.exchange(2, std::memory_order_relaxed))
m_waitset.wait();
}

void unlock()
{
if (m_state.exchange(0, std::memory_order_release) == 2)
m_waitset.signal();
}

private:

std::atomic<unsigned int> m_state;

auto_event m_waitset;
};

[Chris M. Thomasson]

On 2/12/2019 5:27 PM, mvor...@gmail.com wrote:
> On Tuesday, February 12, 2019 at 6:30:05 PM UTC-5, Chris M. Thomasson wrote:
>> On 2/12/2019 5:48 AM, mvor...@gmail.com wrote:
>>> On Tuesday, February 12, 2019 at 1:48:13 AM UTC-5, Chris M. Thomasson wrote:
>>>> On 2/11/2019 10:32 PM, Chris M. Thomasson wrote:
>>>>> On 2/8/2019 6:24 AM, mvor...@gmail.com wrote:

[...]

>> Fwiw, I just coded up a Relacy test unit for it. Works like a charm.
>> Here is the code, using standalone membars to show you exactly where
>> they need to be:
>> ____________________________

[...]

> I still have to learn a lot about the C++ memory model :(
> can it be rewritten and simplified into this(?):
>
>
>
> class fast_mutex
> {
> public:
> fast_mutex() : m_state(0) {}
>
> void lock()
> {
> if (m_state.exchange(1, std::memory_order_acquire))
> while (m_state.exchange(2, std::memory_order_relaxed))
> m_waitset.wait();
> }

^^^^^^^^^^^^^^^^^^^^^^^^^^^^

No, that does not work. You are missing the acquire operation on the
inner while loop condition. The standalone fences work fine, but once
you start embedding the memory_order into the atomic themselves, things
can get trickier. In this case, the acquire needs to be in both of the
atomic exchanges for lock. If we remove one of these acquires, then the
whole algorithm bites the dust:

standalone fences commented out...
________________________

void lock()
{
if (m_state.exchange(1, std::memory_order_acquire))
{

while (m_state.exchange(2, std::memory_order_acquire))
{
m_waitset.wait();
}
}

//std::atomic_thread_fence(std::memory_order_acquire);
}

void unlock()
{
//std::atomic_thread_fence(std::memory_order_release);

if (m_state.exchange(0, std::memory_order_release) == 2)
{
m_waitset.signal();
}
}
________________________


This works because it adheres to the acquire/release relationship
between all of the atomic operations. The standalone fence kept
everything together on a "higher level". Embedding membars inside of
atomics can get you into a lower level, that needs more attention to detail.

[mvor...@gmail.com]

yes I caught that and corrected it before posting on my blog :)

thank you very much for all your help!

[Chris M. Thomasson]

[...]

> yes I caught that and corrected it before posting on my blog :)

You sure did. :^)

Just keep in mind that the acquire needs to be from _both_ of the
possible paths wrt locking the mutex. Imvvho, the standalone fences are
just so nice to work with; a habit of mine. However, they can show one
exactly where they need to be wrt maintaining a coherent memory
visibility relationship.

> thank you very much for all your help!

No problem. Fwiw, I have many fond memories of working with threads,
atomics and membars back in the day. Still pretty good at it, but was
better back then. I am doing a lot of math intensive fractal work now.