Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #729 > unrolled thread

How is it that he is calling his queue the most efficient and fastest mpmc queue ?

Back to article view | Back to comp.programming.threads

Contents

  How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-15 12:56 -0800
    Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-15 13:18 -0800
      Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-15 13:30 -0800
        Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-15 14:45 -0800
          Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-16 01:17 -0800
            Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-16 01:27 -0800
    Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-16 02:02 -0800
      Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-16 07:26 -0800
        Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-16 08:54 -0800
          Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-16 11:56 -0800
        Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-16 11:51 -0800
          Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-16 12:50 -0800
            Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-16 12:56 -0800
              Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-16 13:42 -0800
                Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-16 21:58 -0800
                  Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-16 22:14 -0800
                    Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-17 10:07 -0800
                      Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-17 12:01 -0800
                        Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-17 14:34 -0800
                          Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-17 14:56 -0800
                            Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-17 14:59 -0800
                            Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-17 16:16 -0800
                              Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-17 16:23 -0800
                                Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? aminer <aminer68@gmail.com> - 2011-12-17 16:50 -0800
                              Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ? "Chris M. Thomasson" <cristom@charter.net> - 2011-12-17 16:45 -0800

Page 1 of 2  [1] 2  Next page →

#729 — How is it that he is calling his queue the most efficient and fastest mpmc queue ?

I have looked at the mpmc queue from Chris M. Thomasson ,
and i think that his is using the Bakery algorithm in his mpmc queue,
but since he is using the Bakery algorithm it's the same as using
critical sections ,
so why  Chris M. Thomasson is saying that his algorithm is the most
efficient
algorithm and the fastest one ? perhaps i don't understand what Chris
is saying ?

can you explain please ?



thank you.


Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#730

But perhaps i am missing something, and i don't understand well his
algorithm...


So, can you explain correctly why it's the most efficient mpmc queue
and the fastest one...



Amine Moulay Ramdane.







On Dec 15, 3:56 pm, aminer <amine...@gmail.com> wrote:
> I have looked at the mpmc queue from Chris M. Thomasson ,
> and i think that his is using the Bakery algorithm in his mpmc queue,
> but since he is using the Bakery algorithm it's the same as using
> critical sections ,
> so why  Chris M. Thomasson is saying that his algorithm is the most
> efficient
> algorithm and the fastest one ? perhaps i don't understand what Chris
> is saying ?
>
> can you explain please ?
>
> thank you.
>
> Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#731

To be honest with you , i can not use his mpmc queue cause i don't
understand it
correctly, and also it must be well tested and he must prove it to us
formally that it's
working correctly, and also he said that his mpmc queue is the most
efficient and one of
the fastest one , so he must also prove it to us. But until then i can
not use his mpmc queue.



Amine Moulay Ramdane.





On Dec 15, 4:18 pm, aminer <amine...@gmail.com> wrote:
> But perhaps i am missing something, and i don't understand well his
> algorithm...
>
> So, can you explain correctly why it's the most efficient mpmc queue
> and the fastest one...
>
> Amine Moulay Ramdane.
>
> On Dec 15, 3:56 pm, aminer <amine...@gmail.com> wrote:
>
>
>
> > I have looked at the mpmc queue from Chris M. Thomasson ,
> > and i think that his is using the Bakery algorithm in his mpmc queue,
> > but since he is using the Bakery algorithm it's the same as using
> > critical sections ,
> > so why  Chris M. Thomasson is saying that his algorithm is the most
> > efficient
> > algorithm and the fastest one ? perhaps i don't understand what Chris
> > is saying ?
>
> > can you explain please ?
>
> > thank you.
>
> > Amine Moulay Ramdane.- Hide quoted text -
>
> - Show quoted text -

[toc] | [prev] | [next] | [standalone]

#732

I have asked someone called Darek  to translate the Chris M.
Thomasson's
mpmc queue to Delphi and Freepascal, but the answer was :


"But there is used other primitives: LOAD and STORE
http://en.wikipedia.org/wiki/Load-link/store-conditional
Not all architecture have it:" Darek


So, with wich primitives i have to replace Store() and Load() in the
x86 architecture ?



Amine Moulay Ramdane.






On Dec 15, 4:30 pm, aminer <amine...@gmail.com> wrote:
> To be honest with you , i can not use his mpmc queue cause i don't
> understand it
> correctly, and also it must be well tested and he must prove it to us
> formally that it's
> working correctly, and also he said that his mpmc queue is the most
> efficient and one of
> the fastest one , so he must also prove it to us. But until then i can
> not use his mpmc queue.
>
> Amine Moulay Ramdane.
>
> On Dec 15, 4:18 pm, aminer <amine...@gmail.com> wrote:
>
>
>
> > But perhaps i am missing something, and i don't understand well his
> > algorithm...
>
> > So, can you explain correctly why it's the most efficient mpmc queue
> > and the fastest one...
>
> > Amine Moulay Ramdane.
>
> > On Dec 15, 3:56 pm, aminer <amine...@gmail.com> wrote:
>
> > > I have looked at the mpmc queue from Chris M. Thomasson ,
> > > and i think that his is using the Bakery algorithm in his mpmc queue,
> > > but since he is using the Bakery algorithm it's the same as using
> > > critical sections ,
> > > so why  Chris M. Thomasson is saying that his algorithm is the most
> > > efficient
> > > algorithm and the fastest one ? perhaps i don't understand what Chris
> > > is saying ?
>
> > > can you explain please ?
>
> > > thank you.
>
> > > Amine Moulay Ramdane.- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

