Scalable and relaxed MPMC queue

A scalable and relaxed MPMC and almost strict FIFO priority Queue version 1.09

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 and relaxed MPMC priority Queue.

Relaxed means not a strict FIFO, but it's almost a strict FIFO, it processes the jobs in a FIFO order in each queue, and when there is no items in the queue the thread steals from the other queues in a round robin manner, that's good.

Where can my scalable and relaxed MPMC priority Queue be useful ?

When for example you want to do something like a threadpool that do parallel tasks, and you can find that in many applications that do parallel mathematical calculations or parallel mechanical or graphic calculations and many parallel tasks... so you will reduce on those applications the S part in the Amdahl equation using my scalable and relaxed MPMC priority Queue.

The number of consumer threads and the number of producers must be equal to the number of queues that you pass to the constructor so that it become scalable, and you have to initialize first the Push() method with high(pqueue.long), look at how to do it inside the test1.pas example inside the zip file.

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 is no job in the queue - for more efficiency -

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

Look into defines.inc there is many options:

CPU32: for 32 bits architecture

CPU64: for 64 bits architecture

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

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

-Sd for delphi mode....

Required Delphi switches: -DMSWINDOWS -$H+ -DDelphi

For Delphi use -DDelphi