Lockfree queue, one producer many consumers...

76 views
Skip to first unread message

Amine

unread,
Jun 26, 2009, 12:47:14 PM6/26/09
to

Hello,

I am still thinking and working on an algorithm for
many producer many consumers.

But here is an algorithm that works for one producer many consumers.
it runs on Win , Linux and Mac (x86), just compile
with Delphi or Freepascal ( http://www.freepascal.org/ )


-----------------------------------------------------------------------
unit flqueue;

interface

type
tNodeQueue = tObject;
typecache1 = array[0..15] of longword;

tFLQueue = class
private
tail,
head: typecache1;
fMask : typecache1;
fSize : longword;
tab : array of tNodeQueue;
procedure setobject(lp : integer;const aobject : tNodeQueue);
function getLength:integer;
function getSize:longword;
function getObject(lp : integer):tNodeQueue;
public
constructor create(aPower : integer =20); {allocate tab with
size equal 2^aPower, for 20 size is equal 1048576}
destructor Destroy;
function push(tm : tNodeQueue):boolean;
function pop(var obj:tNodeQueue):boolean;
property length : integer read getLength;
property size : longword read getSize;

end;


implementation

function CAS(var Target: longword; Comperand: longword;NewValue:
longword ): boolean; assembler;stdcall;
asm
mov ecx,Target
mov edx,NewValue
mov eax,Comperand
lock cmpxchg [ecx],edx
JNZ @@2
MOV AL,01
JMP @@Exit
@@2:
XOR AL,AL
@@Exit:
end;


constructor tFLQueue.create(aPower : integer );
begin
fMask[0]:=not($FFFFFFFF shl aPower);
fSize:=1 shl aPower;
setLength(tab,fSize);
tail[0]:=0;
head[0]:=0;
end;

destructor tFLQueue.Destroy;

begin
inherited Destroy;
end;


procedure tFLQueue.setObject(lp : integer;const aobject : tNodeQueue);
begin
tab[lp and fMask[0]]:=aObject;
end;

function tFLQueue.getObject(lp : integer):tNodeQueue;
begin
result:=tab[lp and fMask[0]];
end;

function tFlQueue.push(tm : tNodeQueue):boolean;
var
lastTail: typecache1;

begin
result:=true;
repeat
if getlength >= (fsize-1000)
then
begin
result:=false;
exit;
end;
lasttail[0]:=tail[0];
setObject(lastTail[0],tm);
if CAS(longword(tm),longword(tab[tail[0] and fMask[0]]), longword
(tm))
then
begin
//CAS(tail[0],lastTail[0],lasttail[0]+1);
inc(tail[0]);
exit;
end;
until false;
end;


function tFLQueue.pop(var obj:tNodeQueue):boolean;

var
newhead,
lastHead : typecache1;
begin
repeat
lastHead[0]:=head[0];
if tail[0]<>head[0]
then begin
if CAS(head[0],lasthead[0],lasthead[0]+1)
then
begin
obj:=getObject(lastHead[0]);
if integer(obj)=0
then result:=false
else result:=true;
exit;
end;
end
else
begin
result:=false;
exit;
end;
until false;
end;

function tFLQueue.getLength:integer;
begin
if tail[0] < head[0]
then result:= (4294967295-head[0])+(1+tail[0])
else result:=(tail[0]-head[0]);
end;

function tFLQueue.getSize:longword;

begin
result:=fSize;
end;

end.
-------------------------------------------------------------

and a test programs:

program test ;

uses flqueue,sysutils;

type
TStudent = class
i:integer;
Name: string;
end;


var Tqueue:Tflqueue;
obj:TStudent;
temp:Tobject;
i:integer;

begin
tqueue:=Tflqueue.create(20);

writeln(tqueue.size);
readln;
for I := 0 to 1048576-1001 do
begin

obj:=TStudent.create;
obj.Name:='Amine'+inttostr(i);
obj.i:=i;

if not Tqueue.push(obj)
then
begin
writeln('push overflow');
exit;
end;
end;
while tqueue.pop(temp)
do
begin
writeln(TStudent(temp).name);
temp.free
end;
writeln(tqueue.length);
tqueue.free;

end.


-------------------------------------------------

Regards,
Amine.

Amine

unread,
Jun 26, 2009, 1:22:46 PM6/26/09
to

Hello,

In this lock-free queue one producer many consumers
no lock is needed inside the push() , just one CAS on
the pop() side and it's safe on the pop side.

So, with this lock-free queue you can for example use
a local queue for each server thread + use work-stealing
= optimize for more throuput and minimize contention.

So change the push() to this:

----------------------------------------------------------------
function tFlQueue.push(tm : tNodeQueue):boolean;
begin
result:=true;
if getlength >= (fsize-100)


then
begin
result:=false;
exit;
end;

setObject(Tail[0],tm);
inc(tail[0]);
end;
------------------------------------------------


Thank you for your time.

Amine.

Amine

unread,
Jun 26, 2009, 1:30:37 PM6/26/09
to
Hello,

And please change in the push() side:

getlength >= (fsize-100)
by
getlength >= fsize

like this:

----------------------------------------------------------------

function tFlQueue.push(tm : tNodeQueue):boolean;
begin
result:=true;

if getlength >= fsize


then
begin
result:=false;
exit;
end;
setObject(Tail[0],tm);
inc(tail[0]);
end;

------------------------------------------------

And i think all will be fine :)


