A Scalable MPMC FIFO priority Queue

[aminer]

Hello,

As i have promised, my Scalable MPMC FIFO priority Queue version 1.0
is here.


Author: Amine Moulay Ramdane


Language: FPC Pascal v2.2.0+ / Delphi 5+: http://www.freepascal.org/

Operating Systems: Win , Linux and Mac (x86).


Description:

A Scalable MPMC FIFO priority Queue.

The following have been added:

- You can give the following priorities to jobs:

LOW_PRIORITY
NORMAL_PRIORITY
HIGH_PRIORITY

- A queue for each worker thread and it uses work-stealing - for more efficiency -

- Enters in a wait state when there no is job in the queue - for more efficiency -

- Uses O(1) complexity on enqueue and O(3) complexity worst case on dequeue.

Look into defines.inc there is many options:

CPU32: for 32 bits architecture
CPU64: for 64 bits architecture

Please read an article that i wrote about my Threadpool engine: article.

Look test.pas and  at test1.pas examples inside the zip file that shows you that my PQueue is scaling.


You can download PQueue version 1.0 from:

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

Required FPC switches: -O3 -Sd -dFPC -dWin32 -dFreePascal

-Sd for delphi mode....

Required Delphi switches: -DMSWINDOWS -$H+

For Delphi 5,6,7 use -DDelphi

For Delphi 2005,2006,2007,2009,2010+ use the switch -DDELPHI2005+



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

You have to start the same number of consumer threads than the number
of cores or queues that you will pass to the constructor, or you have to use the pop() method with the wait parameter set to false.


Look at my algorithm and you will understand what i mean.



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

I have enhanced my algorithm with the following on the pop() side:

==

j:=0;
if Queues[index].count = 0
then
 begin
  for i:=0 to Fthreadcount-1
 do j:=j+Queues.length;
zqueue.push(tobject(index));
 end;

==

So i don't think you have to start the number of consumers
threads equal to the number of producers threads equal to the
number of cores or queues passed to the constructor.


You can download again PQueue from:

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



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

Sorry i have returned back to my previous version, cause you have
to start the same number of consumer threads than the number
of producer threads than the number of queues that you will pass
to the constructor, or you have to use the pop() method with the wait parameter set to false.

Look at my algorithm and you will understand what i mean.

You can download again PQueue from:

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



Thank you,
Amine Moulay Ramdane.


Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

I have deleted this scalable FIFO queue , cause the requirement
is not good, it is better to use this method inside
my PThreadpool engine.



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

If you want to scale your FIFO queue, read the following paper:


http://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/SPAA2005.pdf



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,


I have thought more about my scalable FIFO MPMC priority queue,
and i think it's still interresting, but there is a requirement,
it's mandatory to start the same number of consumer threads than the number of producer threads than the number of queues and cores that you will pass to the constructor.


You can download my Scalable MPMC FIFO priority Queue version 1.0

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



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,


I will let it as it is inside my PThreadpool, cause
this requirement to be strict FIFO is not good for scalability.



Thank you,
Amine Moulay Ramdane

[aminer]

Question:

Why did you deleted your scalable FIFO MPMC priority queue ?

Answer:

If you keep the work-stealing part it will not be a strict FIFO
queue, if you don't keep work-stealing part it will not scale well,
so this requirement to be strict FIFO is not good for scalability, we have to relax it to not be a strict FIFO and it will scale.


Thank you,
Amine Moulay Ramdane.

[aminer]

Question:

Why your PThreadpool and Threadool can scale better ?


Answer:

Cause they are not strict FIFO, so they scale better.



Amine Moulay Ramdane.

[aminer]

Hello,


I have thought more about my scalable MPMC FIFO queue,
and i have found that it is sufficiently fair, i mean it's
sufficiently fair when the producers are consuming in ther
 queues , but when there is work-stealing it's also sufficiently
fair.

I think i will tweak it more and put it in my website
for download.

But you have a mandatory requirement, you must have  the same number of consumer threads than the number of producer threads than the number of queues that you will pass to the constructor.


This queue is not strict FIFO , but i think it's sufficiently fair
to be used in many applications.


So i will call it, a  scalable sufficiently fair MPMC priority queue.



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,


Here is the Scalable sufficiently fair MPMC priority Queue version 1.0:
 
I have thought more about this my Scalable sufficiently fair MPMC priority Queue, and i have found that it is sufficiently fair, i mean it's sufficiently fair when the producers are consuming in there
corresponding queues , but when there is work-stealing it's also sufficiently fair.


But you have a mandatory requirement, you must start the same number of consumer threads than that you will pass to the constructor.

This queue is not strict FIFO , but i think it's sufficiently fair
to be used in many applications.


Youi can download it from:


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



Thank you,
Amine Moulay Ramdane.

[aminer]

I correct, please read again...


Hello,


Here is the Scalable sufficiently fair MPMC priority Queue version 1.0:

I have thought more about this my Scalable sufficiently fair MPMC priority Queue, and i have found that it is sufficiently fair, i mean it's sufficiently fair when the consumers are consuming in there
corresponding queues , but when there is work-stealing it's also sufficiently fair.


But you have a mandatory requirement, you must start the same number of consumer threads than the number of queues that you will pass to the constructor.

This queue is not strict FIFO , but i think it's sufficiently fair
to be used in many applications.


You can download it from:


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



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

Read the following about the flat combining sychchronious queue , you
will notice that it is unfair:

http://www.cs.bgu.ac.il/~hendlerd/papers/FC-synch-queue-main.pdf



But i think that my Scalable sufficiently fair MPMC priority Queue
is sufficiently fair and it will scale.

But you have a mandatory requirement, you must start the same number of consumer threads than the number of queues that you will pass to the constructor.

This queue is not strict FIFO , but i think it's sufficiently fair
to be used in many applications.


You can download it from:


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



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

I have used my SemaMonitor(it's a mixture of a Semaphore
and a condition variable) inside my Scalable sufficiently
fair MPMC priority Queue and when i have replaced my SemaMonitor
with a Semaphore it was 2X times slower than my SemaMonitor,
so in this application my SemaCondvar is 2X times faster than
a windows Semaphore(i have tested it under windows).


So my SemaCondvar is useful.




Thank you,
Amine Moulay Ramdane.