Intel® Moderncode for Parallel Architectures
Support for developing parallel programming applications on Intel® Architecture.
1695 Discussions

## an eventcount algorithm...

New Contributor I
330 Views
I am presenting an eventcount algorithm I invented. I know that Dmitriy Vyukov has already submitted one to the TBB, but his algorithm is based on TLS/TSD. I just wanted to show an alternative technique that does not require TLS/TSD. Here is code which is based on Dmitriy excellent Relacy Race Detector package:

```[cpp]#define RL_GC
#include
#include

class eventcount {
public:
typedef unsigned long key_type;

private:
mutable rl::atomic m_count;
rl::mutex m_mutex;
rl::condition_variable m_cond;

void prv_signal(key_type key) {
if (key & 1) {
m_mutex.lock(\$);
while (! m_count(\$).compare_exchange_weak(key, (key + 2) & ~1,
rl::memory_order_seq_cst));
m_mutex.unlock(\$);
m_cond.notify_all(\$);
}
}

public:
eventcount() {
m_count(\$).store(0, rl::memory_order_relaxed);
}

public:
key_type get() const {
return m_count(\$).fetch_or(1, rl::memory_order_acquire);
}

void signal() {
}

void signal_relaxed() {
}

void wait(key_type cmp) {
m_mutex.lock(\$);
if ((m_count(\$).load(rl::memory_order_seq_cst) & ~1) == (cmp & ~1)) {
m_cond.wait(m_mutex, \$);
}
m_mutex.unlock(\$);
}
};

template
class mpmcq {
struct node {
rl::atomic m_next;
T volatile m_state;
};

rl::atomic m_tail;

public:
mpmcq() {
node* n = RL_NEW(node);
n->m_next(\$).store(NULL, rl::memory_order_relaxed);
m_tail(\$).store(n, rl::memory_order_relaxed);
}

~mpmcq() {
}

public:
void push(T& state) {
node* n = RL_NEW(node);
n->m_next(\$).store(NULL, rl::memory_order_relaxed);
n->m_state = state;
p->m_next(\$).store(n, rl::memory_order_seq_cst);
}

bool pop(T& state) {
node* n;
do {
if (! n) return false;
state = n->m_state;
} while (! m_tail(\$).compare_exchange_weak(t, n, rl::memory_order_seq_cst));
return true;
}
};

#define PRODUCERS 2
#define CONSUMERS 2
#define ITERS 6

struct mpmcq_test : rl::test_suite {
eventcount m_ecount;
mpmcq m_queue;
std::atomic m_count;

void before() {
m_count(\$).store(PRODUCERS * ITERS, rl::memory_order_relaxed);
}

void invariant() {
}

void after() {
}

int i;
if (tidx < PRODUCERS) {
for (i = 0; i < ITERS; ++i) {
m_queue.push(i);
m_ecount.signal();
}
} else {
do {
while (! m_queue.pop(i)) {
eventcount::key_type key = m_ecount.get();
if (m_queue.pop(i)) break;
m_ecount.wait(key);
}
} while (i != -666 &&
if (i != -666) {
for (i = 1; i < CONSUMERS; ++i) {
int x = -666;
m_queue.push(x);
}
m_ecount.signal();
}
}
}
};

int main() {
rl::test_params params;
params.iteration_count = 99999999;
//params.search_type = rl::fair_full_search_scheduler_type;
//params.search_type = rl::fair_context_bound_scheduler_type;
rl::simulate(params);
std::puts("nnn____________________________________n"
"DONE!!!!npress  to exit...");
std::fflush(stdin);
std::fflush(stdout);
std::getchar();
return 0;
}[/cpp]```

Here is an implementation of the algorithm in C#:

http://cpt.pastebin.com/f72cc3cc1

You can obtain Relacy here: