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

Groups > comp.programming.threads > #2298

A very fast concurrent FIFO Queue version 1.01

Cross-posted to 2 groups.

Show all headers | View raw

Hello,


My very fast concurrent FIFO Queue was updated to 1.01

I have included inside the zipfile two variants of my concurrent FIFO 
queue, there is a file called WQueue.pas that is only starvation-free on 
the pop() side and there is a file called WSFQueue.pas that is fully 
starvation-free.


Here is the explanation of the WQueue.pas algorithm:

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


What have changed in version 1.01 is that the WSFQueue.pas algorithm has 
become fully starvation-free and this update has made this fast 
concurrent FIFO queue faster.

You can download very fast concurrent FIFO Queue version 1.01:

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


Authors: Amine Moulay Ramdane

Description:

A very fast concurrent FIFO queue that satisfies many requirements: it 
has more parallelism than the two locks algorithm, it is FIFO fair , 
it's starvation-free and it has more parallelism than the two locks 
algorithm, it minimizes efficiently the cache-coherence traffic and it 
is energy efficient on the pop() side when you set the wait parameter to 
true in the construtor: when there is no items in the queue it will not 
spin-wait , but it will block wait on my SemaMonitor, and when the wait 
parameter of the constructor is set to false, and it uses only an atomic 
increment on the push() side and an atomic increment on the pop() side, 
so it's very fast,  this concurrent FIFO queue is limited to 1000 
threads on the push() side, if you want to higher that, just modify the 
"margin" constant in the source code, and the number of threads in the 
pop() side is limited by the length of the array.

You have 3 options for setting the kind of locks, just look inside 
defines.inc , if you want to set it for my array based lock called 
AMLock just uncomment the option AMLock inside defines.inc, if you want 
to set it for Ticket Spinlock just uncomment the option TicketSpinlock 
,If you want to set it for Spinlock just uncomment the option Spinlock, 
the Spinlock gives better performance under contention it scored 6.4 
millions of transactions per second on my 2.4 GHz Quadcore, the Ticket 
Spinlock option scored 6.4 millions of transactions per second on my 2.4 
GHz Quadcore.

I have included inside the zipfile two variants of my concurrent FIFO 
queue, there is a file called WQueue.pas that is only starvation-free on 
the pop() side and there is a file called WSFQueue.pas that is fully 
starvation-free.

The size of the queue must be passed to the constructor and it must be a 
power of 2.

Look here at my reasonning to prove to you that my algorithm is correct: 
Concurrent FIFO queue.

Please take a look a the test.pas Object Pascal demo inside the zipfile, 
compile and run it...

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

Operating Systems: Windows, Mac OSX , Linux , Unix...


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

-Sd for delphi mode....

{$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems

{$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems



Thank you,
Amine Moulay Ramdane.

Back to comp.programming.threads | Previous | Next | Find similar | Unroll thread

Thread

A very fast concurrent FIFO Queue version 1.01 aminer <aminer@toto.net> - 2014-04-29 11:49 -0700

csiph-web