Regards,
Amine

Dmitriy Vyukov

unread,
Jun 26, 2009, 2:23:23 PM6/26/09
to


I am just skimmed through the algo, but can't producer overwrite value
that is not yet consumed by consumer?
Assume:
queue is full
producer increments head
now consumer comes in and sees that there is 1 free slot
consumer overwrites that slot with new value, old value is lost
now producer reads the value, but it's the new value, not the old one
Is this possible?


--
Dmitriy V'jukov

Amine

unread,
Jun 26, 2009, 2:55:06 PM6/26/09
to

ok.

> producer increments head

It is the consumer that increment head...

if queue is full there is a test tail[0]<>head[0] in
the consumer side , it's safe.

Please look again.


Regards,
Amine.

Dmitriy Vyukov

unread,
Jun 26, 2009, 3:40:15 PM6/26/09
to

Ok, consumer increments head and now queue does not look full, however
consumer does not yet read his item. Now producer comes in and
overwrites that item.

--
Dmitriy V'jukov

Amine

unread,
Jun 26, 2009, 4:01:19 PM6/26/09
to

I didn't saw this one , you are very correct.

And if we change it to something like getObject(lastHead[0])
*before* the CAS ?

Like this:
------------------------------------------------------------------

function tFLQueue.pop(var obj:tNodeQueue):boolean;


var
newhead,
lastHead : typecache1;
begin
repeat
lastHead[0]:=head[0];
if tail[0]<>head[0]

obj:=getObject(lastHead[0]);


then begin
if CAS(head[0],lasthead[0],lasthead[0]+1)
then
begin

if integer(obj)=0
then result:=false
else result:=true;
exit;
end;
end
else

begin
result:=false;
exit;
end;

until false;
end;
-------------------------------------------------------------


Is it correct now ?


Amine.


>
> --
> Dmitriy V'jukov- Hide quoted text -
>
> - Show quoted text -

Dmitriy Vyukov

unread,
Jun 26, 2009, 4:16:17 PM6/26/09
to


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. 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
succeeds and consumer returns already consumed item. Is it possible
with your algo?


Don't neglect Relacy Race Detector ;)


--
Dmitriy V'jukov

Amine

unread,
Jun 26, 2009, 4:30:21 PM6/26/09
to


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

> succeeds and consumer returns already consumed item. Is it possible
> with your algo?

>
> Don't neglect Relacy Race Detector ;)
>
> --

> Dmitriy V'jukov- Hide quoted text -
>
> - Show quoted text -


Amine,
Regards.

Dmitriy Vyukov

unread,
Jun 26, 2009, 4:38:42 PM6/26/09
to


Ok, false alarm. head and tail are a kind of ABA-counters in your
algo.


--
Dmitriy V'jukov

Amine

unread,
Jun 26, 2009, 4:43:37 PM6/26/09
to

:)

>head and tail are a kind of ABA-counters in your
> algo.


That's correct :)


take care,

Amine.

Amine

unread,
Jun 26, 2009, 4:50:05 PM6/26/09
to
> Dmitriy V'jukov- Hide quoted text -
>
> - Show quoted text -

Tell me Dmitry,

Can we use this lockfree queue in a work-stealing manner:
a local queue for each server thread + work-stealing
to minimize contention and for higher throuput ?
how will it compare to a work-stealing dequeue like the
one in cilk ?


Amine.


Dmitriy Vyukov

unread,
Jun 26, 2009, 6:50:25 PM6/26/09
to


Definitely we can. Take a look at the design of the libasync-smp:
http://www.scs.stanford.edu/~dm/home/papers/zeldovich:async-mp.pdf
It uses similar approach, i.e. FIFO queue for every worker thread +
work stealing + separation of computational work and IO callbacks +
callback prioritization.

However work-stealing works best when you have tasks of different
sizes + means to determine task sizes, then when thread is out of work
is steals big task and then works on it locally. If you have large
number of equally sized tasks then straightforward work-stealing may
not work that good, because threads will be constantly searching for
work and stealing from each other.

There is also such techniques as work-distribution, work-requesting
and centralized management. Each has benefits and drawbacks. I don't
think that there is one "true" way to do efficient scheduling. However
you can mix some recipe from the above pieces for particular
situation.
For example, AFAIK, Erlang on SMP/multicore uses following technique.
It makes pro-active periodical work-distribution between threads
(tries to equalize work) + work-stealing in between.

Regarding Cilk's deque. Well, main difference is that it uses LIFO
order, this tends to be very cache-friendly. However LIFO is not
suitable for general case, because it's very amenable to starvation.
As for per-operation costs, it seems that they are basically equal:
virtually costless push() + 1 CAS/membar per pop(). However in Cilk
stealers steal from one end of the deque, and owner thread makes
pushes and pops on another end of the deque, so they are a kind of
more separated.


--
Dmitriy V'jukov

Amine

unread,
Jun 26, 2009, 7:41:55 PM6/26/09
to
On Jun 26, 6:50 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> On 27 ÉÀÎ, 00:50, Amine <ami...@colba.net> wrote:
>
>
>
>
>
> > On Jun 26, 4:38špm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>
> > > On Jun 27, 12:30šam, Amine <ami...@colba.net> wrote:
>
> > > > On Jun 26, 4:16špm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>
> > > > > On Jun 27, 12:01šam, Amine <ami...@colba.net> wrote:
>
> > > > > > On Jun 26, 3:40špm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>
> > > > > > > On Jun 26, 10:55špm, Amine <ami...@colba.net> wrote:
>
> > > > > > > > On Jun 26, 2:23špm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:

>
> > > > > > > > > On Jun 26, 9:30špm, Amine <ami...@colba.net> wrote:
>
> > > > > > > > > > Hello,
>
> > > > > > > > > > And please change in the push() side:
>
> > > > > > > > > > getlength >= (fsize-100)
> > > > > > > > > > by
> > > > > > > > > > getlength >= fsize
>
> > > > > > > > > > like this:
>
> > > > > > > > > > š----------------------------------------------------------------
>
> > > > > > > > > > function tFlQueue.push(tm : tNodeQueue):boolean;
> > > > > > > > > > šbegin
> > > > > > > > > > šresult:=true;
> > > > > > > > > > š if getlength >= fsize
> > > > > > > > > > š šthen
> > > > > > > > > > š š š šbegin
> > > > > > > > > > š š š š š šresult:=false;
> > > > > > > > > > š š š š š šexit;
> > > > > > > > > > š š š šend;
> > > > > > > > > > šsetObject(Tail[0],tm);
> > > > > > > > > > šinc(tail[0]);
> > > > > > > > > > šend;
>
> > > > > > > > > > š------------------------------------------------

>
> > > > > > > > > > And i think all will be fine :)
>
> > > > > > > > > I am just skimmed through the algo, but can't producer overwrite value
> > > > > > > > > that is not yet consumed by consumer?
> > > > > > > > > Assume:
> > > > > > > > > queue is full
>
> > > > > > > > ok.
>
> > > > > > > > > producer increments head
>
> > > > > > > > It is the consumer that increment head...
>
> > > > > > > > if queue is full there is a test tail[0]<>head[0] in
> > > > > > > > the šconsumer side , it's safe.

>
> > > > > > > > Please look again.
>
> > > > > > > Ok, consumer increments head and now queue does not look full, however
> > > > > > > consumer does not yet read his item. Now producer comes in and
> > > > > > > overwrites that item.
>
> > > > > > I didn't saw this one , you are very correct.
>
> > > > > > And if we change it to something like getObject(lastHead[0])
> > > > > > *before* the CAS ?
>
> > > > > > Like this:
> > > > > > ------------------------------------------------------------------
>
> > > > > > function tFLQueue.pop(var obj:tNodeQueue):boolean;
>
> > > > > > var
> > > > > > š newhead,
> > > > > > š lastHead : typecache1;
> > > > > > begin
> > > > > > š repeat
> > > > > > š š lastHead[0]:=head[0];
> > > > > > š š if tail[0]<>head[0]
> > > > > > š š obj:=getObject(lastHead[0]);
> > > > > > š š šthen begin
> > > > > > š š š š š š if CAS(head[0],lasthead[0],lasthead[0]+1)
> > > > > > š š š š š š š then
> > > > > > š š š š š š š š begin
> > > > > > š š š š š š š š š š š šif integer(obj)=0
> > > > > > š š š š š š š š š š š šthen result:=false
> > > > > > š š š š š š š š š š š šelse result:=true;
> > > > > > š š š š š š š š š exit;
> > > > > > š š š š š š š š end;
> > > > > > š š š š š end
> > > > > > š š šelse
> > > > > > š š š šbegin
> > > > > > š š š š result:=false;
> > > > > > š š š š exit;
> > > > > > š š š šend;
> > > > > > š until false;

> > > > > > end;
> > > > > > -------------------------------------------------------------
>
> > > > > > Is it correct now ?
>
> > > > > 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.
>
> > > > He 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.
>
> > > Ok, false alarm. head and tail are a kind of ABA-counters in your
> > > algo.
>
> > > --
> > > Dmitriy V'jukov- Hide quoted text -
>
> > > - Show quoted text -
>
> > Tell me Dmitry,
>
> > Can we use this lockfree queue in a work-stealing manner:
> > a local queue for each server thread + šwork-stealing

> > to minimize contention and for higher throuput ?
> > how will it compare to a work-stealing dequeue like the
> > one in cilk ?
>
> Definitely we can. Take a look at the design of the libasync-smp:http://www.scs.stanford.edu/~dm/home/papers/zeldovich:async-mp.pdf
> It uses similar approach, i.e. FIFO queue for every worker thread +
> work stealing + separation of computational work and IO callbacks +
> callback prioritization.
>
> However work-stealing works best when you have tasks of different
> sizes + means to determine task sizes, then when thread is out of work
> is steals big task and then works on it locally. If you have large
> number of equally sized tasks then straightforward work-stealing may
> not work that good, because threads will be constantly searching for
> work and stealing from each other.
>
> There is also such techniques as work-distribution, work-requesting
> and centralized management. Each has benefits and drawbacks. I don't
> think that there is one "true" way to do efficient scheduling. However
> you can mix some recipe from the above pieces for particular
> situation.
> For example, AFAIK, Erlang on SMP/multicore uses following technique.
> It makes pro-active periodical work-distribution between threads
> (tries to equalize work) + work-stealing in between.
>
> Regarding Cilk's deque. Well, main difference is that it uses LIFO
> order, this tends to be very cache-friendly. However LIFO is not
> suitable for general case,

that's true.

>because it's very amenable to starvation.
> As for per-operation costs, it seems that they are basically equal:
> virtually costless push() + 1 CAS/membar per pop().
>However in Cilk
> stealers steal from one end of the deque,  and owner thread makes
> pushes and pops on another end of the deque, so they are a kind of
> more separated.


good information Dmitriy.

Have you any link to the Erlang techniques ?

Amine.


Chris M. Thomasson

unread,
Jun 26, 2009, 8:37:05 PM6/26/09
to
"Amine" <ami...@colba.net> wrote in message
news:0ce1f268-1274-4982...@r34g2000vba.googlegroups.com...

>
> Hello,
>
> I am still thinking and working on an algorithm for
> many producer many consumers.
>
> But here is an algorithm that works for one producer many consumers.
> it runs on Win , Linux and Mac (x86), just compile
> with Delphi or Freepascal ( http://www.freepascal.org/ )
>
>
> -----------------------------------------------------------------------
> unit flqueue;
>
> interface
>
> type
> tNodeQueue = tObject;
> typecache1 = array[0..15] of longword;
>
> tFLQueue = class
> private
> tail,
> head: typecache1;
> fMask : typecache1;
> fSize : longword;
[...]

I am wondering why `tail', `head' and `fMask' are arrays? Unless I am
missing something, you only explicitly reference the first item (e.g.,
tail[0], head[0] and fMask[0])...

Chris M. Thomasson

unread,
Jun 26, 2009, 8:46:30 PM6/26/09
to
"Amine" <ami...@colba.net> wrote in message
news:c43b8c97-f110-4322...@r16g2000vbn.googlegroups.com...

On Jun 26, 4:38 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> On Jun 27, 12:30 am, Amine <ami...@colba.net> wrote:
[...]

> Tell me Dmitry,

> Can we use this lockfree queue in a work-stealing manner:
> a local queue for each server thread + work-stealing
> to minimize contention and for higher throuput ?
> how will it compare to a work-stealing dequeue like the
> one in cilk ?

IIRC, membars aside for a moment, a worker thread in Clik can pop items from
the deque without using locks/atomic RMW if the head and tail are not at the
same place. So, that would make their implementation more efficient for that
specific operation.

Amine

unread,
Jun 26, 2009, 8:48:04 PM6/26/09
to
On Jun 26, 8:37 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> "Amine" <ami...@colba.net> wrote in message
>
> news:0ce1f268-1274-4982...@r34g2000vba.googlegroups.com...
>
>
>
>
>
> > Hello,
>
> > I am still thinking and working on an algorithm for
> > many producer many consumers.
>
> > But here is an algorithm that works for one producer many consumers.
> > it runs on Win , Linux and Mac (x86), just compile
> > with Delphi or Freepascal (http://www.freepascal.org/)
>
> > -----------------------------------------------------------------------
> > unit flqueue;
>
> > interface
>
> > type
> >  tNodeQueue = tObject;
> >  typecache1  = array[0..15] of longword;
>
> >  tFLQueue = class
> >  private
> >      tail,
> >      head: typecache1;
> >      fMask : typecache1;
> >      fSize : longword;
>
> [...]
>

Hello Chris,

> I am wondering why `tail', `head' and `fMask' are arrays? Unless I am
> missing something, you only explicitly reference the first item (e.g.,
> tail[0], head[0] and fMask[0])...

I was testing and trying to avoid false sharing
by aligning - all the variables - at 64 bits , like a fool.. :)

have you any advice Chris ?

Amine.

Amine

unread,
Jun 26, 2009, 8:51:14 PM6/26/09
to
On Jun 26, 8:37 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> tail[0], head[0] and fMask[0])...- Hide quoted text -


tail and head has to be aligned at 64 bytes,
not the other variables like fMask...

have you any advise Chris ?

Amine.


Chris M. Thomasson

unread,
Jun 27, 2009, 12:51:43 AM6/27/09
to
"Amine" <ami...@colba.net> wrote in message
news:5576cc6c-d033-452c...@l34g2000vbi.googlegroups.com...

> Hello Chris,

Humm... Well, I am not all that experienced in Pascal. I can find my way
around, but I am not expert enough to know how Pascal actually lays out
data-structures in memory. Anyway, AFAICT it seems like your always going to
have a "ping-pong" between the producer and consumers because the producer
needs to read both the head and tail. So every time a consumer mutates the
tail, that will have an effect on the producer. What am I missing here?

Chris M. Thomasson

unread,
Jun 27, 2009, 1:13:20 AM6/27/09
to
"Chris M. Thomasson" <n...@spam.invalid> wrote in message
news:h248ev$o66$1...@news.ett.com.ua...

However, I would still try and pad the distance between the head and tail by
at least 128-bytes. Also, You might want to add padding before the head
itself. This will help prevent false-sharing from unrelated pieces of code
and the queue itself. But, since this is Pascal, who knows how the memory is
going to be exactly laid out. Perhaps you can enlighten me on this aspect of
Pascal...

Chris M. Thomasson

unread,
Jun 27, 2009, 2:03:34 PM6/27/09
to
"Amine" <ami...@colba.net> wrote in message
news:0ce1f268-1274-4982...@r34g2000vba.googlegroups.com...

>
> Hello,
>
> I am still thinking and working on an algorithm for
> many producer many consumers.
>
> But here is an algorithm that works for one producer many consumers.
> it runs on Win , Linux and Mac (x86), just compile
> with Delphi or Freepascal ( http://www.freepascal.org/ )
[...]

I have implemented your algorithm in Relacy, but before I simulate it, I
need to know if I translated it correctly:
_____________________________________________________________________________
#define POWER 2U
#define SIZE (1U << POWER)
#define MASK (~(0xFFFFFFFFU << POWER))


template<typename T>
class spmcq {
rl::var<T> m_tab[SIZE];
rl::atomic<unsigned> m_head;
rl::atomic<unsigned> m_tail;


unsigned get_length() {
unsigned head = m_head($).load();
unsigned tail = m_tail($).load();
if (tail < head) {
return UINT_MAX - head + 1 + tail;
} else {
return tail - head;
}
}


public:
spmcq() {
m_head($).store(0, rl::memory_order_relaxed);
m_tail($).store(0, rl::memory_order_relaxed);
for (unsigned i = 0; i < SIZE; ++i) {
m_tab[i] = T();
}
}


public:
bool push(T& state) {
if (get_length() >= SIZE) {
return false;
}
unsigned tail = m_tail($).load();
m_tab[tail & MASK]($) = state;
m_tail($).store(tail + 1);
return true;
}


bool pop(T& state) {
unsigned last_head = m_head($).load();
for (;;) {
if (m_tail($).load() == head) {
return false;
}
state = m_tab[last_head & MASK];
if (m_head($).compare_exchange_weak(last_head, last_head + 1)) {
if (! (int)state) {
return false;
} else {
return true;
}
}
}
return true;
}
};
_____________________________________________________________________________

One thing that concerns me is the check to see if the popped item is equal
to zero:

if integer(obj)=0
then result:=false
else result:=true;

Does that mean that I cannot store a value of zero in your queue?


Any thoughts?

Amine

unread,
Jun 27, 2009, 4:51:53 PM6/27/09
to
On Jun 27, 2:03 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> "Amine" <ami...@colba.net> wrote in message
>
> news:0ce1f268-1274-4982...@r34g2000vba.googlegroups.com...
>
> > Hello,
>
> > I am still thinking and working on an algorithm for
> > many producer many consumers.
>
> > But here is an algorithm that works for one producer many consumers.
> > it runs on Win , Linux and Mac (x86), just compile
> > with Delphi or Freepascal (http://www.freepascal.org/)
>
> [...]
>
> I have implemented your algorithm in Relacy, but before I simulate it, I
> need to know if I translated it correctly:

all seems correct, please go ahead and simulate it.

> ___________________________________________________________________________­__

> ___________________________________________________________________________­__


>
> One thing that concerns me is the check to see if the popped item is equal
> to zero:
>
> if integer(obj)=0
> then result:=false
> else result:=true;
>
> Does that mean that I cannot store a value of zero in your queue?

Just delete it.

>
> Any thoughts?


Amine.


Amine

unread,
Jun 27, 2009, 5:04:26 PM6/27/09
to


correct.

Amine.

Chris M. Thomasson

unread,
Jun 27, 2009, 7:59:15 PM6/27/09
to
"Amine" <ami...@colba.net> wrote in message
news:2df52eab-64cd-4d49...@g1g2000yqh.googlegroups.com...

On Jun 27, 2:03 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> "Amine" <ami...@colba.net> wrote in message
>
> news:0ce1f268-1274-4982...@r34g2000vba.googlegroups.com...
[...]
> > I have implemented your algorithm in Relacy, but before I simulate it, I
> > need to know if I translated it correctly:

> all seems correct, please go ahead and simulate it.

[...]


Here is the simulation code:


http://relacy.pastebin.com/f6916a1f5


Okay. Relacy likes your algorithm if the number of pushed items never
exceeds the `SIZE' of the queue. It also likes it if I only use a single
consumer. However, when I increase the number of pushed items `ITERS'
__and__ use more than one consumer its giving me a data-race error between
the store in line (54) and the load in line (66); here is the exact output I
am experiencing:


http://relacy.pastebin.com/m6f5db774


This means that the producer is storing to the same place a consumer is
loading from at the same time. Please examine the algorithm and try to
ensure that I did not make some retarded boneheaded mistake wrt translation
from Pascal to Relacy C++!


So far, it goes like:


1 consumer == works fine
N consumers w/ total items never exceeding SIZE == works fine
N consumer w/ total items exceeding SIZE == data-race

Amine

unread,
Jun 27, 2009, 10:07:50 PM6/27/09
to
On Jun 27, 7:59 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> "Amine" <ami...@colba.net> wrote in message
>
> news:2df52eab-64cd-4d49...@g1g2000yqh.googlegroups.com...
> On Jun 27, 2:03 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
>
> > "Amine" <ami...@colba.net> wrote in message
>
> >news:0ce1f268-1274-4982...@r34g2000vba.googlegroups.com...
> [...]
> > > I have implemented your algorithm in Relacy, but before I simulate it, I
> > > need to know if I translated it correctly:
> > all seems correct, please go ahead and simulate it.
>
> [...]
>
> Here is the simulation code:
>
> http://relacy.pastebin.com/f6916a1f5
>
> Okay. Relacy likes your algorithm if the number of pushed items never
> exceeds the `SIZE' of the queue.

How can pushed items exeeds the size if we are testing with

if getlength >= fsize


then
begin
result:=false;
exit;
end;


?


Amine

Chris M. Thomasson

unread,
Jun 28, 2009, 12:37:43 AM6/28/09
to
"Amine" <ami...@colba.net> wrote in message
news:053d099a-6c64-44d4...@h28g2000yqd.googlegroups.com...

[...]
> > Here is the simulation code:
> >
> > http://relacy.pastebin.com/f6916a1f5
> >
> > Okay. Relacy likes your algorithm if the number of pushed items never
> > exceeds the `SIZE' of the queue.

> How can pushed items exeeds the size if we are testing with

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

Yikes! I need to restate that...


If the number of attempted pushes never exceeds the maximum size of the
queue, Relacy likes it.


Anyway, please examine the code and tell me if I make mistake in your
algorithm.

Amine

unread,
Jun 28, 2009, 10:54:51 AM6/28/09
to
On Jun 28, 12:37 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> "Amine" <ami...@colba.net> wrote in message
>
> news:053d099a-6c64-44d4...@h28g2000yqd.googlegroups.com...
> [...]
>
> > > Here is the simulation code:
>
> > >http://relacy.pastebin.com/f6916a1f5
>
> > > Okay. Relacy likes your algorithm if the number of pushed items never
> > > exceeds the `SIZE' of the queue.
> > How can pushed items exeeds the size if we are testing with
> > if getlength >= fsize
> >    then
> >        begin
> >            result:=false;
> >            exit;
> >        end;
>
> Yikes! I need to restate that...
>
> If the number of attempted pushes never exceeds the maximum size of the
> queue, Relacy likes it.

correct.

>
> Anyway, please examine the code and tell me if I make mistake in your
> algorithm.

I have looked at it and it seems correct.

And you can translate it in C# and C++ so that we gave it
to the internet community and don't forget to put my name ,
the name Dariusz Mazur and your name also chris(write that
you have translate it to C++ and C# and you have test it
with relacy...)


Amine.

Amine

unread,
Jun 28, 2009, 11:28:00 AM6/28/09
to

If Dmitriy Vyukov can also translate it to Java it will be fine.

And don't forget to put the name of Dmitry Vyukov and a link
to his Relacy tool(for publicity)


Amine.

Chris M. Thomasson

unread,
Jun 28, 2009, 8:31:06 PM6/28/09
to
"Amine" <ami...@colba.net> wrote in message
news:ef5e462e-bc14-4902...@f19g2000yqo.googlegroups.com...

On Jun 28, 10:54 am, Amine <ami...@colba.net> wrote:
> > On Jun 28, 12:37 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> >
[...]

> > > Yikes! I need to restate that...
> >
> > > If the number of attempted pushes never exceeds the maximum size of
> > > the
> > > queue, Relacy likes it.
> >
> > correct.
> >
> >
> >
> > > Anyway, please examine the code and tell me if I make mistake in your
> > > algorithm.
> >
> > I have looked at it and it seems correct.
> >
> > And you can translate it in C# and C++ so that we gave it
> > to the internet community and don't forget to put my name ,
> > the name Dariusz Mazur and your name also chris(write that
> > you have translate it to C++ and C# and you have test it
> > with relacy...)

I apologize for not documenting proper attributions: ;^(...


> If Dmitriy Vyukov can also translate it to Java it will be fine.

> And don't forget to put the name of Dmitry Vyukov and a link
> to his Relacy tool(for publicity)

I have not created a version of your algorithm in C# yet. However, when you
say "it will be fine" in am not sure what your getting at. Do you mean it
will fix the bug that was found by Relacy? What am I missing Dariusz?

Reply all
Reply to author
Forward
0 new messages