Lock-free queue: SPMC + MPMC

Hello,

Lock-free SPMC algorithm to handle queue FIFO proposed by
Amine Moulay Ramadane, use only single CAS on pop and
no CAS on push. You can use it in a work-stealing manner
with a local queue for each server thread to optimize for more
throuput and minimize contention.

and

Lock-free MPMC algorithm to handle queue FIFO proposed
by Dariusz Mazur (and modified by Amine Moulay Ramdane),
use only single CAS on pop and single CAS on push.


Welcome:  http://www.colba.net/~aminer/


Regards,
Amine.

Hello,


Language: FPC Pascal v2.2.0+ / Delphi 5+: http://www.freepascal.org/
Operating Systems: Win , Linux and Mac (x86).


Regards,
Amine Moulay Ramdane.


On Jun 30, 1:29 pm, Amine <ami...@...net> wrote:
>Hello,
>
>Lock-free SPMC algorithm to handle queue FIFO proposed by
>Amine Moulay Ramadane, use only single CAS on pop and
>no CAS on push. You can use it in a work-stealing manner
>with a local queue for each server thread to optimize for more
>throuput and minimize contention.
>
>and
>
>Lock-free MPMC algorithm to handle queue FIFO proposed
>by Dariusz Mazur (and modified by Amine Moulay Ramdane),
>use only single CAS on pop and single CAS on push.
>
>Welcome:  http://www.colba.net/~aminer/
>
>Regards,
>Amine.

"Amine" <aminer@...net> wrote in message
news:be08f1b1-f624-4bd6-a166-fdd2ce1ac688@...com...
>
>Hello,
>
>Lock-free SPMC algorithm to handle queue FIFO proposed by
>Amine Moulay Ramadane, use only single CAS on pop and
>no CAS on push. You can use it in a work-stealing manner
>with a local queue for each server thread to optimize for more
>throuput and minimize contention.

Did you fix the bug that Relacy found?




>and
>
>Lock-free MPMC algorithm to handle queue FIFO proposed
>by Dariusz Mazur (and modified by Amine Moulay Ramdane),
>use only single CAS on pop and single CAS on push.

I will code this in Relacy when I get some time.




>Welcome:  http://www.colba.net/~aminer/

On Jun 30, 7:42 pm, "Chris M. Thomasson" <n...@...invalid> wrote:
>"Amine" <ami...@...net> wrote in message
>
>news:be08f1b1-f624-4bd6-a166-fdd2ce1ac688@...com...
>
>
>
>>Hello,
>
>>Lock-free SPMC algorithm to handle queue FIFO proposed by
>>Amine Moulay Ramadane, use only single CAS on pop and
>>no CAS on push. You can use it in a work-stealing manner
>>with a local queue for each server thread to optimize for more
>>throuput and minimize contention.
>
>Did you fix the bug that Relacy found?


There is no bug.

In the SPMC model, pushes items can not exceed
the 'size' of the queue, cause in the push() function
we are testing like this:

if getlength >= fsize
then
begin
result:=false;
exit;
end;

if getlength >=  fsize,  push() will return false and  exit.


>>and
>
>>Lock-free MPMC algorithm to handle queue FIFO proposed
>>by Dariusz Mazur (and modified by Amine Moulay Ramdane),
>>use only single CAS on pop and single CAS on push.
>
>I will code this in Relacy when I get some time.


that's good, go ahead.


regards,
Amine.

"Amine" <aminer@...net> wrote in message
news:65d8b15d-0130-4a63-bda8-a04f8881c82a@...com...
On Jun 30, 7:42 pm, "Chris M. Thomasson" <n...@...invalid> wrote:
>>"Amine" <ami...@...net> wrote in message
>>
>>news:be08f1b1-f624-4bd6-a166-fdd2ce1ac688@...com...
>>
>>
>>
>>>Hello,
>>
>>>Lock-free SPMC algorithm to handle queue FIFO proposed by
>>>Amine Moulay Ramadane, use only single CAS on pop and
>>>no CAS on push. You can use it in a work-stealing manner
>>>with a local queue for each server thread to optimize for more
>>>throuput and minimize contention.
>>
>>Did you fix the bug that Relacy found?


>There is no bug.

>In the SPMC model, pushes items can not exceed
>the 'size' of the queue, cause in the push() function
>we are testing like this:

>if getlength >= fsize
>   then
>       begin
>           result:=false;
>           exit;
>       end;
>if getlength >=  fsize,  push() will return false and  exit.

[...]

Relacy detects a data-race error regardless of the condition above only when
the producer attempts to push more items than the queues size. The
`getlength >= fsize' condition does not prevent this race.

On 1 июл, 07:11, Amine <ami...@...net> wrote:

>>>Lock-free SPMC algorithm to handle queue FIFO proposed by
>>>Amine Moulay Ramadane, use only single CAS on pop and
>>>no CAS on push. You can use it in a work-stealing manner
>>>with a local queue for each server thread to optimize for more
>>>throuput and minimize contention.
>
>>Did you fix the bug that Relacy found?
>
>There is no bug.
>
>In the SPMC model, pushes items can not exceed
>the 'size' of the queue, cause in the push() function
>we are testing like this:
>
>if getlength >= fsize
>   then
>       begin
>           result:=false;
>           exit;
>       end;
>
>if getlength >=  fsize,  push() will return false and  exit.


I think Chris saying about race I described here:
http://groups.google.com/group/comp.programming.threads/tree/browse_frm/thread/1d57ec498b5268e9/02fee1fe708f387b?rnum=1&_done=%2Fgroup%2Fcomp.programming.threads%2Fbrowse_frm%2Fthread%2F1d57ec498b5268e9%3F#doc_e2410afc5243e7b7


--
Dmitriy V'jukov

On Jul 1, 5:44 am, Dmitriy Vyukov <dvyu...@...com> wrote:
>On 1 ÉÀÌ, 07:11, Amine <ami...@...net> wrote:
>
>
>
>
>
>>>>Lock-free SPMC algorithm to handle queue FIFO proposed by
>>>>Amine Moulay Ramadane, use only single CAS on pop and
>>>>no CAS on push. You can use it in a work-stealing manner
>>>>with a local queue for each server thread to optimize for more
>>>>throuput and minimize contention.
>
>>>Did you fix the bug that Relacy found?
>
>>There is no bug.
>
>>In the SPMC model, pushes items can not exceed
>>the 'size' of the queue, cause in the push() function
>>we are testing like this:
>
>>if getlength >= fsize
>>š šthen
>>š š š šbegin
>>š š š š š šresult:=false;
>>š š š š š šexit;
>>š š š šend;
>
>>if getlength >= šfsize, špush() will return false and šexit.
>
>I think Chris saying about race I described here:http://groups.google.com/group/comp.programming.threads/tree/browse_f...
>
>--
>Dmitriy V'jukov- Hide quoted text -
>
>- Show quoted text -


I responded like this:

Dmitriy V'jukov wrote:
>Assume consumer has read the object, then he is preempted so that he
>misses 1000 pops and pushes, then the consumer scheduled again and his
>CAS accidentally succeeds.


It can't succeed cause head[0] will be different from lastHead[0]
and CAS(head[0],lasthead[0],lasthead[0]+1) will return false.


>In result, he returns very old object that
>was already consumed.

>I think here is another issue. Assume consumer successfully verifies
>that tail[0]<>head[0], then he is preempted and misses 1000 pushes and
>1001 pops, so that head stay the same, however now tail==head. CAS


tail==head but head and lasthead are not equal, so
CAS will not succeed.


So where is the problem ?


Amine.

"Amine" <aminer@...net> wrote in message
news:30ee8c6e-17e0-4807-a597-975926b4f515@...com...
On Jul 1, 5:44 am, Dmitriy Vyukov <dvyu...@...com> wrote:
>On 1 ÉÀÌ, 07:11, Amine <ami...@...net> wrote:
>
[...]

>I responded like this:

> Dmitriy V'jukov wrote:
>>Assume consumer has read the object, then he is preempted so that he
>>misses 1000 pops and pushes, then the consumer scheduled again and his
>>CAS accidentally succeeds.


>It can't succeed cause head[0] will be different from lastHead[0]
>and CAS(head[0],lasthead[0],lasthead[0]+1) will return false.


>>In result, he returns very old object that
>>was already consumed.

>>I think here is another issue. Assume consumer successfully verifies
>>that tail[0]<>head[0], then he is preempted and misses 1000 pushes and
>>1001 pops, so that head stay the same, however now tail==head. CAS


>tail==head but head and lasthead are not equal, so
>CAS will not succeed.


>So where is the problem ?

The problem is that Relacy detects that a consumer thread is loading from a
cell while the producer is currently mutating it. Are you saying that the
race is harmless? I can fix the Relacy test if I replace `rl::var<T>
m_tab[size]' with `rl::atomic<T> m_tab[size]':

http://relacy.pastebin.com/f64f171ad

Now everything is passing and no data-races are observed.

"Chris M. Thomasson" <no@...invalid> wrote in message
news:h2g354$g6t$1@...ua...
>"Amine" <aminer@...net> wrote in message
>news:30ee8c6e-17e0-4807-a597-975926b4f515@...com...
>On Jul 1, 5:44 am, Dmitriy Vyukov <dvyu...@...com> wrote:
>>On 1 ÉÀÌ, 07:11, Amine <ami...@...net> wrote:
>>
>[...]
>
>>I responded like this:
>
>> Dmitriy V'jukov wrote:
>>>Assume consumer has read the object, then he is preempted so that he
>>>misses 1000 pops and pushes, then the consumer scheduled again and his
>>>CAS accidentally succeeds.
>
>
>>It can't succeed cause head[0] will be different from lastHead[0]
>>and CAS(head[0],lasthead[0],lasthead[0]+1) will return false.
>
>
>>>In result, he returns very old object that
>>>was already consumed.
>
>>>I think here is another issue. Assume consumer successfully verifies
>>>that tail[0]<>head[0], then he is preempted and misses 1000 pushes and
>>>1001 pops, so that head stay the same, however now tail==head. CAS
>
>
>>tail==head but head and lasthead are not equal, so
>>CAS will not succeed.
>
>
>>So where is the problem ?
>
>The problem is that Relacy detects that a consumer thread is loading from
>a cell while the producer is currently mutating it. Are you saying that
>the race is harmless? I can fix the Relacy test if I replace `rl::var<T>
>m_tab[size]' with `rl::atomic<T> m_tab[size]':
>
>http://relacy.pastebin.com/f64f171ad
>
>Now everything is passing and no data-races are observed.


Here is a Relacy test that setups a work-stealing environment using your
queue:

http://relacy.pastebin.com/f264e97ce

On Jul 1, 12:33 pm, "Chris M. Thomasson" <n...@...invalid> wrote:
>"Amine" <ami...@...net> wrote in message
>
>news:30ee8c6e-17e0-4807-a597-975926b4f515@...com...
>On Jul 1, 5:44 am, Dmitriy Vyukov <dvyu...@...com> wrote:> On 1 ÉÀÌ, 07:11, Amine <ami...@...net> wrote:
>
>[...]
>
>>I responded like this:
>> Dmitriy V'jukov wrote:
>>>Assume consumer has read the object, then he is preempted so that he
>>>misses 1000 pops and pushes, then the consumer scheduled again and his
>>>CAS accidentally succeeds.
>>It can't succeed cause head[0] will be different from lastHead[0]
>>and CAS(head[0],lasthead[0],lasthead[0]+1) will return false.
>>>In result, he returns very old object that
>>>was already consumed.
>>>I think here is another issue. Assume consumer successfully verifies
>>>that tail[0]<>head[0], then he is preempted and misses 1000 pushes and
>>>1001 pops, so that head stay the same, however now tail==head. CAS
>>tail==head but head and lasthead are not equal, so
>>CAS will not succeed.
>>So where is the problem ?
>
>The problem is that Relacy detects that a consumer thread is loading from a
>cell while the producer is currently mutating it. Are you saying that the
>race is harmless? I can fix the Relacy test if I replace `rl::var<T>
>m_tab[size]' with `rl::atomic<T> m_tab[size]':

can you clarify please..

what do you mean by this change from rl::var to rl::atomic ?
i don't undertand what's that mean in relacy?
can relacy gave us more information ?
i mean *where* is exactly the problem ?


Amine.


>
>http://relacy.pastebin.com/f64f171ad
>
>Now everything is passing and no data-races are observed.

On Jul 1, 8:33 pm, "Chris M. Thomasson" <n...@...invalid> wrote:

>>I responded like this:
>> Dmitriy V'jukov wrote:
>>>Assume consumer has read the object, then he is preempted so that he
>>>misses 1000 pops and pushes, then the consumer scheduled again and his
>>>CAS accidentally succeeds.
>>It can't succeed cause head[0] will be different from lastHead[0]
>>and CAS(head[0],lasthead[0],lasthead[0]+1) will return false.
>>>In result, he returns very old object that
>>>was already consumed.
>>>I think here is another issue. Assume consumer successfully verifies
>>>that tail[0]<>head[0], then he is preempted and misses 1000 pushes and
>>>1001 pops, so that head stay the same, however now tail==head. CAS
>>tail==head but head and lasthead are not equal, so
>>CAS will not succeed.
>>So where is the problem ?
>
>The problem is that Relacy detects that a consumer thread is loading from a
>cell while the producer is currently mutating it. Are you saying that the
>race is harmless? I can fix the Relacy test if I replace `rl::var<T>
>m_tab[size]' with `rl::atomic<T> m_tab[size]':
>
>http://relacy.pastebin.com/f64f171ad
>
>Now everything is passing and no data-races are observed.


Amine,
I forgot that you already fixed problem I described - by swapping
order in which consumers increment head and read data item. So I do
not see any problems now.

Chris,
Regarding race detected by Relacy. I think it's a benign race and data
items must be declared as atomic<> instead of var<>. Assume following
situation. Consumer reads data item, them he is preempted for a long
time. In that time, producer and other consumers may 'spin queue
around', i.e. ARRAY_SIZE elements will be consumed and ARRAY_SIZE
elements will be produced. So now producer may actually write to the
location first preempted consumer 'just' read - that's why Relacy
shows a data race I think. However then CAS will inevitably fail for
that preempted consumer, so algorithm correctness is not broken.

Btw, can't Pascal compiler reorder following 2 operations for
producer:
setObject(Tail[0],tm);
inc(tail[0]);
?
I guess there is no such guarantee in the language spec.

--
Dmitriy V'jukov