[toc] | [prev] | [next] | [standalone]

#733

"aminer" <aminer68@gmail.com> wrote in message
news:0dac4225-c70d-4d60-94e2-87961a458ca1@da3g2000vbb.googlegroups.com...

>I have asked someone called Darek  to translate the Chris M.
>Thomasson's
> mpmc queue to Delphi and Freepascal, but the answer was :

> "But there is used other primitives: LOAD and STORE
> http://en.wikipedia.org/wiki/Load-link/store-conditional
> Not all architecture have it:" Darek

> So, with wich primitives i have to replace Store() and Load() in the
> x86 architecture ?

I don't know Pascal very well; sorry about that. I am typing this in 
directly in the newsreader, I believe it's some form of "Pascal"... I think 
I totally forgot how pointers work:
_________________________________________________
{ Data Types }
type cell = record
   ver:integer;
   state:real;
end;




{ Global Variables/Prodecures }


{ N must be power of 2 }
var cells : array[0..(N - 1)] of cell;
var head:integer;
var tail:integer;


procedure init;
    var i:integer;
begin
    head := 0;
    tail := 0;
    for i := 0 to N do cells[i].ver := i;
end;




{ Atomic Ops / MASM impl }
ATOMIC_STORE PROC
  mov ecx, [esp + 4]
  mov eax, [esp + 8]
  mov [ecx], eax
  ret
ATOMIC_STORE ENDP


ATOMIC_LOAD PROC
  mov ecx, [esp + 4]
  mov eax, [ecx]
  ret
ATOMIC_LOAD ENDP


ATOMIC_XADD PROC
  mov ecx, [esp + 4]
  mov eax, [esp + 8]
  lock xadd [ecx], eax
  ret
ATOMIC_XADD ENDP




{ Backoff/Blocking Code }
procedure backoff;
begin
    {
        use whatever for now (e.g., Sleep(1)).
        The algorithm is in need of a distributed
        conditional waiting algorihtm! Distributed
        Eventcounts sound nice...  ;^)
    }
end;




{ Queue Ops }
procedure producer(state:real);
    var ver:integer;
    var c:^cell;
begin
    ver := ATOMIC_XADD(@head, 1);
    c := @cells[ver and (N - 1)];
    while ATOMIC_LOAD(@c^.ver) != ver do backoff;
    c^.state := state;
    ATOMIC_STORE(@c^.ver, ver + 1);
end;


function consumer:real;
    var ver:integer;
    var c:^cell;
begin
    ver := ATOMIC_XADD(@tail, 1);
    c := @cells[ver and (N - 1)];
    while ATOMIC_LOAD(@c^.ver) != ver + 1 do backoff;
    consumer := c^.state;
    ATOMIC_STORE(@c^.ver, ver + N);
end;
_________________________________________________




I hope that helps for now... 

[toc] | [prev] | [next] | [standalone]

#734

"Chris M. Thomasson" <cristom@charter.net> wrote in message 
news:%0EGq.1020$Mw4.374@newsfe06.iad...
> "aminer" <aminer68@gmail.com> wrote in message
> news:0dac4225-c70d-4d60-94e2-87961a458ca1@da3g2000vbb.googlegroups.com...
>
>>I have asked someone called Darek  to translate the Chris M.
>>Thomasson's
>> mpmc queue to Delphi and Freepascal, but the answer was :
>
>> "But there is used other primitives: LOAD and STORE
>> http://en.wikipedia.org/wiki/Load-link/store-conditional
>> Not all architecture have it:" Darek
>
>> So, with wich primitives i have to replace Store() and Load() in the
>> x86 architecture ?
>
> I don't know Pascal very well; sorry about that. I am typing this in 
> directly in the newsreader, I believe it's some form of "Pascal"... I 
> think I totally forgot how pointers work:
> _________________________________________________
> { Data Types }
> type cell = record
>   ver:integer;
>   state:real;
> end;
>
>
>
>
> { Global Variables/Prodecures }
>
>
> { N must be power of 2 }
> var cells : array[0..(N - 1)] of cell;
> var head:integer;
> var tail:integer;
>
>
> procedure init;
>    var i:integer;
> begin
>    head := 0;
>    tail := 0;
>    for i := 0 to N do cells[i].ver := i;

   OOPS! I think that should be:

for i := 0 to N - 1 do cells[i].ver := i;

;^/

> end;

[toc] | [prev] | [next] | [standalone]

#735

"aminer" <aminer68@gmail.com> wrote in message 
news:8269e127-41ff-4089-8463-3b450483ed57@n6g2000vbg.googlegroups.com...
>
> I have looked at the mpmc queue from Chris M. Thomasson ,
> and i think that his is using the Bakery algorithm in his mpmc queue,
> but since he is using the Bakery algorithm it's the same as using
> critical sections ,

I am using a _distributed_ bakery algorithm... Please, examine the algorithm 
very closely...


XADD = atomic fetch and add ; XADD on x86
LOAD = atomic load ; MOV on x86
STORE = atomic store ; MOV on x86


> so why  Chris M. Thomasson is saying that his algorithm is the most
> efficient
> algorithm and the fastest one ? perhaps i don't understand what Chris
> is saying ?
>
> can you explain please ?

AFAICT, it's pretty good algorithm wrt existing MPMC bounded queues. One 
single XADD on push/pop. This is the only way I can think of getting around 
CAS!  :^) 

[toc] | [prev] | [next] | [standalone]

#738

Here is the code that i have changed , and when i run it gives a
runtime bug in the program,
can you please take a look at it and tell me what's the problem, is
the assembler code
correct ? i have translate the assembler code to the delphi basm ...

here is the code:

----

program test;

uses windows;

{ Data Types }
type cell = record
ver:integer;
state:real;
end;
{ Global Variables/Prodecures }
{ N must be power of 2 }
const N=16;

var cells : array[0..(N - 1)] of cell;
var head:integer;
var tail:integer;
procedure init;
var i:integer;
begin
head := 0;
tail := 0;
for i := 0 to N-1 do cells[i].ver := i;
end;

function ATOMIC_STORE(T: POINTER; C:integer ): integer;
assembler;stdcall;
asm
mov ecx, T
mov eax, C
mov [ecx], eax
end;
function ATOMIC_LOAD(T: POINTER): integer; assembler;stdcall;
asm
mov ecx, T
mov eax, [ecx]
end;
function ATOMIC_XADD(T: POINTER; C:integer ): integer;
assembler;stdcall;
asm
mov ecx, T
mov eax, C
lock xadd [ecx], eax
end;

{ Backoff/Blocking Code }
procedure backoff;
begin
sleep(1);
end;
{ Queue Ops }

procedure producer(state:real);
var ver:integer;
var c:^cell;
begin
ver := ATOMIC_XADD(@head, 1);
c := @cells[ver and (N - 1)];
while ATOMIC_LOAD(@c^.ver) <> ver do backoff;
c^.state := state;
ATOMIC_STORE(@c^.ver, ver + 1);
end;

function consumer:real;
var ver:integer;
var c:^cell;
begin
ver := ATOMIC_XADD(@tail, 1);
c := @cells[ver and (N - 1)];
while ATOMIC_LOAD(@c^.ver) <> ver + 1 do backoff;
consumer := c^.state;
ATOMIC_STORE(@c^.ver, ver + N);
end;

begin
producer(24.0);
producer(23.0);

writeln(consumer);

end.

[toc] | [prev] | [next] | [standalone]

#739

Hello,


Another question:

You are doing this on the consumer side:

ver := ATOMIC_XADD(@tail, 1);


How are you avoiding that tail is not going beyong head in your
algorithm ?

and you are doing on the producer side:

ver := ATOMIC_XADD(@head, 1);

How are you avoiding that head is not going beyong tail in your
algorithm ?


Regards,
Amine Moulay Ramdane.












On Dec 16, 10:26 am, aminer <amine...@gmail.com> wrote:
> Here is the code that i have changed , and when i run it gives a
> runtime bug in the program,
> can you please take a look at it and tell me what's the problem, is
> the assembler code
> correct ? i have translate the assembler code to the delphi basm ...
>
> here is the code:
>
> ----
>
> program test;
>
> uses windows;
>
> { Data Types }
> type cell = record
> ver:integer;
> state:real;
> end;
> { Global Variables/Prodecures }
> { N must be power of 2 }
> const N=16;
>
> var cells : array[0..(N - 1)] of cell;
> var head:integer;
> var tail:integer;
> procedure init;
> var i:integer;
> begin
> head := 0;
> tail := 0;
> for i := 0 to N-1 do cells[i].ver := i;
> end;
>
> function ATOMIC_STORE(T: POINTER; C:integer ): integer;
> assembler;stdcall;
> asm
> mov ecx, T
> mov eax, C
> mov [ecx], eax
> end;
> function ATOMIC_LOAD(T: POINTER): integer; assembler;stdcall;
> asm
> mov ecx, T
> mov eax, [ecx]
> end;
> function ATOMIC_XADD(T: POINTER; C:integer ): integer;
> assembler;stdcall;
> asm
> mov ecx, T
> mov eax, C
> lock xadd [ecx], eax
> end;
>
> { Backoff/Blocking Code }
> procedure backoff;
> begin
> sleep(1);
> end;
> { Queue Ops }
>
> procedure producer(state:real);
> var ver:integer;
> var c:^cell;
> begin
> ver := ATOMIC_XADD(@head, 1);
> c := @cells[ver and (N - 1)];
> while ATOMIC_LOAD(@c^.ver) <> ver do backoff;
> c^.state := state;
> ATOMIC_STORE(@c^.ver, ver + 1);
> end;
>
> function consumer:real;
> var ver:integer;
> var c:^cell;
> begin
> ver := ATOMIC_XADD(@tail, 1);
> c := @cells[ver and (N - 1)];
> while ATOMIC_LOAD(@c^.ver) <> ver + 1 do backoff;
> consumer := c^.state;
> ATOMIC_STORE(@c^.ver, ver + N);
> end;
>
> begin
> producer(24.0);
> producer(23.0);
>
> writeln(consumer);
>
> end.

