Groups > comp.programming.threads > #759

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

From	"Chris M. Thomasson" <cristom@charter.net>
Newsgroups	comp.programming.threads
References	(6 earlier) <483dd461-9327-4622-80d7-f182c6c3848b@i8g2000vbh.googlegroups.com> <fcWGq.21554$8O1.7770@newsfe07.iad> <27e050a5-efd9-49c2-b11e-d179538edccb@p9g2000vbb.googlegroups.com> <rT4Hq.21797$U16.15645@newsfe15.iad> <07cf9ccc-19b7-4708-90f5-35ee9b4cd7b2@m7g2000vbc.googlegroups.com>
Subject	Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ?
Message-ID	<pN8Hq.1549$Gb.30@newsfe03.iad> (permalink)
Date	2011-12-17 14:34 -0800

Show all headers | View raw

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

Thread

csiph-web