chaoran / fast-wait-free-queue Goto Github PK
View Code? Open in Web Editor NEWA benchmark framework for concurrent queue implementations
License: MIT License
A benchmark framework for concurrent queue implementations
License: MIT License
I'm now trying to use LCRQ in production and I found that queue_free for it isn't implemented. I'm trying to implement it myself, however currently I'm getting some trouble to keep track of ring queue buffers being swapped of the queue. Could you provide a proper implementation of LCRQ queue_free?
Hi Chaoran.
As I appreciate and study from the wonderful technology and extraordinary ideas of this wait-free queue impl, a tricky question produced in my heart, this question looks like violate Invariant 1(enqueue result cannot be changed in future) in [1], maybe you can have a look when you have time.
It ocurred when someone(enq-thread itself or deq-helper-thread) put a enqueue request in one cell(index) through enq_slow or help_enq, The question is, when we put request in the cell, we know enq.id, the unique request responsible by this cell. But when others help this request to improve parallelism, they may read another enqueue request there:
long ei = ACQUIRE(&e->id);
void *ev = ACQUIRE(&e->val);
if (ei > i) {
if (c->val == TOP && q->Ei <= i) return BOT;
} else {
if ((ei > 0 && CAS(&e->id, &ei, -i)) || (ei == -i && c->val == TOP)) {
long Ei = q->Ei;
while (Ei <= i && !CAS(&q->Ei, &Ei, i + 1))
;
c->val = ev;
}
}
Actually, the enq of one enqueue thread will evolution like a sequence(val1,id1) (va2,id2) and so on.
We could recognized value belongs to a later request, but we can't distinguish id1 and id2, so image two deq-thread to help the same Cell, maybe thread1 help_enq one Cell with id1(val1) and produce result TOP(because other cell do real-help), then, enqueue thread of id1(val1) produce new request(va2, id2), and thread2 in help_enq process the same Cell with id2(val2) but may produce result val2 if id2 is appropriate. This behavior maybe lost data in help_deq, caused by higher-cell defeats lower-cell then:
if (new != 0) {
if (CASra(&deq->idx, &idx, new)) idx = new;
if (idx >= new) new = 0;
}
Because the valid value in lower-cell will be lost, and there seems to be no simple solution for me.
Hi chaoran, this is confirm stuck if mcsp
Nproc = 16
consumer: 14
producer: 1
0x0000000000400e5f in running_wfq_test (arg_producer=, arg_consumer=, arg_producing=,
arg_consuming=, total_threads=15, test_type=0x401fbd "MCSP") at main_test.c:121
121 while (__sync_fetch_and_add(&config.nConsuming, 0) < TEST_MAX_INPUT * (config.nProducer)) {
Missing separate debuginfos, use: debuginfo-install glibc-2.17-222.el7.x86_64
(gdb) info threads
Id Target Id Frame
16 Thread 0x7fffbf7fe700 (LWP 25694) "test" spin (p=0x7fffc8031980) at wfqueue.c:32
15 Thread 0x7fffbffff700 (LWP 25693) "test" spin (p=0x7fffc8032180) at wfqueue.c:32
14 Thread 0x7fffdcff9700 (LWP 25692) "test" spin (p=0x7fffc80324c0) at wfqueue.c:30
13 Thread 0x7fffdd7fa700 (LWP 25691) "test" 0x0000000000401788 in spin (p=0x7fffc8032a80) at wfqueue.c:30
12 Thread 0x7fffddffb700 (LWP 25690) "test" 0x0000000000401788 in spin (p=0x7fffc8032d80) at wfqueue.c:30
11 Thread 0x7fffde7fc700 (LWP 25689) "test" 0x0000000000401788 in spin (p=0x7fffc8033200) at wfqueue.c:30
10 Thread 0x7fffdeffd700 (LWP 25688) "test" spin (p=0x7fffc8033540) at wfqueue.c:32
9 Thread 0x7fffdf7fe700 (LWP 25687) "test" spin (p=0x7fffc80338c0) at wfqueue.c:32
8 Thread 0x7fffdffff700 (LWP 25686) "test" 0x0000000000401788 in spin (p=0x7fffc8033cc0) at wfqueue.c:30
7 Thread 0x7ffff4fec700 (LWP 25685) "test" 0x00000000004017f9 in help_enq (i=91476149, c=0x7fffc8033ec0, th=0x7fffd8001000, q=0x605000)
at wfqueue.c:213
6 Thread 0x7ffff57ed700 (LWP 25684) "test" 0x0000000000401788 in spin (p=0x7fffe4013080) at wfqueue.c:30
5 Thread 0x7ffff5fee700 (LWP 25683) "test" 0x0000000000401788 in spin (p=0x7fffe4013200) at wfqueue.c:30
4 Thread 0x7ffff67ef700 (LWP 25682) "test" 0x0000000000401788 in spin (p=0x7fffc802cd80) at wfqueue.c:30
3 Thread 0x7ffff6ff0700 (LWP 25681) "test" 0x0000000000401788 in spin (p=0x7fffe4013380) at wfqueue.c:30
Hi,
I'm trying out a conversion of the wfqueue.c
to Rust. The following line of code in enq_slow()
seems to be partly dead if (CAS(&enq->id, &id, -i)) id = -i;
. The CAS is still needed, I think, but the Rust compiler has identified that the store to id
is never needed. Cursory examination of the code following the do-while loop would indeed suggest that is the case, as id
is always written to.
Of course, the compiler could be wrong...
I get the following error with a high core count:
#! Host: archlinux
#! Benchmarks: wfqueue wfqueue0 faa lcrq ccqueue msqueue delay
#! Threads: 36
36 300.96 3.95 309.71 2.89 205.67 4.08(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
./driver: line 40: ((: 2 >= 10 || 2 >= 5 && == 1: syntax error: operand expected (error token is "== 1")
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
./driver: line 40: ((: 3 >= 10 || 3 >= 5 && == 1: syntax error: operand expected (error token is "== 1")
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
(standard_in) 1: syntax error
./driver: line 40: ((: 4 >= 10 || 4 >= 5 && == 1: syntax error: operand expected (error token is "== 1")
Probably because in the following line https://github.com/chaorayn/fast-wait-free-queue/blob/master/driver#L40
$(echo "$PRECISION < 0.02" | bc)
gives empty result
Hi! I'm porting the queue described in [1] to Rust: https://github.com/jeehoonkang/crossbeam-queue It's a work in progress, but soon I'd like to evaluate its performance using the benchmark tools in this repo (mainly for comparing with the implementation in wfqueue.c
).
So I'm following the instruction in README.md [2] for adding a new queue implementation, but I found that README.md differs from what is described in queue.h
, esp.:
queue_free
, but it's not documented in the README.EMPTY
is described in README, but it is not declared in queue.h
.I could kinda guess what are they, but I wonder if the author of this repository could clarify their meanings. Thank you very much!
[1] Yang and Mellor-Crummey. A Wait-free Queue as Fast as Fetch-and-Add. PPoPP 2016.
[2] https://github.com/chaoran/fast-wait-free-queue/blob/master/README.md#how-to-add-a-new-queue-implementation
Id Target Id Frame
16 Thread 0x7fffbf7fe700 (LWP 22384) "a.out" 0x0000000000401779 in help_enq (i=33724383, c=0x7fffcc05db40, th=0x7fffb4001000, q=0x605000)
at wfqueue.c:213
15 Thread 0x7fffbffff700 (LWP 22383) "a.out" 0x000000000040192b in help_enq (i=33705511, c=0x7fffc80aa3c0, th=0x7fffb0001000, q=0x605000)
at wfqueue.c:236
14 Thread 0x7fffdcff9700 (LWP 22382) "a.out" spin (p=0x7fffcc0f3940) at wfqueue.c:30
13 Thread 0x7fffdd7fa700 (LWP 22381) "a.out" spin (p=0x7fffcc05e140) at wfqueue.c:30
12 Thread 0x7fffddffb700 (LWP 22380) "a.out" spin (p=0x7fffcc05e2c0) at wfqueue.c:30
11 Thread 0x7fffde7fc700 (LWP 22379) "a.out" spin (p=0x7fffcc05e3c0) at wfqueue.c:30
10 Thread 0x7fffdeffd700 (LWP 22378) "a.out" spin (p=0x7fffcc05c140) at wfqueue.c:32
* 1 Thread 0x7ffff7fe0740 (LWP 22369) "a.out" 0x0000000000400def in running_wfq_test (arg_producer=<optimized out>, arg_consumer=<optimized out>,
This issue happened on and off, and it always stucking at last 5 count
Total Nproc = 16 core
nProducerThread = 8, nConsumerThread= 7
nProducing = 8000000, nConsuming = 7999995,
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.