Re: C++1x: lock-free algos and blocking
On 18 =CF=CB=D4, 21:03, "Chris M. Thomasson" <n...@spam.invalid> wrote:
C++1x provides a complete toolset for lock-based programming: mutex
for ensuring consistency and condition variable for blocking/
signaling.
However, as for lock-free (non-blocking) programming C++1x provides
only atomics for ensuring consistency. And what about thread blocking/
signaling? Condition variables are of no help here, because they
require the state to be protected by a mutex. Yes, some lock-free
algorithms do not require blocking (for example, hash map). But things
like producer-consumer queues, work-stealing deques, etc, do require
some primitives for thread blocking/signaling.
I would like to hear from some people close to the committee on this.
How it's intended I must handle this?
Yes, I can build a semaphore from mutex+condvar+counter. And then
build blocking/signaling logic on top of the semaphore. However IMHO
it's (1) a kind of suboptimal from performance point of view and (2)
everybody will have to build it's own semaphore.
For example, Java provides thread park/unpark primitives for that
purpose, which is a kind of semaphore associated with every thread
with sticky signals and a maximum value of 1. IMHO, it's not the way
to go for C++1x, because one will have to pass thread objects
everywhere.
Thank you.
Humm. Well, the "simplest" algorithm I know of is basically equal to the
original eventcount algorithm I posted here, except it uses different
waitbit value and increments the counter by an even number:
Should something like this be standardized? I am not so sure here simply
because one can rather easily use C++1x to create a 100% portable
implementation of an eventcount... Humm...
Chris, probably your are right in the sense that if one builds lock-
free algorithms then he must be able to build blocking/signaling logic
too. And std::condition_variable+std::mutex is a sufficient toolset
for that.
Since you've mentioned an eventcount, I know what you will hear next -
"write your proposal" :)
Btw, here is "a more C++" interface for an eventcount, I've designed
for a contribution to Intel TBB. It supports RAII waiting, and
signaling with arbitrary predicate, with which you may encode for
example "wakeup only thread that waits for exactly this
element" (useful for producer-consumer queues), or "wakeup all threads
that satisfy this condition but at least 1 thread" (useful for work-
stealing environments, condition means data affinity): such fine-
grained signaling avoids unnecessary thread wakeups and thundering
herd, the idea is that it's better to do some more work on producer
thread but avoid boatload of senseless thread wakeups/blocks:
class eventcount
{
public:
eventcount()
void prepare_wait(void* ctx = 0);
void commit_wait();
void cancel_wait();
void notify_one();
void notify_one_relaxed();
void notify_all()
void notify_all_relaxed();
template<typename predicate_t> void notify(predicate_t pred);
template<typename predicate_t> void notify_relaxed(predicate_t
pred)
class wait_guard;
};
class eventcount::wait_guard
{
public:
wait_guard(eventcount& ec, void* ctx = 0);
void commit_wait();
};
And predicate for notify must be of the form:
bool pred(void* ctx, size_t thread_count, size_t thread_index);
// ctx is a arbitrary values passed to prepare_wait (can be allocated
on a stack of a blocked thread)
// return value determines unblock thread or not
--
Dmitriy V'jukov