chaoran / fast-wait-free-queue Goto Github PK

  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,

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.

1. Yang and Mellor-Crummey. A Wait-free Queue as Fast as Fetch-and-Add. PPoPP 2016.

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'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?

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 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

• 1 Thread 0x7ffff7fe0740 (LWP 25676) "test" 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

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.:

• It seems I need to implement 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