[toc] | [prev] | [next] | [standalone]

#742

"aminer" <aminer68@gmail.com> wrote in message 
news:9c882317-7733-45b7-b6b8-d2efb39d364c@i6g2000vbe.googlegroups.com...

> Another question:

> You are doing this on the consumer side:
> ver := ATOMIC_XADD(@tail, 1);

> How are you avoiding that tail is not going beyong head in your
> algorithm ?

The tail version is allowed to be greater than the head version.


> and you are doing on the producer side:
> ver := ATOMIC_XADD(@head, 1);

> How are you avoiding that head is not going beyong tail in your
> algorithm ?

The head version is allowed to be greater than the tail version.


It's the distributed bakery algorithms that makes everything actually work.


Now that I have a working version in FreePascal, I think you will quickly 
catch on to exactly what I am doing here with the version numbers... 

[toc] | [prev] | [next] | [standalone]

#741

"aminer" <aminer68@gmail.com> wrote in message 
news:b04b1d21-a39c-4394-ae33-ca759afa1425@z25g2000vbs.googlegroups.com...
>
> Here is the code that i have changed , and when i run it gives a
> runtime bug in the program,
> can you please take a look at it and tell me what's the problem, is
> the assembler code
> correct ? i have translate the assembler code to the delphi basm ...
[...]

The following compiles and runs for me on freepascal:

http://pastebin.com/2yTjUJBH

I basically had to change all integer types to longword and use AT&T syntax 
for the inline assembler. Anyway, I think I will work on a distributed 
conditional waiting mechanism for this. That way, we can get rid of the 
backoff and use "real" waiting primitives.  ;^) 

[toc] | [prev] | [next] | [standalone]

#745

On Dec 16, 2:51 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:b04b1d21-a39c-4394-ae33-ca759afa1425@z25g2000vbs.googlegroups.com...
>
> > Here is the code that i have changed , and when i run it gives a
> > runtime bug in the program,
> > can you please take a look at it and tell me what's the problem, is
> > the assembler code
> > correct ? i have translate the assembler code to the delphi basm ...
>
> [...]
>
> The following compiles and runs for me on freepascal:
>
> http://pastebin.com/2yTjUJBH
>
> I basically had to change all integer types to longword and use AT&T syntax
> for the inline assembler. Anyway, I think I will work on a distributed
> conditional waiting mechanism for this. That way, we can get rid of the
> backoff and use "real" waiting primitives.  ;^)


Can you remember me what is the FPC switch to compile the AT&T
assembler syntax ?


also is ther any problem to change the double type with and integer
type in
your algorithm so that i can test it against my lockfree_mpmc fifo
queue ?


Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#746

On Dec 16, 3:50 pm, aminer <amine...@gmail.com> wrote:
> On Dec 16, 2:51 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
>
>
>
>
>
> > "aminer" <amine...@gmail.com> wrote in message
>
> >news:b04b1d21-a39c-4394-ae33-ca759afa1425@z25g2000vbs.googlegroups.com...
>
> > > Here is the code that i have changed , and when i run it gives a
> > > runtime bug in the program,
> > > can you please take a look at it and tell me what's the problem, is
> > > the assembler code
> > > correct ? i have translate the assembler code to the delphi basm ...
>
> > [...]
>
> > The following compiles and runs for me on freepascal:
>
> >http://pastebin.com/2yTjUJBH
>
> > I basically had to change all integer types to longword and use AT&T syntax
> > for the inline assembler. Anyway, I think I will work on a distributed
> > conditional waiting mechanism for this. That way, we can get rid of the
> > backoff and use "real" waiting primitives.  ;^)
>
> Can you remember me what is the FPC switch to compile the AT&T
> assembler syntax ?


Just forget about the FPC switch for AT&T assembler.


>
> also is ther any problem to change the double type with and integer
> type in
> your algorithm so that i can test it against my lockfree_mpmc fifo
> queue ?
>
> Amine Moulay Ramdane.- Hide quoted text -
>
> - Show quoted text -

[toc] | [prev] | [next] | [standalone]

#747

Hello,

I have tested you queue  with 2 threads, and it gives very bad
performance.


Can you please do your benchmarks with multiple threads and give us
the throuput ?


example my lockfree_mpmc on  an Intel Core 2 Quad Q6600:with 4 cores
and 4 threads
under contention does give a throuput of:

38 millions of pop transactions/s

and

9 millions of push transactions/s


thank you.

Amine Moulay Ramdane.




