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

Groups > comp.programming.threads > #2303

A new algorithm of a very fast concurrent FIFO queue

Cross-posted to 2 groups.

Show all headers | View raw

Hello,


I have invented a new and more advanced algorithm of a very fast 
concurrent FIFO queue that has more parallelism than my previous 
algorithms, and this new algorithm scales better even if the number of 
threads are greater than the number of cores and my new algorithm has 
scored 20% more throughput on the pop() side than the following Chriss 
Thomasson algorithm that uses the bakery algorithm and the same
throughput on the push() side than the following Chriss Thomasson algorithm.


Here is the Chriss Thomasson algorithm:

https://groups.google.com/forum/#!topic/lock-free/acjQ3-89abE/discussion


Here is my new algorithm, the pop() method have changed:

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



A very fast concurrent FIFO Queue version 1.0

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 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 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, this 
very fast concurrent FIFO queue scales better even of the number of 
threads are greater than the number of cores.

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 option scored 8.5 millions of transactions per second on my 
2.4 GHz Quadcore, the Ticket Spinlock option scored 8.5 millions of 
transactions per second on my 2.4 GHz Quadcore.

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

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.



You can download the source code of my new algorithm of a very fast 
concurrent FIFO queue from:

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

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 (x86)...


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 new algorithm of a very fast concurrent FIFO queue aminer <aminer@toto.net> - 2014-05-05 20:32 -0700

csiph-web