On Dec 16, 3:56 pm, aminer <amine...@gmail.com> wrote:
> On Dec 16, 3:50 pm, aminer <amine...@gmail.com> wrote:
>
>
>
>
>
> > On Dec 16, 2:51 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
>
> > > "aminer" <amine...@gmail.com> wrote in message
>
> > >news:b04b1d21-a39c-4394-ae33-ca759afa1425@z25g2000vbs.googlegroups.com...
>
> > > > Here is the code that i have changed , and when i run it gives a
> > > > runtime bug in the program,
> > > > can you please take a look at it and tell me what's the problem, is
> > > > the assembler code
> > > > correct ? i have translate the assembler code to the delphi basm ...
>
> > > [...]
>
> > > The following compiles and runs for me on freepascal:
>
> > >http://pastebin.com/2yTjUJBH
>
> > > I basically had to change all integer types to longword and use AT&T syntax
> > > for the inline assembler. Anyway, I think I will work on a distributed
> > > conditional waiting mechanism for this. That way, we can get rid of the
> > > backoff and use "real" waiting primitives.  ;^)
>
> > Can you remember me what is the FPC switch to compile the AT&T
> > assembler syntax ?
>
> Just forget about the FPC switch for AT&T assembler.
>
>
>
>
>
> > also is ther any problem to change the double type with and integer
> > type in
> > your algorithm so that i can test it against my lockfree_mpmc fifo
> > queue ?
>
> > Amine Moulay Ramdane.- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

[toc] | [prev] | [next] | [standalone]

#753

"aminer" <aminer68@gmail.com> wrote in message 
news:483dd461-9327-4622-80d7-f182c6c3848b@i8g2000vbh.googlegroups.com...

> I have tested you queue  with 2 threads, and it gives very bad
> performance.

What was the size of N? I only have it set to 4 in my crude example. Also, I 
did nothing to prevent false sharing simply because I don't know how to 
explicitly pad to cache line and align on cache line boundary in Pascal. 
Perhaps you can help me out with that... Something like this:

http://groups.google.com/group/comp.programming.threads/msg/f2b1cac59c8e98a3

how can I do that in Pascal?


Also, it really needs distributed conditional blocking mechanism.


> Can you please do your benchmarks with multiple threads and give us
> the throuput ?

I am going to implement it in C very soon and eliminate false sharing 
wherever I can. I will post the code here. The only other algorithm I think 
I can benchmark against is this beautiful algorithm invented by Dmitriy 
Vyukov:

http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue

IMVHO, it's the only one I can find that is comparable.


> example my lockfree_mpmc on  an Intel Core 2 Quad Q6600:with 4 cores
> and 4 threads
> under contention does give a throuput of:

> 38 millions of pop transactions/s

> and

> 9 millions of push transactions/s


Can you show me the code? 

[toc] | [prev] | [next] | [standalone]

#754

On Dec 17, 12:58 am, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:483dd461-9327-4622-80d7-f182c6c3848b@i8g2000vbh.googlegroups.com...
>
> > I have tested you queue  with 2 threads, and it gives very bad
> > performance.
>
> What was the size of N? I only have it set to 4 in my crude example. Also, I
> did nothing to prevent false sharing simply because I don't know how to
> explicitly pad to cache line and align on cache line boundary in Pascal.
> Perhaps you can help me out with that... Something like this:
>
> http://groups.google.com/group/comp.programming.threads/msg/f2b1cac59...
>
> how can I do that in Pascal?


You can do this for example:

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

and do something like this:

var
tail:longword;
tmp1:typecache1;
head: longword;


>
> Also, it really needs distributed conditional blocking mechanism.
>
> > Can you please do your benchmarks with multiple threads and give us
> > the throuput ?
>
> I am going to implement it in C very soon and eliminate false sharing
> wherever I can. I will post the code here. The only other algorithm I think
> I can benchmark against is this beautiful algorithm invented by Dmitriy
> Vyukov:
>
> http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpm...
>
> IMVHO, it's the only one I can find that is comparable.
>
> > example my lockfree_mpmc on  an Intel Core 2 Quad Q6600:with 4 cores
> > and 4 threads
> > under contention does give a throuput of:
> > 38 millions of pop transactions/s
> > and
> > 9 millions of push transactions/s
>
> Can you show me the code?


Here is the code:

http://pages.videotron.com/aminer/zip/lockfree_queue.zip


Just compile the pop.pas and push.pas tests examples that you
will find inside the zip file....


Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#755

"aminer" <aminer68@gmail.com> wrote in message 
news:27e050a5-efd9-49c2-b11e-d179538edccb@p9g2000vbb.googlegroups.com...
> On Dec 17, 12:58 am, "Chris M. Thomasson" <cris...@charter.net> wrote:
> > "aminer" <amine...@gmail.com> wrote in message
> >
> > news:483dd461-9327-4622-80d7-f182c6c3848b@i8g2000vbh.googlegroups.com...
> >
> > > I have tested you queue with 2 threads, and it gives very bad
> > > performance.
> >
> > What was the size of N? I only have it set to 4 in my crude example. 
> > Also, I
> > did nothing to prevent false sharing simply because I don't know how to
> > explicitly pad to cache line and align on cache line boundary in Pascal.
> > Perhaps you can help me out with that... Something like this:
> >
> > http://groups.google.com/group/comp.programming.threads/msg/f2b1cac59...
> >
> > how can I do that in Pascal?


> You can do this for example:

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

> and do something like this:

> var
> tail:longword;
> tmp1:typecache1;
> head: longword;

Okay. I can do something with that; thank you. However, I still am wondering 
how to actually align data-structures on cache line boundaries. This is very 
important because if the data-structure is padded but _not_ properly 
aligned, you can still get false sharing. Basically, I want to know how to 
perform pointer arithmetic such that I can get the queue aligned properly?


> Also, it really needs distributed conditional blocking mechanism.
>
> > Can you please do your benchmarks with multiple threads and give us
> > the throuput ?

I should have a crude C test program up by the end of today or the middle of 
tomorrow. I will test against Dmitriy's awesome queue algorithm, and the 
dual spinlock queue (e.g., the one that you are using).


> I am going to implement it in C very soon and eliminate false sharing
> wherever I can. I will post the code here. The only other algorithm I 
> think
> I can benchmark against is this beautiful algorithm invented by Dmitriy
> Vyukov:
>
> http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpm...
>
> IMVHO, it's the only one I can find that is comparable.
>
> > example my lockfree_mpmc on an Intel Core 2 Quad Q6600:with 4 cores
> > and 4 threads
> > under contention does give a throuput of:
> > 38 millions of pop transactions/s
> > and
> > 9 millions of push transactions/s
>
> Can you show me the code?


> Here is the code:

> http://pages.videotron.com/aminer/zip/lockfree_queue.zip


> Just compile the pop.pas and push.pas tests examples that you
> will find inside the zip file....

Sorry, but I cannot find my queue code in there. Can you please provide me 
with the test you used for my algorithm specifically. I say "specifically" 
simply because the pop and push tests you are using are _not_ compatible 
with my mpmc queue interface. You seem to be expecting a boolean return 
value indicating full/empty border conditions. My queue implicitly blocks on 
such conditions. AFAICT, Pascal won't even compile my queue interface WRT 
your test harness. BTW, I still need to know what the size of N was. I 
cannot see my algorithm in the zip file, therefore, I cannot test my own 
algorithm without altering your existing test code. 

[toc] | [prev] | [next] | [standalone]

#756

On Dec 17, 1:07 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:27e050a5-efd9-49c2-b11e-d179538edccb@p9g2000vbb.googlegroups.com...
>
>
>
>
>
> > On Dec 17, 12:58 am, "Chris M. Thomasson" <cris...@charter.net> wrote:
> > > "aminer" <amine...@gmail.com> wrote in message
>
> > >news:483dd461-9327-4622-80d7-f182c6c3848b@i8g2000vbh.googlegroups.com...
>
> > > > I have tested you queue with 2 threads, and it gives very bad
> > > > performance.
>
> > > What was the size of N? I only have it set to 4 in my crude example.
> > > Also, I
> > > did nothing to prevent false sharing simply because I don't know how to
> > > explicitly pad to cache line and align on cache line boundary in Pascal.
> > > Perhaps you can help me out with that... Something like this:
>
> > >http://groups.google.com/group/comp.programming.threads/msg/f2b1cac59...
>
> > > how can I do that in Pascal?
> > You can do this for example:
> > type
> > typecache1  = array[0..15] of longword;
> > and do something like this:
> > var
> > tail:longword;
> > tmp1:typecache1;
> > head: longword;
>
> Okay. I can do something with that; thank you. However, I still am wondering
> how to actually align data-structures on cache line boundaries. This is very
> important because if the data-structure is padded but _not_ properly
> aligned, you can still get false sharing. Basically, I want to know how to
> perform pointer arithmetic such that I can get the queue aligned properly?


I have used an object for that cause all the members are 32 bit
alligned inside an object.

>
> > Also, it really needs distributed conditional blocking mechanism.
>
> > > Can you please do your benchmarks with multiple threads and give us
> > > the throuput ?
>
> I should have a crude C test program up by the end of today or the middle of
> tomorrow. I will test against Dmitriy's awesome queue algorithm, and the
> dual spinlock queue (e.g., the one that you are using).
>
>
>
>
>
> > I am going to implement it in C very soon and eliminate false sharing
> > wherever I can. I will post the code here. The only other algorithm I
> > think
> > I can benchmark against is this beautiful algorithm invented by Dmitriy
> > Vyukov:
>
> >http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpm...
>
> > IMVHO, it's the only one I can find that is comparable.
>
> > > example my lockfree_mpmc on an Intel Core 2 Quad Q6600:with 4 cores
> > > and 4 threads
> > > under contention does give a throuput of:
> > > 38 millions of pop transactions/s
> > > and
> > > 9 millions of push transactions/s
>
> > Can you show me the code?
> > Here is the code:
> >http://pages.videotron.com/aminer/zip/lockfree_queue.zip
> > Just compile the pop.pas and push.pas tests examples that you
> > will find inside the zip file....
>
> Sorry, but I cannot find my queue code in there. Can you please provide me
> with the test you used for my algorithm specifically. I say "specifically"
> simply because the pop and push tests you are using are _not_ compatible
> with my mpmc queue interface. You seem to be expecting a boolean return
> value indicating full/empty border conditions. My queue implicitly blocks on
> such conditions. AFAICT, Pascal won't even compile my queue interface WRT
> your test harness. BTW, I still need to know what the size of N was. I
> cannot see my algorithm in the zip file, therefore, I cannot test my own
> algorithm without altering your existing test code.- Hide quoted text -


I have noticed that when i push 100 integers  it's working, but when i
push 5000 integers
it's not working.

Would you want me to show you the test? but the test is not working
correclty here.



Amine Moulay Ramdane



>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

[toc] | [prev] | [next] | [standalone]

#759

"aminer" <aminer68@gmail.com> wrote in message 
news:07cf9ccc-19b7-4708-90f5-35ee9b4cd7b2@m7g2000vbc.googlegroups.com...
On Dec 17, 1:07 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> > > On Dec 17, 12:58 am, "Chris M. Thomasson" <cris...@charter.net> wrote:
> > > > "aminer" <amine...@gmail.com> wrote in message
> >
> > > >news:483dd461-9327-4622-80d7-f182c6c3848b@i8g2000vbh.googlegroups.com...
> >
> > > > > I have tested you queue with 2 threads, and it gives very bad
> > > > > performance.
> >
> > > > What was the size of N? I only have it set to 4 in my crude example.
> > > > Also, I
> > > > did nothing to prevent false sharing simply because I don't know how 
> > > > to
> > > > explicitly pad to cache line and align on cache line boundary in 
> > > > Pascal.
> > > > Perhaps you can help me out with that... Something like this:
> >
> > > >http://groups.google.com/group/comp.programming.threads/msg/f2b1cac59...
> >
> > > > how can I do that in Pascal?
> > > You can do this for example:
> > > type
> > > typecache1 = array[0..15] of longword;
> > > and do something like this:
> > > var
> > > tail:longword;
> > > tmp1:typecache1;
> > > head: longword;
> >
> > Okay. I can do something with that; thank you. However, I still am 
> > wondering
> > how to actually align data-structures on cache line boundaries. This is 
> > very
> > important because if the data-structure is padded but _not_ properly
> > aligned, you can still get false sharing. Basically, I want to know how 
> > to
> > perform pointer arithmetic such that I can get the queue aligned 
> > properly?


> I have used an object for that cause all the members are 32 bit
> alligned inside an object.

No. I want the queue to be aligned on a cache line boundary. 32-bit is not 
going to cut it. I can do this in C, not sure how to do it in Pascal.




> > > Also, it really needs distributed conditional blocking mechanism.
> >
> > > > Can you please do your benchmarks with multiple threads and give us
> > > > the throuput ?
> >
> > I should have a crude C test program up by the end of today or the 
> > middle of
> > tomorrow. I will test against Dmitriy's awesome queue algorithm, and the
> > dual spinlock queue (e.g., the one that you are using).
> >
> > > I am going to implement it in C very soon and eliminate false sharing
> > > wherever I can. I will post the code here. The only other algorithm I
> > > think
> > > I can benchmark against is this beautiful algorithm invented by 
> > > Dmitriy
> > > Vyukov:
> >
> > >http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpm...
> >
> > > IMVHO, it's the only one I can find that is comparable.
> >
> > > > example my lockfree_mpmc on an Intel Core 2 Quad Q6600:with 4 cores
> > > > and 4 threads
> > > > under contention does give a throuput of:
> > > > 38 millions of pop transactions/s
> > > > and
> > > > 9 millions of push transactions/s
> >
> > > Can you show me the code?
> > > Here is the code:
> > >http://pages.videotron.com/aminer/zip/lockfree_queue.zip
> > > Just compile the pop.pas and push.pas tests examples that you
> > > will find inside the zip file....

> > Sorry, but I cannot find my queue code in there. Can you please provide 
> > me
> > with the test you used for my algorithm specifically. I say 
> > "specifically"
> > simply because the pop and push tests you are using are _not_ compatible
> > with my mpmc queue interface. You seem to be expecting a boolean return
> > value indicating full/empty border conditions. My queue implicitly 
> > blocks on
> > such conditions. AFAICT, Pascal won't even compile my queue interface 
> > WRT
> > your test harness. BTW, I still need to know what the size of N was. I
> > cannot see my algorithm in the zip file, therefore, I cannot test my own
> > algorithm without altering your existing test code.- Hide quoted text -


> I have noticed that when i push 100 integers  it's working, but when i
> push 5000 integers
> it's not working.

> Would you want me to show you the test? but the test is not working
> correclty here.

Heck yeah I want to see the test. I know that the algorithm itself works 
fine, I cannot see how pushing 5000 integers is not working unless you are 
totally misusing my algorithm. Keep in mind that it implicitly provides 
blocking for full/empty cases. I already know that the test code that I 
downloaded is simply not compatible with the interface into my queue. So, 
yes I need to see the code. 

[toc] | [prev] | [next] | [standalone]

#760

On Dec 17, 5:34 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:07cf9ccc-19b7-4708-90f5-35ee9b4cd7b2@m7g2000vbc.googlegroups.com...
> On Dec 17, 1:07 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
>
>
>
>
>
> > "aminer" <amine...@gmail.com> wrote in message
>
> > > > On Dec 17, 12:58 am, "Chris M. Thomasson" <cris...@charter.net> wrote:
> > > > > "aminer" <amine...@gmail.com> wrote in message
>
> > > > >news:483dd461-9327-4622-80d7-f182c6c3848b@i8g2000vbh.googlegroups.com...
>
> > > > > > I have tested you queue with 2 threads, and it gives very bad
> > > > > > performance.
>
> > > > > What was the size of N? I only have it set to 4 in my crude example.
> > > > > Also, I
> > > > > did nothing to prevent false sharing simply because I don't know how
> > > > > to
> > > > > explicitly pad to cache line and align on cache line boundary in
> > > > > Pascal.
> > > > > Perhaps you can help me out with that... Something like this:
>
> > > > >http://groups.google.com/group/comp.programming.threads/msg/f2b1cac59...
>
> > > > > how can I do that in Pascal?
> > > > You can do this for example:
> > > > type
> > > > typecache1 = array[0..15] of longword;
> > > > and do something like this:
> > > > var
> > > > tail:longword;
> > > > tmp1:typecache1;
> > > > head: longword;
>
> > > Okay. I can do something with that; thank you. However, I still am
> > > wondering
> > > how to actually align data-structures on cache line boundaries. This is
> > > very
> > > important because if the data-structure is padded but _not_ properly
> > > aligned, you can still get false sharing. Basically, I want to know how
> > > to
> > > perform pointer arithmetic such that I can get the queue aligned
> > > properly?
> > I have used an object for that cause all the members are 32 bit
> > alligned inside an object.
>
> No. I want the queue to be aligned on a cache line boundary. 32-bit is not
> going to cut it. I can do this in C, not sure how to do it in Pascal.
>
>
>
>
>
> > > > Also, it really needs distributed conditional blocking mechanism.
>
> > > > > Can you please do your benchmarks with multiple threads and give us
> > > > > the throuput ?
>
> > > I should have a crude C test program up by the end of today or the
> > > middle of
> > > tomorrow. I will test against Dmitriy's awesome queue algorithm, and the
> > > dual spinlock queue (e.g., the one that you are using).
>
> > > > I am going to implement it in C very soon and eliminate false sharing
> > > > wherever I can. I will post the code here. The only other algorithm I
> > > > think
> > > > I can benchmark against is this beautiful algorithm invented by
> > > > Dmitriy
> > > > Vyukov:
>
> > > >http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpm...
>
> > > > IMVHO, it's the only one I can find that is comparable.
>
> > > > > example my lockfree_mpmc on an Intel Core 2 Quad Q6600:with 4 cores
> > > > > and 4 threads
> > > > > under contention does give a throuput of:
> > > > > 38 millions of pop transactions/s
> > > > > and
> > > > > 9 millions of push transactions/s
>
> > > > Can you show me the code?
> > > > Here is the code:
> > > >http://pages.videotron.com/aminer/zip/lockfree_queue.zip
> > > > Just compile the pop.pas and push.pas tests examples that you
> > > > will find inside the zip file....
> > > Sorry, but I cannot find my queue code in there. Can you please provide
> > > me
> > > with the test you used for my algorithm specifically. I say
> > > "specifically"
> > > simply because the pop and push tests you are using are _not_ compatible
> > > with my mpmc queue interface. You seem to be expecting a boolean return
> > > value indicating full/empty border conditions. My queue implicitly
> > > blocks on
> > > such conditions. AFAICT, Pascal won't even compile my queue interface
> > > WRT
> > > your test harness. BTW, I still need to know what the size of N was. I
> > > cannot see my algorithm in the zip file, therefore, I cannot test my own
> > > algorithm without altering your existing test code.- Hide quoted text -
> > I have noticed that when i push 100 integers  it's working, but when i
> > push 5000 integers
> > it's not working.
> > Would you want me to show you the test? but the test is not working
> > correclty here.
>
> Heck yeah I want to see the test. I know that the algorithm itself works
> fine, I cannot see how pushing 5000 integers is not working unless you are
> totally misusing my algorithm. Keep in mind that it implicitly provides
> blocking for full/empty cases. I already know that the test code that I
> downloaded is simply not compatible with the interface into my queue. So,
> yes I need to see the code.- Hide quoted text -


Here is the code, just compiler mpmc.pas with the -Sd option under
freepascal,
and notice that it is not working correctly.

http://pages.videotron.com/aminer/zip/test1.zip



Amine Moulay Ramdane









>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.programming.threads

csiph-web